题目传送门:第 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