2A直接写,最多用个字符串hash,
#include<iostream> #include<string> #include<fstream> using namespace std; struct PI { int point; int lastRound; int maxpoint; }; PI record[99991]; unsigned int ELFHash(char* str) { unsigned int hash=0; unsigned int x=0; while(*str) { hash=(hash<<4)+(*str++); if((x=hash&0xf0000000)!=0) { hash^=(x>>24); hash&=~x; } } return (hash&0x7fffffff); } int main() { ifstream fin("2A.txt"); memset(record,0,sizeof(record)); string str[1002]; int pt[1002]; int n; cin>>n; for(int i=1;i<=n;i++) { int po; cin>>str[i]>>po; pt[i]=po; int hashIndex=ELFHash(const_cast<char*>(str[i].c_str()))%99991; record[hashIndex].point+=po; if(record[hashIndex].point>record[hashIndex].maxpoint) { record[hashIndex].maxpoint=record[hashIndex].point; }record[hashIndex].lastRound=i; } int maxpoint=0,leastround=1200; for(int i=0;i<99991;i++) { if(record[i].point>maxpoint) maxpoint=record[i].point; } for(int i=0;i<99991;i++) { if(record[i].point==maxpoint) { string ss=str[record[i].lastRound]; int sum=0; int j; for( j=1;j<=n;j++) { if(str[j]==ss) { sum+=pt[j]; if(sum>=maxpoint) { break; } } } if(j<leastround) leastround=j; } } cout<<str[leastround]<<endl; return 0; }
2B真是晕，感觉不是很难，dp部分比较简单，判断最后0的个数也就是USACO里提到过的，找2和5个数就完了，可是写出来vs报错stack overflow，但是我看我申请的空间还没以前做题用的大，贴个别人过了先.晕，这几天好忙，头都爆了
#include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <iostream> #define maxn 1010 #define inf 0xfffffff using namespace std; int tmp[maxn][maxn],five[maxn][maxn],two[maxn][maxn]; int dp2[maxn][maxn],dp5[maxn][maxn]; char dir2[maxn][maxn],dir5[maxn][maxn]; int n; int get(int p,int n) { if(n==0) return 1; int cnt=0; while(n%p==0) { n/=p; cnt++; } return cnt; } int zero_x,zero_y; bool flag; void print(char dir[][maxn],int x,int y) { //cout<<x<<":"<<y<<endl; if(x==1&&y==1) return ; if(dir[x][y]=='D') print(dir,x-1,y); else print(dir,x,y-1); printf("%c",dir[x][y]); } int main() { scanf("%d",&n); flag=true; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { scanf("%d",&tmp[i][j]); if(tmp[i][j]) { two[i][j]=get(2,tmp[i][j]); five[i][j]=get(5,tmp[i][j]); } else { flag=false; zero_x=i; zero_y=j; } } memset(dp2,0,sizeof(dp2)); memset(dp5,0,sizeof(dp5)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(tmp[i][j]==0) { dp2[i][j]=inf; } else if(i==1&&j==1) { dir2[i][j]=' '; dp2[i][j]=two[i][j]; } else if(i==1) { dp2[i][j]=dp2[i][j-1]+two[i][j]; dir2[i][j]='R'; } else if(j==1) { dp2[i][j]=dp2[i-1][j]+two[i][j]; dir2[i][j]='D'; } else { if(dp2[i-1][j]<dp2[i][j-1]) dir2[i][j]='D'; else dir2[i][j]='R'; dp2[i][j]=min(dp2[i-1][j],dp2[i][j-1])+two[i][j]; } } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(tmp[i][j]==0) { dp5[i][j]=inf; } else if(i==1&&j==1) { dir5[i][j]=' '; dp5[i][j]=five[i][j]; } else if(j==1) { dir5[i][j]='D'; dp5[i][j]=dp5[i-1][j]+five[i][j]; } else if(i==1) { dir5[i][j]='R'; dp5[i][j]=dp5[i][j-1]+five[i][j]; } else { if(dp5[i-1][j]<dp5[i][j-1]) dir5[i][j]='D'; else dir5[i][j]='R'; dp5[i][j]=min(dp5[i-1][j],dp5[i][j-1])+five[i][j]; } } if(!flag) { if(dp2[n][n]==0) { printf("0 "); print(dir2,n,n); } else if(dp5[n][n]==0) { printf("0 "); print(dir5,n,n); } else { printf("1 "); for(int i=2;i<=zero_x;i++) printf("D"); for(int j=2;j<=zero_y;j++) printf("R"); for(int i=zero_x+1;i<=n;i++) printf("D"); for(int j=zero_y+1;j<=n;j++) printf("R"); } } else { if(dp2[n][n]>dp5[n][n]) { printf("%d ",dp5[n][n]); print(dir5,n,n); } else { printf("%d ",dp2[n][n]); print(dir2,n,n); } } printf(" "); return 0; }