NOip2009
第一题 一看到字母就想用map做了，先读入再处理mp，过程中判断是否合法，最后逐个字母翻译就行。不用map用0到25表示26个大写字母也是没问题的。题目较简单，在此不再赘述。只是要注意三种非法情况（一对多或多对一或不完全，当时就是因为只写了两种就wa了）。
#include <iostream>#include <cstdio>#include <algorithm>#include <map>#include <cstring>using namespace std;map<char,char>mp;char sa[105], sb[105], qs[105], ans[105];int used[26], usedd[26];int main(){ freopen("spy.in", "r", stdin); freopen("spy.out", "w", stdout); scanf("%s%s%s", sa, sb, qs);//一起读入 int lena = strlen(sa); int lenb = strlen(sb); int lenq = strlen(qs); if(lena != lenb){PRintf("Failed");return 0;} for(int i=0; i<lena; i++){ if(mp[sa[i]] != 0 && mp[sa[i]] != sb[i]){printf("Failed");return 0;}//一对多非法 mp[sa[i]] = sb[i]; used[sa[i]-'A'] = 1;//不完全非法 usedd[sb[i]-'A'] = 1;//多对一非法（sa完全了，sb不完全就是多对一） } char cc = 'A'; for(int i=0; i<=25; i++) if(used[i] == 0 || usedd[i] == 0){printf("Failed");return 0;} for(int i=0; i<lenq; i++){ printf("%c", mp[qs[i]]); } printf("/n"); return 0;} 
第二题 唯一分解定理求解。先初始化50000以下的素数（最大值开根求得），用线性筛要快一些，像这种有多组数据的题目，一定要清空数组！！！（错太多次了）。mi的四个数组存的是分解质因数后的指数，对每一位指数进行讨论，求出其可能值，再累乘起来就是答案了。注意，最后有一个特判，b0>1，表示的是可能分解之后剩下一个大于50000的质数（一定是质数，因为50000*50000已超上限），所以取或是不取这个数又有两种情况，*2。详细原理不好叙述，请读者自己用数据模拟。
#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>using namespace std;const int N = 50010;int aa[N], su[N], mia[N], mib[N], mic[N], mid[N];int num;void qsu(){//初始化素数 int idc = 0; for(int i=2; i<=N; i++){ if(aa[i] == 1) continue; su[++idc] = i; for(int j=i*2; j<=N; j+=i) aa[j] = 1; } num = idc;}int main(){ freopen("son.in", "r", stdin); freopen("son.out", "w", stdout); int T; scanf("%d",&T); qsu(); while(T--){ memset(mia,0,sizeof(mia)); memset(mib,0,sizeof(mib)); memset(mic,0,sizeof(mic)); memset(mid,0,sizeof(mid)); int a0, a1, b0, b1; scanf("%d%d%d%d", &a0,&a1,&b0,&b1); for(int i=1; i<=num, b0>1 ; i++){ if(i>num) break; if(b0 % su[i] == 0){ mia[i]++; b0 /= su[i]; i--; } } for(int i=1; i<=num, b1>1 ; i++){ if(i>num) break; if(b1 % su[i] == 0){ mib[i]++; b1 /= su[i]; i--; } } for(int i=1; i<=num, a0>1 ; i++){ if(a0 % su[i] == 0){ mic[i]++; a0 /= su[i]; i--; } } for(int i=1; i<=num, a1>1 ; i++){ if(a1 % su[i] == 0){ mid[i]++; a1 /= su[i]; i--; } }//分解 int ans = 1; for(int i=1; i<=num+1; i++){ if(mia[i] == mib[i] && mid[i] == mic[i]){ int x = mia[i] + 1 - mid[i]; if(x < 1) x = 0; ans *= x; } if(mia[i] == mib[i] && mia[i] < mid[i]){ ans *= 0; } if(mia[i] != mib[i] && mib[i] < mid[i]){ ans *= 0; } if(mia[i] != mib[i] && mib[i] > mid[i] && mid[i] != mic[i]){ ans *= 0; } } int c = 1; if(b0>1) c = 2;//最后剩下的质数大于50005时，取与不取应该再*2 printf("%d/n", ans*c); } return 0;} 
第三题 这道题当时没有想出比较优的解法。一直在想怎么一遍dfs或者bfs就把同一路径中的max和min都搞定，结果发现很难实现。后来讨论到才发现其实完全没有必要一次性就搞定，直接把每一个城市都当做一个节点，从起点到它求一个min，再从终点到它求一个max，等于是开头存遍的时候存两次，然后直接两遍bfs，代码都是差不多的，只需要换一个方向就行。因为有一个买卖关系，所以说两次bfs不能交换位置（先买再卖）。又因为这可能是一个带环的图，所以采用spfa。最后只需要每个点（每条路径）上的max-min取一个最大值就行了。
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int M = 500010;const int N = 100010;int n, m, idc;int head1[N], head2[N], w[N], minn[N], maxx[N];struct ln{ int next1,next2,u,v; ln(){next1 = -1; next2 = -1;}}ed[M * 2];//邻接表开两倍void adde(int u,int v){ idc++; ed[idc].u = u; ed[idc].v = v; ed[idc].next1 = head1[u]; head1[u] = idc; ed[idc].next2 = head2[v]; head2[v] = idc;}void bfs1(){ int head = 0, tail = 1; int L[N], flag[N]; memset(flag,0,sizeof(flag)); memset(minn,0x7f,sizeof(minn)); L[tail] = 1; minn[1] = w[1]; flag[1] = 1; do{ head++; int u = L[head]; for(int k = head1[u]; k; k = ed[k].next1){ int v = ed[k].v; if(minn[v] > minn[u] || w[v] < minn[v]){ minn[v] = min(w[v], minn[u]); if(flag[v] == 0) L[++tail] = v; flag[v] = 1; } } flag[u] = 0;//出队 }while(head < tail);}void bfs2(){ int head = 0, tail = 1; int L[N], flag[N]; memset(flag,0,sizeof(flag)); memset(maxx,-1,sizeof(maxx)); L[tail] = n; maxx[n] = w[n]; flag[n] = 1; do{ head++; int u = L[head]; for(int k = head2[u]; k; k = ed[k].next2){ int v = ed[k].u; if(maxx[u] > maxx[v] || w[v] > maxx[v]){ maxx[v] = max(w[v], maxx[u]); if(flag[v] == 0) L[++tail] = v; flag[v] = 1; } } flag[u] = 0; }while(head < tail);}int main(){ freopen("trade.in","r",stdin); freopen("trade.out","w",stdout); memset(head1,-1,sizeof(head1)); memset(head2,-1,sizeof(head2)); scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) scanf("%d", &w[i]); for(int i=1; i<=m; i++){ int u, v, k; scanf("%d%d%d", &u, &v, &k); if(k == 1) adde(u,v); else{ adde(u,v); adde(v,u); } } bfs1();//先买 bfs2();//再卖 int ans = 0; for(int i=1; i<=n; i++) ans = max(ans, maxx[i] - minn[i]); printf("%d", ans); return 0;} 
第四题 当听说这道题正解就是搜索时还是有点无语的（除了跳舞链，听说应用不太广泛就没有学，不过用来解数独还是挺六的）。大神教了一种神奇的优化方案，位运算。类似状压dp，用二进制记录状态，位运算寻找要填的地方，以及排除不可能填的数。一下子就把O（27）的排除降成了O(1)。这下基本上就不会T掉了。最开始构造一个score数组就避免了最后for一遍求ans的情况了（直接带着走，填一个加一个）。还有一个优化就是从可能性最小的地方填起（按照每行中空位的多少，从小到大排出一个填的顺序，至于为什么，就想想做数独的时候怎么做容易就好了）。还有就是据说倒着填会快一些（可能是数据想卡吧）。
#include <cstdio> #include <algorithm>#include <cstring> using namespace std; int score[10][10] = {{0,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 ,0 }, {0,6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 }, {0,6 ,7 ,7 ,7 ,7 ,7 ,7 ,7 ,6 }, {0,6 ,7 ,8 ,8 ,8 ,8 ,8 ,7 ,6 }, {0,6 ,7 ,8 ,9 ,9 ,9 ,8 ,7 ,6 }, {0,6 ,7 ,8 ,9 ,10,9 ,8 ,7 ,6 }, {0,6 ,7 ,8 ,9 ,9 ,9 ,8 ,7 ,6 }, {0,6 ,7 ,8 ,8 ,8 ,8 ,8 ,7 ,6 }, {0,6 ,7 ,7 ,7 ,7 ,7 ,7 ,7 ,6 }, {0,6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 ,6 }}; int emp[10],colu[10],rowu[10],coll[10],order[10],map[10][10],latu[4][4]; int ans,p,sum; int r[1 << 10]; int init(){ memset(colu,0,sizeof(colu)); memset(rowu,0,sizeof(rowu)); memset(emp,0,sizeof(emp)); memset(coll,0,sizeof(coll)); memset(order,0,sizeof(order)); memset(map,0,sizeof(map));//存图 memset(latu,0,sizeof(latu)); sum = 0; for(int i=1; i<=9; i++) for(int j=1; j<=9; j++) { scanf("%d", &map[i][j]); if(map[i][j]){ sum += map[i][j] * score[i][j];//积分 emp[i] |= 1 << (j - 1);//每行的已填位置 p = 1 << (map[i][j] - 1);//转二进制 if((colu[i] & p) || (rowu[j] & p) || (latu[(i - 1) / 3][(j - 1) / 3] & p)){ //已经出现重复 printf("-1"); return 0; } colu[i] |= p;//列 rowu[j] |= p;//行 latu[(i - 1) / 3][(j - 1) / 3] |= p;//块 } else coll[i]++;//每行待填个数 } for(int i=1; i<=9; i++) order[i] = i;//搜索顺序：从已填数多的一行开始填 for(int i=1; i<=8; i++) for(int j=i+1; j<=9; j++) if(coll[order[i]] > coll[order[j]]){ int t = order[i]; order[i] = order[j]; order[j] = t;//从限制多的行填到限制少的行，数组保存填行的顺序 } for(int i=1; i<=9; i++) if(coll[order[i]]) return i;//此行有空 } void dfs(int k, int sum){ if(k == 10) ans = max(ans, sum); else{ int x,first,row,able,pos,col; col = order[k];//第几行 x = 511 - emp[col];//511->111111111 first = x & ( -x );//未填的最后一个位置 emp[col] |= first; row = r[first]+1;//找格子 务必加一 pos = 511 - (colu[col] | rowu[row] | latu[(col - 1) / 3][(row - 1) / 3]); //可以填的数（排除了不能填的数） while(pos){ //填格子 able = pos & ( -pos ); pos -= able;//枚举能填的数 map[col][row] = r[able]+1;//务必加一 colu[col] |= able; rowu[row] |= able; latu[(col - 1) / 3][(row - 1) / 3] |= able; //更新 if(x == first)//一行填完 dfs(k+1, sum + map[col][row] * score[col][row]); else//填此行的上一个 dfs(k, sum + map[col][row] * score[col][row]); colu[col] -= able; rowu[row] -= able; latu[(col - 1) / 3][(row - 1) / 3] -= able; //还原 } emp[col] -= first;//还原 } } int main(){ freopen("sudoku.in","r",stdin); freopen("sudoku.out","w",stdout); for(int i=1; i<=9; i++){ r[1 << i] = i; } int st = init();//dfs起始行 if(!st){//非法 printf("-1"); return 0; } dfs(st, sum); if(!ans) printf("-1"); else printf("%d",ans); return 0; } 考试总结 这一次的失误主要在于时间上，首先就是第一题解决的速度不够，用了将近40min，而且分还没有得全，需要注意的是应该在做完题目之后再读一遍题目，检查一下有没有忽略的条件，限制等。切忌样例数据一通过就跑。最好在读题的时候就形成成熟的思路，考虑到所有的情况。站在自己想出解决方案的对立面，找出方法的漏洞。还有一个技巧值得一提，就是数据分治。在数据跨度较大，或是部分数据有明显特征的时候，学会用不同的方法解决不同类的数据。这样就可以多得部分分数（要注意的就是首先要提升代码速度）。谈到代码速度就不得不说说暴力了。对于一些毫无头绪的题目，就只能选择暴力的方式骗分了，不过这就会又产生一个问题，就是说也许你写暴力的时间都多于想出正解的时间了，但是分数却要少很多。为什么写暴力？就是为了节省时间，所以说又快又好的写一个暴力就显得至关重要了。很多的时候我们都不太敢写暴力，可事实就是需要我们果断地巧妙地写暴力。还有一个就是暴力的优化，一些大神写一个暴力都能得七八十分（orz~），各种优化一加上跑的飞快！怎么做到这一点呢？概括的说就是要寻找题目的特性，分析题目。这显然是一个比较灵活的东西，只有靠自己的悟性和训练了。
