题目传送门：第 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;
}
Comments NOTHING