CF1008 Codeforces Round 497 (Div. 2)

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;
}