题目来自BAPC2017 Preliminaries
A题:Abandoned Animal
最后输入的m个字符串是sister按顺序买的物品(保证买的物品不重复),首先输入的k行数据(i,s)代表第i个商店所卖的物品s,保证每个商店卖的物品不同。问sister买的物品所在的商店的编号是不是一个非递减的序列。如果不是输出"impossible",如果是并且这个商店的编号序列是唯一的,输出"unique",否则输出"ambiguous".
我们可以首先对商店的信息按照商店的编号从小到大排序,用a[]数组存储每个商店第一件物品的下标,用b[]数组存储每个商店最后一件物品的下标
第一次首先按照sister的顺序对她买的物品去寻找商店的编号,记下当前商店第一件物品的下标,下次寻找时,从该下标开始往后寻找。如果当前寻找操作找不到对应的商店,则输出“impossible”。否则再倒着按着sister的顺序倒着去寻找商店的编号。如果两次寻找后的序列一样,输出“unique”,否则输出“ambiguous".


1 #include<bits/stdc++.h> 2 using namespace std; 3 struct node 4 { 5 int pos; 6 string s; 7 }mp[100005]; 8 bool cmp(node a,node b) 9 { 10 return a.pos<b.pos; 11 } 12 int n,k,m; 13 string t[100005]; 14 int a[100005],b[100005],Left[100005],Right[100005]; 15 int main() 16 { 17 // freopen("in.txt","r",stdin); 18 ios::sync_with_stdio(false); 19 cin.tie(0); 20 cin>>n>>k; 21 for(int i=0;i<k;i++) 22 { 23 cin>>mp[i].pos>>mp[i].s; 24 } 25 sort(mp,mp+k,cmp); 26 for(int i=k-1;i>=0;i--) 27 a[mp[i].pos]=i; 28 for(int i=0;i<k;i++) 29 b[mp[i].pos]=i; 30 cin>>m; 31 int now=a[0],flag,ff=0; 32 for(int i=0;i<m;i++) 33 { 34 cin>>t[i]; 35 if(ff) continue; 36 flag=0; 37 for(int j=now;j<k;j++) 38 { 39 if(t[i]==mp[j].s) 40 { 41 Left[i]=mp[j].pos; 42 now=a[mp[j].pos]; 43 flag=1; 44 break; 45 } 46 } 47 if(!flag) ff=1; 48 } 49 if(ff) 50 { 51 cout<<"impossible"<<endl; 52 return 0; 53 } 54 now=k-1; 55 for(int i=m-1;i>=0;i--) 56 { 57 for(int j=now;j>=0;j--) 58 { 59 if(t[i]==mp[j].s) 60 { 61 Right[i]=mp[j].pos; 62 now=b[mp[j].pos]; 63 break; 64 } 65 } 66 if(Right[i]!=Left[i]) 67 { 68 cout<<"ambiguous"<<endl; 69 return 0; 70 } 71 } 72 cout<<"unique"<<endl; 73 return 0; 74 }
B题:Booming Business


1 #include <bits/stdc++.h> 2 using namespace std; 3 const int mod=1e9+7; 4 typedef long long ll; 5 ll f[400][400]; 6 int main() 7 { 8 int h,w; 9 scanf("%d%d",&h,&w); 10 f[1][1]=1; 11 for(int i=2;i<=h;i++) 12 { 13 f[1][i]=1; 14 for(int j=2;j<=w;j++) 15 { 16 for(int k=1;k<=j-1;k++) 17 f[j][i]=(f[j][i]%mod+f[k][i-1]%mod*f[j-k][i]%mod)%mod; 18 } 19 } 20 ll ans=(f[w][h]-f[w][h-1]+mod)%mod; 21 printf("%lld\n",ans); 22 return 0; 23 }
C题:Crowd Control
待更新。。。
D题:Disastrous Doubling
不需要大数,可以直接处理。当细菌的数量>=输入数据的最大值时才开始取模


1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 const int N=1e5+10; 6 const int mod=1e9+7; 7 int n; 8 bool flag; 9 int main() 10 { 11 scanf("%d",&n); 12 ll ans=1,tmp=1ll<<61,x; 13 for (int i=1;i<=n;i++) 14 { 15 scanf("%lld",&x); 16 17 if (!flag) 18 { 19 ans=ans*2; 20 if (ans>=tmp) flag=1; 21 ans=ans-x; 22 if (ans<0) 23 { 24 printf("error\n"); 25 return 0; 26 } 27 } 28 else ans=(ans*2%mod-x%mod+mod)%mod; 29 } 30 printf("%lld\n",ans%mod); 31 return 0; 32 }
E题:Envious Exponents
输入n和k,求k个2的不同次幂的和,满足它是最小的大于n的数。
把n转化成二进制,然后就在二进制中找k个1,使其满足条件。


1 #include <bits/stdc++.h> 2 3 using namespace std; 4 typedef long long ll; 5 int a[1000]; 6 ll n; 7 ll k; 8 int main() 9 { 10 scanf("%lld %lld",&n,&k); 11 ll nn=n; 12 int cnt=0; 13 while(nn) 14 { 15 a[cnt++]=nn%2; 16 nn/=2; 17 } 18 int cnt1=0,flag=0,pos; 19 for(int i=cnt-1;i>=0;i--) 20 { 21 if(a[i]==1) 22 { 23 cnt1++; 24 pos=i; 25 } 26 if(cnt1==k) 27 { 28 flag=1; 29 a[i]=0; 30 break; 31 } 32 } 33 if(!flag) //1 is not enough 34 { 35 for(int i=0;i<cnt;i++) //从最低位到最高位把0变成1,如果1的个数还不满足k个,就增加位数添加1 36 { 37 if(a[i]==0){ 38 a[i]=1; 39 cnt1++; 40 } 41 if(cnt1==k) 42 break; 43 } 44 while(cnt1<k) 45 { 46 a[cnt++]=1; 47 cnt1++; 48 } 49 } 50 else //1 is enough 51 { 52 for(int i=0;i<pos;i++) //0到pos都变成0 53 a[i]=0; 54 int flag1=0,pos1; 55 for(int i=pos+1;i<cnt;i++) //从pos开始到最高位,把第一个0变成1,并且把该位置后面的所有1都移到低位 56 { 57 if(a[i]==0) 58 { 59 a[i]=1; 60 flag1=1; 61 pos1=i; 62 break; 63 } 64 } 65 if(!flag1) 66 { 67 a[cnt++]=1; 68 for(int i=cnt-2;i>=k-1;i--) 69 a[i]=0; 70 for(int i=0;i<k-1;i++) 71 a[i]=1; 72 } 73 else 74 { 75 int cnt2=0; 76 for(int i=cnt-1;i>=pos1;i--) 77 if(a[i]==1) cnt2++; 78 for(int i=0;i<k-cnt2;i++) 79 a[i]=1; 80 for(int i=k-cnt2;i<pos1;i++) 81 a[i]=0; 82 } 83 } 84 ll ans=0; 85 ll p=1; 86 for(int i=0;i<cnt;i++) 87 { 88 ans+=p*(ll)a[i]; 89 p*=2; 90 } 91 printf("%lld\n",ans); 92 return 0; 93 }
H题:Horror Film Night


1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 1e6+5; 4 struct node 5 { 6 bool pre1,pre2; 7 }v[maxn]; 8 int main() 9 { 10 int n,m,op; 11 scanf("%d",&n); 12 while(n--) 13 { 14 scanf("%d",&op); 15 v[op].pre1=1; 16 } 17 scanf("%d",&m); 18 while(m--) 19 { 20 scanf("%d",&op); 21 v[op].pre2=1; 22 } 23 int ans=0,flag=3; 24 for(int i=0;i<maxn;i++) 25 { 26 if(v[i].pre1==1&&v[i].pre2==1) 27 { 28 ans++; 29 flag=3; 30 } 31 else if(v[i].pre1==1&&v[i].pre2==0) 32 { 33 if(flag==2||flag==3) 34 { 35 ans++; 36 flag=1; 37 } 38 } 39 else if(v[i].pre1==0&&v[i].pre2==1) 40 { 41 if(flag==1||flag==3) 42 { 43 ans++; 44 flag=2; 45 } 46 } 47 } 48 printf("%d\n",ans); 49 return 0; 50 }