CF1008A Romaji
直接模拟。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=105;
int n;
char s[N];
int main()
{
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)
if(s[i]!='a'&&s[i]!='e'&&s[i]!='i'&&s[i]!='o'&&s[i]!='u'&&s[i]!='n')
{
if(s[i+1]!='a'&&s[i+1]!='e'&&s[i+1]!='i'&&s[i+1]!='o'&&s[i+1]!='u')
{
printf("NO");
return 0;
}
}
printf("YES");
return 0;
}
CF1008B Turn the Rectangles
从左往右使得每个位置能高尽量高。
#include<iostream>
#include<cstdio>
using namespace std;
const int N=100005;
int n;
int w[N],h[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&w[i],&h[i]);
int pre=1e9;
for(int i=1;i<=n;i++)
{
if(w[i]<h[i]) swap(w[i],h[i]);
if(w[i]<=pre) pre=w[i];
else if(h[i]<=pre) pre=h[i];
else
{
printf("NO");
return 0;
}
}
printf("YES");
return 0;
}
CF1008C Reorder the Array
将 \(a\) 从大到小排序，从左往右扫一遍，维护一下左边的数用到了第几个，如果能匹配就答案加一。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
int a[N];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1,greater<int>());
int ans=0,pre=1;
for(int i=2;i<=n;i++)
if(a[pre]>a[i]) ans++,pre++;
printf("%d",ans);
return 0;
}
CF1008D Pave the Parallelepiped
分类讨论容斥即可。
注意计数要不重不漏。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=100005;
int n;
int prime[N],tot;
bool isprime[N];
void init(int n=100000)
{
memset(isprime,true,sizeof(isprime));
isprime[1]=false;
for(int i=2;i<=n;i++)
{
if(isprime[i]) prime[++tot]=i;
for(int j=1;j<=tot&&i*prime[j]<=n;j++)
{
isprime[i*prime[j]]=false;
if(i%prime[j]==0) break;
}
}
return;
}
long long d(int n)
{
vector<int>pos;
for(int i=1;i<=tot&&prime[i]<=sqrt(n);i++)
if(n%prime[i]==0)
{
int cnt=0;
while(n%prime[i]==0) cnt++,n/=prime[i];
pos.emplace_back(cnt);
}
if(n!=1) pos.emplace_back(1);
long long res=1;
for(int c:pos)
res*=(c+1);
return res;
}
int T;
int a,b,c;
void solve()
{
scanf("%d%d%d",&a,&b,&c);
int ab=__gcd(a,b),ac=__gcd(a,c),bc=__gcd(b,c),abc=__gcd(ab,bc);
long long ans=d(a)*d(b)*d(c);
ans-=(d(c)*d(ab)*(d(ab)-1)+d(b)*d(ac)*(d(ac)-1)+d(a)*d(bc)*(d(bc)-1))/2;
ans+=d(abc)*(d(abc)-1)*(d(abc)-2)/6*4;
ans+=d(abc)*(d(abc)-1)*(d(ab)+d(bc)+d(ac)-3*d(abc)+2)/2;
ans-=(d(ab)-d(abc))*(d(bc)-d(abc))*(d(ac)-d(abc));
printf("%lld\n",ans);
return;
}
int main()
{
init();
scanf("%d",&T);
while(T--)
solve();
return 0;
}
CF1008E Guess two numbers
维护一下当前的值 \(x,y\)，满足 \(x\leq a,b\leq y\)，我们可以用一个 \(dx,dy\) 找出 \(x+dx\le a,y+dy\le b\)，用类似倍增的方法搞一搞就好了，复杂度不太会证。
#include<iostream>
#include<cstdio>
using namespace std;
long long n;
int query(long long x,long long y)
{
printf("%lld %lld\n",x,y);
fflush(stdout);
int k;
scanf("%d",&k);
if(k==0) exit(0);
return k;
}
int main()
{
scanf("%lld",&n);
long long x=0,y=0,dx=1,dy=1;
while(1)
{
int k=query(x+dx,y+dy);
if(k==1) x+=dx,dx=min(dx*2,n-x);
else if(k==2) y+=dy,dy=min(dy*2,n-y);
else if(k==3) dx=max(dx/2,1LL),dy=max(dy/2,1LL);
}
return 0;
}