Codeforces Round #497 (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 IT set<node>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 1000006
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=1e9+7;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 
24 bool Check(char ch){
25     if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u') return true;
26     return false;
27 }
28 
29 int main(){
30     std::ios::sync_with_stdio(false);
31     string str;
32     cin>>str;
33     if(str.length()==1){
34         if(!Check(str[0])&&str[0]!='n') cout<<"NO";
35         else  cout<<"YES";
36         return 0;
37     }
38     for(int i=0;i<str.length()-1;i++){
39         if(!Check(str[i])&&str[i]!='n'){
40             if(!Check(str[i+1])){
41                 cout<<"NO";
42                 return 0;
43             }
44         }
45     }
46     if(!Check(str[str.length()-1])&&str[str.length()-1]!='n'){
47          cout<<"NO";
48          return 0;
49     }
50 
51     cout<<"YES";
52 }

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 IT set<node>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 1000006
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=1e9+7;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 vector<pii>ve;
24 
25 int main(){
26     std::ios::sync_with_stdio(false);
27     int n;
28     int x,y;
29     cin>>n;
30     for(int i=0;i<n;i++){
31         cin>>x>>y;
32         if(x<y) swap(x,y);
33         ve.pb({x,y});
34     }
35     x=ve[0].first;
36     for(int i=1;i<ve.size();i++){
37         if(x>=ve[i].first){
38             x=ve[i].first;
39         }
40         else if(x>=ve[i].second){
41             x=ve[i].second;
42         }
43         else{
44             cout<<"NO";
45             return 0;
46         }
47     }
48     cout<<"YES";
49 }

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 IT set<node>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 1000006
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=1e9+7;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 
24 int a[maxn];
25 
26 bool cmp(int a,int b){return a>b;}
27 
28 int main(){
29     std::ios::sync_with_stdio(false);
30     int n;
31     cin>>n;
32     for(int i=1;i<=n;i++){
33         cin>>a[i];
34     }
35     sort(a+1,a+n+1,cmp);
36     int pos=1;
37     for(int i=2;i<=n;i++){
38         if(a[pos]>a[i]){
39             pos++;
40         }
41     }
42     cout<<pos-1<<endl;
43 }

View Code

D

组合数学

题意：给你一个长方体，长，宽，高分别为A,B,C，求有多少种方案使a×b×c能够拼凑出这个长方体 a|A,b|B,c|C

思路：先预处理出每个数的因子个数，然后考虑A,B,C每个数有7种情况

001 是A的因数
010 是B的因数
011 是A的因数也是B的因数，即是gcd（A，B）的因数
100 是C的因数
101 是A的因数也是C的因数，即是gcd（A，C）的因数
110 是B的因数也是C的因数，即是gcd（B，C）的因数
111 是A的因数也是B的因数也是C的因数，即是gcd（A，B，C）的因数

最后枚举每一种状态相乘即可

参考博客：https://blog.csdn.net/codeswarrior/article/details/81146331

 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 IT set<node>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 100005
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=1e9+7;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 ll cal(int n,int m){
24     ll ans=1;
25     for(int i=1;i<=m;i++){
26         ans=ans*(n-i+1)/i;
27     }
28     return ans;
29 }
30 
31 bool Check(int a,int b,int c){
32     if((a&1)&&(b&2)&&(c&4)) return true;
33     if((a&1)&&(c&2)&&(b&4)) return true;
34     if((b&1)&&(a&2)&&(c&4)) return true;
35     if((b&1)&&(c&2)&&(a&4)) return true;
36     if((c&1)&&(a&2)&&(b&4)) return true;
37     if((c&1)&&(b&2)&&(a&4)) return true;
38     return false;
39 }
40 
41 int cnt[15],used[15];
42 int fac[maxn];
43 
44 void Init(){
45     for(int i=1;i<maxn;i++){
46         for(int j=i;j<maxn;j+=i){
47             fac[j]++;
48         }
49     }
50 }
51 
52 int main(){
53     std::ios::sync_with_stdio(false);
54     int t;
55     Init();
56     cin>>t;
57     ll x,y,z;
58     while(t--){
59         cin>>x>>y>>z;
60         ll xy=__gcd(x,y);
61         ll yz=__gcd(y,z);
62         ll xz=__gcd(x,z);
63         ll xyz=__gcd(xy,z);
64         cnt[7]=fac[xyz];
65         cnt[6]=fac[yz]-fac[xyz];
66         cnt[5]=fac[xz]-fac[xyz];
67         cnt[4]=fac[z]-fac[xz]-fac[yz]+fac[xyz];
68         cnt[3]=fac[xy]-fac[xyz];
69         cnt[2]=fac[y]-fac[xy]-fac[yz]+fac[xyz];
70         cnt[1]=fac[x]-fac[xy]-fac[xz]+fac[xyz];
71         ll ans=0;
72         for(int i = 1; i < 8; i++){
73             for(int j = i; j < 8; j++){
74                 for(int k = j; k < 8; k++){
75                     if(Check(i,j,k)){
76                         memset(used,0,sizeof(used));
77                         used[i]++;
78                         used[j]++;
79                         used[k]++;
80                         ll tmp = 1;
81                         for(int q = 1; q < 8; q++){
82                             if(used[i])
83                                 tmp *= cal(cnt[q]+used[q]-1,used[q]);
84                         }
85                         if(tmp > 0)
86                             ans += tmp;
87                     }
88                 }
89             }
90         }
91         cout<<ans<<endl;
92     }
93 }

View Code

E

交互题

题意：给定n，在1-n中求a，b两个数，假设你猜的数是x，y

当a==0&&y==0时，返回0

当x比a小，返回1

当y比b小，返回2

当x比a大或y比b大，返回3

思路：不断二分逼近即可

 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 IT set<node>::iterator
 6 #define sqr(x) ((x)*(x))
 7 #define pb push_back
 8 #define eb emplace_back
 9 #define maxn 1000006
10 #define eps 1e-8
11 #define pi acos(-1.0)
12 #define rep(k,i,j) for(int k=i;k<j;k++)
13 typedef long long ll;
14 typedef pair<int,int> pii;
15 typedef pair<ll,ll>pll;
16 typedef pair<ll,int> pli;
17 typedef pair<pair<int,string>,pii> ppp;
18 typedef unsigned long long ull;
19 const long long MOD=1e9+7;
20 const double oula=0.57721566490153286060651209;
21 using namespace std;
22 
23 
24 int main(){
25     std::ios::sync_with_stdio(false);
26     ll x,n;
27     cin>>n;
28     ll ans1=0,ans2=0,a=1,b=1;
29     for(int i=0;i<600;i++){
30         cout<<ans1+a<<" "<<ans2+b<<endl;
31         cin>>x;
32         if(x==0) return 0;
33         else if(x==1){
34             ans1+=a;
35             a=min(n-ans1,a<<1);
36         }
37         else if(x==2){
38             ans2+=b;
39             b=min(n-ans2,b<<1);
40         }
41         else{
42             a=max(a>>1,1LL);
43             b=max(b>>1,1LL);
44         }
45     }
46 }

View Code