一：
给你一个只有4和7的数字，求这是第几个幸运数字？
思路：
我们把4映射成0,7映射成1，然后就如下枚举：0,1，00,01,10,11。因为是映射的，所以可以前导0，然后我们就会知道给出的那个数字在里面的规律了，找出来就好了。
关键：映射思想
二：CF 319 DIV1 A
一种组合计数问题：
给你一个01串（因为是字符串，可以前导0），长度为n。然后给你一个编号为0到（2^n）-1的所有数字，将这些所有编号取异或然后让原数字和这个异或的数字配对成(a,b)。问，有多少套这样的数，满足(a,b)，(c,d),其中c>a,b>d。
思路：
a和c的右边是一定是一样的，那么二进制中，c到某一位的数字是0，而a是1，那么无论后面的数字再怎么枚举都不可能a>=c，所以我们只需要固定这一位，然后左边的高位一样，右边的可以不一样（不一样的相乘即可），这样就OK了。
关键：移位、固定条件、等思想（这个思想在CD667 div2的D也有）
三：CF 315 DIV2 C
题目大意：
有n个人，分别这些人有a[i]的rank，然后通过一定的计算公式，计算出他们的值，如果其中的值小于k，那么就删除这个数字。注意，这个数组是动态的，例如，原来有5个，那么删除了第二个以后后面的3,4,5的a[i]的位置就变成了2,3,4了。
思路：
因为第一个是0，那么我们只需要知道下面所计算的，如果遇到一个tmp<k的就直接删除就可以了，并不需要每一次都重新计算所有的值
关键：无论怎么样的规律，都要先试试看直接按照顺序做或者逆序做
四：UVA1103 world final2011
题目大意，给你几个图片，每个图片都有特征，再给你为h*w的数组，输出数组中描述的图片。（按照字母大小排序）
思路：
dfs，每个特征就是其中的空白块有几个。
这里的一些思想
①把所有不同类型的块弄成不同的颜色，再统计即可
②利用vector<set<int>>来统计集合
关键：让特征不同的对应不同的值，使得容易区分
五：八皇后问题书p193
八皇后问题就是一个简单的回溯法，但是从中我们要获得一些思想：
①主对角线和副对角线之间是有关联的，y-x表示的是主对角线的特征，y+x表示的是副对角线的特征（如果有两个这样的是相等的话，那就表示他们是在同一条对角线上）。或者用vis[1][cur+i] and vis[2][cur-i+n]来表示主和副对角线
六：理想路径 UVA1599 NERRC 2010
题目大意：给n个点，m条边（2<=n<=100000, 1<=m<=200000）的无向图，每条边有一个颜色。求从1到n的路径，使得经过的边最少，如果有多条路径，那么就是找经过的color字典序最小，且输出路径上的color（颜色为1-1e9）
思路一：
反向bfs找路径d，再正向bfs每次找目前节点上color最小的那条边即可。
#include<bits/stdc++.h> using namespace std; const int maxn = 200000 + 5; const int inf = 0x3f3f3f3f; struct edge{ int u, v; int color; edge(int uu, int vv, int cc): u(uu), v(vv), color(cc){} }; vector<edge> G[maxn]; int d[maxn]; int n, m; void init(){ for (int i = 0; i < n; i++) d[i] = inf; for (int i = 0; i < n; i++) G[i].erase(G[i].begin(), G[i].end()); for (int i = 0; i < m; i++){ int u, v, c; scanf("%d%d%d", &u, &v, &c); if (u == v) continue; G[u - 1].push_back(edge(u - 1, v - 1, c)); G[v - 1].push_back(edge(v - 1, u - 1, c)); } } void bfs1(int s){ queue<int> que; que.push(s); d[s] = 0; while (!que.empty()){ int u = que.front(); que.pop(); for (int i = 0; i < G[u].size(); i++){ edge e = G[u][i]; if (d[u] < inf && d[u] + 1 < d[e.v]){ d[e.v] = d[u] + 1; que.push(e.v); } } } } vector <int> ans; void bfs2(int s){ ans.erase(ans.begin(), ans.end()); queue<int> que; que.push(s); //printf("%d ", d[s]); int cnt = d[s] - 1; vector <int> v; int c = inf; while (!que.empty()){ int u = que.front(); que.pop(); for (int i = 0; i < G[u].size(); i++){ edge e = G[u][i]; if (cnt != d[e.v]) continue; //printf("cnt = %d ", cnt); if (c > e.color){ v.erase(v.begin(), v.end()); v.push_back(e.v); c = e.color; } else if (c == e.color){ v.push_back(e.v); } } if (c == inf) if (que.empty() && v.size()){ for (int i = 0; i < v.size(); i++){ que.push(v[i]); } ans.push_back(c); c = inf; cnt--; v.erase(v.begin(), v.end()); } } int len = ans.size(); printf("len = %d ", len); for (int i = 0; i < len; i++){ printf("%d%c", ans[i], i == len - 1 ? ' ' : ' '); } } int main(){ while (scanf("%d%d", &n, &m) == 2){ init(); bfs1(n - 1); bfs2(0); } return 0; }
关键：两次bfs的作用不同。 倒叙。
思路二：
一次bfs就够了（我不会。。。）
七：修改天平UVA12166 NWERC2008
题目大意：给一个深度不超过16的二叉树，代表一个天平，每个杆都挂在中间，每个秤砣的重量已知。问，至少修改多少个秤砣的重量才能让天平平衡？
吐槽：
T了我一脸。。。而且自己的之前思路还错了。。。
思路：
由于是天平，且是二叉树，因此，我们知道，修改一个点就等于要修改全部的点。因此，我们可以固定一下。首先我们选取二叉树上的一点为值，如果天平要平衡，那么天平上的总重量必然为（目前选取的这个重量为w，深度为d）w<<d。然后我们把每个值所对应的w<<d求出来，用map保存，然后最后扫一遍map就行了。
关键：定点，平衡与总和，逆向（就是反过来用w<<d求）
这里知道了strlen(char数组)是O(n)的方法寻找的，所以在多组的时候一定要小心。（因为这个T了一脸）
还有就是map的遍历map<>::iterator it = map.begin() for(; it != map.end(); it++){}
#include<bits/stdc++.h> using namespace std; typedef long long LL; const int inf = 0x3f3f3f3f; const int maxn = 5000000 + 5; //char ch[maxn]; map <LL, int> m; string ch; int main(){ int t; cin >> t; while (t--){ //scanf("%s", ch); cin >> ch; m.clear(); int sum = 0; int nowd = 0; for (int i = 0; i < ch.size()/*strlen(ch)*/; i++){ if (ch[i] == ',') continue; else if (ch[i] == '[') nowd++; else if (ch[i] == ']') nowd--; else { LL val = ch[i] - '0'; while (ch[i + 1] >= '0' && ch[i + 1] <= '9'){ val = LL(val * 10 + ch[i + 1] - '0'); i += 1; } val <<= nowd; m[val] += 1; sum++; } } int ans = inf; map<LL, int>::iterator it = m.begin(); for ( ; it != m.end(); it++){ ans = min(ans, sum - it->second); } printf("%d ", ans); } return 0; }
八：寻找矩形（一次多校赛前的测试，估计题目已经无法交了：链接）
账号密码team244 123570
题目大意：给你n个点，n<1e5，每个点都有坐标(x,y)（xandy的绝对值都小于1e9），有一个矩形，每条边都平行于x和y。问有多少个矩形符合每条边上都有m个点。（每个顶点都必须有一个点）
思路：
离散化以后枚举点，然后之前将所有点按x排序，y排序，最后再寻找这个点上方的m-1个和左边的m-1个，然后找到以后得到新的x和y，然后判断这个x和y存不存在即可。
关键：离散化，上方枚举和下方枚举
#include<bits/stdc++.h> #define mk make_pair using namespace std; typedef long long LL; const int maxn = 300000 + 1000; int n, m; pair<int, int> xx[maxn]; vector<LL> v; vector<int> x[maxn]; vector<int> y[maxn]; map<pair<int, int>, int> p; int len; void solve(){ int cnt = 0; for (int i = 0; i < n; i++){ if (m <= 1) break; int tx = xx[i].first; int ty = xx[i].second; int lenx = x[tx].size(); //表示里面有几个y int leny = y[ty].size();//表示里面有几个x if (lenx < m) continue; if (leny < m) continue; //先找x上方的m-1个，里面放着y int py = lower_bound(x[tx].begin(), x[tx].end(), ty) - x[tx].begin();//在x的集合里面，y的位置 if (py + m > lenx) continue; int px = lower_bound(y[ty].begin(), y[ty].end(), tx) - y[ty].begin();//在y这个集合里面，x的位置 if (px + m > leny) continue; int posx = y[ty][px + m - 1]; int posy = x[tx][py + m - 1];//this? if (p[mk(posx, posy)]){ cnt++; } } printf("%d ", cnt); } int main(){ int t; cin >> t; while (t--){ scanf("%d%d", &n, &m); for (int i = 0; i < n; i++){ LL a, b; scanf("%I64d%I64d", &a, &b); xx[i] = mk(a, b); v.push_back(a); v.push_back(b); } sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); int lx = 0, ly = 0; for (int i = 0; i < n; i++){ int tx = xx[i].first = lower_bound(v.begin(), v.end(), xx[i].first) - v.begin(); int ty = xx[i].second = lower_bound(v.begin(), v.end(), xx[i].second) - v.begin(); //printf("%d %d ", xx[i].first, xx[i].second); p[mk(tx, ty)] = 1; x[tx].push_back(ty); y[ty].push_back(tx); lx = max(lx, tx); ly = max(ly, ty); } for (int i = 0; i <= lx; i++){ sort(x[i].begin(), x[i].end()); } for (int i = 0; i <= ly; i++){ sort(y[i].begin(), y[i].end()); } solve(); //初始化 p.clear(); v.clear(); for (int i = 0; i <= lx; i++){ x[i].clear(); } for (int i = 0; i <= ly; i++){ y[i].clear(); } memset(xx, 0, sizeof(xx)); } return 0; }
九：数学（链接：账号密码同上）
题意：对自然数列{1,2,3,4,5,6...}进行n次操作，每次操作有一个x，意思是前x个保留，后x个删去，再x个保留，后x个删去。。。形成新的序列，问n次操作后第n个数字。
思路：逆序插入
关键：逆序思想