你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛(上海)(D,E,G)

2021-12-1 20:41:04

题目

  • D Strange_Fractions
  • E Strange_Integers
  • G Edge Groups

题目链接.

D Strange_Fractions

当时在场内做志愿者,说实话看到题的第一眼确实不知道怎么写,然后再次来写题的时候才想明白。
式子等价于:
p q = a 2 + b 2 a ∗ b \frac pq =\frac {a^2+b^2 }{ a*b} qp=aba2+b2
暴力枚举a的值即可。
若有解:当a从1枚举到 p \sqrt{p} p 一定会存在 a 2 a^2 a2 + + + b 2 b^2 b2 = = = p p 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 n( n n n为奇数)的树分割为 n − 1 2 \frac {n-1}2 2n1条长度为2的路,求一共有多少分法。
思路:设某个点的子树有 x x x条边。
x x x为奇数时:边两两组合多出一条边一定与该点与其父节点的边相连;
x x x为偶数时:边恰好能两两组合。
s u m = 1 ∗ 3 ∗ 5 ∗ . . . . . i ( i < = n ) sum=1*3*5*.....i(i<=n) sum=135.....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;
}