Codeforces Round #497 (Div. 2)
https://codeforces.com/contest/1008
A
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define IT set<node>::iterator
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<ll,int> pli;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long MOD=1e9+;
const double oula=0.57721566490153286060651209;
using namespace std; bool Check(char ch){
if(ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u') return true;
return false;
} int main(){
std::ios::sync_with_stdio(false);
string str;
cin>>str;
if(str.length()==){
if(!Check(str[])&&str[]!='n') cout<<"NO";
else cout<<"YES";
return ;
}
for(int i=;i<str.length()-;i++){
if(!Check(str[i])&&str[i]!='n'){
if(!Check(str[i+])){
cout<<"NO";
return ;
}
}
}
if(!Check(str[str.length()-])&&str[str.length()-]!='n'){
cout<<"NO";
return ;
} cout<<"YES";
}
B
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define IT set<node>::iterator
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<ll,int> pli;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long MOD=1e9+;
const double oula=0.57721566490153286060651209;
using namespace std; vector<pii>ve; int main(){
std::ios::sync_with_stdio(false);
int n;
int x,y;
cin>>n;
for(int i=;i<n;i++){
cin>>x>>y;
if(x<y) swap(x,y);
ve.pb({x,y});
}
x=ve[].first;
for(int i=;i<ve.size();i++){
if(x>=ve[i].first){
x=ve[i].first;
}
else if(x>=ve[i].second){
x=ve[i].second;
}
else{
cout<<"NO";
return ;
}
}
cout<<"YES";
}
C
题意：给一个序列，你需要生成这个序列的任意一个排列，使得这个排列上某个位置的值大于原序列的值，求最多能有多少个数符合条件
思路：排个序比较即可
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define IT set<node>::iterator
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<ll,int> pli;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long MOD=1e9+;
const double oula=0.57721566490153286060651209;
using namespace std; int a[maxn]; bool cmp(int a,int b){return a>b;} int main(){
std::ios::sync_with_stdio(false);
int n;
cin>>n;
for(int i=;i<=n;i++){
cin>>a[i];
}
sort(a+,a+n+,cmp);
int pos=;
for(int i=;i<=n;i++){
if(a[pos]>a[i]){
pos++;
}
}
cout<<pos-<<endl;
}
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
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define IT set<node>::iterator
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 100005
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<ll,int> pli;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long MOD=1e9+;
const double oula=0.57721566490153286060651209;
using namespace std; ll cal(int n,int m){
ll ans=;
for(int i=;i<=m;i++){
ans=ans*(n-i+)/i;
}
return ans;
} bool Check(int a,int b,int c){
if((a&)&&(b&)&&(c&)) return true;
if((a&)&&(c&)&&(b&)) return true;
if((b&)&&(a&)&&(c&)) return true;
if((b&)&&(c&)&&(a&)) return true;
if((c&)&&(a&)&&(b&)) return true;
if((c&)&&(b&)&&(a&)) return true;
return false;
} int cnt[],used[];
int fac[maxn]; void Init(){
for(int i=;i<maxn;i++){
for(int j=i;j<maxn;j+=i){
fac[j]++;
}
}
} int main(){
std::ios::sync_with_stdio(false);
int t;
Init();
cin>>t;
ll x,y,z;
while(t--){
cin>>x>>y>>z;
ll xy=__gcd(x,y);
ll yz=__gcd(y,z);
ll xz=__gcd(x,z);
ll xyz=__gcd(xy,z);
cnt[]=fac[xyz];
cnt[]=fac[yz]-fac[xyz];
cnt[]=fac[xz]-fac[xyz];
cnt[]=fac[z]-fac[xz]-fac[yz]+fac[xyz];
cnt[]=fac[xy]-fac[xyz];
cnt[]=fac[y]-fac[xy]-fac[yz]+fac[xyz];
cnt[]=fac[x]-fac[xy]-fac[xz]+fac[xyz];
ll ans=;
for(int i = ; i < ; i++){
for(int j = i; j < ; j++){
for(int k = j; k < ; k++){
if(Check(i,j,k)){
memset(used,,sizeof(used));
used[i]++;
used[j]++;
used[k]++;
ll tmp = ;
for(int q = ; q < ; q++){
if(used[i])
tmp *= cal(cnt[q]+used[q]-,used[q]);
}
if(tmp > )
ans += tmp;
}
}
}
}
cout<<ans<<endl;
}
}
E
交互题
题意：给定n，在1-n中求a，b两个数，假设你猜的数是x，y
当a==0&&y==0时，返回0
当x比a小，返回1
当y比b小，返回2
当x比a大或y比b大，返回3
思路：不断二分逼近即可
#include<bits/stdc++.h>
using namespace std;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define IT set<node>::iterator
#define sqr(x) ((x)*(x))
#define pb push_back
#define eb emplace_back
#define maxn 1000006
#define eps 1e-8
#define pi acos(-1.0)
#define rep(k,i,j) for(int k=i;k<j;k++)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll>pll;
typedef pair<ll,int> pli;
typedef pair<pair<int,string>,pii> ppp;
typedef unsigned long long ull;
const long long MOD=1e9+;
const double oula=0.57721566490153286060651209;
using namespace std; int main(){
std::ios::sync_with_stdio(false);
ll x,n;
cin>>n;
ll ans1=,ans2=,a=,b=;
for(int i=;i<;i++){
cout<<ans1+a<<" "<<ans2+b<<endl;
cin>>x;
if(x==) return ;
else if(x==){
ans1+=a;
a=min(n-ans1,a<<);
}
else if(x==){
ans2+=b;
b=min(n-ans2,b<<);
}
else{
a=max(a>>,1LL);
b=max(b>>,1LL);
}
}
}