希望
【题目描述】
网页浏览器者有后退与前进按钮，一种实现这两个功能的方式是用两个栈，
“前进栈”、“后退栈”。
这里你需要实现以下几个功能：
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(){
cin>>c;
if(c=="QUIT")break;
if(c=="VISIT"){
cin>>web;top2+=;top1=;
s2[top2]=now;now=web;
}
if(c=="BACK"){
if(top2==){
cout<<"Ignored"<<endl;
continue;
}
else{
top1+=;s1[top1]=now;
now=s2[top2];top2-=;
}
}
if(c=="FORWARD"){
if(top1==){
cout<<"Ignored"<<endl;
continue;
}
else{
top2+=;s2[top2]=now;
now=s1[top1];top1-=;
}
}
cout<<now<<endl;
}
return ;
}
残
【问题描述】
令?(?)为斐波那契数列第?项，其中?(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[][],a[][];
void mul(ll a[][],ll b[][]){
ll c[][];memset(c,,sizeof(c));
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mod)%mod;
for(int i=;i<;i++)
for(int j=;j<;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=,y=,z=;
for(int i=;i<=n;i++){
z=x+y;y=x;x=z;
}
if(z==){cout<<<<endl;continue;}
if(z==||z==){cout<<<<endl;continue;}
n=z-;
f[][]=;f[][]=;f[][]=;f[][]=;
a[][]=;a[][]=;a[][]=;a[][]=;
while(n){
if(n&)mul(f,a);
mul(a,a);n>>=;
}
cout<<f[][]<<endl;
}
return ;
}
正解%%%
/*
mod了几个神奇的数
具体为啥 还在思考中23333
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const ll mod=;
ll T,n,f[][],a[][],len;
char s[];
ll Mod(){
ll r=,mo=(mod*+)*;
for(int i=;i<len;i++)
r=(r*+s[i]-'')%mo;
return r;
}
void mul(ll a[][],ll b[][],ll mo){
ll c[][];memset(c,,sizeof(c));
for(int i=;i<;i++)
for(int j=;j<;j++)
for(int k=;k<;k++)
c[i][j]=(c[i][j]+a[i][k]*b[k][j]%mo)%mo;
for(int i=;i<;i++)
for(int j=;j<;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,,sizeof(s));
cin>>s;len=strlen(s);
n=Mod();
if(n==){cout<<<<endl;continue;}
if(n==||n==){cout<<<<endl;continue;}
n=n-;
f[][]=;f[][]=;f[][]=;f[][]=;
a[][]=;a[][]=;a[][]=;a[][]=;
while(n){
if(n&)mul(f,a,mod*+);
mul(a,a,mod*+);n>>=;
}
n=f[][];n-=;
f[][]=;f[][]=;f[][]=;f[][]=;
a[][]=;a[][]=;a[][]=;a[][]=;
while(n){
if(n&)mul(f,a,mod);
mul(a,a,mod);n>>=;
}
cout<<f[][]<<endl;
}
return ;
}
党
【问题描述】
你现在希望组建一支足球队，一支足球队一般来说由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>||c2>||c3>||c4>)return;
if(now==n+){
if(c1+c2+c3+c4!=)return;
if(c1<||c2<||c3<||c4<)return;
if(V+mxx>mx||(V+mxx==&&mx==)){
mx=V+mxx;cost=C;sum=;
}
else if(V+mxx==mx)sum++;
return;
}
if(r[now]==)Dfs(now+,c1+,c2,c3,c4,V+v[now],C+c[now],max(mxx,v[now]));
if(r[now]==)Dfs(now+,c1,c2+,c3,c4,V+v[now],C+c[now],max(mxx,v[now]));
if(r[now]==)Dfs(now+,c1,c2,c3+,c4,V+v[now],C+c[now],max(mxx,v[now]));
if(r[now]==)Dfs(now+,c1,c2,c3,c4+,V+v[now],C+c[now],max(mxx,v[now]));
Dfs(now+,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=;i<=n;i++){
cin>>s>>x>>y;
v[i]=x;c[i]=y;
if(s=="Goalkeeper")r[i]=;
if(s=="Defender")r[i]=;
if(s=="Midfielder")r[i]=;
if(s=="Forward")r[i]=;
}
cin>>lim;
Dfs(,,,,,,,);
cout<<mx<<" "<<cost<<" "<<sum<<endl;
return ;
}
正解dp
/*
考试的时候觉得类似背包的搞搞
然而没写出来......
对于方案数有点怂 没啥好办法
最后直接暴力 还被卡掉一个点QAQ
f[a][b][c][d][e]表示4中人非别选了abcd个人
因为还有个很蛋疼的队长 还有方案数
所以在+上几个值 多一维012 分别表示最大价值 方案数 队长价值
节约空间逆序循环 把到那一个人的第一位扔了
然后枚举到那个人 然后五维费用的背包跑跑
注意更新的时候比较麻烦 具体看代码
然后统计一下最大val 以及对应的cost anss
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 1010
#define mod 1000000000
using namespace std;
int n,f[][][][][maxn][],L[],R[],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][]<r){
f[a][b][c][d][e][]=r;
f[a][b][c][d][e][]=;
f[a][b][c][d][e][]=mx;
}
if(f[a][b][c][d][e][]==r&&f[a][b][c][d][e][]<mx){
f[a][b][c][d][e][]=;
f[a][b][c][d][e][]=mx;
}
if(f[a][b][c][d][e][]==r&&f[a][b][c][d][e][]==mx){
f[a][b][c][d][e][]+=s;
if(f[a][b][c][d][e][]>mod)f[a][b][c][d][e][]=mod;
}
}
void Insert(int x){
for(int a=R[]-(p[x].r==);a>=;a--)
for(int b=R[]-(p[x].r==);b>=;b--)
for(int c=R[]-(p[x].r==);c>=;c--)
for(int d=R[]-(p[x].r==);d>=;d--)if(a+b+c+d<)
for(int e=lim-p[x].c;e>=;e--)
if(f[a][b][c][d][e][]){
int val=p[x].v+f[a][b][c][d][e][];
Up(a+(p[x].r==),b+(p[x].r==),c+(p[x].r==),d+(p[x].r==),e+p[x].c,val,f[a][b][c][d][e][],p[x].v);
}
}
int main()
{
freopen("wosa.in","r",stdin);
freopen("wosa.out","w",stdout);
cin>>n;
int V,C;
L[]=;L[]=;L[]=;L[]=;
R[]=;R[]=;R[]=;R[]=;
for(int i=;i<=n;i++){
cin>>s>>V>>C;
if(s=="Goalkeeper")p[i].r=;
if(s=="Defender")p[i].r=;
if(s=="Midfielder")p[i].r=;
if(s=="Forward")p[i].r=;
p[i].v=V;p[i].c=C;
}
cin>>lim;
sort(p+,p++n,cmp);
f[][][][][][]=;
f[][][][][][]=-;
for(int i=;i<=n;i++)Insert(i);
for(int a=L[];a<=R[];a++)
for(int b=L[];b<=R[];b++)
for(int c=L[];c<=R[];c++)
for(int d=L[];d<=R[];d++)
if(a+b+c+d==)
for(int e=;e<=lim;e++){
if(f[a][b][c][d][e][]==)continue;
int val=f[a][b][c][d][e][]+f[a][b][c][d][e][];
if(val>ansv){
ansv=val;ansc=e;
anss=;
}
if(val==ansv&&e<ansc){
ansc=e;anss=;
}
if(val==ansv&&e==ansc){
anss+=f[a][b][c][d][e][];
if(anss>mod)anss=mod;
}
}
cout<<ansv<<" "<<ansc<<" "<<anss<<endl;
return ;
}