文章目录
题目集地址 第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（上海）
放假第一次训练，效果还不错，做了DE两个签到题
本次补题：
DE（签到）
G（树上DP）
I（背包DP）
J（位运算）
K（构造）
D Strange_Fractions 思维+数学
题目地址D Strange_Fractions
题目大意:给出一个分数
p
q
\frac{p}{q}
qp ，现在找到两个正整数a , b a,ba,b使得等式
p
q
=
a
b
+
b
a
\frac{p}{q}=\frac{a}{b}+\frac{b}{a}
qp=ba+ab ，如果无解就输出两个0
思路:将原问题转换，设
x
=
a
b
,
t
=
p
q
x=\frac{a}{b},t=\frac{p}{q}
x=ba,t=qp ，那么原等式就可以变成
x
+
1
x
=
t
x+\frac{1}{x}=t
x+x1=t，等价于求解方程
x
2
−
t
x
+
1
=
0
x^2-tx+1=0
x2−tx+1=0，可得解为
x
=
t
±
(
t
2
−
4
)
2
x=\frac{t±\sqrt{(t^2-4)}}{2}
x=2t±(t2−4)
，可知题目条件是有理数解，那么
(
t
2
−
4
)
\sqrt{(t^2-4)}
(t2−4)
就必须是有理数，得出来的解分别对应
a
b
,
b
a
\frac{a}{b},\frac{b}{a}
ba,ab，因此直接对给定的q,p带入方程求出解，判断是否是有理数解即可，如果是，则进一步将求得的解化为分数形式获得a,b。
AC代码:
#include <bits/stdc++.h>
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <stdio.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e5+10;
const int mod = 1e9+7;
ll gcd(ll a,ll b)
{
if(a<b)
swap(a,b);
ll yu;
yu=a%b;
while(true)
{
a=b;
b=yu;
if(yu==0)
break;
yu=a%b;
}
return a;
}
void solve()
{
bool bol=true;
ll p,q;
scanf("%lld%lld",&p,&q);
ll k=p*p-4*q*q;
ll kk=sqrt(k);
if(kk*kk==k)
bol=true;
else
bol=false;
ll gcdd=gcd(p-kk,q*2);
if(!bol)
printf("0 0\n");
else
{
printf("%lld %lld\n",(p-kk)/gcdd,q*2/gcdd);
}
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}
E Strange_Integers 思维
题目地址E Strange_Integers
题目大意:给定一个长为n的序列，从序列中选择m个数字，满足这m个数字中任意两个数的差的绝对值大于等于k值，问m的最大值
思路:将原序列排序，先选出一个最小值t，再从序列中找大于等于t+k的最小值，直到找遍整个序列，找到的数字的个数就是最大的m值
AC代码：
#include <bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1e5+5;
int a[N];
void solve()
{
int n,k;
scanf("%d%d",&n,&k);
for(int i = 1;i <= n;i++)
{
scanf("%d",a+i);
}
sort(a+1,a+n+1);
int ans = 0;
int t = a[1];
int pos = 1;
while(pos!=n+1)
{
t=a[pos];
t+=k;
ans++;
pos = lower_bound(a+1,a+1+n,t)-a;
}
printf("%d\n",ans);
}
int main()
{
int t = 1;
while(t--)
{
solve();
}
return 0;
}
G Edge Groups 思维+数学
题目地址G Edge Groups
题目大意:给出一个n点n-1边的无向连通图，n必为奇数，现在要将n-1条边分成(n-1)/2组，每组满足的条件如下：一组只有两条边， 两条边有一个共同点，输出所有满足条件的分组方案的方案数对998244353取模后结果
思路:n （奇数）个点的树，n−1 条边分成 n − 1 2 \frac{n−1}{2} 2n−1 组，每组两条边并且这两条边要有一个公共点，询问分组的方案数。子树 x 中若有偶数个点，那么奇数条边必然无法分组，需要 x 连向其父亲的边。如果有奇数个点，那么偶数条边可以分组。
设 d[x] 为分组 x 子树中的边的方案数，设 x 的孩子 y 中，有 a 个 y 需要 (x,y) 这条边与 y 子树中的边配对，有 b 个 y 是 (x,y) 在 x 这里配对的。那么当 b 是奇数时还需要 x 与其父亲连接的边。也就是说，x 有 a 个子树点数是偶数，b 个子树点数是奇数。现在只需要考虑把 b 个子树两两分组即可，如果 b 是奇数，那么还需要 (x,fa) 加入其中。
d
[
x
]
=
{
f
[
b
]
∗
∏
d
[
y
]
f
[
b
+
1
]
∗
∏
d
[
y
]
d[x]=\left\{ \begin{matrix} f[b]*\prod{d[y]} \\ f[b+1]*\prod{d[y]} \end{matrix} \right.
d[x]={f[b]∗∏d[y]f[b+1]∗∏d[y]
n 个元素，每组两个分成
n
2
\frac{n}{2}
2n 组的方案数是 f[n]，有递推式 f[n]=f[n−2]∗(n−1) 。
AC代码:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,j,k) for(int i=int(j);i<=int(k);i++)
#define per(i,j,k) for(int i=int(j);i>=int(k);i--)
typedef long long ll;
const int N = 100010, mod = 998244353;
int n, sz[N];
vector<int> g[N];
ll d[N], f[N];
void dfs(int x, int fa)
{
sz[x] = 1;
d[x] = 1;
int cnt = 0;
for(auto &y : g[x])
{
if(y == fa) continue;
dfs(y, x);
sz[x] += sz[y];
d[x] = d[x] * d[y] % mod;
if(sz[y] & 1) cnt ++;
}
if(cnt & 1) cnt ++;
d[x] = d[x] * f[cnt] % mod;
}
int main()
{
scanf("%d", &n);
for(int i=1; i<n; i++)
{
int x, y;
scanf("%d%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
f[0] = 1;
for(int i=2; i<=n; i+=2)
{
f[i] = f[i-2] * (i-1) % mod;
}
dfs(3, 0);//这里其实可以以任意一个结点为根结点，其实以其他节点为根节点来遍历也是可以的
printf("%lld\n", d[3]);
return 0;
}
I Steadily Growing Steam DP
题目地址I Steadily Growing Steam
题目大意: 给出n张牌，每张牌有一个数字标签和一个价值，可以至多选择s张牌翻倍数字标签，现在从加倍之后的牌中选择两组牌，使得牌的数字标签之和相等且价值和最大
思路:可看作01背包问题，使用动态规划。
dp[i][j][k]，从前i张牌中，至多使用j次技能，两组牌的ti之和的差+2600为k，k之所以定义为差+2600，是因为差最小为-2600，防止数组下标为负数，加一个偏移量，根据不同的情况：放入S不加倍，放入S加倍，放入T不加倍，放入T加倍直接进行状态转移即可
AC代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,s,dp[101][101][5201],v[101],t[101];
const int inf=0x3f3f3f3f;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >>n>>s;
for(int i=1; i<=n; i++)
cin >>v[i]>>t[i];
for(int i=0; i<=s; i++)//初始化
for(int j=0; j<=5200; j++)
dp[0][i][j]=-inf*(j!=2600);
//这个地方不能动2600，因为2600为解，一开始解为0
for(int i=1; i<=n; i++)
for(int j=0; j<=s; j++)
for(int k=0; k<=5200; k++) {
dp[i][j][k]=dp[i-1][j][k];
if(k>=t[i])dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k-t[i]]+v[i]);
//装入T
if(k+t[i]<=5200)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j][k+t[i]]+v[i]);
//装入S
if(j&&k>=2*t[i])dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k-2*t[i]]+v[i]);
//加倍后装入S
if(j&&k+2*t[i]<=5200)dp[i][j][k]=max(dp[i][j][k],dp[i-1][j-1][k+2*t[i]]+v[i]);
//加倍后装入T
}
cout <<dp[n][s][2600]<<endl;
return 0;
}