Educational Codeforces Round 156 (Rated for Div. 2) - VP记录

A. Sum of Three

枚举即可，是否可行只与 \(a,b,c\) 模三的余数有关，所以随便小范围枚举一下 \(a,b\) 就行了（只枚举 \(1,2,3\) 可能会因为两数相同而误判），这样最不容易错。

#include<cstdio>
using namespace std;

int main()
{
	int T; scanf("%d",&T);
	while(T--)
	{
		int n; scanf("%d",&n);
		if(n<=6) puts("NO");
		else
		{
			bool flag=false;
			for(int i=1;i<=10;i++)
			{
				for(int j=1;j<=10;j++)
				{
					int t=n-i-j;
					if(i!=j&&i!=t&&j!=t && i%3&&j%3&&t%3 && t>0)
					{
						flag=true;
						puts("YES");
						printf("%d %d %d\n",i,j,t);
						break;
					}
				}
				if(flag) break;
			}
			if(!flag) puts("NO");
		}
	}
	return 0;
}

B. Fear of the Dark

我的洛谷题解

C. Decreasing String

我的洛谷题解

D. Monocarp and the Set

据说是道诈骗题，需要结合一下排列组合的知识，做法参考这篇题解。

赛时差不多想到正解了的，但是因为没想到特判而得出答案不符合样例，所以没有打。

#include<cstdio>
#define LL long long
using namespace std;

const int N=3e5+5,P=998244353;
int n,m; char s[N];

inline LL quick_pow(LL x,LL y)
{
	LL res=1;
	while(y)
	{
		if(y&1) res=res*x%P;
		x=x*x%P,y>>=1;
	}
	return res;
}
inline LL inv(LL x){return quick_pow(x,P-2);}

int main()
{
	scanf("%d%d%s",&n,&m,s+1);
	long long ans=1;
	for(int i=2;i<=n+1;i++)
		if(s[i]=='?') ans=ans*(i+1-2)%P;
	if(s[1]=='?') printf("0\n");
	else printf("%lld\n",ans);
	for(int i=1;i<=m;i++)
	{
		int x; char ch[5];
		scanf("%d%s",&x,ch);
		if(x>1)
		{
			if(s[x]!='?'&&ch[0]=='?') ans=ans*(x+1-2)%P;
			if(s[x]=='?'&&ch[0]!='?') ans=ans*inv(x+1-2)%P;
		}
		s[x]=ch[0];
		if(s[1]=='?') printf("0\n");
		else printf("%lld\n",ans);
	}
	return 0;
}