Codeforces Beta Round #46 (Div. 2)

A

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define maxn 1000005
 8 typedef long long ll;
 9 typedef unsigned long long ull;
10 
11 
12 int main(){
13     #ifndef ONLINE_JUDGE
14         freopen("input.txt","r",stdin);
15     #endif
16     std::ios::sync_with_stdio(false);
17     map<char,int>mp;
18     mp['A']++;
19     mp['E']++;
20     mp['I']++;
21     mp['O']++;
22     mp['U']++;
23     mp['Y']++;
24     mp['a']++;
25     mp['e']++;
26     mp['i']++;
27     mp['o']++;
28     mp['u']++;
29     mp['y']++;
30     string str;
31     getline(cin,str);
32     char ch;
33     for(int i=str.length()-1;i>=0;i--){
34         if((str[i]>='A'&&str[i]<='Z')||(str[i]>='a'&&str[i]<='z')){
35             ch=str[i];
36             break;
37         }
38     }
39     if(mp[ch]) cout<<"YES"<<endl;
40     else cout<<"NO"<<endl;
41 }

View Code

B

模拟进制转换和运算

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define maxn 1000005
 8 typedef long long ll;
 9 typedef unsigned long long ull;
10 
11 int getmax(int a){
12     int Max=0;
13     while(a){
14         Max=max(a%10,Max);
15         a/=10;
16     }
17     return Max;
18 }
19 
20 int Change(int n,int base){
21     int p=1;
22     int ans=0;
23     while(n){
24         ans=ans+(n%10)*p;
25         n/=10;
26         p*=base;
27     }
28     return ans;
29 }
30 
31 
32 int main(){
33     #ifndef ONLINE_JUDGE
34      //   freopen("input.txt","r",stdin);
35     #endif
36     std::ios::sync_with_stdio(false);
37     int a,b;
38     cin>>a>>b;
39     int base=max(getmax(a),getmax(b))+1;
40     int sum=Change(a,base)+Change(b,base);
41     int ans=0;
42     while(sum){
43         sum/=base;
44         ans++;
45     }
46     cout<<ans<<endl;
47 }

View Code

C

找规律

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define maxn 1000005
 8 typedef long long ll;
 9 typedef unsigned long long ull;
10 
11 
12 
13 int main(){
14     #ifndef ONLINE_JUDGE
15      //   freopen("input.txt","r",stdin);
16     #endif
17     std::ios::sync_with_stdio(false);
18     int n;
19     cin>>n;
20     cout<<n<<" ";
21     for(int i=1;i<n;i++) cout<<i<<" ";
22 }

View Code

D

枚举第一个是0还是1，然后不断向后遍历判断，取最小值

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define maxn 1000005
 8 typedef long long ll;
 9 typedef unsigned long long ull;
10 
11 int n;
12 string str;
13 
14 int func(int ch){
15     int ans=0;
16     if(str[0]!=ch+'0') ans++;
17     ch^=1;
18     for(int i=1;i<str.length();i++){
19         if(str[i]!=ch+'0'){
20             ans++;
21         }
22         ch^=1;
23     }
24     return ans;
25 }
26 
27 int main(){
28     #ifndef ONLINE_JUDGE
29      //   freopen("input.txt","r",stdin);
30     #endif
31     std::ios::sync_with_stdio(false);
32     cin>>n;
33     cin>>str;
34     int ans=0x3f3f3f3f;
35     ans=min(ans,func(0));
36     ans=min(ans,func(1));
37     cout<<ans<<endl;
38 }

View Code

E

区间DP

参考博客：https://blog.csdn.net/zhjchengfeng5/article/details/8201105

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define pb push_back
 7 #define eb emplace_back
 8 #define maxn 1000005
 9 #define rep(k,i,j) for(int k=i;k<j;k++)
10 typedef long long ll;
11 typedef unsigned long long ull;
12 
13 string s[2];
14 int n;
15 string str[55];
16 int dp[55][55];
17 bool book[2][55][55][55];
18 int len[2];
19 
20 void Init(int id){
21     len[id]=s[id].length();
22     rep(i,0,len[id]){
23         book[id][i][i][s[id][i]-'a']=1;
24     }
25     rep(L,1,len[id]+1){
26         int st=0;
27         rep(en,st+L-1,len[id]){
28             rep(mid,st,en){
29                 rep(i,0,n){
30                     if(book[id][st][mid][str[i][3]-'a']&&book[id][mid+1][en][str[i][4]-'a']){
31                         book[id][st][en][str[i][0]-'a']=1;
32                     }
33                 }
34             }
35             st++;
36         }
37     }
38 }
39 
40 int main(){
41     #ifndef ONLINE_JUDGE
42         freopen("input.txt","r",stdin);
43     #endif
44     std::ios::sync_with_stdio(false);
45     cin>>s[0]>>s[1];
46     cin>>n;
47     for(int i=0;i<n;i++){
48         cin>>str[i];
49     }
50     Init(0),Init(1);
51     memset(dp,0x3f,sizeof(dp));
52     dp[0][0]=0;
53     rep(mid0,0,len[0]){
54         rep(mid1,0,len[1]){
55             rep(st0,mid0,len[0]){
56                 rep(st1,mid1,len[1]){
57                     rep(ch,0,26){
58                         if(book[0][mid0][st0][ch]&&book[1][mid1][st1][ch]){
59                             dp[st0+1][st1+1]=min(dp[st0+1][st1+1],dp[mid0][mid1]+1);
60                         }
61                     }
62                 }
63             }
64         }
65     }
66     int ans=dp[len[0]][len[1]];
67     if(ans==0x3f3f3f3f) cout<<-1<<endl;
68     else cout<<ans<<endl;
69 }

View Code