题目链接：Regionals 2013 Asia – Daejeon
6500Boxes
题意：将箱子（矩阵的1）全移动到矩阵的底部需要几步
思路：按列从下到上统计。（n,m）的矩阵，移动一个箱子（x,y），如果有c个箱子在底部，那么移动该箱子的步数是（n-x-c-1）。
AC代码：
#include <stdio.h>#include <string.h>int mp[110][110];int main(){int t;int i,j,n,m;scanf("%d",&t);while(t–){scanf("%d %d",&n,&m);for(i=0;i<n;i++){for(j=0;j<m;j++){scanf("%d",&mp[i][j]);}}int ans=0,c=0;for(j=0;j<m;j++){c=0;for(i=n-1;i>=0;i–){if(mp[i][j]){ans+=(n-i-c-1);c++;}}}printf("%d\n",ans);}return 0;}/*35 41 0 0 00 0 1 01 0 0 10 1 0 01 0 1 03 31 1 10 0 00 0 0*/
6506Padovan Sequence
题意：用等边三角组成多边形，每次所增加的正三角形的边长都是该多边形最长的边。（表述的不好，，看题中的图会明白很多）
思路：找规律，发现f[i]=f[i-2]+f[i-3]。注意long long
#include <stdio.h>#define LL long long LL ans[110];void init(){ans[1]=1,ans[2]=1,ans[3]=1,ans[4]=2,ans[5]=2;LL i;for(i=6;i<=100;i++){ans[i]=ans[i-2]+ans[i-3];}}int main(){LL t;LL n;init();scanf("%lld",&t);while(t–){scanf("%lld",&n);printf("%lld\n",ans[n]);}return 0;}
6508Permutation Graphs
题意：给出两个序列把他们数字相同连线，求交点的个数
思路：将第一串数字编号，第二串按照编号译码，答案就是第二串译码后的逆序数
1 5 3 4 2 7 6
7 1 5 3 4 2 6
编号：
（1 5 3 4 2 7 6）一一对应（1 2 3 4 5 6 7）
（7 1 5 3 4 2 6）得到（6 1 2 3 4 5 7）
（6 1 2 3 4 5 7） 的逆序数为5
画个图看下比较清晰些。
AC代码：
#include <stdio.h>#include <algorithm>#include <vector>#include <string.h>using namespace std;int a[100010];int n,c[100003];int x[100010];vector<int> s;vector<int>::iterator it;int lowbit(int x) {return x&(-x);}int sum(int x){int sum=0;while(x<=n) {sum+=c[x];x+=lowbit(x);}return sum;}void inster(int x,int i) {while(x>0) {c[x]+=i;x-=lowbit(x);}}int main(){int t;int i;scanf("%d",&t);while(t–){s.clear();memset(c,0,sizeof c);scanf("%d",&n);for(i=0;i<n;i++){scanf("%d",&a[i]);s.push_back(a[i]);}int k=1;for(it=s.begin();it!=s.end();it++)x[*it]=k++;for(i=0;i<n;i++){scanf("%d",&a[i]);a[i]=x[a[i]];}int ans=0;for(i=0;i<n;i++){//printf("%d,",a[i]);inster(a[i],1);ans+=sum(a[i]+1);//printf("%d\n",sum(a[i]+1));}printf("%d\n",ans);}return 0;}/*452 5 4 1 31 5 3 2 475 6 7 1 2 3 45 6 7 1 2 3 471 5 3 4 2 7 67 1 5 3 4 2 661 2 3 4 5 62 1 4 3 6 5*/
6510Stickers
题意：给出一个2*n的矩阵，取数使得到的结果最大，要求取的数不能有公共边。
思路：dp[i][j]表示前i列，状态j所取数的最大值，j==0 表示不取，j==1表示去第1行的数，j==2表示取第2行的数。状态转移见代码
AC代码：
#include <stdio.h>#include <algorithm>#include <string.h>using namespace std;int dp[100010][5];//0 都不选 1选上面一张（0）。2选下面一张（1）int mp[5][100010];int main(){int t;int i,j,n;scanf("%d",&t);while(t–){scanf("%d",&n);for(i=1;i<=2;i++){for(j=0;j<n;j++){scanf("%d",&mp[i][j]);}}memset(dp,0,sizeof dp);dp[0][0]=0;dp[0][1]=mp[1][0];dp[0][2]=mp[2][0];for(i=1;i<n;i++){for(j=0;j<=2;j++){if(j==0){dp[i][j]=max(dp[i][j],dp[i-1][0]);dp[i][j]=max(dp[i][j],dp[i-1][1]);dp[i][j]=max(dp[i][j],dp[i-1][2]);}else if(j==1) {dp[i][j]=max(dp[i][j],dp[i-1][0]+mp[1][i]);dp[i][j]=max(dp[i][j],dp[i-1][2]+mp[1][i]);}//j==2else {dp[i][j]=max(dp[i][j],dp[i-1][0]+mp[2][i]);dp[i][j]=max(dp[i][j],dp[i-1][1]+mp[2][i]);}}}int ans;ans=max(dp[n-1][2],max(dp[n-1][1],dp[n-1][0]));printf("%d\n",ans);}return 0;}
6511Term Project
题意： 给出n对关系，问这个n对关系中不在 成环（自环也算）中的个数。
思路：有向图的强连通，先处理自环，在计算如果强连通分量中点的个数大于1，说明成环，答案就是（n-环中的点数）
AC代码：
#include <stdio.h>#include <vector>#include <string.h>using namespace std;const int MAXN = 100010;//点数const int MAXM = 100010;//边数struct Edge{int to,next;}edge[MAXM];int head[MAXN],tot;int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~sccint Index,top;int scc;//强连通分量的个数bool Instack[MAXN];int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc//num数组不一定需要，结合实际情况void addedge(int u,int v){edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;}void Tarjan(int u){int v;Low[u] = DFN[u] = ++Index;Stack[top++] = u;Instack[u] = true;for(int i = head[u];i != -1;i = edge[i].next){v = edge[i].to;if( !DFN[v] ){Tarjan(v);if( Low[u] > Low[v] )Low[u] = Low[v];}else if(Instack[v] && Low[u] > DFN[v])Low[u] = DFN[v];}if(Low[u] == DFN[u]){scc++;do{v = Stack[–top];Instack[v] = false;Belong[v] = scc;num[scc]++;}while( v != u);}}void solve(int N){memset(DFN,0,sizeof(DFN));memset(Instack,false,sizeof(Instack));memset(num,0,sizeof(num));Index = scc = top = 0;for(int i = 1;i <= N;i++)if(!DFN[i])Tarjan(i);}void init(){tot = 0;memset(head,-1,sizeof(head));}int main(){int t;int i,n,a;scanf("%d",&t);while(t–){init();int ans=0;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&a);addedge(i,a);if(i==a) ans++;}solve(n);//printf("%d\n",scc);for(i=1;i<=scc;i++){if(num[i]>1) ans+=num[i];}printf("%d\n",n-ans);}return 0;}/*273 1 3 7 3 4 681 2 3 4 5 6 7 8332 3 131 2 362 3 1 5 4 6*/
每一个成功者都有一个开始。勇于开始，才能找到成功的路。
