2023“钉耙编程”中国大学生算法设计超级联赛(2)

1001 Alice Game

题意:

起初有n个物品,玩家可以有如下操作:
①若该堆物品数量小于等于k,全部拿走。
②若该堆物品数量大于k,则只能选择拿走k个物品,并将剩余物品分成不为空的两堆。
Alice先手,问谁必胜。

分析:

打表可知当n % (4 * k + 2) == k + 1时Alice必败,其他时候必胜。


打表代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1e6 + 5;
LL f[N];

int sg(int x, int k)
{
	if (f[x] != -1)
		return f[x];
		
	set<int> S;
	
	if (x <= k && x > 0)
		S.insert(sg(0, k));
	else
	{
		for (int i = 2; i <= x - k; i ++)
		{
			S.insert(sg(i - 1, k) ^ sg(x - (i + k - 1), k));
		}	
	}
	
	for (int i = 0;; i ++)
	{
		if (S.count(i) == 0)
			return f[x] = i;
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int k = 3;
	for (int i = 1; i <= 100; i ++)
	{
		memset(f, -1, sizeof f);
		cout << sg(i, k) << " ";
		if (i % (4 * k + 2) == 0)
			cout << endl;
	}

	return 0;
}

代码:

#include <bits/stdc++.h>
using namespace std;

int main()
{
	std::ios::sync_with_stdio(false); 
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, k;
		cin >> k >> n;
		
		if ((n % (4 * k + 2)) == k + 1)
			cout << "Bob" << endl;
		else
			cout << "Alice" << endl;
	}
	
	return 0;
}

1002 Binary Number

题意:

给定一个01串,有k次操作,每次选择一个区间将其翻转,求k次操作后的最大结果。

分析:

最高位一定是1。
①n = 1:k为奇数则输出0,k为偶数则输出1
②n > 1:设连续0的段数为m。显然要让结果最大,要尽可能将高位的0翻转。
k < m:则将前k端连续0翻转为1;
k ≥ m:特别的当m = 0,k = 1时将最后一位变为0。其他情况,我们先将m段0翻转为1,然后考虑对较低的位去操作,若k - m是偶数则翻转最后一位k - m次,因此不影响结果;若k - m是奇数可以先翻转最低位一次,再翻转次低位一次,然后将次低位和最低位一起翻转,剩下的操作为偶数不影响结果。综上除了特殊情况其他均输出n个1。

代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{	
		int n;
		LL k;
		cin >> n >> k;
		
		string s;
		cin >> s;
		
		if (n == 1)
		{
			if (k & 1)
				cout << 0 << endl;
			else
				cout << 1 << endl;
			continue;
		}
		
		int cnt = 0;
		for (int i = 0; i < n;)
		{
			int j = i + 1;
			if (s[i] == '0')
			{
				while (j < n && s[j] == '0')
					j ++;
				cnt ++;
			}
			i = j;
		}
		
		if (k < cnt)
		{
			if (k == 0)
				cout << s;
			else
			{
				for (int i = 0; i < n;)
				{
					int j = i + 1;
					if (s[i] == '0')
					{
						if (k)
						{
							k --;
							cout << 1;
							while (j < n && s[j] == '0')
							{
								cout << 1;
								j ++;
							}
						}
						else
							cout << 0;
					}
					else
						cout << 1;
					i = j;
				}
			}
		}
		else
		{
			if (cnt == 0 && k & 1)
			{
				for (int i = 0; i < n - 1; i ++)
					cout << 1;
				cout << 0;
			}
			else
			{
				for (int i = 0; i < n; i ++)
					cout << 1;
			}
		}
		cout << endl;
	}		
	
	return 0;
}

1004 Card Game

题意:

给你n个堆,起初第一个堆放了k个东西,下面大上面小,其它堆都是空的,需要通过其它空堆的中转作用将k个东西从第一个堆全部放到第二个堆上(也是下面大上面小),问最多可以成功转移的k的个数是多少。

分析:

找规律。发现f[n] = f[n - 1] * 2 + 1 => f[n] = \(2^{n - 1}\) - 1。

代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
int mod = 998244353;

LL qmi(LL m, LL k)
{
	LL res = 1, t = m;
	while (k)
	{
		if (k & 1)
			res = res * t % mod;
		t = t * t % mod;
		k >>= 1;
	}
	return res;
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		cout << qmi(2, n - 1) - 1 << endl;
	}
	
	return 0;
}

1007 foreverlasting and fried-chicken

题意:

给你一个无向图,求出如下图形的数量。

分析:

枚举度大于等于6的点和度大于等于4的点,分别设为u,v。设与u相连的结点数为cnt,u和v均相连的结点数为cnt2,则u,v能组成的目标图形数为\(C_{cnt2}^4·C_{cnt - cnt2}^2\)。倘若暴力枚举cnt2会是\(O^3\)的复杂度,因此考虑用bitset优化。可以用bitset维护一个邻接矩阵g,cnt = g[u].count(),cnt2 = (g[u] & g[v]).count()。

代码:

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 1010, mod = 1e9 + 7;
bitset<N> g[N];
LL f[N], f2[N];

LL qmi(LL m, LL k)
{
	LL res = 1, t = m;
	
	while (k)
	{
		if (k & 1)
			res = res * t % mod;
		t = t * t % mod;
		k >>= 1;
	}
	
	return res;
}

void init()
{
	f[0] = f2[0] = 1;
	for (int i = 1; i < N; i ++)
	{
		f[i] = f[i - 1] * i % mod;
		f2[i] = f2[i - 1] * qmi(i, mod - 2) % mod;
	}
}

LL C(int a, int b)
{
	if (a < b || b < 0)
		return 0;
	else
		return f[a] * f2[b] % mod * f2[a - b] % mod;
}

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	init();
	
	while (t --)
	{
		int n, m;
		cin >> n >> m;
		
		for (int i = 1; i <= n; i ++)
			g[i].reset();
		
		while (m --)
		{
			int a, b;
			cin >> a >> b;
			
			g[a][b] = g[b][a] = 1;
		}
		
		LL res = 0;
		
		for (int i = 1; i <= n; i ++)
		{
			for (int j = i + 1; j <= n; j ++)
			{		
				int cnt1 = g[i].count(), cnt2 = g[j].count();
				if (g[i][j])
					cnt1 --, cnt2 --;
				int cnt3 = (g[i] & g[j]).count();
				res = (res + C(cnt3, 4) * C(cnt1 - 4, 2) + C(cnt3, 4) * C(cnt2 - 4, 2)) % mod;
			}
		}
		
		cout << res << "\n";
	}
	
	return 0;
}

1009 String Problem

题意:

取k个子串,每个子串只包含一种字母,问子串长度之和减去k的最大值是多少。

分析:

双指针枚举满足条件的子串的最长长度,其对答案的贡献为子串长度减1。

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 27;

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{	
		string s;
		cin >> s;
		
		int res = 0;
		for (int i = 0; i < s.size();)
		{
			int j = i + 1;
			while (j < s.size() && s[j] == s[i])
				j ++;
			res += j - i - 1;
			i = j;
		}
		
		cout << res << endl;
	}		
	
	return 0;
}

1010 Klee likes making friends

题意:

给定n个元素,每个元素有一个权值,要求每连续m个元素至少要有两个元素被选,求所选元素权值之和的最小值。

分析:

考虑dp。
f[i][j]表示所选方案中最后一个在i倒数第二个在j的权值之和的最小值,且i - j < m。由于[j,i]之间没有元素被选,因此倒数第三个所选的元素k应当在[i - m, j - 1]内。f[i][j] = a[i] + min(f[j][k]), k∈[i - m, j - 1]。 min(f[j][k])可以通过在递推时维护一个后缀最小值来处理。我们可以预处理前m个元素,然后递推,最后对在[n - m + 1, n]内的所有f[i][j]取个min就是答案。
但这样定义状态i×j最大有1e8级别,会MLE。考虑优化,首先很容易想到j可以用相对距离i - j来描述。其次,由于我们每次考虑一个长度为m的区间,因此第一维可以用i % m表示。新的状态可以定义为:f[k][l]表示所选方案中最后一个元素所在位置为k(k = i % m)倒数第二个元素与倒数第一个元素的相对距离为l(l = i - j)的权值之和的最小值。

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 2010, M = 20010;
int f[N][N], Min[N][N], pos[M];
int a[M];

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n, m;
		cin >> n >> m;
		
		for (int i = 1; i <= n; i ++)
		{
			cin >> a[i];
			pos[i] = i % m;
		}
		
		for (int i = 0; i <= m; i ++)
		{
			for (int j = 0; j <= m; j ++)
			{
				f[i][j] = Min[i][j] = 0x3f3f3f3f;
			}
		}
		
		for (int i = 2; i <= m; i ++)
		{
			for (int j = i - 1; j >= 1; j --)
			{
				f[pos[i]][i - j] = a[i] + a[j];
				Min[pos[i]][i - j] = min(Min[pos[i]][i - j - 1], f[pos[i]][i - j]);
			}
		}
		
		for (int i = m + 1; i <= n; i ++)
		{
			for (int j = i - 1; j >= i - m + 1; j --)
			{
				f[pos[i]][i - j] = a[i] + Min[pos[j]][j - (i - m)];
				Min[pos[i]][i - j] = min(Min[pos[i]][i - j - 1], f[pos[i]][i - j]); 
			}
		}
		
		int res = 0x3f3f3f3f;
		for (int i = n - m + 2; i <= n; i ++)
		{
			for (int j = i - 1; j >= n - m + 1; j --)
			{
				res = min(res, f[pos[i]][i - j]);	
			} 
		}
		
		cout << res << endl;
	}
	
	return 0;
}

1011 SPY finding NPY

题意:

n个人,IQ值为n的全排列,先取前k个人的最大IQ值m,之后从[k + 1, n - 1]位置内去选第一个大于m的人否则选第n个人,问选到IQ为n的概率最大时k的最小值。

分析:

设选到的人在位置a,且在[1, a - 1]内,IQ最大的人在[1, k]的概率:\(\frac{k}{n(a - 1)}\)。则选到IQ为n的概率为:\(\frac{1}{n}\sum_{i=k+1}^{n}{\frac{k}{(i - 1)}} = \frac{k}{n}\sum_{i=k}^{n-1}{\frac{1}{i}}\)。可以用前缀和预处理出\(\sum{\frac{1}{i}}\),然后枚举k取个min即可。

代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5;
double f[N];

struct Ans
{
	int k;
	double p;
};

int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	
	int t;
	cin >> t;
	
	while (t --)
	{
		int n;
		cin >> n;
		
		memset(f, 0, sizeof f);
		
		for (int i = 1; i <= n; i ++)
			f[i] = f[i - 1] +  1.0 / i;
			
		Ans ans = {0, 1.0 / n};
		
		for (int k = 1; k < n; k ++)
		{
			double p2 = 1.0 * k / n * (f[n - 1] - f[k - 1]);
			if (ans.p < p2)
			{
				ans = {k, p2};
			}
		}
		
		cout << ans.k << endl;
	}
	
	return 0;
}

热门相关:总裁别再玩了   锦庭娇   金粉   万古至尊   还在相爱吗?