ACM

http://codeforces.com/contest/604/problem/E 题意：有两个人做游戏，游戏规则如下： 有n堆石子，每次可以对一堆石子进行操作，如果当前石子是偶数，那么可以选择将这2*x个石子分成k堆石子数为x的石子堆，还有一种没有前提的操作是取走当前堆的一个石子，问先手赢还是后手赢，先手和后手都足够聪明的情况下。 思路：博弈论。。不会做。。第一次接触sg函数。。转载一篇题解： http://m.blog.csdn.net/blog/qq_24451605/50154973

http://codeforces.com/contest/604/problem/D 题意：一个恒等式 f(kx%p)=kf(x)%p ,k,p为常数，且满足x对于定义域为0..p-1的p的整数，值域也在0..p-1范围（不一定一一对应）。问满足题意的f有多少个。 思路： f(0)=0，对于其他的值，当f（x）确定时，f（kx%p）也随之确定，那么把kx%p看做新的x,f（kkx%p）也随之确定…相当于【1，p-1】被分为r个小环，确定每个环可以任选一个数字，ans=p^r。环的个数可以用dfs跑一遍得到r. 注意当k=1的时候是特殊情况，f(x)恒等于f(x)那么答案应该有p的p次方种。因为对于p个f(0..p-1)，每一个都可以任意取p种值。

http://acm.hdu.edu.cn/showproblem.php?pid=1221 题意：问圆和矩形是否相交 思路：主要特殊的包含情况，然后判断与线段相交。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月21日 星期一 21时38分22秒 4File Name :code/hdu/rr1221.cpp 5************************************************ */ 6 7#include <iostream> 8#include <string.h> 9#include <stdio.h> 10#include <algorithm> 11#include <cmath> 12#define eps 1e-8 13using namespace std; 14struct point 15{ 16 double x; 17 double y; 18}circle,a,b,c,d; 19double r; 20double dis(point &a,point &b) 21{ 22 return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); 23} 24 25bool ok() 26{ 27 28 if(dis(a,circle)<r && dis(b,circle) <r && dis(c,circle)<r && dis(d,circle) <r) 29 return false; 30 if(circle.x>=a.x && circle.x<=b.x) 31 { 32 if(fabs(circle.y-a.y) <= r || fabs(circle.y-b.y) <= r) 33 return true; 34 } 35 if((circle.y >= a.y && circle.y <=b.y) || (circle.y>=b.y && circle.y<=a.y)) 36 { 37 if(fabs(circle.x-a.x) <=r || fabs(circle.x-b.x) <=r) 38 return true; 39 } 40 if(dis(a,circle)<=r || dis(b,circle) <=r || dis(c,circle)<=r || dis(d,circle) <=r) 41 return true; 42 return false; 43} 44int main() 45{ 46 #ifndef ONLINE_JUDGE 47 freopen("code/in.txt","r",stdin); 48 #endif 49 int t; 50 scanf("%d",&t); 51 while(t--) 52 { 53 scanf("%lf %lf %lf %lf %lf %lf %lf",&circle.x,&circle.y,&r,&a.x,&a.y,&b.x,&b.y); 54 if(a.x > b.x) 55 swap(a,b); 56 c.x=a.x,c.y=b.y; 57 d.x=b.x,d.y=a.y; 58 59 if (ok()) 60 { 61 puts("YES"); 62 } 63 else 64 { 65 puts("NO"); 66 } 67 } 68 return 0; 69}

http://poj.org/problem?id=3687 题意：给定几个标签球的重量大小关系，求每个球是第几重的(即每个球在所有球的重量中由小到大排名是多少)。 （输出是每个球第几重，而不是几号球比几号球重！）。一开始理解错了QAQ 思路：反向拓扑+优先队列。因为正向不好用。。。所以我们连边的时候由重的指向轻的。。这样最先出队的就是最重的。。和上道题差不多？

http://poj.org/problem?id=3660 题意：给定n个奶牛，m个奶牛的关系，a,b表示a比b强…问能确定多少个奶牛的排名。 思路：最重要的一点是。。能确定奶牛i的排名的条件是。。知道奶牛i和其他n-1个奶牛的关系。。不管是能打败奶牛i也好。。会被奶牛i打败也好。。只要不是不确定就行。。所以我们跑一遍floyd做传递闭包。得到任何两个点之间的联系。然后对于每一个点。看其他n-1个点是否和他有关系。

http://acm.hdu.edu.cn/showproblem.php?pid=2647 题意：老板要给很多员工发奖金， 但是部分员工有个虚伪心态， 认为自己的奖金必须比某些人高才心理平衡； 但是老板很人道， 想满足所有人的要求， 并且很吝啬，想画的钱最少 输入若干个关系 a b a c c b 意味着a 的工资必须比b的工资高 同时a 的工资比c高； c的工资比b高

http://acm.hdu.edu.cn/showproblem.php?pid=3342 裸题。 注意有重边。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月17日 星期四 19时29分00秒 4File Name :code/hdoj/3342.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E2+7; 34 35int n,m; 36 37bool v[N][N]; 38int in[N]; 39 40void topo() 41{ 42 queue<int>q; 43 44 for ( int i = 0 ; i < n ; i++) 45 { 46 if (in[i]==0) q.push(i); 47 } 48 49 int cnt = 0 ; 50 while (!q.empty()) 51 { 52 cnt++; 53 int u = q.front(); q.pop(); 54 55 for ( int i = 0 ; i< n ; i++) 56 { 57 if (!v[u][i]) continue; 58 59 in[i]--; 60 if (in[i]==0) 61 { 62 q.push(i); 63 } 64 } 65 } 66 if (cnt==n) 67 { 68 puts("YES"); 69 } 70 else 71 { 72 puts("NO"); 73 } 74} 75int main() 76{ 77 #ifndef ONLINE_JUDGE 78 freopen("code/in.txt","r",stdin); 79 #endif 80 81 while (~scanf("%d %d",&n,&m)!=EOF) 82 { 83 if (n==0) break; 84 ms(v,false); 85 ms(in,0); 86 while (m--) 87 { 88 int x,y; 89 scanf("%d %d",&x,&y); 90 if (v[x][y]) continue ; //重边? 91 v[x][y] = true; 92 in[y]++; 93 } 94 95 topo(); 96 } 97 98 #ifndef ONLINE_JUDGE 99 fclose(stdin); 100 #endif 101 return 0; 102}

http://acm.hdu.edu.cn/showproblem.php?pid=2795 题意：一个尺寸为wh的方格。要按顺序放放n个尺寸为1wi的纸条。问每一个纸条回被放在哪里。如果有多个，放在最上面（编号小） 思路：把没横行能放的最大长度看做一个序列建树。由于h比n大很多。。多出来的没用。。直接取较小值就行。

http://codeforces.com/problemset/problem/466/C 题意：给定一个序列。要将序列分成三个非零的连续部分，使得三部分的和相等。问有多少中分法。 思路：首先可以知道，如果是序列的和不为3的倍数，那么一定无解，输出0.设序列的和为sum，那么每一部分的和就应该为sum/3。我们可以预处理出从1开始的和为sum/3的点（我开了数组表示前缀和。。想了下其实不用。。我只需要点的信息。。所以用一个变量表示即可），将点的下标存在p[i]里。对于每一个p[i]，我想要知道比p[i]大且补与p[i]相邻的点中，有多少个j，使得从j到n的和为sum/3。因为如果有两部分的和都为sum/3，那么剩下的那部分也一定为sum/3.然后要知道有多少个满足题意的j，我们可以从后往前扫一遍，标记从n开始往前扫，和为sum/3的点，可以用一个0,1数组表示。如果和为sum/3，那么标记为1，否则为0.然后再用一个类似前缀和的思路。再开一个数组c记录从j到n有的和为多少，也就是从j到n有多少个点满足该点到n的和为sum/3.

http://codeforces.com/problemset/problem/279/B 题意：给定一个序列，问一段连续的序列的和小于等于t的最长的序列的长度。 思路：尺取法。三个月前学习的了。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月15日 星期二 20时08分16秒 4File Name :code/cf/problem/279B.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=1E5+7; 34int n; 35int t; 36int a[N]; 37 38void solve() 39{ 40 int head = 1; 41 int tail = 1; 42 int sum = 0 ; 43 int ans = 0 ; 44 while (tail<=n) 45 { 46// cout<<"aaaaa?"<<endl; 47 sum = sum + a[tail]; 48// cout<<"head:"<<head<<" tail:"<<tail<<" sum:"<<sum<<endl; 49 if (sum>t) 50 { 51 while (sum>t) 52 { 53 sum = sum - a[head]; 54// cout<<"sum:"<<sum<<endl; 55 head++; 56 } 57 } 58 if (sum<=t) 59 ans = max(ans,tail-head+1); 60 tail++; 61 62 } 63 printf("%d\n",ans); 64} 65int main() 66{ 67 #ifndef ONLINE_JUDGE 68 freopen("code/in.txt","r",stdin); 69 #endif 70 71 scanf("%d%d",&n,&t); 72 for ( int i =1 ; i <= n ; i++) scanf("%d",&a[i]); 73 solve(); 74 75 #ifndef ONLINE_JUDGE 76 fclose(stdin); 77 #endif 78 return 0; 79}

http://acm.hdu.edu.cn/showproblem.php?pid=4391 题意：有 n 个点，每个点有一种颜色（可能相同），两种操作：1、将区间 [a,b] 染成颜色 c ; 2、询问区间 [a,b] 中颜色为 c 的点有多少个。 思路：因为颜色种类很多。。。没办法通过建很多棵线段树解决。我们用分块的办法。。。

http://acm.hdu.edu.cn/showproblem.php?pid=1754 题意：给定一个区间，有m组操作，操作可以是改变单点，或者查询区间最大值。对于每组查询，输出。 思路：分块。这篇博客说得很不错。http://www.cnblogs.com/sweetsc/archive/2012/08/15/2639395.html

http://codeforces.com/problemset/problem/519/C 题意：两种组队方式，3人一组，1个大牛+2个蒟蒻或者1个蒟蒻+2个大牛。给定大牛和蒟蒻的个数。问最多能组多少队。 思路：线性规划。设两种队分别有x,y个即可。 突然发现这题以前做过。。。比当时的代码简单了一些。还不错。

http://codeforces.com/problemset/problem/552/A 题意：一个100*100的网格。然后给n个矩形。每个格子中填上包含这个格子的矩形的个数。最后问所有格子的和。 思路：树状数组搞得…然而..直接求所有矩形面积的和就可以啊喂。。o(n)。。。111qqz你个炒鸡大菜鸡。

http://codeforces.com/problemset/problem/1/B 题意：给出了两种表格的表示方法。要求互相转化。 思路：直接模拟即可。注意和一般的进制转化不同的是，26进制对应的是1到26而不是0到25，所以要记得处理下借位。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月13日 星期日 19时46分09秒 4File Name :code/cf/problem/1B.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33 34char st[100]; 35int a26[100]; 36int a10[100]; 37 38void pre() 39{ 40 a26[0]=1; 41 for ( int i = 1 ;i<=5; i++) 42 { 43 a26[i] = a26[i-1]*26; 44// cout<<"i:"<<i<<" "<<a26[i]<<endl; 45 } 46 a10[0] = 1; 47 for ( int i = 1 ; i<=7 ; i++) 48 { 49 a10[i] = a10[i-1]*10; 50 } 51} 52void solve() 53{ 54 cin>>st; 55 int len = strlen(st); 56 int p1=-1,p2=-1; 57 for ( int i = 0 ; i < len ; i++) 58 { 59 char ch = st[i]; 60 if (ch>='A'&&ch<='Z') 61 { 62 if (p1==-1) 63 { 64 p1 = i ; 65 } 66 else 67 { 68 p2 = i; 69 break; 70 } 71 } 72 } 73 if (p2-p1==1||p2==-1) 74 { 75 int dig = 0 ; 76 int alp = 0; 77 int sum = 0 ; 78 int sum2 = 0 ; 79 for ( int i = len -1 ; i>= 0 ; i--) 80 { 81 char ch = st[i]; 82 if (!isdigit(ch)) 83 { 84 sum += (ch-'A'+1)*a26[alp]; 85 alp++; 86 } 87 else 88 { 89 sum2+= (ch-'0')*a10[dig]; 90 dig++; 91 } 92 } 93 printf("R%d\n",sum2,sum); 94 } 95 else 96 { 97 int dig1 = 0 ; 98 int dig2 = 0; 99 int sum1 = 0 ; 100 int sum2 = 0 ; 101 int p = 1; 102 for ( int i = len-1 ; i>= 0 ; i-- ) 103 { 104 char ch = st[i]; 105 if (isdigit(ch)) 106 { 107 // cout<<"ch:"<<ch<<endl; 108 if (p) 109 { 110 sum1+=(ch-'0')*a10[dig1]; 111 // cout<<"sum1:"<<sum1<<endl; 112 dig1++; 113 } 114 else 115 { 116 sum2+=(ch-'0')*a10[dig2]; 117 dig2++; 118 } 119 120 121 } 122 else 123 { 124 p = 0 ; 125 } 126 } 127// cout<<"sum1:"<<sum1<<" sum2:"<<sum2<<endl; 128 int cnt = 0 ; 129 int b[50]; 130 while(sum1) 131 { 132 cnt++; 133 b[cnt] = sum1; 134 sum1/=26; 135// cout<<"sum1::::"<<sum1<<endl; 136 } 137// cout<<"cnt:"<<cnt<<endl; 138 for ( int i = 1 ; i <= cnt -1 ; i ++) 139 { 140 if (b[i]<=0) 141 { 142 b[i]+=26; 143 b[i+1]--; 144 } 145 } 146 while (b[cnt]==0) cnt--; 147 148 for ( int i = cnt ; i >=1 ; i--) 149 { 150 151 // cout<<"b[i]:"<<b[i]<<endl; 152 cout<<char(b[i]+'A'-1); 153 } 154 cout<<sum2<<endl; 155 156 157 158 159 } 160 161 162} 163int main() 164{ 165 #ifndef ONLINE_JUDGE 166 freopen("code/in.txt","r",stdin); 167 #endif 168 169 pre(); 170 int T; 171 cin>>T; 172 while (T--) 173 { 174 solve(); 175 } 176 177 #ifndef ONLINE_JUDGE 178 fclose(stdin); 179 #endif 180 return 0; 181}

http://codeforces.com/contest/526/problem/B 题意：有一棵完全二叉树。每条边上有一定数量的路灯。问最少需要添加多少个路灯。使得根节点道叶子节点的每一条路径上的路灯数量一样。 思路：同叶子节点网上更新即可。 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月11日 星期五 16时57分27秒 4File Name :code/cf/problem/526B.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=3E3+7; 34int n; 35int a[N]; 36int main() 37{ 38 #ifndef ONLINE_JUDGE 39 freopen("code/in.txt","r",stdin); 40 #endif 41 cin>>n; 42 LL res = 0 ; 43 n = (2<<n)-2; 44 for ( int i = 1 ; i <= n ; i++) 45 { 46 cin>>a[i]; 47 } 48 for ( int i = n ; i >= 1 ; i-=2) 49 { 50 res +=abs(a[i]-a[i-1]); 51 if (i!=2) a[i/2-1] += max(a[i],a[i-1]); 52 } 53 cout<<res<<endl; 54 55 56 #ifndef ONLINE_JUDGE 57 fclose(stdin); 58 #endif 59 return 0; 60}

http://codeforces.com/problemset/problem/574/B 题意：给定一个无相图。选出三个点，使得这三个点之间互相有边相连，且三个点的度数之和最小。 思路：暴力出奇迹。复杂度o(n2+n*m) 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2015年12月09日 星期三 21时33分28秒 4File Name :code/cf/problem/574B.cpp 5************************************************ */ 6 7#include <cstdio> 8#include <cstring> 9#include <iostream> 10#include <algorithm> 11#include <vector> 12#include <queue> 13#include <set> 14#include <map> 15#include <string> 16#include <cmath> 17#include <cstdlib> 18#include <ctime> 19#define fst first 20#define sec second 21#define lson l,m,rt<<1 22#define rson m+1,r,rt<<1|1 23#define ms(a,x) memset(a,x,sizeof(a)) 24typedef long long LL; 25#define pi pair < int ,int > 26#define MP make_pair 27 28using namespace std; 29const double eps = 1E-8; 30const int dx4[4]={1,0,0,-1}; 31const int dy4[4]={0,-1,1,0}; 32const int inf = 0x3f3f3f3f; 33const int N=4E3+7; 34int n ,m; 35vector<int>edge[N]; 36int ans; 37 38bool conc[N][N]; 39int d[N]; 40int main() 41{ 42 #ifndef ONLINE_JUDGE 43 freopen("code/in.txt","r",stdin); 44 #endif 45 46 cin>>n>>m; 47 ms(conc,false); 48 ms(d,0); 49 for ( int i = 0 ; i < m ;i++) 50 { 51 int x,y; 52 cin>>x>>y; 53 conc[x][y] = true; 54 conc[y][x] = true; 55 d[x]++; 56 d[y]++; 57 } 58 int ans = inf; 59 for ( int i = 1 ; i <= n ; i++) 60 for ( int j = 1 ; j <= n ;j++) 61 if (conc[i][j]&&d[i]+d[j]<ans) 62 { 63 for ( int k = 1 ; k <= n ; k++) 64 if (conc[i][k]&&conc[j][k]) 65 ans = min(ans,d[i]+d[j]+d[k]); 66 } 67 if (ans!=inf) 68 cout<<ans-6<<endl; 69 else puts("-1"); 70 71 #ifndef ONLINE_JUDGE 72 fclose(stdin); 73 #endif 74 return 0; 75}

http://codeforces.com/contest/510/problem/C 题意：给定n个字符串。问是否存在一种字母顺序，使得这n个字符串的顺序满足字典序（自定义的）。如果有多种顺序，输出字典序（标准的）最小的。 思路：将字符串的关系处理成边的关系。每次对于第i个和第i+1个字符串，从前往后扫，直到不相等的那一位，设为k，然后连边，指向i+1。表明第i个字符串的第k位大于第i+1个字符串的第k位。如果没有不想等的。说明其中一个是另一个的字串。如果前者是后者的字串，那么不影响。如果后者是前者的字串，则不存在满足条件的字典序。然后做拓扑排序。由于有多种输出字典序（标准的）最小的方案。所以存点的时候用优先队列存。

题意：给定n组u关系。每组表示a战胜b。。问根据这些关系能否确定冠军。 思路：如果a战胜b就从a连一条指向b的边。那么能确定冠军的条件就变成了，有且只有一个入度为0的点。翻译过来就是，有一个人没有被任何人战胜过。且，这样的人只有一个。一开始想用map来搞。。但是比较麻烦。。其实用set比较好。。开两个set，一个存所有的人，一个存输过的人。出度为0的点只有一个等价为，有且只有一个人没有输过。也就是两个set的元素差个数为1.

http://acm.hdu.edu.cn/showproblem.php?pid=1285 题意： 有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。