第46届ICPC国际大学生程序设计竞赛亚洲区域赛(上海)补题D E G I

发布于 2022-09-22  279 次阅读


题目传送门:第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛(上海)

D Strange_Fractions(解方程,数论)

解方程,设\(t = \frac{b}{a}\),将方程两边同时乘\(t\)可以得到\(qt^2 - pt + q = 0\),通过小学二年级学的一元二次方程求根公式可知:当\(p^2 - 4q^2 \ge 0\)时方程有解。由求根公式可以得到\(t = \frac{p+\sqrt{p^2-4q^2}}{2q}\)(另一解排除),如果\(p^2-4q^2\)不是一个平方数就无解(无理数不能用分数表示),只需要让b = 分子,a = 分母即可。

一个数论小知识:设\(y = \sqrt{x}\),如果\(y\)不是一个整数,那么\(y\)一定是无理数。

同时还有无理数和非零有理数相乘还是一个无理数,所以这道题当根号下不是平方数的时候说明\(t\)是一个无理数,无法用分数表示,也就无解。

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

int ex_gcd(int a,int b){return b == 0 ? a : gcd(b, a % b);}

void solve()
{
	int p, q;cin >> p >> q;
	
	int c = sqrt(p * p - 4 * q * q);
	if(c * c != p * p - 4 * q * q || c < 0)cout << "0 0" << '\n';
	else
	{
		int a = p + c;
		int b = 2 * q;
		if(a <= 0)cout << "0 0" << '\n';
		else 
		{
			int d = gcd(a, b);
			cout << b / d << ' ' << a / d << '\n';
		}
	}
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _;cin >> _;
	while(_ --)solve();
	
	
	return 0;
}
 

E Strange_Integers(思维)

给定一个序列a,求一个新序列b,使得b中任意两个数字之差的绝对值>=K,问序列b的最大长度

不难发现这道题就是要求原序列a排序后,从前往后有多少个数字满足a[i] - b.back() >= K,只要满足条件就加入到b中,最后计算长度即可。

因为要求b中任意两个数字的差的绝对值都>=K,这时候a中原本序列的顺序就和答案无关了,所以可以排序,排序之后,以此将数字选入b中,b也会是一个不降的的序列。

如果a中的某个元素要加入到b中,必然有a[i] >= b.back()(因为b中的元素都是a[i]左侧的元素),只需要满足a[i]与b中最后一个元素的差的绝对值>=K,a[i]就可以加入到b中,所以只需要维护b中的最后一个元素也就是最大的元素。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9;
int a[maxn];


void solve()
{
	int N, K;cin >> N >> K;
	for(int i = 1;i <= N; ++ i)cin >> a[i];
	sort(a + 1,a + 1 + N);
	int ans = 1;
	for(int i = 2, tmp = a[1];i <= N; ++ i)
		if(a[i] - tmp >= K)ans ++, tmp = a[i];
    cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _ = 1;
	while(_ --)solve();
	
	return 0;
}
 

G Edge Groups(图论,排列组合,树)

给定一个有奇数个点的树,现在要将这棵树的所有边分组,每组里面有确切的两条边,两条边共用一个点,问分法有多少种。

边的分组要求

换言之就是每一组必须连通,不能分开。由于有奇数个点,那就有偶数条边,这棵树一定至少有一种方案被完整地划分。

既然是要将边划分,那么就考虑将每一条边划分给一个点,以一个点为中心点(上图中左侧度数为2的点),将这棵树划分成若干个小块,计算小块的方案数再用乘法原理。

我们知道每一块必须有偶数条边才可以完整地分配,如果是奇数条边一定会有一条边落单。

对于一个有x(x为偶数)条边的块,它的分配方案数为\(x! / ({2^{\frac{x}{2}}(\frac{x}{2})!})\)。

排列组合的原理是:确定(1, 2), (3, 4), (5, 6)....为一组,然后将所有点全排列,再除去无关的排列数2的阶乘的x / 2次方和x/2的阶乘。阶乘可以预处理出来。

现在的问题就是如何分块了,可以用类似topo的方式来分块,从叶子节点开始往回走,当前点为x,x有一个权值表示现在有多少条边连着自己,如果现在的边数是奇数,那么新的边就连到x,否则就连到y。这是为了使得每一块都是偶数。

分完之后统计答案就可以了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e5 + 9, p = 998244353;
int a[maxn], deg[maxn], fac[maxn];
vector<int> g[maxn];
queue<int> q;
bitset<maxn> del;


int qmi(int a,int b)
{
	int res = 1;
	while(b)
	{
		if(b & 1)res = res * a % p;
		a = a * a % p, b >>= 1;
	}
	return res;
}

int f(int x)
{
	return fac[x] * qmi(qmi(2, x / 2) * fac[x / 2] % p, p - 2) % p;
}

void solve()
{
	int N;cin >> N;
	fac[0] = 1;
	for(int i = 1;i <= N + 5; ++ i)fac[i] = fac[i - 1] * i % p;
	for(int i = 1;i < N; ++ i)
	{
		int x, y;cin >> x >> y;
		g[x].push_back(y), g[y].push_back(x);
		deg[x] ++, deg[y] ++;
	}
	
	for(int i = 1;i <= N; ++ i)
		if(deg[i] == 1)q.push(i), deg[i] = 0;
	
	while(!q.empty())
	{
		int x = q.front();q.pop();
		for(auto &y : g[x])
		{
			if(del[y])continue;
			
			if(a[x] & 1)a[x] ++;
			else a[y] ++;
			
			deg[y] --;
			if(deg[y] == 1)q.push(y), deg[y] = 0;
		}
		del[x] = true;//del表示这个点已经成为一个完整的块了,不会再加边进去了
	}
	int ans = 1;//保证了每个a[i]都是偶数
	for(int i = 1;i <= N; ++ i)ans = ans * f(a[i]) % p;
	cout << ans << '\n';
	
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _ = 1;
	while(_ --)solve();
	
	return 0;
}
 

I Steadily Growing Steam(DP)

这个DP比较好写,理解了题意就容易写出来。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 103, p = 998244353, fix = 2605;
int t[maxn], v[maxn];
int dp[2][maxn][6000];//dp[i][j][k]到i位置,翻转了j个,A - B = k时最大v 
 

void solve()
{
	int N, K;cin >> N >> K;
	for(int i = 1;i <= N; ++ i)cin >> v[i] >> t[i];
    memset(dp, -127, sizeof dp);//设为负无穷
    dp[0][0][fix] = dp[1][0][fix] = 0;//转移起点为0
	int F = 0;
	for(int i = 1;i <= N; ++ i, F ^= 1)
	{
		for(int j = 0;j <= i && j <= K; ++ j)
		{
			for(int k = fix - 2603;k <= fix + 2603; ++ k)//新的差 
			{
				//延续
				dp[F][j][k] = max(dp[F][j][k], dp[F ^ 1][j][k]);
				//不翻转
				//+ A 
				dp[F][j][k] = max(dp[F][j][k], dp[F ^ 1][j][k - t[i]] + v[i]);
				//+ B
				dp[F][j][k] = max(dp[F][j][k], dp[F ^ 1][j][k + t[i]] + v[i]);
				
				if(j == 0)continue;
				//翻转
				//+ A 
				dp[F][j][k] = max(dp[F][j][k], dp[F ^ 1][j - 1][k - t[i] * 2] + v[i]);
				//+ B
				dp[F][j][k] = max(dp[F][j][k], dp[F ^ 1][j - 1][k + t[i] * 2] + v[i]);
			}
		}
	}
	int ans = 0;
	for(int i = 0;i <= K; ++ i)ans = max(ans, dp[F ^ 1][i][fix + 0]);
	
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	
	int _ = 1;
	while(_ --)solve();
	
	return 0;
}