ABC222

rk1865，手速太慢了。

A和B都是语法题。

C是个小模拟，过 m 轮每一轮 2k-1 名和 2k 名比较谁赢了计入进去，每一轮弄完之后直接在排序啊。

#include <bits/stdc++.h>
using namespace std;
const int N=1010;
 
//by zplqwq
inline int read()
{
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
int n,m;
struct node 
{
	string s;
	int pos,qwq;
	friend bool operator<(const node& a, const node& b) 
	{
		if(a.qwq!=b.qwq) return a.qwq>b.qwq;
		return a.pos<b.pos;
	} 
}a[N];
int check(char a, char b) 
{
	if(a==b) return 0;
	if(a =='G' and  b=='C' or a=='C' and b =='P' or a=='P' and b=='G') return 1;
	return -1;
}
 
int main() 
{
	n=read();
	m=read();
	for(int i=1;i<=2*n;i++) 
	{
		cin>>a[i].s;
		a[i].pos=i;
		a[i].qwq=0;
	}
	for(int i=0;i<m;i++)
	{
		sort(a+1,a+1+2*n);
		for(int j=1;j<=n;j++)
		{
			char tmp=a[2*j-1].s[i];
			char tmpp=a[2*j].s[i];
			if(check(tmp,tmpp)>0)a[2*j-1].qwq++;
			else if(check(tmp,tmpp)<0) a[2*j].qwq++;
		}
	}
	sort(a+1,a+1+2*n);
	for(int i=1;i<=2*n;i++)cout<<a[i].pos<<endl;
	return 0;
}

D 是个 dp.

考虑 \(dp_{i,j}\) 表示总共\(i\) 个数字结尾为 \(j\) 的方案数。

得到转移方程：

\[dp_{i,j}=\left\{\begin{array}{l}f_{0,0}=1\\ f_{i,j}=\sum{0\le k\le j} f_{i-1,k} (i \ge 1 & a_i \le j \le b_i)\\ \end{array}\right. \]

但显然这个转移方程不够优。

因此我们考虑前缀和优化。

令 \(s_{i,j}\) 表示 \(dp_{i,j}\) 的前缀和。

即 \(sum_{i,j}=(sum_{i,j-1}+dp_{i,j})\)

然后 \(dp_{i,j}=sum_{i-1,j}\) 然后就做完了。

答案即为所有 \(dp_{n,i}\) 的和。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
	int s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		s=s*10+ch-'0';
		ch=getchar();
	}
	return s*f;
}
// by : zplqwq
const int N=5010;
int n,k;
const int mod=998244353;
int dp[N][N];
int ans=0;
int a[N];
int b[N];
int sum[N][N];
signed main()
{
	n=read();
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	dp[0][0]=1;
	for(int i=0;i<=3000;i++)
	{
		sum[0][i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=a[i];j<=b[i];j++)
		{
			dp[i][j]=sum[i-1][j];
		}
		for(int j=0;j<=3000;j++)
		{
			sum[i][j]=(sum[i][j-1]+dp[i][j])%mod;
		}
	}
	int ans=0;
	for(int i=0;i<=3000;i++)
	{
		ans+=dp[n][i]; 
		ans%=mod;
	}
	cout<<ans<<endl;
	return 0;
}

EFGH 不会，决定这个上午搞定 E 和 F。