【题解】10-7入门组模拟

A.[CCC 2021 J5/S2] Modern Art

lnk

// Problem:Luogu P9023 [CCC 2021 J5/S2] Modern Art

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a[5000000],b[5000000];
signed main()
{
	cin>>n>>m>>k;
	for(int i=1;i<=k;i++)
	{
		char opt;
		int u;
		cin>>opt>>u;
		if(opt=='R')a[u]++;
		else b[u]++;
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cnt+=(a[i]+b[j])%2;
	cout<<cnt;
	return 0;
}

B.「GFOI Round 2」Jom & Terry

lnk

// Problem:Luogu P11280 「GFOI Round 2」Jom & Terry

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000010;
int n,m,root,dis[MAXN];
vector <int> g[MAXN];
bool vis[MAXN];
int read()
{
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c))
	{
		if(c=='-')f=-1;
		c=getchar();
	}
	while(isdigit(c))
	{
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
void bfs()
{
	queue <int> q;
	q.push(root);
	vis[root]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(auto v:g[u])
		{
			if(!vis[v])
			{
				dis[v]=dis[u]+1;
				vis[v]=1;
				q.push(v);
			}
		}
	}
}
int main()
{
	puts("I'm here!");
	n=read(),m=read(),root=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bfs();
	int k=read();
	for(int i=1;i<=k;i++)
	{
		int u=read(),v=read();
		if(dis[u]<=dis[v])puts("Terry");
		else puts("Jom");
	}
}

C.「Wdoi-4」芙兰？姆Q！贤者与谜题

lnk

// Problem:Luogu P7871 「Wdoi-4」芙兰？姆Q！贤者与谜题

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e5+10;
int n,q,tol[MAXN],tor[MAXN],res[MAXN],idx;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>q;
	for(int i=1;i<=q;i++)
	{
		int s,t;
		cin>>s>>t;
		if(s<t)
			tol[s-1]++,tol[t-1]--;
		else tor[t]++,tor[s]--;
	}
	for(int i=1;i<=n;i++)
		tol[i]+=tol[i-1],
		tor[i]+=tor[i-1];
	for(int i=1;i<=n;i++)
		if(tol[i]&&tor[i])
		{
			puts("QED");
			return 0;
		}
	for(int i=1;i<=n;i++)
	{
		if(res[i]==0)
		{
			int len=1;
			for(int j=i;tol[j]&&j+2<=n;j+=2)len++;
			for(int j=1;j<=len;j++)
				res[i+(len-j)*2]=++idx;
		}
	}
	for(int i=1;i<=n;i++)
		cout<<res[i]<<" ";
	return 0;
}

D. [yLCPC2024] D. 排卡

lnk

// Problem:Luogu P10236 [yLCPC2024] D. 排卡

#include<bits/stdc++.h>
using namespace std;
#define int long long
int mod=998244353;
int quickpow(int x,int y)
{
	if(x==0&&y==0)return 0;
	int ans=1,p=x;
	while(y>0)
	{
		if(y&1)ans=(ans*p)%mod;
		p=(p*p)%mod;
		y>>=1;
	}
	return ans;
}
int dp[1009][1009][2],a[1009],n; 
signed main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=1;i<=n;i++)
		{
			cin>>a[i];
		}
		memset(dp,0,sizeof(0));
		for(int len=n;len>=1;len--)
		{
			for(int i=1;i<=n-len+1;i++)
			{
				int j=i+len-1;
				dp[i][j][0]=max(dp[i-1][j][0]+quickpow(a[i-1],a[i]),dp[i][j+1][1]+quickpow(a[j+1],a[i]));
				dp[i][j][1]=max(dp[i-1][j][0]+quickpow(a[i-1],a[j]),dp[i][j+1][1]+quickpow(a[j+1],a[j]));
			}
		}
		int ans=0;
		for(int i=1;i<=n;i++)
			ans=max({ans,dp[i][i][0],dp[i][i][1]});
		cout<<ans<<endl;
	}
	return 0;
 }