hujunzheng_个人页

2014 网选 5007 Post Robot（暴力或者AC_自动机（有点小题大作了））

//暴力，从每一行的开始处开始寻找要查询的字符 #include #include #include #include using namespace std; char str[100005]; int main(){ while(gets(str)){ ...

2014 网选 5014 Number Sequence（异或）

1 /* 2 题意：a, b两个序列，规定由[0, n]区间的数！ 3 求 a[i] ^ b[i] 的和最大！ 4 5 思路：如果数字 n的二进制有x位， 那么一定存在一个数字m，使得n^m的所有二进制位 6 都是1，也就是由x位...

java中解决组件重叠的问题（例如鼠标移动组件时）

java中解决组件覆盖的问题！     有时候在移动组件的时候会出现两个组件覆盖的情况，但是你想让被覆盖的组件显示出来或者不被覆盖！在设计GUI时已经可以定义组件的叠放次序了（按摆放组件的先后顺序）。 真正麻烦的是响应哪个组件，这就要创建一个链表，把组件对象按顺序存起来，响应事件时扫描这个链表，按 链表中的先后顺序选择响应组件对象。

codeforce Number of Ways(暴力)

1 #include 2 #include 3 #include 4 #include 5 #define N 500005 6 using namespace std; 7 typedef long long LL; 8 LL prefix[N], suffix[...

c++中继承和java中继承的对比

java中： class Parent{ public void test(int a){ System.out.println("Parent:" + a); System.

poj 3486 A Simple Problem with Integers（树状数组第三种模板改段求段）

1 /* 2 树状数组第三种模板（改段求段）不解释！ 不明白的点这里：here！ 3 */ 4 #include 5 #include 6 #include 7 #include 8 #define N 100005 9 using nam...

树状数组三种模型

树状数组在区间求和问题上有大用，其三种复杂度都比线段树要低很多……有关区间求和的问题主要有以下三个模型（以下设A[1..N]为一个长为N的序列，初始值为全0）： （1）“改点求段”型，即对于序列A有以下操作： 【1】修改操作：将A[x]的值加上c； 【2】求和操作：求此时A[l..r]的和。

codeforces Restore Cube（暴力枚举）

1 /* 2 题意：给出立方体的每个顶点的坐标（是由源坐标三个数某几个数被交换之后得到的！）， 3 问是否可以还原出一个立方体的坐标，注意这一句话： 4 The numbers in the i-th output line must be a permu...

codeforce No to Palindromes!（枚举）

1 /* 2 题意：给定一个字符串中没有任何长度>1的回文子串！求按照字典序的该串的下一个字符串 3 也不包含长度>1的任何回文子串！ 4 5 思路：从最低位进行枚举，保证第i位 不与 第 i-1位和第 i-2位相同就好了！那么因为前边...

java中子类与父类中隐含的this引用的分析

/* 看一下下面的程序，看是否你的答案和运行的答案是否一致！ */ class Parent{ public int x; public Parent p; public Parent(){} public Parent(int x){ this.

c++中基类与派生类中隐含的this指针的分析

先不要看结果，看一下你是否真正了解了this指针？ 1 #include 2 using namespace std; 3 4 class Parent{ 5 public: 6 int x; 7 Parent *p; ...

c++中关于初始化型参列表的一些问题

1 /* 2 1.成员是按照他们在类中出现的顺序进行初始化的，而不是按照他们在初始化列表出现的顺序初始化的! 3 一个好的习惯是，按照成员定义的顺序进行初始化。 4 2.数组成员在初始化型参列表中不正确 5 */ 6 #include 7 #include ...

2014牡丹江网络zoj3816Generalized Palindromic Number（dfs或者bfs）

1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #inc...

2014牡丹江网络赛ZOJPretty Poem（暴力枚举）

/* 　　将给定的一个字符串分解成ABABA 或者 ABABCAB的形式！ 思路：暴力枚举A, B, C串！ */ 1 #include 2 #include 3 #include 4 #include 5 6 using namespace std...

poj1949Chores（建图或者dp）

1 /* 2 题意：n个任务，有某些任务要在一些任务之前完成才能开始做！ 3 第k个任务的约束只能是1...k-1个任务！问最终需要最少的时间完成全部的 4 ...

poj 1950 Dessert（dfs枚举,模拟运算过程）

/* 　　这个代码运行的时间长主要是因为每次枚举之后都要重新计算一下和的值！　　　 如果要快的话，应该在dfs，也就是枚举的过程中计算出前边的数值（这种方法见第二个代码），直到最后，这样不必每一次枚举都要从头再算一遍值！ */ 1 #include 2 #include 3 #in...

java中自动装箱的问题

package wrapper; public class WrapperDemo { public static void main(String[] args) { Integer a=new Integer(5); Integer b=new Integer(5); System.

hdu4292Food（最大流Dinic算法）

/* 　　 题意：每一个人都有喜欢的吃的和喝的，每一个人只选择一个数量的吃的和一个数量的喝的，问能满足最多的人数！？　　　　思路：建图很是重要！f-food, p-people, d-drink　　　　建图： 0（源点）--->f--->p---->p'---->d--->t(汇点)　...

codeforces Gargari and Permutations(DAG+BFS)

1 /* 2 题意：求出多个全排列的lcs！ 3 思路：因为是全排列，所以每一行的每一个数字都不会重复，所以如果有每一个全排列的数字 i 都在数字 j的前面，那么i， j建立一条有向边！ 4 最后用bfs遍历整个图，求出源点到每一个点的距离，其中最大...

codeforces Gargari and Bishops（很好的暴力）

1 /* 2 题意：给你一个n*n的格子，每一个格子都有一个数值！将两只bishops放在某一个格子上， 3 每一个bishop可以攻击对角线上的格子（主对角线和者斜对角线），然后会获得格子上的 4 数值（只能获取一次）。

poj3342Party at Hali-Bula（树形dp）

1 /* 2 树形dp！ 3 判重思路： 4 当dp[v][0]==dp[v][1]时，很自然，flag[u][0]必然是有两种方案的。flag[u][1]则不然， 5 因为它只和dp[v][0]有关系。

hdu4750Count The Pairs（最小生成树找瓶颈边）

1 /* 2 题意：就是给你一个图，图的每两个点都有多条路径，每一条路径中都有一条最大边， 3 所有最大边的最小边（也就是瓶颈边）就是这两点之间的val值！然后给你一个值f， 4 问有多少个顶点对的val>=f! (u,v) 和 (v, u)是不同的顶点对！ ...

hdu4751Divide Groups（dfs枚举完全图集合或者bfs染色）

1 /************************************************************************* 2 > File Name: j.

poj1273Drainage Ditches

1 #include 2 /* 3 题意：就是寻找从源点到汇点的最大流！ 4 要注意的是每两个点的流量可能有多个，也就是说有重边，所以要把两个点的所有的流量都加起来 5 就是这两个点之间的流量了！ 6 ...

hdu Caocao's Bridges(无向图边双连通分量，找出权值最小的桥)

1 /* 2 题意：给出一个无向图，去掉一条权值最小边，使这个无向图不再连同！ 3 4 tm太坑了... 5 1,如果这个无向图开始就是一个非连通图，直接输出0 6 2，重边（两个节点存在多条边， 权值不一样） 7 3，...

NYOJ 1023 还是回文(DP,花最少费用形成回文串)

1 /* 2 题意：给出一串字符(全部是小写字母)，添加或删除一个字符，都会产生一定的花费。 3 那么，将字符串变成回文串的最小花费是多少呢？ 4 5 思路：如果一个字符串增加一个字符 x可以形成一个回文串，那么从这个字符串中删除这个字符 x 6...

NYOJ995硬币找零(简单dp)

1 /* 2 题意：给你不同面额的硬币（每种硬币无限多），需要找零的面值是T，用这些硬币进行找零， 3 如果T恰好能被找零，输出最少需要的硬币的数目！否则请输出剩下钱数最少的找零方案中的最少硬币数！ 4 5 思路：转换成完全背包的问题！ ...

ZOJ 3804 YY's Minions (简单模拟)

1 /* 2 题意：一个矩阵中有 n*m个宠物，每一个宠物都有一个状态， 1醒着的，0睡着的 3 X离开的！如果这个宠物（醒着的）的周围醒着的个数>3 ||

ZOJ3805Machine(二叉树左右子树变换)

1 /* 2 题意：建立一棵二叉树，左子树和父节点占一个宽度，右子树另外占一个宽度！ 3 使任意左右子树交换顺序，使得整个树的宽度最小！ 4 思路：递归交换左右子树 ！ 开始写的代码复杂了，其实左右子树不用真的交换，只要返回交换与不...

poj3249Test for Job（记忆化搜索）

1 /* 2 题意：给一个DAG图，n个节点，每个节点都对应一个值，入度为零的点走到出度为零的点，计算所有可能路径 3 经过节点值的和最大！ 4 5 思路：记忆话搜索：也就是如果我们搜索到某一个节点的时候发现该节点已经存在了值，那么直接返回该节点的值！...

poj 2385Apple Catching（简单dp）

1 /* 2 题意： 有两棵苹果树，每一棵苹果树每一秒间隔的掉落下来一个苹果，一个人在树下接住苹果，不让苹果掉落！ 3 人在两棵树之间的移动是很快的！但是这个人移动的次数是有限制的，问最多可以接住多少个苹果！ 4 5 思路：dp[i][j]表示...

hdu1269迷宫城堡(判断有向图是否是一个强连通图)

1 /* 题意： 给你一个图，求这个有向图示否是一个强连通图（每两个节点都是可以相互到达的）！ 思路1：按正向边dfs一遍，将经过的节点计数，如果记录的节点的个数小于n，那么就说明图按照正向边就不是连同的，所以就不是强连通图！ ...

poj1062昂贵的聘礼（Dijkstra**）

1 /* 2 题意： 物主有一个物品，价值为P，地位为L， 以及一系列的替代品Ti和该替代品所对应的"优惠"Vi 3 g[u][i] 表示的是u物品被i物品替换后的优惠价格！(u>0, i>0) 4 g[u][0]表示不用替换该物品的实际价格 ！ 5 d...

森林转换成二叉树以及二叉树还原为森林代码

1 /* 2 森林转换成二叉树 3 思路：u的孩子节点为v1, v2, v3....（v1,v2,....互为兄弟节点） 4 那么将u的一个孩子节点（v1）连在u的左子树上，那么其他的孩子节点都连在v1的右子树上！ 5 */ 6 #inc...

java中有关线程的题目

1，看一下下面程序错误发生在哪一行！ class Test implements Runnable{ public void run(Thread t){ } } 2，输出结果是什么？ class Test{ public static void main(...

poj2513Colored Sticks（无向图的欧拉回路）

1 /* 2 题意：将两端涂有颜色的木棒连在一起，并且连接处的颜色相同！ 3 思路：将每一个单词看成一个节点，建立节点之间的无向图！判断是否是欧拉回路或者是欧拉路 4 5 并查集判通 + 奇度节点个数等于2或者0 6 */ 7 #includ...

poj 1386 Play on Words(有向图欧拉回路)

1 /* 2 题意：单词拼接，前一个单词的末尾字母和后一个单词的开头字母相同 3 思路：将一个单词的开头和末尾单词分别做两个点并建一条有向边！然后判断是否存在欧拉回路或者欧拉路 4 5 再次强调有向图欧拉路或欧拉回路的判定方法： 6 (1)有向图G为欧拉图(存在欧拉回路)，当且仅当G的基图连通，且所有顶点的入度等于出度。

java中多线程模拟（多生产，多消费，Lock实现同步锁，替代synchronized同步代码块）

import java.util.concurrent.locks.*; class DuckMsg{ int size;//烤鸭的大小 String id;//烤鸭的厂家和标号 DuckMsg(){ } DuckMsg(int size, String id){ this.

java中线程存活和线程执行的问题！

1 /* 2 下面的程序会出现下面的情况，当Thread-0， Thread-1， Thread-2都被wait的时候，可能会同时苏醒 3 Thread-0 put 4 Thread-1 put 5 Thread-2 put 6 Thread...

34988 Happy Reversal(二进制去取反)

1 /* 2 题意：给多个二进制数，对某些数进行按位取反操作！ 3 然后从中找到最大数和最小数，并输出他们的差值！ 4 注意：所有的数都是整数，包括取反之后 5 6 思路：一个n为二进制数x，令tmp为n位全1！则 y=tmp&(tmp^x...

poj 2594Treasure Exploration(有向图路径可相交的最小路径覆盖)

1 #include 2 #include 3 #include 4 #include 5 #define N 505 6 using namespace std; 7 8 int g[N][N]; 9 int n, m; 10 int vis[N], l...

Floyd算法的理解

poj 2226 Muddy Fields(合理建图+二分匹配)

1 /* 2 题意：用木板盖住泥泞的地方，不能盖住草。木板任意长！可以重叠覆盖！ '*'表示泥泞的地方，'.'表示草！ 3 思路： 4 首先让我们回忆一下HDU 2119 Matrix这一道题，一个矩阵中只有0， 1，然后让我们通过选择一行，或者 ...

二分匹配最大匹配的理解（附图解）

  定义一个PXP的有向图中，路径覆盖就是在图中找一些路径，使之覆盖了图中的所有顶点，且任何一个顶点有且只有一条路径与之关联；（如果把这些路径中的每条路径从它的起始点走到它的终点，那么恰好可以经过图中的每个顶点一次且仅一次）；如果不考虑图中存在回路，那么每条路径就是一个弱连通子集．由上面可以得出：1.

poj2060Taxi Cab Scheme(二分图匹配)

1 /* 2 题意： 出租车 有一个出发的时间，从点（a, b）到点（c, d），时间为 3 abs(a-c)+abs(b-d)! 一辆车可以在运完一个乘客后运另一个乘客, 4 条件是此车要在预约开始前一分钟之前到达出发地, 问最少需要几辆车 5 搞定所有预约。

codeforce Pashmak and Buses(dfs枚举)

1 /* 2 题意：n个同学，k个车， 取旅游d天！ 3 要求所有的学生没有两个或者两个以上的在同一辆车上共同带d天！ 输出可行的方案！ 4 5 对于d行n列的矩阵，第i行第j列表示的是第i天第j个同学所在的车号！ 6 也就是保证所有行不全相...

UVAoj 348 - Optimal Array Multiplication Sequence

1 /* 2 题意：矩阵相乘的最少的步数 3 dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+num[i-1]*num[k]*num[j]); 4 表示的是第i个矩阵到第j个矩阵相乘的最少步数 5 sign[...

poj2253 Frogger（最短路变型或者最小生成树）

1 /* 2 题意：就是源点到终点有多条的路径，每一条路径中都有一段最大的距离！ 3 求这些路径中最大距离的最小值！ 4 5 Dijkstra, Floyd, spfa都是可以的！只不过是将松弛的条件变一下就行了！ 6 7 ...

ZZUOJ1196: 单调数

1 /* 2 注意的事项:是输出小于 10^n的正整数的个数哦！开始的时候总比样例输出多一个数， 3 纠结了好久，原来是 0加了进去了！ 4 5 dpI[n][m]表示的是第n位添加数字m（0.

hdu3339 In Action(Dijkstra+01背包)

1 /* 2 题意：有 n 个站点（编号1...n），每一个站点都有一个能量值，为了不让这些能量值连接起来，要用 3 坦克占领这个站点！已知站点的 之间的距离，每个坦克从0点出发到某一个站点，1 unit distance costs 1 unit oil！ ...