Butteruni Blog
0%

2023杭电暑期多校4（C F J K L）

发表于 更新于 分类于

题目链接

由易到难分别为 LFC，J，FK

L. a-b Problem

对于 或 来说，无论让对方少拿还是自己多拿对答案造成的贡献都是一样的，因此每次都贪心即可，贪心依据为 

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
42
43
44
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
struct Node
{
    ll a,b;
};
bool cmp(Node A,Node B)
{
    return A.a+A.b>B.a+B.b;
}
int T;
int n;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>T;
    while(T--)
    {   
        ll ans=0;
        cin>>n;
        vector<Node>ls(n+1);
        for(int i=1;i<=n;i++)
        {
            cin>>ls[i].a>>ls[i].b;
        }
        sort(ls.begin()+1,ls.begin()+n+1,cmp);
        for(int i=1;i<=n;i++)
        {
            if(i%2==1)
            {
                ans+=ls[i].a;
            }
            else
            {
                ans-=ls[i].b;
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

F. PSO

显然要么两条边要么一条边，特殊判断 的情况即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
double mx,ans;
int main()
{
    int t;
    scanf("%d",&t);
    mx = 2.0;
    while(t--)
    {
        long long n;
        scanf("%lld",&n);
        ll cnt1 = n * (n - 1) / 2;
        ll cnt2 = n - 1;
        ans = (cnt1 * 2.0 - cnt2) / cnt1;
        if(n == 2)
            mx = 1.0;
        printf("%.9lf %.9lf\n",ans,mx);
    }
}

C. Simple Set Problem

读入所有元素后按元素大小升序排列，之后二分答案，每次check的过程使用单调队列优化

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PLL;
const int N=1e6+10;
ll m;
vector<PLL>ls;
int T;
int n;
bool check(ll val)
{
    vector<ll>st(n+1);
    ll cnt=0,l=0,r=0;
    for(int i=0;i<ls.size();i++)
    {
        if(ls[i].first>ls[0].first+val)break;
        r=i;
        if(!st[ls[i].second])cnt++;
        st[ls[i].second]++;
    }
    bool flag=false;
    if(cnt==n)flag=true;
    while(!flag&&r<ls.size()&&l<=r)
    {
        ll h=ls[l].first;
        while(l<ls.size()&&ls[l].first==h)
        {
            st[ls[l].second]--;
            if(!st[ls[l].second])cnt--;
            l++;
        }
        h=ls[l].first;
        while(r+1<ls.size()&&ls[r+1].first<=h+val)
        {
            if(!st[ls[r+1].second])cnt++;
            st[ls[r+1].second]++;
            r++;
        }
        if(cnt==n)
        {
            flag=true;
        }
        if(r==ls.size()-1)break;
    }
    return flag;
}
int main()
{
    std::ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>T;
    
    while(T--)
    {
        m = 2e9;
        ls.clear();
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            int t;
            cin>>t;
            ll mm = 0;
            for(int j=1;j<=t;j++)
            {
                ll a;
                cin>>a;
                mm = max(mm,a);
                ls.push_back({a,i});
            }
            m = min(mm,m);
        }
        sort(ls.begin(),ls.end());
        ll l=0,r=(ls[ls.size()-1].first-ls[0].first);
        while(l<r)
        {
            ll mid=(l+r)>>1;
            if(check(mid))r=mid;
            else l=mid+1;
        }
        // cout<<check(0)<<"---\n";
        cout<<l<<"\n";
    }
    return 0;
}

J. Kong Ming Qi

猜猜题，当为一行或一列时答案为 ，否则只在 时答案为 ，其余情况答案为 

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
#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
int T;
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--)
    {
        int n,m;
        cin>>n>>m;
        int mn=min(n,m),mx=max(n,m);    
        int ans = 1;
        if(mn == 1)
            ans = (mx + 1) / 2;
        else if(mn % 3 == 0 || mx % 3 == 0)
        {
            ans += 1;
        }
        cout << ans << '\n';
    }
    return 0;
}

F. Guess

简单的莫比乌斯反演题，属于知道有这个东西就会做的水平。

对于 定义 ， 则有 列举几个数之后发现若 只存在唯一质因数 ， 则 ，否则 ，于是只要判断 是否存在多个质因数即可，考虑 的范围使用Miller_Rabin大数判素。

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll mod = 998244353;
int T;
ll max_factor, n;

ll gcd(ll a,ll b)
{
    return (!b)?a:gcd(b,a%b);
}

// a^b % mod
ll power(ll a,ll b,ll mod) 
{
	ll sum=1;
	while(b) 
    {
		if(b&1)sum=(__int128)sum*a%mod;
		a=(__int128)a*a%mod;
		b>>=1;
	}
	return sum;
}

bool Miller_Rabin(ll p) // 判断素数
{  
    if(p<2)return false;
    if(p==2)return true;
    if(p==3)return true;
    ll d=p-1,r=0;
    while(!(d&1))++r,d>>=1;  // 将d处理为奇数
    for(ll k=0;k<10;k++) 
    {
        ll a=rand()%(p-2)+2;
        ll x=power(a,d,p);
        if(x==1||x==p-1)continue;
        for(int i=0;i<r-1;i++) 
        {
            x=(__int128)x*x%p;
            if(x==p-1)break;
        }
        if(x!=p-1) return false;
    }
    return true;
}

ll Pollard_Rho(ll x) 
{
    ll s=0,t=0;
    ll c=(ll)rand()%(x-1)+1;
    int step=0,goal=1;
    ll val=1;
    for(goal=1;;goal*=2,s=t,val=1) // 倍增优化
    {  
        for(step=1;step<=goal;step++) 
        {
            t=(__int128)t*t%x;
            t=(t+c)%x;
            val=(__int128)val*abs(t-s)%x;
            if((step%127)==0) 
            {
                ll d=gcd(val,x);
                if(d>1)return d;
            }
        }
        ll d=gcd(val,x);
        if(d>1)return d;
    }
}

void fac(ll x) 
{
    if(x<=max_factor||x<2)return;
    if(Miller_Rabin(x))// 如果x为质数 
    {              
        max_factor=max(max_factor, x);  // 更新答案
        return;
    }
    ll p = x;
    while(p>=x)p=Pollard_Rho(x);  // 使用该算法
    while((x%p)==0)x/=p;
    fac(x);fac(p);  // 继续向下分解x和p
}

int main() 
{
    srand(time(0));
    scanf("%d",&T);
    while(T--) 
    {
        max_factor=0;
        scanf("%lld",&n);
        fac(n);
        if(max_factor==n)  // 最大的质因数即自己
        {
            printf("%lld ",n % mod);
        }
        else
        {
            if(n == 1)
            {
                printf("1 ");
            }else 
            {
                ll mx = max_factor;
                while(mx < n)
                {
                    mx = mx * max_factor;
                }
                if(mx == n)
                {
                    printf("%lld ",max_factor % mod);
                }else 
                {
                    printf("1 ");
                }
            }
        }
    }
    return 0;
}

K. Circuit

不算难的图论题。

首先我们考虑一个环如何才能不重不漏地被计算。假设环上有点 ，如果走完floyd之后进行判环，则这个环在环上所有点处都有可能参与计数，因此判环的过程应当在floyd的过程中进行，同时为了保证每个环被计算一次，我们将环上编号最小的点 作为环的起点进行计数，此时所有将编号大于 的点 作为起点的环都已被统计完，因此这些点都可能作为以 为起点的环的一部分。于是若 与 所形成的环小于当前最小环则更新最小环并将答案改为当前环可能组合方案，若等于则答案直接加上当前方案数

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const ll inf = 1e18;
const int N = 510;
ll dis[N][N];
ll link[N][N];
ll cnt[N][N];
ll mn,ans;
int t;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n,m;
        cin >> n >> m;
        for(int i = 1;i <= n;++i)
        {
            for(int j = 1;j <= n;++j)
            {
                link[i][j] = 0;
                cnt[i][j] = 0;
                dis[i][j] = inf;
                if(i == j)
                    dis[i][j] = 0;
            }
        }
        for(int i = 1;i <= m;++i)
        {
            int a,b;
            ll w;
            cin >> a >> b >> w;
            dis[a][b] = w;
            cnt[a][b] = 1;
            link[a][b] = w;
        }
        mn = inf,ans = 0;
        for(int k = n;k >= 1;--k)
        {
            for(int i = 1;i <= n;++i)
            {
                for(int j = 1;j <= n;++j)
                {
                    if(dis[i][j] > dis[i][k] + dis[k][j])
                    {
                        dis[i][j] = dis[i][k] + dis[k][j];
                        cnt[i][j] = cnt[i][k] * cnt[k][j] % mod;
                    }else if(dis[i][j] == dis[i][k] + dis[k][j])
                    {
                        cnt[i][j] = (cnt[i][k] * cnt[k][j] + cnt[i][j]) % mod;
                    }
                }
            }
            for(int i = k + 1;i <= n ;++i)
            {
                if(link[k][i])
                {
                    if(link[k][i] + dis[i][k] < mn)
                    {
                        mn = link[k][i] + dis[i][k];
                        ans = cnt[i][k];
                    }else if(link[k][i] + dis[i][k] == mn)
                    {
                        ans = (ans + cnt[i][k]) % mod;
                    }
                }
            }
        }
        if(mn == inf)
            cout << -1 << " " << -1 << '\n';
        else 
            cout << mn << " " << ans << '\n';
    }
}