思路：模拟搞一下就出来了。
#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 1010 using namespace std; char s[101],ss[1001]; int top1,top2,num,now; int stack1[MAXN],stack2[MAXN]; map<int,string>ma; map<string,int>mm; int main(){ //freopen("lppin.txt","r",stdin); freopen("kami.in","r",stdin); freopen("kami.out","w",stdout); ma[++num]="http://www.acm.org/"; mm["http://www.acm.org/"]=num; now=1; while(cin>>s&&s[0]!='Q'){ if(s[0]=='V'){ cin>>ss; if(!mm[ss]){ ma[++num]=ss; mm[ss]=num; } top1++;stack1[top1]=now; now=mm[ss]; cout<<ss<<endl;top2=0; } else if(s[0]=='B'){ if(top1){ top2++;stack2[top2]=now; now=stack1[top1];top1--; cout<<ma[now]<<endl; } else cout<<"Ignored"<<endl; } else if(s[0]=='F'){ if(top2){ top1++;stack1[top1]=now; now=stack2[top2];top2--; cout<<ma[now]<<endl; } else cout<<"Ignored"<<endl; } } } /* VISIT http://acm.ashland.edu/ VISIT http://acm.baylor.edu/acmicpc/ BACK BACK BACK FORWARD VISIT http://www.ibm.com/ BACK BACK FORWARD FORWARD FORWARD QUIT */
思路：40分矩阵快速幂暴力
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define mod 1000000007 using namespace std; typedef long long LL; int T,n; LL t[2][2],ans[2][2],r[2][2]; void mul(LL a[2][2],LL b[2][2]){ memset(r,0,sizeof(r)); for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) r[i][j]+=a[i][k]*b[k][j],r[i][j]%=mod; for(int i=0;i<2;i++) for(int j=0;j<2;j++) a[i][j]=r[i][j]; } void mul1(LL a[2][2],LL b[2][2]){ memset(r,0,sizeof(r)); for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) r[i][j]+=a[i][k]*b[k][j]; for(int i=0;i<2;i++) for(int j=0;j<2;j++) a[i][j]=r[i][j]; } int main(){ //freopen("lppin.txt","r",stdin); freopen("na.in","r",stdin); freopen("na.out","w",stdout); scanf("%d",&T); while(T--){ scanf("%d",&n); memset(ans,0,sizeof(ans)); memset(t,0,sizeof(t)); if(n==0){ cout<<"0"<<endl; continue; } t[0][0]=t[0][1]=t[1][0]=1; ans[0][0]=ans[0][1]=1; long long p; if(n==1||n==2) p=1; else{ n-=2; while(n){ if(n&1) mul1(ans,t); mul1(t,t); n>>=1; } } p=ans[0][0]; memset(ans,0,sizeof(ans)); memset(t,0,sizeof(t)); t[0][0]=t[0][1]=t[1][0]=1; ans[0][0]=ans[0][1]=1; if(p==1||p==2){ cout<<"1"<<endl; continue; } else{ p-=2; while(p){ if(p&1) mul(ans,t); mul(t,t); p>>=1; } } cout<<ans[0][0]<<endl; } }
题解：（╮(╯▽╰)╭虽然有几个地方并没有看懂）
#include<cstdio> #include<cstdlib> #include<cstring> using namespace std; #ifdef unix #define LL "%lld" #else #define LL "%I64d" #endif const int maxn=200; const long long mo=1000000007; const long long mo2=mo*2+2; const long long mo3=mo2*3; char s[maxn]; struct matrix { long long z[3][3]; matrix() { memset(z,0,sizeof(z)); } matrix operator*(const matrix &a)const { matrix ans; for (int b=1;b<=2;b++) for (int c=1;c<=2;c++) for (int d=1;d<=2;d++) ans.z[b][c]=(ans.z[b][c]+z[b][d]*a.z[d][c]%mo)%mo; return ans; } matrix operator+(const matrix &a)const { matrix ans; for (int b=1;b<=2;b++) for (int c=1;c<=2;c++) for (int d=1;d<=2;d++) ans.z[b][c]=(ans.z[b][c]+z[b][d]*a.z[d][c]%mo2)%mo2; return ans; } }m1,m2; struct bign { int z[maxn],l; void init() { memset(z,0,sizeof(z)); scanf("%s",s+1); l=strlen(s+1); for (int a=1;a<=l;a++) z[a]=s[l-a+1]-'0'; } long long operator%(const long long &a)const { long long b=0; for (int c=l;c>=1;c--) b=(b*10+z[c])%a; return b; } }z; long long get(long long v) { if (v==0) return 0; m1.z[1][1]=0; m1.z[1][2]=1; m2.z[1][1]=0; m2.z[1][2]=m2.z[2][1]=m2.z[2][2]=1; while (v) { if (v&1) m1=m1*m2; m2=m2*m2; v>>=1; } return m1.z[1][1]; } long long get1(long long v) { if (v==0) return 0; m1.z[1][1]=0; m1.z[1][2]=1; m2.z[1][1]=0; m2.z[1][2]=m2.z[2][1]=m2.z[2][2]=1; while (v) { if (v&1) m1=m1+m2; m2=m2+m2; v>>=1; } return m1.z[1][1]; } int main() { freopen("na.in","r",stdin); freopen("na.out","w",stdout); int t; scanf("%d",&t); for (int a=1;a<=t;a++) { z.init(); long long v1=z % mo3; v1=get1(v1); printf(LL " ",get(v1)); } return 0; }
思路：
想写30分的暴力，还挂了一个点，30分暴力：
#include<map> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define MAXN 510 using namespace std; map<string,int>ma; int vis[MAXN]; int n,H,mmp,ansval=-1,anscost=0x7f7f7f7f,ans; struct nond{ int job,val,cost; }v[MAXN]; void dfs(int now,int sum,int val,int cost,int door,int back,int mid,int front,int head){ if(sum+n-now+1<11) return ; if(cost>H) return ; if(sum==11&&door!=0&&back>=3&&back<=5&&mid>=2&&mid<=5&&front>=1&&front<=3&&head!=0){ string s; for(int i=1;i<=n;i++) s+=char(vis[i]+'0'); s+=char(head+'0'); if(val>ansval){ ansval=val;anscost=cost; ans=1;ma[s]=1; } else if(val==ansval){ if(anscost==cost){ if(!ma[s]){ if(val==716&&ans==1){ int hh=1; } ma[s]=1;ans++; } } else if(cost<anscost){ anscost=cost; ans=1; } } return ; } if(now>n) return ; if(v[now].job==1){ if(door==0) vis[now]=1,dfs(now+1,sum+1,val+v[now].val,cost+v[now].cost,1,back,mid,front,head),vis[now]=0; if(door==0&&head==0) vis[now]=1,dfs(now+1,sum+1,val+v[now].val*2,cost+v[now].cost,1,back,mid,front,now),vis[now]=0; dfs(now+1,sum,val,cost,door,back,mid,front,head); } else if(v[now].job==2){ if(back<5) vis[now]=1,dfs(now+1,sum+1,val+v[now].val,cost+v[now].cost,door,back+1,mid,front,head),vis[now]=0; if(back<5&&head==0) vis[now]=1,dfs(now+1,sum+1,val+v[now].val*2,cost+v[now].cost,door,back+1,mid,front,now),vis[now]=0; dfs(now+1,sum,val,cost,door,back,mid,front,head); } else if(v[now].job==3){ if(mid<5) vis[now]=1,dfs(now+1,sum+1,val+v[now].val,cost+v[now].cost,door,back,mid+1,front,head),vis[now]=0; if(mid<5&&head==0) vis[now]=1,dfs(now+1,sum+1,val+v[now].val*2,cost+v[now].cost,door,back,mid+1,front,now),vis[now]=0; dfs(now+1,sum,val,cost,door,back,mid,front,head); } else if(v[now].job==4){ if(front<3) vis[now]=1,dfs(now+1,sum+1,val+v[now].val,cost+v[now].cost,door,back,mid,front+1,head),vis[now]=0; if(front<3&&head==0) vis[now]=1,dfs(now+1,sum+1,val+v[now].val*2,cost+v[now].cost,door,back,mid,front+1,now),vis[now]=0; dfs(now+1,sum,val,cost,door,back,mid,front,head); } } int cmp(nond a,nond b){ if(a.val==b.val) return a.cost<b.cost; return a.val>b.val; } int main(){ //freopen("lppin.txt","r",stdin); freopen("wosa1.in","r",stdin); freopen("wosa.out","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ char c[100];cin>>c; int y,z;cin>>y>>z;mmp+=z; if(c[0]=='G') v[i].job=1; else if(c[0]=='D') v[i].job=2; else if(c[0]=='M') v[i].job=3; else if(c[0]=='F') v[i].job=4; v[i].val=y;v[i].cost=z; } cin>>H; if(n<=20){ dfs(1,0,0,0,0,0,0,0,0); cout<<ansval<<" "<<anscost<<" "<<ans; } else if(H>=mmp){ sort(v+1,v+1+n,cmp); for(int a=3;a<=5;a++) for(int b=2;b<=5;b++){ int c=11-1-a-b; int door=0,back=0,mid=0,front=0,val=0,cost=0; if(c<1) continue; for(int i=1;i<=n;i++){ if(v[i].job==1){ if(door==0) door=1,val+=v[i].val,cost+=v[i].cost; } else if(v[i].job==2){ if(back<a) back++,val+=v[i].val,cost+=v[i].cost; } else if(v[i].job==3){ if(mid<b) mid++,val+=v[i].val,cost+=v[i].cost; } else if(v[i].job==4){ if(front<c) front++,val+=v[i].val,cost+=v[i].cost; } } val+=v[1].val; if(val>ansval){ ansval=val; ans=1; } if(val==ansval){ if(cost==anscost) ans++; else if(cost<anscost){ anscost=cost;ans=1; } } } if(ans>100) ans=1000000000; cout<<ansval<<" "<<anscost<<" "<<ans; } else { dfs(1,0,0,0,0,0,0,0,0); cout<<ansval<<" "<<anscost<<" "<<ans; } } /* 15 Defender 23 45 Midfielder 178 85 Goalkeeper 57 50 Goalkeeper 57 50 Defender 0 45 Forward 6 60 Midfielder 20 50 Goalkeeper 0 50 Midfielder 64 65 Midfielder 109 70 Forward 211 100 Defender 0 40 Defender 29 45 Midfielder 57 60 Defender 52 45 600 */
题解：见代码
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define mod 1000000000 using namespace std; struct nond{ int job,val,cost; }v[501]; int n,H,ansval=-1,anscost,ans; int L[5],R[5]; int f[2][6][6][4][1001][3]; /*f[a][b][c][d][e][f]表示到花费了e元为至 a表示选的守门员，b表示选了几个后卫，c表示选了几个中锋， e表示选了几个前锋 f如果等于0表示价值，如果是1表示方案数，如果是2表示队长价值*/ int cmp(nond a,nond b){ if(a.val==b.val) return a.cost>b.cost; return a.val<b.val; } void up(int a,int b,int c,int d,int e,int val,int num,int mx){ if(f[a][b][c][d][e][0]<val){ f[a][b][c][d][e][0]=val; f[a][b][c][d][e][1]=num; f[a][b][c][d][e][2]=mx; } else if(f[a][b][c][d][e][0]==val&&f[a][b][c][d][e][2]<mx){ f[a][b][c][d][e][1]=num; f[a][b][c][d][e][2]=mx; } else if(f[a][b][c][d][e][0]==val&&f[a][b][c][d][e][2]==mx){ f[a][b][c][d][e][1]+=num; if(f[a][b][c][d][e][1]>mod) f[a][b][c][d][e][1]=mod; } } /*背包*/ void insert(int x){ for(int a=R[1]-(v[x].job==1);a>=0;a--) for(int b=R[2]-(v[x].job==2);b>=0;b--) for(int c=R[3]-(v[x].job==3);c>=0;c--) for(int d=R[4]-(v[x].job==4);d>=0;d--) for(int e=H-v[x].cost;e>=0;e--) if(f[a][b][c][d][e][1]){ int val=v[x].val+f[a][b][c][d][e][0]; up(a+(v[x].job==1),b+(v[x].job==2),c+(v[x].job==3),d+(v[x].job==4),e+v[x].cost,val,f[a][b][c][d][e][1],v[x].val); } } int main(){ freopen("wosa4.in","r",stdin); //freopen("wosa.out","w",stdout); //freopen("1wosaout.txt","w",stdout); scanf("%d",&n); for(int i=1;i<=n;i++){ char s[100];cin>>s; int x,y;cin>>x>>y; if(s[0]=='G') v[i].job=1; if(s[0]=='D') v[i].job=2; if(s[0]=='M') v[i].job=3; if(s[0]=='F') v[i].job=4; v[i].val=x;v[i].cost=y; } scanf("%d",&H); L[1]=1;R[1]=1;L[2]=3;R[2]=5; L[3]=2;R[3]=5;L[4]=1;R[4]=3; //分别表示4种人所选的人数的限制范围。 sort(v+1,v+1+n,cmp);//预处理排序（不明白啊啊啊啊，为什么这么排） f[0][0][0][0][0][1]=1; //没选的方案数。 f[0][0][0][0][0][2]=-1; //没选的队长价值（没有队长，所以设成-1） for(int i=1;i<=n;i++) insert(i); for(int a=L[1];a<=R[1];a++) for(int b=L[2];b<=R[2];b++) for(int c=L[3];c<=R[3];c++) for(int d=L[4];d<=R[4];d++) if(a+b+c+d==11) for(int e=0;e<=H;e++){ if(f[a][b][c][d][e][1]==0) continue; int val=f[a][b][c][d][e][0]+f[a][b][c][d][e][2]; if(val>ansval){ ansval=val;anscost=e; ans=f[a][b][c][d][e][1]; } else if(val==ansval&&e<anscost){ anscost=e; ans=f[a][b][c][d][e][1]; } else if(val==ansval&&e==anscost){ ans+=f[a][b][c][d][e][1]; if(ans>mod) ans=mod; } } cout<<ansval<<" "<<anscost<<" "<<ans; } /* 15 Defender 23 45 Midfielder 178 85 Goalkeeper 57 50 Goalkeeper 57 50 Defender 0 45 Forward 6 60 Midfielder 20 50 Goalkeeper 0 50 Midfielder 64 65 Midfielder 109 70 Forward 211 100 Defender 0 40 Defender 29 45 Midfielder 57 60 Defender 52 45 600 */