希望
【题目描述】
网页浏览器者有后退与前进按钮，一种实现这两个功能的方式是用两个栈，
“前进栈”、“后退栈”。
这里你需要实现以下几个功能：
BACK: 如果“后退栈”为空则忽略此命令。 否则将当前两面压入“前进栈”，
从“后退栈”中取出栈顶页面，并设置为当前页面。
FORWARD: 如果“前进栈”为空则忽略此命令。否则将当前两面压入“后
退栈”，从“前进栈”中取出栈顶页面，并设置为当前页面。
VISIT: 将当前页面压入“后退栈”、 并将当前页面置为指定页面， 并将“前
进栈”置空。
QUIT: 退出。
假设此浏览器初始页面为 http://www.acm.org/
【输入格式】
输入为一系列命令：BACK, FORWARD, VISIT 和 QUIT，页面网址为不含空
格的字符串
假设任一时刻任意时刻两个栈中的元素都不会超过 100。
最后一个命令为 QUIT。
【输出格式】
输对于除 QUIT 外所有命令，输出当前页面（网址）
如果该命令被忽略则输出“Ignored”。
【样例输入】
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
【样例输出】
http://acm.ashland.edu/
http://acm.baylor.edu/acmicpc/
http://acm.ashland.edu/
http://www.acm.org/
Ignored
http://acm.ashland.edu/
http://www.ibm.com/
http://acm.ashland.edu/
http://www.acm.org/
http://acm.ashland.edu/
http://www.ibm.com/
Ignored
【样例解释】
无。
【数据范围与规定】
对于100%的数据，操作数量不超过1000，每行字符串长度不超过500。
/*开始手残多写个++*/ #include<iostream> #include<cstdio> #include<cstring> #define maxn 210 using namespace std; int top1,top2; string s1[maxn],s2[maxn],c,now,web; int main() { freopen("kami.in","r",stdin); freopen("kami.out","w",stdout); now="http://www.acm.org/"; while(1){ cin>>c; if(c=="QUIT")break; if(c=="VISIT"){ cin>>web;top2+=1;top1=0; s2[top2]=now;now=web; } if(c=="BACK"){ if(top2==0){ cout<<"Ignored"<<endl; continue; } else{ top1+=1;s1[top1]=now; now=s2[top2];top2-=1; } } if(c=="FORWARD"){ if(top1==0){ cout<<"Ignored"<<endl; continue; } else{ top2+=1;s2[top2]=now; now=s1[top1];top1-=1; } } cout<<now<<endl; } return 0; }
残
【问题描述】
令?(?)为斐波那契数列第?项，其中?(0) = ?(1) = 1,?(?) = ?(? −1) +
?(? −2)。
所以要干啥呢？
求?(?(?))。
【输入格式】
第一行一个整数?代表数据组数。
接下来?行每行一个整数?。
【输出格式】
?行每行一个整数代表答案对10 9 + 7取模的值。
【样例输入】
4
0
1
2
6
【样例输出】
0
1
1
21
【样例解释】
无。
【数据规模与约定】
215 490。
70%的数据，1 ≤ ? ≤ 10 5 。
对于100%的数据，1 ≤ ? ≤ 10 3 ,1 ≤ ? ≤ 10 100 。
暴力矩阵乘法40
#include<iostream> #include<cstdio> #include<cstring> #define mod 1000000007 #define ll long long using namespace std; ll T,n,f[2][2],a[2][2]; void mul(ll a[2][2],ll b[2][2]){ ll c[2][2];memset(c,0,sizeof(c)); for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod; for(int i=0;i<2;i++) for(int j=0;j<2;j++) a[i][j]=c[i][j]; } int main() { freopen("na.in","r",stdin); freopen("na.out","w",stdout); cin>>T; while(T--){ cin>>n; ll x=0,y=1,z=0; for(int i=1;i<=n;i++){ z=x+y;y=x;x=z; } if(z==0){cout<<0<<endl;continue;} if(z==1||z==2){cout<<1<<endl;continue;} n=z-2; f[0][0]=1;f[0][1]=1;f[1][0]=0;f[1][1]=0; a[0][0]=1;a[0][1]=1;a[1][0]=1;a[1][1]=0; while(n){ if(n&1)mul(f,a); mul(a,a);n>>=1; } cout<<f[0][0]<<endl; } return 0; }
正解%%%
/* mod了几个神奇的数 具体为啥 还在思考中23333 */ #include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; const ll mod=1000000007; ll T,n,f[2][2],a[2][2],len; char s[110]; ll Mod(){ ll r=0,mo=(mod*2+2)*3; for(int i=0;i<len;i++) r=(r*10+s[i]-‘0‘)%mo; return r; } void mul(ll a[2][2],ll b[2][2],ll mo){ ll c[2][2];memset(c,0,sizeof(c)); for(int i=0;i<2;i++) for(int j=0;j<2;j++) for(int k=0;k<2;k++) c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mo)%mo; for(int i=0;i<2;i++) for(int j=0;j<2;j++) a[i][j]=c[i][j]; } int main() { freopen("na.in","r",stdin); freopen("na.out","w",stdout); cin>>T; while(T--){ memset(s,0,sizeof(s)); cin>>s;len=strlen(s); n=Mod(); if(n==0){cout<<0<<endl;continue;} if(n==1||n==2){cout<<1<<endl;continue;} n=n-2; f[0][0]=1;f[0][1]=1;f[1][0]=0;f[1][1]=0; a[0][0]=1;a[0][1]=1;a[1][0]=1;a[1][1]=0; while(n){ if(n&1)mul(f,a,mod*2+2); mul(a,a,mod*2+2);n>>=1; } n=f[0][0];n-=2; f[0][0]=1;f[0][1]=1;f[1][0]=0;f[1][1]=0; a[0][0]=1;a[0][1]=1;a[1][0]=1;a[1][1]=0; while(n){ if(n&1)mul(f,a,mod); mul(a,a,mod);n>>=1; } cout<<f[0][0]<<endl; } return 0; }
党
【问题描述】
你现在希望组建一支足球队，一支足球队一般来说由11人组成。这11人有四
种不同的职业：守门员、后卫、中锋、前锋组成。你在组队的时候必须满足以下
规则：
1 足球队恰好由11人组成。
2 11人中恰好有一名守门员，3-5 名后卫，2-5 名中锋，1-3 名前锋。
3 你需要从这11人中选出一名队长。
4、 你这个足球队的价值是11人的价值之和再加上队长的价值， 也就是说
队长的价值会被计算两次。
5、 你这个足球队的花费是11人的花费之和， 你的花费之和不能超过给定
的上限。
现在告诉你球员的总数，每个球员的职业、价值、花费，以及花费的上限，
你希望在满足要求的情况下，达到以下目标：
1 最大化队伍的价值。
2 在最大化队伍的价值的情况下，最小化队伍的花费。
3、 在满足以上两个要求的情况下，有多少种选择球员的方案。如果有两
种方案它们的区别仅仅是队长不一样， 那么这两种方案应该被认为是
一种方案。
你的任务是输出这三个值：价值、花费、方案数。
【输入格式】
第一行一个正整数?，代表可选的球员个数。
接下来?行，每行描述一个球员的信息。每行开始是一个字符串，可能的字
符串有 Goalkeeper、Defender、Midfielder、Forward，分别代表该球员的职业是守
门员、后卫、中锋、前锋。接下来两个数?,?，分别代表该球员的价值和花费。
最后一行一个整数，代表花费的上限。
数据保证一定存在一种解。
【输出格式】
一行三个整数，分表代表最大价值、最小花费和方案数。如果方案数超过了
10 9 ，则直接输出10 9 。
【样例输入】
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
【样例输出】
716 600 2
【样例解释】
选择所有的五名后卫，选择价值为178,20,54,109的中锋和价值为6的前锋，
两名守门员任意选择。选择价值为178的中锋作为队长。
【数据规模与约定】
3? ≤ 20。
60%的数据，费用上限足够大。
对于100%的数据， 1 ≤ ? ≤ 500， 所有球员的价值和花费以及花费上限均在
暴力30
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1010 #define ll long long using namespace std; ll n,c[maxn],r[maxn],v[maxn],mx,cost,sum,lim,f[maxn]; string s; void Dfs(ll now,ll c1,ll c2,ll c3,ll c4,ll V,ll C,ll mxx){ if(C>lim)return; if(c1>1||c2>5||c3>5||c4>3)return; if(now==n+1){ if(c1+c2+c3+c4!=11)return; if(c1<1||c2<3||c3<2||c4<1)return; if(V+mxx>mx||(V+mxx==0&&mx==0)){ mx=V+mxx;cost=C;sum=1; } else if(V+mxx==mx)sum++; return; } if(r[now]==1)Dfs(now+1,c1+1,c2,c3,c4,V+v[now],C+c[now],max(mxx,v[now])); if(r[now]==2)Dfs(now+1,c1,c2+1,c3,c4,V+v[now],C+c[now],max(mxx,v[now])); if(r[now]==3)Dfs(now+1,c1,c2,c3+1,c4,V+v[now],C+c[now],max(mxx,v[now])); if(r[now]==4)Dfs(now+1,c1,c2,c3,c4+1,V+v[now],C+c[now],max(mxx,v[now])); Dfs(now+1,c1,c2,c3,c4,V,C,mxx); } int main() { freopen("wosa.in","r",stdin); freopen("wosa.out","w",stdout); ll x,y; cin>>n; for(ll i=1;i<=n;i++){ cin>>s>>x>>y; v[i]=x;c[i]=y; if(s=="Goalkeeper")r[i]=1; if(s=="Defender")r[i]=2; if(s=="Midfielder")r[i]=3; if(s=="Forward")r[i]=4; } cin>>lim; Dfs(1,0,0,0,0,0,0,0); cout<<mx<<" "<<cost<<" "<<sum<<endl; return 0; }
正解dp
/* 考试的时候觉得类似背包的搞搞 然而没写出来...... 对于方案数有点怂 没啥好办法 最后直接暴力 还被卡掉一个点QAQ f[a][b][c][d][e]表示4中人非别选了abcd个人 因为还有个很蛋疼的队长 还有方案数 所以在+上几个值 多一维012 分别表示最大价值 方案数 队长价值 剩下的明天再写~~ */ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define maxn 1010 #define mod 1000000000 using namespace std; int n,f[2][6][6][4][maxn][3],L[5],R[5],lim,ansv,ansc=0x7fffffff,anss; string s; struct node{ int v,c,r; }p[maxn]; int cmp(const node &x,const node &y){ if(x.v==y.v)return x.c>y.c; return x.v<y.v; } void Up(int a,int b,int c,int d,int e,int r,int s,int mx){ if(f[a][b][c][d][e][0]<r){ f[a][b][c][d][e][0]=r; f[a][b][c][d][e][1]=0; f[a][b][c][d][e][2]=mx; } if(f[a][b][c][d][e][0]==r&&f[a][b][c][d][e][2]<mx){ f[a][b][c][d][e][1]=0; f[a][b][c][d][e][2]=mx; } if(f[a][b][c][d][e][0]==r&&f[a][b][c][d][e][2]==mx){ f[a][b][c][d][e][1]+=s; 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]-(p[x].r==1);a>=0;a--) for(int b=R[2]-(p[x].r==2);b>=0;b--) for(int c=R[3]-(p[x].r==3);c>=0;c--) for(int d=R[4]-(p[x].r==4);d>=0;d--)if(a+b+c+d<11) for(int e=lim-p[x].c;e>=0;e--) if(f[a][b][c][d][e][1]){ int val=p[x].v+f[a][b][c][d][e][0]; Up(a+(p[x].r==1),b+(p[x].r==2),c+(p[x].r==3),d+(p[x].r==4),e+p[x].c,val,f[a][b][c][d][e][1],p[x].v); } } int main() { freopen("wosa.in","r",stdin); freopen("wosa.out","w",stdout); cin>>n; int V,C; L[1]=1;L[2]=3;L[3]=2;L[4]=1; R[1]=1;R[2]=5;R[3]=5;R[4]=3; for(int i=1;i<=n;i++){ cin>>s>>V>>C; if(s=="Goalkeeper")p[i].r=1; if(s=="Defender")p[i].r=2; if(s=="Midfielder")p[i].r=3; if(s=="Forward")p[i].r=4; p[i].v=V;p[i].c=C; } cin>>lim; sort(p+1,p+1+n,cmp); f[0][0][0][0][0][1]=1; f[0][0][0][0][0][2]=-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<=lim;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>ansv){ ansv=val;ansc=e; anss=0; } if(val==ansv&&e<ansc){ ansc=e;anss=0; } if(val==ansv&&e==ansc){ anss+=f[a][b][c][d][e][1]; if(anss>mod)anss=mod; } } cout<<ansv<<" "<<ansc<<" "<<anss<<endl; return 0; }
原文：http://www.cnblogs.com/yanlifneg/p/5929702.html
