【题目记录】——第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（上海）

2022/1/24 12:34:26

编程Tag： int long 程序设计 include DP ll 46 frac ICPC

本文主要是介绍【题目记录】——第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（上海），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

D Strange_Fractions 思维+数学
E Strange_Integers 思维
G Edge Groups 思维+数学
I Steadily Growing Steam DP

题目集地址第 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加倍直接进行状态转移即可