Codeforces Round #295 (Div. 2)

A. Pangram

题意：给出长度为n的字符串，判断26个字母（比如a，A都算作a出现了）是否都在该串中出现了

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath>   
 5 #include<algorithm>  
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 
10 
11 
12 int main()
13 {
14     int i,j,n;
15     char s[105];char a[52];
16     strcpy(a,"aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ");
17     scanf("%d",&n);
18     cin>>s;
19     int flag=1;
20     int ans=0;
21     if(n<26) flag=0;
22     else
23     {
24         for(i=0;i<52;i=i+2)
25       {
26         for(j=0;j<n;j++)
27         {
28             if(a[i]==s[j]||a[i+1]==s[j]) 
29             {
30                 ans++;
31                 break;
32             }
33         }
34      }
35      if(ans<26) flag=0;
36     }
37     
38     if(flag) printf("YES
");
39     else printf("NO
");
40 }

View Code

B. Two Buttons

题意：给出n,k，n可以作减1，乘2的操作，问至少通过多少次操作得到k

第一反应是贪心，后来在提示（不--是明示下（>﹏<)）知道是BFS,和catch that cow一样，删掉一句就可以了

后来又用贪心写了，分别挂在第7个数据--第九个数据上--

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring>  
 4 #include<algorithm>
 5 #include<queue>  
 6 #define maxn 10005
 7 using namespace std;
 8 queue<int> q;
 9 int visit[maxn],step[maxn],n,k;
10 
11 int bfs(int n,int k)
12 {
13     int head,next,i;
14     q.push(n);
15     visit[n]=1;
16     step[n]=0;
17     while(!q.empty())
18     {
19         head=q.front();
20         q.pop();
21         for(i=1;i<=3;i++)
22         {
23             if(i==1) next=head-1;
24             else next=2*head;
25             if(next<=10005&&next>0) 
26             {
27                 if(!visit[next])//���� 
28                 {
29                 q.push(next);
30                 visit[next]=1;
31                 step[next]=step[head]+1;
32                 }
33             }
34             if(next==k) return step[next];
35         }       
36     }
37 }
38 
39 int main()
40 {
41     scanf("%d %d",&n,&k);
42     if(n>=k) printf("%d
",n-k);
43     else
44     printf("%d
",bfs(n,k));    
45 }

View Code

C. DNA Alignment

题意：给出ACGT组成的字符串s,求满足使得p（s,t）最多的字符串有多少个

因为对于给出的字符串s,t中的每个字符都要匹配n次，

假设t[i]为现在去匹配的一个字符，需要匹配n次，

t[i]对p(s,t)的贡献即为t[i]在s这个串中出现的次数（因为对于题目中所给的p(s,t)的定义，t[i]每个位置都可以去匹配，所以s中有多少个t[i],t[i]的贡献就为多少）

这样就可以求出使得p(s,t)最大的条件，即为找出s串中出现次数最多的字母，如果这个次数对应有num个字母，那么总的就为num^n（因为有n个位置，每个位置有num个选择）

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath>   
 5 #include<algorithm>  
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 const int mod=1e9+7;
10 char s[100005];
11 
12 LL quick_mod(LL a,LL b)
13 {
14     LL ans=1;
15     while(b)
16     {
17         if(b&1) ans=ans*a%mod;
18         b>>=1;
19         a=a*a%mod;
20     }
21     return ans;
22 }
23 
24 int main()
25 {
26     int n,i,j,k,maxn=-1,num=0;
27     int cnt[55];
28     

29     scanf("%d",&n);
30     cin>>s;
31     memset(cnt,0,sizeof(cnt));
32     for(i=0;i<n;i++) //计算Ａ　Ｃ　Ｇ　Ｔ分别出现的次数 
33     {
34         cnt[s[i]-'A']++;        
35     }
36      
37     for(i=0;i<20;i++)
38     maxn=max(maxn,cnt[i]);　 //找出出现次数最多的次数 
39 
40     for(i=0;i<20;i++)
41     {
42         if(cnt[i]==maxn) num++; //找出出现次数最多的对应有几个字母 
43     }
44     printf("%I64d
",quick_mod(num,n)); 
45     return 0;    
46 }

View Code

哎----理解了的话= = 当时一直往排列组合那边想，觉得是有公式的-----5555555555

加油啊 go--go--go