这套题，勾起了我无数美好的回忆←意思是该好好复习了...
【day1】
一.转圈游戏
首先，第一题，在处理k的时候应该用快速幂算法。
大概就是下面这样，要注意的是：1.二分时要判断有无余数。2.先设数，在进行乘积运算，不然会递归两次=。=
1 int pow(int a,int pos) 2 { 3 if(pos==1) return a%t; 4 int temp=pow(a,pos/2); 5 if(pos%2==1) return (temp*temp*a)%t; 6 return (temp*temp)%t; 7 }
二.火柴排队
读题发现他定义的要求是跟排序有关的，那就先把两组火柴排个序吧。
排序之后呢，将排序后编号相等的两组一一对应，将a组编号当做b组标号的移动目标qwq←有点抽象
所以呢，很自然的想到要求逆序对，【复习】求逆序对可以用树状数组或者归并排序，复杂度都为nlgn。
贴下树状数组方法的程序=。=【因为归并排序忘了！！←滚去复习去
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #include<algorithm> 7 using namespace std; 8 int n,w[100005],c[100005],ys=99999997,ans; 9 struct node{ 10 int num; 11 int hh; 12 }; 13 int comp(const node &x,const node &y) 14 { 15 if(x.hh<y.hh) return 1; 16 if(x.hh>=y.hh) return 0; 17 } 18 node a[100005]; 19 node b[100005]; 20 int lowbit(int x) //以下为树状数组求逆序对 21 { 22 return x&-x; 23 } 24 void update(int j) 25 { 26 while(j<=n) 27 { 28 c[j]++; 29 j+=lowbit(j); 30 } 31 } 32 int getsum(int k) 33 { 34 int sum=0; 35 while(k>0) 36 { 37 sum+=c[k]; 38 k-=lowbit(k); 39 } 40 return sum; 41 } 42 int main() 43 { 44 freopen("match.in","r",stdin); 45 freopen("match.out","w",stdout); 46 scanf("%d",&n); 47 for(int i=1;i<=n;i++) 48 { 49 a[i].num=i; 50 scanf("%d",&a[i].hh); 51 } 52 for(int i=1;i<=n;i++) 53 { 54 b[i].num=i; 55 scanf("%d",&b[i].hh); 56 } 57 sort(a,a+n+1,comp); 58 sort(b,b+n+1,comp); 59 for(int i=1;i<=n;i++) w[a[i].num]=b[i].num; //原位置，现位置 60 for(int i=1;i<=n;i++) 61 { 62 update(w[i]); 63 ans=(ans+(i-getsum(w[i]))%ys)%ys; 64 } 65 printf("%d\n",ans); 66 return 0; 67 }
所以乖乖滚去复习吧...╮(╯_╰)╭
三.货车运输
第三题，嘛...
先用并查集求出最大生成树...然后呢？bfs一下，也就是说推一遍，当然这个后面的数据肯定会“超时”的！！
但是嘛...也只能这样的，能拿多少算多少...至于我为何不贴程序呢...因为没改对啊没改对...T^T...等我改对有心情再贴吧←等不到了..
哦对了，建树的时候最好用邻接链表【没忘吧？没。】...快捷方便毕竟只有n-1条边...哦，记得双向图要存两遍哟！
【day2】
一.积木大赛
首先，拿到题时，发现特征：1.连续 2.线段 =_=
思索稍许，想到分段来处理，于是便有了以下程序：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 using namespace std; 6 int h[100005],n,ans; 7 void cz(int l,int r) 8 { 9 if(l>r)return; 10 if(l==r){ ans+=h[l];h[l]=0;return;} 11 int k=0; 12 for(int i=l;i<=r;i++) 13 { 14 if(h[i]){k++;h[i]--;} 15 else{ 16 while(!h[i]&&i<=r) {i++;} 17 if(k) ans++; 18 cz(l,l+k-1); 19 cz(i,r); 20 return; 21 } 22 } 23 ans++; 24 cz(l,r); 25 } 26 int main() 27 { 28 freopen("block.in","r",stdin); 29 freopen("block.out","w",stdout); 30 scanf("%d",&n); 31 for(int i=1;i<=n;i++) 32 scanf("%d",&h[i]); 33 cz(1,n); 34 printf("%d\n",ans); 35 return 0; 36 }
当然，最后两组超时了...
但同班的某位大可爱和我的思想差不多，但她是针对0进行处理，并且找出每段最小值，再以最小值为基数去处理，不像我的一层一层减，所以最后她过了，所以在这点上应该可以改进的。
当然还有其他的方法比如大神的线段树+树状数组之类什么鬼玩意...⊙﹏⊙
上面这几种是可行的，神转折来了，正解为对数据分析处理就ok，准确来说就是差分，简单点说是找规律...【吐血中...
附上：
1 #include<cstdio> //正解：差分 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 using namespace std; 6 int h[100005],n,ans; 7 int main() 8 { 9 freopen("block.in","r",stdin); 10 freopen("block.out","w",stdout); 11 scanf("%d",&n); 12 for(int i=1;i<=n;i++) 13 { 14 scanf("%d",&h[i]); 15 if(h[i]>h[i-1])ans+=h[i]-h[i-1]; 16 } 17 printf("%d",&ans); 18 return 0; 19 }
总结：分析数据很重要...【别拉我，我正在撞墙....】
二.花匠
哦这道题真的是要哭，最先想到拐点时觉得不会这么简单吧？（心虚）...于是求了个不相邻的最长不下降序列，恩，果然一点面子都不给的错了...
正解：
1.动规，创两个数组，一个上升一个下降，当然你可以记录此点为拐点的前面所有个数，你也可以记录上升或下降趋势的线段。
2.找拐点，要注意的是起点和终点，以及n=1的情况，下面附上代码：
1 #include<cstdio> //正解方法：找拐点\动规 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 using namespace std; 6 int h[100005],n,ans; 7 int sym=-1; 8 int main() 9 { 10 freopen("flower.in","r",stdin); 11 freopen("flower.out","w",stdout); 12 scanf("%d",&n); 13 for(int i=1;i<=n;i++) scanf("%d",&h[i]); 14 for(int i=1;i<n;i++) 15 { 16 if((sym==0||sym==-1)&&h[i]>h[i+1]) 17 { 18 ans++; 19 sym=1; //下降 20 } 21 if((sym==1||sym==-1)&&h[i]<h[i+1]) 22 { 23 ans++; 24 sym=0; 25 } 26 } 27 ans++; 28 printf("%d",ans); 29 return 0; 30 }
总结：所以说不要想太多...但这道题的细节处理上还是很精妙的w\(≧▽≦)/
三.华容道
“what?华容道是啥？！”这是我初见题的心理...
拿到这道题首先想到了暴力，但苦于不想+不太会去模拟，所以放弃。
再后来呢，想到边不多，建个图？再根据环来求白点的移动？Oh,my god！发现更不会...然后就懵了...
评讲时，老师推荐能过70分的暴力bfs，根据白点向四周的移动来bfs，当然一大问题：如何判重？
针对↑这个问题，有人提出hash、A*、set等等【又该复习了】...但我们再观察一下，发现它的横纵坐标<=30个？！于是乎根据白点和棋子的位置建一个思维数组来判重，因为其他棋子不重要，移动或不动都没啥差。
好了，那我就附上代码吧。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<string> 5 #include<queue> 6 using namespace std; 7 const int maxn=30+2,MAX=810000+5; 8 const int mov[2][4]={{0,0,1,-1},{-1,1,0,0}}; 9 int n,m,q,ma[maxn][maxn]; 10 bool f[maxn][maxn][maxn][maxn]; 11 struct node{ 12 int x1,y1; //空白点 13 int x2,y2; //棋子 14 int step; 15 }k[MAX]; 16 bool jud(int a,int b,int c,int d) //白点，棋子 17 { 18 if(!ma[a][b]||a<1||a>n||b<1||b>m) return false; 19 if(f[a][b][c][d]) return false; 20 f[a][b][c][d]=true; 21 return true; 22 } 23 void bfs() 24 { 25 queue<int>q; 26 memset(f,false,sizeof(f)); 27 int ex,ey,w=1; 28 scanf("%d%d%d%d",&k[w].x1,&k[w].y1,&k[w].x2,&k[w].y2); 29 scanf("%d%d",&ex,&ey); 30 if(ex==k[w].x2&&ey==k[w].y2){printf("0\n");return;} 31 q.push(w);f[k[w].x1][k[w].y1][k[w].x2][k[w].y2]=true; 32 k[w].step=0; 33 while(!q.empty()) 34 { 35 int u=q.front();q.pop(); 36 for(int i=0;i<=3;i++) 37 { 38 int bx=k[u].x1+mov[0][i],by=k[u].y1+mov[1][i]; 39 int qx=k[u].x2,qy=k[u].y2; 40 if(bx==qx&&by==qy){qx=k[u].x1;qy=k[u].y1;} //棋子移动 41 if(jud(bx,by,qx,qy)) 42 { 43 q.push(++w); //入队 44 k[w].x1=bx;k[w].y1=by; //赋值 45 k[w].x2=qx;k[w].y2=qy; 46 k[w].step=k[u].step+1; 47 if(qx==ex&&qy==ey){ 48 printf("%d\n",k[w].step);return; 49 } 50 } 51 } 52 } 53 printf("-1\n"); 54 return; 55 } 56 int main() 57 { 58 freopen("puzzle.in","r",stdin); 59 freopen("puzzle.out","w",stdout); 60 scanf("%d%d%d",&n,&m,&q); 61 for(int i=1;i<=n;i++) 62 for(int j=1;j<=m;j++) 63 scanf("%d",&ma[i][j]); 64 for(int i=1;i<=q;i++) 65 bfs(); 66 return 0; 67 }
嗯，就是这样(╯▽╰)...
总的来说，这6道题让我感觉自己许多知识上的遗忘、模糊、欠缺...总得来说：
复习！复习！复习！
好了，滚去复习了，差不多也快下课了，晚安w╮(╯▽╰)╭
原文：http://www.cnblogs.com/Sue2333/p/5662243.html