2021 ICPC上海站补题

65 阅读 0 评论 43 点赞

我是靠谱客的博主寒冷跳跳糖，这篇文章主要介绍2021 ICPC上海站补题，现在分享给大家，希望可以做个参考。

D.Strange_Fractions—暴力

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define int long long
void solve()
{
    int p,q;cin>>p>>q;
    int t=__gcd(p,q);
    p/=t;q/=t;
    bool f=true;
    for(int a=1;a*a<=q;a++)
    {
    	if(q%a)continue;
        int b=q/a;
        if(p*a*b==q*(a*a+b*b))
        {
            cout<<a<<" "<<b<<'n';
            f=false;break;
        }
    }
    if(f)cout<<"0 0"<<'n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--)solve();
}

E.Strange_Integers–贪心

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define int long long
int n,k;
int a[100010];
void solve()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+n+1);
    int res=0;
    for(int i=1,maxv=-2e9;i<=n;i++)
    {
        if(maxv+k<=a[i])
        {
            res++;
            maxv=a[i];
        }
    }
    cout<<res<<'n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;T=1;
    while(T--)solve();
}

G.Edge Groups–树形DP+预处理

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
const int mod = 998244353,N = 100010;
#define int long long
vector<int>g[N];
int res=1;
int pre[N];
bool vis[N];
void dfs(int u,int fa)
{
    int cnt=0;
    for(auto v : g[u])
    {
        if(v==fa)continue;
        dfs(v,u);
        if(vis[v])cnt++;
    }
    if(cnt&1)res=res*cnt%mod*pre[cnt-1]%mod;
    else res=res*pre[cnt]%mod,vis[u]=true;
}

signed main()
{
    pre[0]=1;
    for(int i=2;i<N;i+=2)pre[i]=pre[i-2]*(i-1)%mod;
    
    int n;cin>>n;
    for(int i=1,a,b;i<n;i++)
    {
        cin>>a>>b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1,-1);
    cout<<res<<'n';
}

I.Steadily Growing Steam–01背包

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
#define int long long
int f[2][110][5210];
int v[110],t[110];
int n,K;
signed main()
{
    cin>>n>>K;
	for(int i=1;i<=n;i++)cin>>v[i]>>t[i];
    
    for(int i=0;i<=K;i++)
        for(int j=0;j<=5200;j++)
            f[0][i][j]=-1e18*(j!=2600);
    
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=K;j++)
        {
            for(int k=0;k<=5200;k++)
            {
                f[i&1][j][k]=f[i-1&1][j][k];
                if(k>=t[i])f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][j][k-t[i]]+v[i]);
                if(k+t[i]<=5200)f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][j][k+t[i]]+v[i]);
                if(j&&k>=2*t[i])f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][j-1][k-2*t[i]]+v[i]);
                if(j&&k+2*t[i]<=5200)f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][j-1][k+2*t[i]]+v[i]);
            }
        }
    }
    cout<<f[n&1][K][2600]<<'n';
}