题目链接.

D Strange_Fractions

当时在场内做志愿者，说实话看到题的第一眼确实不知道怎么写，然后再次来写题的时候才想明白。
式子等价于:
$$\frac{p}{q}=\frac{a^2+b^2}{a\ast b}$$
暴力枚举a的值即可。
若有解：当a从1枚举到$\sqrt{p}$一定会存在$a^2$$+$$b^2$$=$$p$。

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define pii pair<int,int>
using namespace std;

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

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>t;
    while(t--)
    {
        cin>>p>>q;
        int x=gcd(p,q);
        p=p/x;
        q=q/x;
        int flag=0;
        for(int i=1;i*i<=p;i++)
        {
            int y=sqrt(p-i*i);
            if(i*i+y*y==p&&i*y==q)
            {
                cout<<i<<" "<<y<<"\n";
                flag=1;
                break;
            }
        }
        if(!flag)cout<<0<<" "<<0<<"\n";
    }

    return 0;
}

E Strange_Integers

签到。

#include<bits/stdc++.h>
#define ll long long
#define INF 0x3f3f3f3f
#define pii pair<int,int>
using namespace std;

int n,k;
int a[100010];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n>>k;
    for(int i=0;i<n;i++)cin>>a[i];
    sort(a,a+n);
    int now=a[0];
    int ans=1;
    for(int i=1;i<n;i++)
    {
        if(a[i]-now>=k)
        {
            now=a[i];
            ans++;
        }
    }
    cout<<ans<<"\n";

    return 0;
}

G Edge Groups

树形dp；
题意：把点为$n$($n$为奇数)的树分割为$\frac{n-1}{2}$条长度为2的路，求一共有多少分法。
思路：设某个点的子树有$x$条边。
$x$为奇数时：边两两组合多出一条边一定与该点与其父节点的边相连;
$x$为偶数时：边恰好能两两组合。
$sum=1\ast 3\ast 5\ast .....i(i<=n)$

#include<bits/stdc++.h>
#define ll long long
ll mod=998244353;
using namespace std;

int n;
ll f[100010];
vector<int>e[100010];

bool dfs(int x,int fa)
{
    f[x]=1;
    int cnt=0;
    for(int i=0;i<e[x].size();i++)
    {
        if(e[x][i]!=fa)
        {
            int y=e[x][i];
            if(dfs(y,x)==0)cnt++;
            f[x]=f[x]*f[y]%mod;
        }
    }
    for(int i=1;i<=cnt;i+=2)f[x]=f[x]*i%mod;
    return cnt%2;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<n;i++)
    {
        int u,v;cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs(1,0);
    cout<<f[1];

    return 0;
}