ACM

http://poj.org/problem?id=3279 反转类问题. 有N*M个方格，每个上面有数字0或者1 操作一个方格，这个方格及其相邻的四个方格(有公共边)会改变状态(由0变1或者由1变0) 问至少需要多少次操作，所有的状态都为0

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=83295#problem/I 最多18个点，选3个点，能够成的三角形不超过1000个，O(n2)暴力就可以。 思路就是枚举三个点点，对于每一个构成的三角形，把这个三角形的最小角和次小角存起来。 然后枚举三角形，判断是否有两个三角形的最小角和次小角分别对应相等。

http://poj.org/problem?id=2398 题意大概是说将一个盒子用n个board分成n+1 部分 然后往里面放toy，给定盒子，board，和toy的坐标 问所有的toy放完后，有多少部分中有t个toy; 简单计算几何

http://poj.org/problem?id=2251 简单bfs，只不过是三维的。。。 唯一的坑点在输出上… Escaped in %d minute(s) 这意思是答案为1输出minute，不为1输出minutes还是说是不是1都输出minute(s)? 试了下，答案是后者。

http://codeforces.com/contest/558/problem/C 题目大意是说，给定N个数，可以对任意数进行任意次两种操作，×2，和/2（整除） 问最少操作多少次，可以让所有数相等。 嘛，前半个小时A掉了前两个提，d E貌似都是线段树。。并不会。。。就一直搞C。。。。

http://poj.org/problem?id=1564 dfs 三个参数 x,sum,k, x表示开始的坐标，sum表示当前的和，k表示这是一组答案中的第几个数，是用来记录路径的… 调了好久没写出来…我写完之后答案会有重复.一开始想开一个boolean数组记录，这样第一组样例的3+1就只会输出一遍，但是这样，2+2就不会被记录到答案中了.

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=82557#problem/A Zk的解法：拆点，把每一个点存成两份，r[i]和r[n+i] 连边的时候如果u和v相连，我们就分别连 u&&v 和 u+n&&v+n 和 u&&v+n 其中最后一个存法是要使用魔法的情况… 最后求从1到n+n的最短路径即可

http://codeforces.com/contest/556/problem/C 果然一晚上不睡觉会导致读错题么… 需要注意的是 如果有一个是 1 2 4 6 那么 1,2是不必拆开的…. 然后我们发现，只有以1为开始且连续的套娃不必拆开….

最大连续区间和是一个经典的问题。给定一个长度为 n 的序列 a[1],a[2]…a[n-1],a[n]，求一个连续的子序列 a[i],a[i+1]…a[j-1],a[j]，使得 a[i]+a[i+1]…a[j-1]+a[j]最大。

http://poj.org/problem?id=3278 bfs，用到了stl的queue 代码实现 1 2 3 /* *********************************************** 4 Author :111qqz 5 Created Time :2016年02月19日 星期五 15时45分05秒 6 File Name :3278.cpp 7 ************************************************ */ 8 9 #include <algorithm> 10 #include <cstdio> 11 #include <iostream> 12 #include <cstring> 13 #include <string> 14 #include <cmath> 15 #include <map> 16 #include <stack> 17 #include <queue> 18 19 using namespace std; 20 typedef long long LL; 21 const int inf = 8E8; 22 const int N=2E5+7; 23 int d[N]; 24 int n,k; 25 void bfs() 26 { 27 queue<int> q; 28 memset(d,-1,sizeof(d)); 29 q.push(n); 30 d[n]=0; 31 while (!q.empty()) 32 { 33 int x = q.front(); 34 q.pop(); 35 if ( x==k ) 36 { 37 break; 38 } 39 int next[10]; 40 next[1]=x-1; 41 next[2]=x+1; 42 next[3]=2*x; 43 for ( int i = 1; i <= 3 ; i++ ) 44 { 45 if (next[i]>=0&&next[i]<=100000&&d[next[i]]==-1) 46 { 47 d[next[i]]=d[x]+1; 48 q.push(next[i]); 49 } 50 } 51 } 52 53 54 } 55 int main() 56 { 57 while (scanf("%d %d",&n,&k)!=EOF) 58 { 59 bfs(); 60 cout<<d[k]<<endl; 61 } 62 return 0; 63 }

http://poj.org/problem?id=1028 代码实现 1 2 3 4 /* *********************************************** 5 Author :111qqz 6 Created Time :2016年02月19日 星期五 15时45分01秒 7 File Name :1028.cpp 8 ************************************************ */ 9 10 #include <algorithm> 11 #include <cstdio> 12 #include <iostream> 13 #include <cstring> 14 #include <string> 15 #include <cmath> 16 #include <map> 17 #include <stack> 18 #include <queue> 19 20 using namespace std; 21 typedef long long LL; 22 const int inf = 8E8; 23 stack<string> backstack; 24 stack<string> forwardstack; 25 string cur; 26 string cmd; 27 int main() 28 { 29 cur ="http://www.acm.org/"; 30 31 while (cin>>cmd) 32 { 33 if (cmd=="QUIT") 34 { 35 break; 36 } 37 if (cmd=="BACK") 38 { 39 if (backstack.empty()) 40 { 41 cout<<"Ignored"<<endl; 42 continue; 43 } 44 forwardstack.push(cur); 45 cur=backstack.top(); 46 backstack.pop(); 47 cout<<cur<<endl; 48 } 49 if (cmd=="FORWARD") 50 { 51 if (forwardstack.empty()) 52 { 53 cout<<"Ignored"<<endl; 54 continue; 55 } 56 backstack.push(cur); 57 cur=forwardstack.top(); 58 forwardstack.pop(); 59 cout<<cur<<endl; 60 } 61 if (cmd=="VISIT") 62 { 63 backstack.push(cur); 64 65 cin>>cur; 66 while (!forwardstack.empty()) forwardstack.pop(); 67 cout<<cur<<endl; 68 69 } 70 } 71 72 73 return 0; 74 }

题目链接：http://poj.org/problem?id=2643 在考stl的map… 我是定义了一个string 指向string的，表示参选人和党派的关系，和一个string 指向int的，表示某个党派被投票的次数。

http://acm.hdu.edu.cn/showproblem.php?pid=1908 看到有两个优先级，然后题目中又有queue。。。就想到了优先队列。。。 但是优先队列的cmp函数没搞懂，因为比较的是结构体，好像要重载< 什么的。 然而并不会。 其实用map就可以做。。。

http://poj.org/problem?id=1833 还是next_permutation. 这次是Int类型的 需要注意的是next_permutation是先判断时候有后继，返回一个bool值，如果为true，就转化到后继。

http://poj.org/problem?id=1256 题意是说求出一个字符串的全排列，按字典序 需要注意的是字典序和传统意义上的字典序不同 重新定义了，A 需要自己重写cmp函数。 next_permutation好神….直接求出全排列…..

http://codeforces.com/problemset/problem/548/B 比赛的时候不懂为什么就没做出来…. 其实很容易想到一个o(q*(n+m))的做法… 就是每次更新，要同时更新当前更新行的最大连续和….O（m）可以完成…然后在O（n）扫一遍，找到所有行中的最大值。 然后需要注意的是，在第一次更改之前就要把每个行的最大值处理出来l.. 然后cf机器真是够快，O(nmq)的1.2S过。。。。

http://codeforces.com/problemset/problem/548/A 水题。分割成K个，每个串判断是否回文，如果都是就yes，否则no 需要注意的是，可能不能正好分成长度相同的K个，这个时候也要No 代码实现 1 2 3 4 5 /* *********************************************** 6 Author :111qqz 7 Created Time :2016年03月03日 星期四 14时09分08秒 8 File Name :code/cf/problem/548A.cpp 9 ************************************************ */ 10 11 #include <algorithm> 12 #include <cstdio> 13 #include <iostream> 14 #include <cstring> 15 #include <string> 16 #include <cmath> 17 #include <map> 18 19 using namespace std; 20 const int N=1E3+5; 21 char st[N]; 22 int k,len,ave; 23 bool ok(int l,int r) 24 { 25 for (int i = l ; i<=(l+r)/2;i++) 26 if (st[i]!=st[l+r-i]) 27 return false; 28 return true; 29 } 30 31 int main() 32 { 33 cin>>st; 34 cin>>k; 35 len = strlen(st); 36 ave= len/k; 37 if (k*ave!=len){cout<<"NO"<<endl;return 0;} 38 for (int i = 1 ; i<=k;i++ ) 39 { 40 if (!ok((i-1)*ave,i*ave-1)) 41 { 42 cout<<"NO"<<endl; 43 //cout<<i<<endl; 44 return 0; 45 } 46 47 } 48 cout<<"YES"<<endl; 49 50 51 52 return 0; 53 }

http://poj.org/problem?id=2492 Hint Huge input,scanf is recommended. 也是带种类的冰茶几。 由于只分了两类…我们还是可以按照上道题的做法。。 感觉完全是一样的题啊。。 结果一直WA。。。。 最后发现。。。我边读入边判断。。发现同性恋了就直接Break掉了。。。后面改组的数据读到下一组去了233，不WA就日了汪了。。。

http://poj.org/problem?id=1703 种类冰茶几…看到还有一种算是拓展的交加权冰茶几？ 看到有做法是在开一个数组。。。记录是哪一组…. 但是因为只有两组….我们可以分别存… 因为不知道每一个D的两个人分别是哪个组（帮派？） 可以都存一下。 TLE了两次….应该是用了cin的事。。。改成scanf就变WA了。。。 想了下。原来是我对“not sure yet”的判断出现失误。 我开了一个v数组，记录在D下出现的人。 我误以为出现的人的帮派一定是确定的。 实际上并不是。 比如 1,3 5,7 3和7都出现了。但是3和7是一组与否显然还是“not sure yet”

http://codeforces.com/problemset/problem/535/C 题读了好几遍才读懂。 题意是给出一个等差数列，操作严格要求从最左边不为零的连续m个数减去1，最多执行t次后问离最左边最远的位置在哪里。 有两个限制条件…一个是本身的si不能大于t，否则无法吃完。 还有一个是从sl到sr的和不能超过m*t (比赛的时候考虑的不周到。。实际上只有当r-l+1比m大的时候才是m，也就是说要取min(m,l-r+1)) 这题正解应该是二分….直接Lower_bound。。。看到也有人用前缀和搞的。 我是解方程了（貌似是个傻逼做法）…. 可以列出一个关于r的一元二次方程。。。然后求根公式2333 方程是：