ACM-ICPC 2018 焦作赛区网络预赛

本文转载自 acgoto 查看原文 2018/09/16 186 网络/ acm-icpc/ ACM

A-Magic Mirror

Jessie has a magic mirror.

Every morning she will ask the mirror: 'Mirror mirror tell me, who is the most beautiful girl in the world?' If the mirror says her name, she will praise the mirror: 'Good guy!', but if the mirror says the name of another person, she will assail the mirror: 'Dare you say that again?'

Today Jessie asks the mirror the same question above, and you are given a series of mirror's answers. For each answer, please output Jessie's response. You can assume that the uppercase or lowercase letters appearing anywhere in the name will have no influence on the answer. For example, 'Jessie' and 'jessie' represent the same person.

Input

The first line contains an integer

Each test case contains one line with a single-word name, which contains only English letters. The length of each name is no more than

Output

For each test case, output one line containing the answer.

样例输入

2
Jessie
Justin

样例输出

Good guy!
Dare you say that again?
解题思路：签道题，把源字符串中的所有大写字母改成小写字母，然后再判断即可。
AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string str;int t;
 4 int main(){
 5     while(cin>>t){
 6         while(t--){
 7             cin>>str;
 8             for(int i=0;str[i];++i)
 9                 if(isupper(str[i]))str[i]+=32;
10             if(str=="jessie")cout<<"Good guy!"<<endl;
11             else cout<<"Dare you say that again?"<<endl;
12         }
13     }
14     return 0;
15 }

G-Give Candies

There are

Input

The first line contains an integer

The next

$10^100000$

Output

For each test case output the number of possible results (mod 1000000007).

样例输入

1
4

样例输出

8
解题思路：签道题，这道题跟hdu4704一样，题解链接：题解报告：hdu 4704 Sum（整数快速幂+费马小定理）。此题题意为给任意多个小伙伴分糖果，每个人可以得到0﹣n块糖果，求将n分完的方案数。很容易想到隔板法，有n-1个空，每个空可以选择插入或不插入一块隔板，那么一共有2^(n-1)种方案数，由于n很大且取模大质数，因此要用费马小定理来降幂。
AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL mod=1000000007;
 5 const int maxn=1e5+5;//N最大有10^5位
 6 char str[maxn];int t;
 7 LL mod_power(LL a,LL b){//整数快速幂
 8     LL ans=1;
 9     while(b){
10         if(b&1)ans=ans*a%mod;
11         a=a*a%mod;
12         b>>=1;
13     }
14     return ans;
15 }
16 int main(){
17     while(cin>>t){
18         while(t--){
19             cin>>str;
20             LL N=0;
21             for(int i=0;str[i]!='\0';++i)
22                 N=(10*N+(str[i]-'0'))%(mod-1);//先处理指数N%(p-1)
23             cout<<mod_power(2,N-1)<<endl;//再求2^(N-1)%mod
24         }
25     }
26     return 0;
27 }

I-Save the Room

Bob is a sorcerer. He lives in a cuboid room which has a length of

Input

For each line, there are three integers

Output

For each test case, if Bob can save his room, print"Yes", otherwise print"No".

样例输入

1 1 2
1 1 4
1 1 1

样例输出

Yes
Yes
No
解题思路：签道题，很容易就发现如果a*b*c为偶数，则为"Yes"，否则为"No"。
AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int main(){
 4     int a,b,c;
 5     while(cin>>a>>b>>c){
 6         if(a*b*c&1)cout<<"No"<<endl;
 7         else cout<<"Yes"<<endl;
 8     }
 9     return 0;
10 }

K-Transport Ship

There are $i_th kind of ship can carry the weight of V[i] and the number of the i_th kind of ship is 2^C[i]−1. How many different schemes there are if you want to use these ships to transport cargo with a total weight of S?$

It is required that each ship must be full-filled. Two schemes are considered to be the same if they use the same kinds of ships and the same number for each kind.

Input

The first line contains an integer

For each test case:

The first line contains two integers:

For the next $i_th kind of ship can carry, and the number of the i_th kind of ship is 2^C[i]−1.$

For the next

Output

For each query, output one line containing a single integer which represents the number of schemes for arranging ships. Since the answer may be very large, output the answer modulo

样例输入

样例输出

0
1
解题思路：本来是一道签道题，由于比赛时把数量看成编号，导致一直WA（搞砸了），QAQ=_=||。题意：给定N种船，每种船有2^C[i]-1艘，每种船能承载V[i]的货物，有q个询问，问选择若干艘船装满重量为S的方案总数。显然这是一道多重背包裸题，二进制将其转化成01背包即可。dp[j]表示用若干艘船装成重量为j的方案数，相关思想，看这里：题解报告：hdu 1284 钱币兑换问题（简单数学orDP）。注意：题目条件还有这样的限制，如果同种船使用相同的数量，其被认为是相同的方案，那么是不能重复计数的，由于同种船中的2^c[i]-1必定拆成c[i]份，且每一份必定不会有相同的数字，所以不会发生重复计数，因此可以01-dp直接进行计数。
AC代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const LL mod=1e9+7;
 5 int t,n,q,cnt,x,y,num,c[22],val[500],s;LL dp[10005];
 6 int main(){
 7     for(int i=0;i<21;++i)c[i]=(1<<i)-1;
 8     while(~scanf("%d",&t)){
 9         while(t--){
10             memset(dp,0,sizeof(dp));dp[0]=1;cnt=0;
11             scanf("%d%d",&n,&q);
12             for(int i=1;i<=n;++i){
13                 scanf("%d%d",&x,&y),num=c[y];
14                 for(int d=1;d<=num;num-=d,d<<=1)
15                     val[cnt++]=x*d;
16                 if(num>0)val[cnt++]=x*num;
17             }
18             for(int i=0;i<cnt;++i){
19                 for(int j=10000;j>=val[i];--j)//每种只使用1次，避免重复计数 20                     dp[j]=(dp[j]+dp[j-val[i]])%mod;
21             }
22             while(q--){
23                 scanf("%d",&s);
24                 printf("%lld\n",dp[s]);
25             }
26         }
27     }
28     return 0;
29 }

智能推荐

注意！

本站转载的文章为个人学习借鉴使用，本站对版权不负任何法律责任。如果侵犯了您的隐私权益，请联系我们删除。

猜您在找

ACM-ICPC 2018 焦作赛区网络预赛 ACM-ICPC 2018 焦作赛区网络预赛 Solution ACM-ICPC 2018 焦作赛区网络预赛 H、L ACM-ICPC 2018 焦作赛区网络预赛 L 题 Poor God Water ACM-ICPC 2018 焦作赛区网络预赛 J Participate in E-sports(大数开方)

赞助商链接