没有想到 dirt 率会这么高，给大家谢罪了qwq

A. 曹髦

预期通过率 $95\%$ 以上

注意 $1$ 号角色多获得两点护甲，护甲的上限为 $5$ 两个细节，按题意模拟即可。

#include <bits/stdc++.h>
#define REP(i,l,r) for (auto i=l; i<=r; i++)
#define REV(i,l,r) for (auto i=l; i>=r; i--)

using namespace std;
using i64 = long long;
using db = long double;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;

	vector<int> a(n), b(n);

	REP(i, 0, n-1) cin >> a[i];

	REP(i, 0, n-1) {
		b[i] += a[i] - 1;
	}

	b[0] += 2;

	REP(i, 0, n-1) cout << min(5, b[i]) << " \n"[i==n-1];

	return 0;
}

B. 沙摩柯

后面加的简单题。

要注意到使用的第 $x$ 张牌对于每个 $x$ 只可能出现一次，所以把所有小于 $n$ 的 $a_i$ 都加起来即可（重复的只能算一次）。

#include <bits/stdc++.h>

using namespace std;

void solve() 
{
	int n;
	cin>>n;
	long long ans=0;
	vector<int> a(n+1,0);
	for (int i=1; i<=n; i++)
	{
		int ccf;
		cin>>ccf;
		
		if (ccf<=n)
		{
			if (a[ccf]==0)
			{
			  a[ccf]=1;
			  ans=ans+ccf;
			}
		}
	}
	cout<<ans;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t=1;
    //std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

C. 戏志才

经过重置的题目。

容易发现其实这道题的伤害结算只有在出现一个环的时候才有可能无限循环把血量减少到 $0$ 。

因此判断一下 $x$ 在不在环上即可。

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

using namespace std;

void solve() {
    int n, z;
    cin >> n >> z;

    int x = 100;
    vector<int> a(n + 1, x);
    vector r(n + 1, vector<int>(0));
    for (int i = 1; i <= n; i++) {
        int ll;
        cin >> ll;
        r[ll].push_back(i);
    }

    int ans = 0;
    auto dfs = [&](auto self, int  pl) -> void {
        if (ans == 1)
            return;
        if (a[pl] != x) {
            ans = 1;
            return;
        }
        a[pl]--;
        for (auto i : r[pl]) {
            //cout<<i<<endl;
            self(self, i);
        }
    };

    dfs(dfs, z);
    if (ans == 1)
        cout << "Yes" << '\n';
    else
        cout << "No" << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t = 1;
    //std::cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

D. 神孙权

经过重置的题目。

注意到神孙权可以摸的总牌数是不变的，可以先算出来，记为 $u$ 。

然后再算一个前缀和的最大值，后缀和的最大值，枚举前面拿至多 $x$ 张，后面拿至多 $u-x$ 张。

这样就可以在 $O(n)$ 解决问题。

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

using namespace std;


void solve() {	
	int n;
	i64 k;
	cin>>n>>k;
	vector<i64> qz(n+2,0);
	vector<i64> hz(n+2,0);
	vector<i64> a(n+1,0);
	for (int i=1; i<=n; i++)
	  cin>>a[i];
	
	i64 ss=0;
	for (int i=1; i<=n; i++)
	{
		ss=ss+a[i];
		qz[i]=max(qz[i-1],ss);
	}
	ss=0;
	for (int i=n; i>=1; i--)
	{
		ss=ss+a[i];
		hz[i]=max(hz[i+1],ss);
	}

	int ci=0;
	for (int i=0; i<n; i++)
	{
		if (k<i)
		  break;
		ci++;
		k=k-i+1;
	}
	
	i64 ans=max(qz[ci],hz[n-ci+1]);
	for (int i=1; i<ci; i++)
	{
		ans=max(ans,qz[i]+hz[n+1-(ci-i)]);
	}
	cout<<ans<<'\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t=1;
    //std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

E. 友诸葛亮

原来放在 $C$ 题，预期通过率 $[50\%,70\%]$ ，被认为是低估了这题的难度。

首先发现友诸葛亮的摸牌仅与界徐盛和自己预测的三种类型的牌的数量有关，与预测的顺序无关。

然后可以发现这是一个经典的模型：最多的牌超过一半友诸葛亮必定可以摸牌，否则必定能有不摸牌的方案。

不妨设友诸葛亮预测的三种牌分别为 $a,b,c$ （ $a\leq b\leq c$ ）张。

因为友诸葛亮预测的牌与界徐盛手牌结构一致，因此可以贪心地放，先把 $a,b$ 放到 $c$ 的位置。

如果 $c$ 的位置被填满后仍然有剩余，说明友诸葛亮一定能摸 $c-a-b$ 张牌，

否则优先放 $b$ 再放 $a$ 最后剩下的一定是 $a$ ，把 $a$ 放在 $b$ 的位置，再把 $c$ 放在所有没放过的位置，一定让友诸葛亮摸不了牌。

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

using namespace std;

void solve() {
	vector<int> b(4);
	cin>>b[1]>>b[2]>>b[3];
	int n=b[1]+b[2]+b[3];
	vector<int> a(n+1);
	vector<pair<int,int> > na(4);
	for (int i=1; i<=n; i++)
	{
	  cin>>a[i];
	  na[a[i]].first++;
	}
	for (int i=0; i<=3; i++)
	  na[i].second=i;
	sort(na.begin(),na.end());
	vector<int> ans(n+1,0);
	for (int i=1; i<=n; i++)
	{
		if (ans[i]==0 && a[i]==na[3].second && b[na[2].second]>0)
		{
			b[na[2].second]--;
			ans[i]=na[2].second;
		}
	}
	
	for (int i=1; i<=n; i++)
	{
		if (ans[i]==0 && a[i]==na[3].second && b[na[1].second]>0)
		{
			b[na[1].second]--;
			ans[i]=na[1].second;
		}
	}
	
	for (int i=1; i<=n; i++)
	{
		if (ans[i]==0 && a[i]==na[2].second && b[na[1].second]>0)
		{
			b[na[1].second]--;
			ans[i]=na[1].second;
		}
	}
	
	for (int i=1; i<=n; i++)
	  if (ans[i]==0)
	    ans[i]=na[3].second;
			
	for (int i=1; i<=n; i++)
	  cout<<ans[i]<<' ';
	cout<<'\n';
	
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t=1;
    //std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}

F. 王璨

原来放 $G$ 题，预期通过率 $[1\%,10\%]$

可以发现在分组背包的基础上加上一维， $dp[i][j][k]$ 代表在前 $i$ 组背包种选择了 $j$ 手牌上限、 $k$ 个使用的桃的最大价值。

$v[i][l]$ 、 $w[i][l]$ 是第 $i$ 个人第 $l$ 张牌的占用手牌上限，价值；其中第 $0$ 张牌代表桃。

$dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-v[i][l]][k]+w[i][l])$

$dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1])$

最终答案在整个 $dp[i][j][k]$ 中 $k \geq j$ 的取最大值即可。

还有个比 std 更优的办法，就是把桃视为两张牌，一张作为桃手牌和一个价值为 $0$ 、占用手牌上限 $-1$ 的牌；再做一个分组背包模板即可。

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

using namespace std;

void solve() 
{
	int n,x,y;
	cin>>n>>x>>y;
	vector dp(n+1,vector(n+1,vector<int>(n+1,0)));
	vector<int> c(n+1);
	vector v(n+1,vector<int>(0));
	vector w(n+1,vector<int>(0));
	
	for (int i=1; i<=n; i++)
	{
		cin>>c[i];
		
		int ccf;
		w[i].push_back(x);
		for (int j=1; j<=c[i]; j++)
		{
			cin>>ccf;
			w[i].push_back(ccf);
		}		
		v[i].push_back(y);
		for (int j=1; j<=c[i]; j++)
		{
			cin>>ccf;
			v[i].push_back(ccf);
		}
	}
	
	int ans=0;
	for (int i=1; i<=n; i++)
	  for (int j=0; j<=n; j++)
	    for (int k=0; k<=i; k++)
	    {
	      for (int l=0; l<=c[i]; l++)
	      {
	      	if (j>=v[i][l] && k<i)
	      	  dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-v[i][l]][k]+w[i][l]);
	      	if (k>=1)
	      	  dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-1]);
	      	if (k>=j)
	      	  ans=max(ans,dp[i][j][k]);
	      }
		  //cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
		}
	cout<<ans<<'\n';
}

int main() 
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t=1;
    //std::cin >> t;
    
    while (t--) 
        solve();
    
    return 0;
}

G. 蒋干

原来的 $E$ 题，预期通过率 $[10\%,30\%]$

容易发现如果有至少两种手牌，且花色集合中的一个花色在手牌出现过，直接替换这个花色即可。

除此之外的情况一定要替换出一个原来手牌不存在的牌。

枚举花色，对于每个花色，用 map 维护否能组合出一张原来手牌不存在的但在牌堆种存在的牌，注意考虑替换后只存在一种牌的情况。

#include <bits/stdc++.h>

using namespace std;

void solve() 
{
	int n,m,k;
	cin>>n>>m>>k;
	map<string,string> shoupai,fshoupai;
	set<string> paiku;
	map<string,vector<string> > pk;
	for (int i=1; i<=n; i++)
	{
		string s1,s2;
		cin>>s1>>s2;
		paiku.insert(s1);
		pk[s1].push_back(s2);
	}
	
	pair<string,string> dan;
	int fd=0;
	for (int i=1; i<=m; i++)
	{
		string s1,s2;
		cin>>s1>>s2;
		if (fd==0)
		{
			fd=1;
			dan={s1,s2};
		}
		else
		{
			if (make_pair(s1,s2)!=dan)
			  fd=2;
		}
		shoupai[s1]=s2;
		fshoupai[s2]=s1;
	}
	
	vector<string> huase(k);
	for (int i=0; i<k; i++)
	  cin>>huase[i];
	sort(huase.begin(),huase.end());
	int len=unique(huase.begin(),huase.end())-huase.begin();
	huase.resize(len);
	
	int fl=0;
	pair<string,string> qian;
	pair<string,string> hou;
	for (auto s:huase)
	{
		if (shoupai.count(s) && fd!=1)
		{
			fl=1;
			qian=hou={s,shoupai[s]};
			break;
		}
		else if (fd!=1 || (fd==1 && s!=dan.first))
		{
			if (paiku.count(s))
			{
				for (auto ss:pk[s])
				{
					if (fshoupai.count(ss))
					{
						fl=1;
						qian={fshoupai[ss],ss};
						hou={s,ss};
						break;
					}
				}
				if (fl)
				  break;	
			}
		}
		
	}
	if (fl)
	{
		cout<<"Yes\n";
		cout<<qian.first<<' '<<qian.second<<'\n';
		cout<<hou.first<<' '<<hou.second<<'\n';
	}
	else
	  cout<<"No\n";
	
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int t=1;
    //std::cin >> t;
    
    while (t--) {
        solve();
    }
    
    return 0;
}