2023年中国大学生程序设计竞赛女生专场 AFGKL

A. 疾羽的救赎

思路：直接模拟即可，注意细节。

记得初始化啊啊啊啊，我就是忘记初始化wa了好多发啊。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod = 1e9 +7;
const int N = 1e5 + 10;

int main()
{
	ios::sync_with_stdio(false);    cin.tie(nullptr),cout.tie(nullptr);
	int t; cin>>t;
	while(t--)
	{
		bool on[10][10];
		int a = 2,b = 3,c = 4;

		for(int i = 1;i <= 12; i++)
		{
			int op,x; cin>>op>>x;
			if(op==1)
			{
				if(!on[1][2]&&!on[1][3])//1上面没有2和3 
				{
					if(a==b)
						on[2][1] = false;
					if(a==c)
						on[3][1] = false; 
					a += x;
					if(a==b)
						on[2][1] = true;
					if(a==c)
						on[3][1] = true;
				}
				else if(!on[1][2]&&on[1][3])//3在1上面 
				{
					if(a==b)
						on[2][1] = false,on[2][3] = false;
					a += x,c += x;
					if(a==b)
						on[2][1] = true,on[2][3] = true;
					 
				}
				else if(on[1][2]&&!on[1][3])//2在1上面
				{
					if(a==c)
						on[3][1] = false,on[3][2] = false;
					a += x,b += x;
					if(a==c)
						on[3][1] = true,on[3][2] = true; 
				 } 
				 else//2,3都在1上面 
				 {
				 	a += x,b += x,c += x;	
				 }
			}
			else if(op==2)
			{
				if(!on[2][1]&&!on[2][3])//2上面没有1和3 
				{
					if(b==a)
						on[1][2] = false;
					if(b==c)
						on[3][2] = false; 
					b += x;
					if(b==a)
						on[1][2] = true;
					if(b==c)
						on[3][2] = true;
				}
				else if(!on[2][1]&&on[2][3])//3在2上面 
				{
					if(b==a)
						on[1][2] = false,on[1][3] = false;
					b += x,c += x;
					if(b==a)
						on[1][2] = true,on[1][3] = true;
					 
				}
				else if(on[2][1]&&!on[2][3])//1在2上面
				{

					if(b==c)
						on[3][1] = false,on[3][2] = false;
					b += x,a += x;
					if(b==c)
						on[3][1] = true,on[3][2] = true; 
				 } 
				 else//1,3都在2上面 
				 {
				 	a += x,b += x,c += x;	
				 }
			}
			else
			{
				if(!on[3][1]&&!on[3][2])//3上面没有1和2
				{
	
					if(c==a)
						on[1][3] = false;
					if(c==b)
						on[2][3] = false; 
					c += x;
					if(c==a)
						on[1][3] = true;
					if(c==b)
						on[2][3] = true;
				}
				else if(!on[3][1]&&on[3][2])//2在3上面 
				{
					if(c==a)
						on[1][2] = false,on[1][3] = false;
					b += x,c += x;
					if(c==a)
						on[1][2] = true,on[1][3] = true;
					 
				}
				else if(on[3][1]&&!on[3][2])//1在3上面
				{
					if(c==b)
						on[2][1] = false,on[2][3] = false;
					a += x,c += x;
					if(c==b)
						on[2][1] = true,on[2][3] = true; 
				 } 
				 else//1,3都在2上面 
				 {
				 	a += x,b += x,c += x;	
				 }
				 
			}
	    	//cout<<a<<" "<<b<<" "<<c<<"\n";
		}
		if(a==9&&b==9&&c==9)cout<<"Y\n";
		else cout<<"N\n";
	}
	return 0;
}

F. 最长上升子序列

思路：构造题。考虑按类分类，比如1的为一类，2的为一类...., 对于每一类里面倒着填。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod = 1e9 +7;
const int N = 1e6 + 10;
vector<int>v[N];
int ans[N],a[N],pre[N];

int main()
{
	ios::sync_with_stdio(false);    cin.tie(nullptr),cout.tie(nullptr);
	
	int n; cin>>n;
	set<int>s;
	for(int i = 1;i <= n; i++){
		cin>>a[i];
		s.insert(a[i]);
		v[a[i]].push_back(i);
	}
	bool ok = true;
	for(int i = 1;i <= n; i++)
	{
		if(pre[i-1]+1<a[i]){
			ok = false;
			break;
		}
		pre[i] = max(pre[i-1],a[i]);
		
	}
	if(!ok)
	{
		cout<<-1<<"\n";
		return 0;
	}
	
	int cnt = 0;
//cout<<s.size()<<"\n";
	for(auto i : s)
	{
		int sz = v[i].size();
		//cout<<"i = "<<i<<" sz = "<<sz<<"\n";
		for(int j = sz-1;j>=0;j--)
			ans[v[i][j]] = ++cnt;
	}
	
	for(int i = 1;i <= n; i++)
	cout<<ans[i]<<" ";
	cout<<"\n";
	
	
	return 0;
}

G. 精灵宝可梦对战

思路：这题考读题啊。

需要注意的几个点：

轮流对战，当A打完B，B再打A，这样算一轮
当一个宝可梦攻击完，就会排到最后一个去
能量是单个宝可梦的能量，不是单个的

读懂题直接模拟即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int long long
const int mod = 1e9 +7;
const int N = 1e5 + 10;
deque<array<int,8> >A,B;
int EA,EB;
signed main()
{
	ios::sync_with_stdio(false);    cin.tie(nullptr),cout.tie(nullptr);
	int n,m,k; cin>>n>>m>>k;
	for(int i = 1;i <= n; i++)
	{
		int h,a,b,c,d,e,w; cin>>h>>a>>b>>c>>d>>e>>w;
		A.push_back({h,a,b,c,d,e,w,0});
	}
	
	for(int i = 1;i <= m; i++)
	{
		int h,a,b,c,d,e,w; cin>>h>>a>>b>>c>>d>>e>>w;
		B.push_back({h,a,b,c,d,e,w,0});
	}
	int now = 0;
	int cnt = 0;
	bool pj = false;
	while(!A.empty()&&!B.empty())
	{
		if(now==1)cnt++;
		
		if(now==0&&!A.empty()&&!B.empty())
		{
			now ^= 1;
			auto ta = A.front();
			A.pop_front();
			auto tb = B.front();
			B.pop_front();
			
			int a_wl = max(0ll,ta[1]-tb[3]);
			int a_mf = max(0ll,ta[2]-tb[4]);
			int a_w = ta[6];
			
		
			int maxx = max({a_wl,a_mf,a_w});
			if(maxx==a_wl||maxx==a_mf)
			{
				//EA++;
				ta[7]++;
				if(tb[0]-maxx>0)
				{
					tb[0] -= maxx;
					B.push_front(tb);
				}
				A.push_back(ta);
			}
			else{
				if(ta[7]>=ta[5])
				{
					ta[7] -= ta[5];
					if(tb[0]-maxx>0)
					{
						tb[0] -= maxx;
						B.push_front(tb);
					}
				}
				else
				{
					maxx = max(a_wl,a_mf);
					ta[7]++;
					if(tb[0]-maxx>0)
					{
						tb[0] -= maxx;
						B.push_front(tb);
					}
				}
				A.push_back(ta);
			}
			//cout<<"now = "<<now<<" EA = "<<EA<<" \n";
				
		}
		else if(now==1&&!A.empty()&&!B.empty())
		{
			now ^= 1;
			auto ta = A.front();
			A.pop_front();
			auto tb = B.front();
			B.pop_front();
			
			int b_wl = max(0ll,tb[1]-ta[3]);
			int b_mf = max(0ll,tb[2]-ta[4]);
			int b_w = tb[6];
			
		
			int maxx = max({b_wl,b_mf,b_w});
			if(maxx==b_wl||maxx==b_mf)
			{
				tb[7]++;
				if(ta[0]-maxx>0)
				{
					ta[0] -= maxx;
					A.push_front(ta);
				}
				B.push_back(tb);
			}
			else{
				if(tb[7]>=tb[5])
				{
					tb[7] -= tb[5];
					if(ta[0]-maxx>0)
					{
						ta[0] -= maxx;
						A.push_front(ta);
					}
				}
				else
				{
					maxx = max(b_wl,b_mf);
					tb[7]++;
					if(ta[0]-maxx>0)
					{
						ta[0] -= maxx;
						A.push_front(ta);
					}
				}
				B.push_back(tb);
			}
				//cout<<"now = "<<now<<" EB = "<<EB<<" \n";
		}
		//cout<<A.size()<<" "<<B.size()<<"\n";
		if(cnt>=k)
		{
			pj = true;
			break;
		}
	}
	//cout<<"cnt = "<<cnt<<"\n";
	if(pj||(A.empty()&&B.empty()))cout<<"Draw\n";
	else if(A.empty()&&!B.empty())cout<<"Bob\n";
	else if(!A.empty()&&B.empty())cout<<"Alice\n";
	else cout<<"Draw\n";
	
	return 0;
}

K. RSP

思路：签到，和m无关，输出1/n即可。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod = 1e9 +7;
const int N = 1e5 + 10;

int main()
{
	ios::sync_with_stdio(false);    cin.tie(nullptr),cout.tie(nullptr);
	ll n,m; cin>>n>>m;
	cout<<1<<"/"<<n<<"\n";
	return 0;
}

L. 养成游戏

思路：看数据范围，很小啊，直接暴搜。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int mod = 1e9 +7;
const int N = 5e6 + 10;
vector<array<int,8> >vec;
int A[N][10];
int tmp[10];
int n,m,k;
int cnt = 0;
void dfs(int step)
{
	if(step>n)
	{
		++cnt;
		for(int i = 1;i <= n; i++)
		{
			A[cnt][i] = tmp[i];
			//cout<<tmp[i]<<" "; 
		}
		//cout<<"\n";
		return;
	}
	
	for(int i = 0;i <= k; i++)
	{
		tmp[step] = i;
		dfs(step+1);
	}
}
int main()
{
	ios::sync_with_stdio(false);    cin.tie(nullptr),cout.tie(nullptr);

	cin>>n>>m>>k;
	for(int t = 1;t <= m; t++)
	{
		int i,j,op,a,b,d,v;
		cin>>i>>j>>op>>a>>b>>d>>v;
		vec.push_back({i,j,op,a,b,d,v});
	}
	
	dfs(1);
	//cout<<cnt<<"\n";
	ll ans = 0;
	for(int T = 1;T <= cnt; T++)
	{
		ll t = 0;
//		for(auto [i,j,op,a,b,d,v]:vec)
//		{
//			if(op==0)
//			{
//				if(a*A[i]+b*A[j]<=d)t += v;
//			}
//			if(op==1)
//			{
//				if(a*A[i]+b*A[j]>=d)t += v;
//			}
//		}
		int sz = vec.size(); 
		for(int tc = 0;tc < sz; tc++)
		{
			int i = vec[tc][0],j = vec[tc][1];
			int op = vec[tc][2],a = vec[tc][3];
			int b = vec[tc][4],d = vec[tc][5];
			int v = vec[tc][6];
			if(op==0)
			{
				if(a*A[tc][i]+b*A[tc][j]<=d)t += v;
			}
			if(op==1)
			{
				if(a*A[tc][i]+b*A[tc][j]>=d)t += v;
			}
		}
		ans = max(ans,t);
	}
	cout<<ans<<"\n";
	
	
	return 0;
}

/*
3 5 5
3 1 0 1 -1 0 4
3 1 0 1 1 2 2
3 1 0 1 0 1 3
3 2 1 1 1 2 0
3 2 1 1 -1 1 3
*/