2023杭电多校4

2023杭电多校4

a-b Problem

题目大意：

每个物品都有 a , b a,b a,b 两个值， A l i c e Alice Alice 拿到该物品得到 a a a的分数， B o b Bob Bob 拿到该物品得到 b b b 的分数。

基本思路：

以 a + b a+b a+b 的值对物品排序，按顺序取即可

代码：

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<unordered_map>
#include<stack>
using namespace std;
#define int long long int 
#define Paddi ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
struct Node 
{
    int a,b;
};
bool cmp(struct Node a,struct Node b)
{
    return a.a + a.b > b.a + b.b;
}
signed main()
{
    Paddi;
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        vector<struct Node> s(n);
        for (int i = 0; i < n; i++)
            cin >> s[i].a >> s[i].b;
        sort(s.begin(), s.end(), cmp);
        int ans1 = 0, ans2 = 0;
        for (int i = 0; i < n; i++)
        {
            if (i % 2 == 0)
                ans1 += s[i].a;
            else
                ans2 += s[i].b;
        }
        cout << ans1 - ans2 << endl;
    }
    return 0;
}

Simple Tree Problem

题目大意：

你有 q q q 个集合，你可以在每个集合取一个数，求取得数最大值和最小值之差

基本思路：

对所有数进行排序之后，枚举右端点。对于某个右端点，我们要找到一个左端点使得这段区间内的数包含了所有的集合，考虑采用双指针，加入一个数后维护目前区间内涵盖所有集合的数量

代码：

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <stack>
#include <array>
#include <vector>
using namespace std;
int read()
{
    int x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}
int main()
{
    int T;
    T = read();
    while (T--)
    {
        int q;
        q = read();
        vector<pair<int, int>> s;
        for (int i = 1; i <= q; i++)
        {
            int k;
            k = read();
            while (k--)
            {
                int x;
                x = read();
                s.push_back({x, i});
            }
        }
        sort(s.begin(), s.end());
        int cnt = q;
        int now = -1;
        vector<int> rec(q + 10, 0);
        int ans = 2e9;
        for (int i = 0; i < s.size(); i++)
        {
            pair<int, int> a = s[i];
            rec[a.second]++;
            if (now==-1)
            {
                if (rec[a.second] == 1)
                    cnt--;
                if(cnt==0)
                    now = 0;
            }
            if(now!=-1)
            {
            	while(rec[s[now].second]>1)
                	rec[s[now].second]--,now++;
            	ans = min(ans, a.first-s[now].first);
			}
        }
        printf("%d\n", ans);
    }
    return 0;
}

Kong Ming Qi

思维题

PSO

题目大意：

给你一张图，非 1 1 1 节点和节点 1 1 1 连一条边，求图上所有 ( i , j ) (i,j) (i,j)对的路径数学期望

思路：

特判 1 1 1,其他节点计算即可

代码：

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <unordered_map>
#include <stack>
using namespace std;
#define int long long int
#define Paddi ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

signed main()
{
    //Paddi;
    int T;
    cin >> T;
    while (T--)
    {
        double n;
        cin >> n;
        if (n == 2)
        {
            printf("%.9lf %.9lf\n", 1.0, 1.0);
        }
        else
        {
            double ans = ((2 * n - 3)*(n - 1) + (n - 1)) / ((n - 1) * n);
            printf("%.9lf %.9lf\n", ans, 2.0);
        }
    }
    return 0;
}

Guess

题目大意：

S ( n ) = ∑ d ∣ n μ ( n d ) ln ⁡ ( d ) S(n)=\sum_{d|n}\mu({n \over d}) \ln(d) S(n)=d∣n∑​μ(dn​)ln(d)
求
e s ( n ) e^{s(n)} es(n)

基本思路：

将公式转化为
∏ d ∣ n d μ ( n d ) \prod_{d|n} d^{\mu({n\over d})} d∣n∏​dμ(dn​)
打表发现当 n = p k , p ∈ P r i m e n=p^k,p\in Prime n=pk,p∈Prime,答案为 p p p，否则答案为 1 1 1.

我们判断 n n n 是否为质数，若是质数，直接输出

若不是质数，我们枚举 k k k,通过二分找到可能的 p p p，判断 p p p是否为质数

代码：

#include <bits/stdc++.h>

using namespace std;
#define int long long int
const int Mod = 998244353;
#define Paddi ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
int ri[70] = {
    0,
    0,
    1000000000,
    1000000,
    31622,
    3981,
    1000,
    372,
    177,
    100,
    63,
    43,
    31,
    24,
    19,
    15,
    13,
    11,
    10,
    8,
    7,
    7,
    6,
    6,
    5,
    5,
    4,
    4,
    4,
    4,
    3,
    3,
    3,
    3,
    3,
    3,
    3,
    3,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    2,
    1,
    1,
    1,
    1,
    1,
};
int qpow(int a, int b, int mod)
{
    int ans = 1;
    while (b)
    {
        if (b & 1ll)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans;
}
int mpow(int a, int b)
{
    int ans = 1;
    for (int i = 1; i <= b; i++)
        ans *= a;
    return ans;
}
long long quick_pow(long long x, long long p, long long mod)
{ 
    long long ans = 1;
    while (p)
    {
        if (p & 1)
            ans = (__int128)ans * x % mod;
        x = (__int128)x * x % mod;
        p >>= 1;
    }
    return ans;
}
bool Miller_Rabin(long long p)
{ 
    if (p < 2)
        return 0;
    if (p == 2)
        return 1;
    if (p == 3)
        return 1;
    long long d = p - 1, r = 0;
    while (!(d & 1))
        ++r, d >>= 1;
    for (long long k = 0; k < 10; ++k)
    {
        long long a = rand() % (p - 2) + 2;
        long long x = quick_pow(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 0;
    }
    return 1;
}

int msqrt(int n, int k)
{
    int l = 1, r = ri[k], ans = 1;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (mpow(mid, k) <= n)
            ans = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    return ans;
}
bool isp(int x)
{
    for (int i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
            return false;
    }
    return true;
}
signed main()
{

    int T;
    cin >> T;
    srand(time(NULL));
    while (T--)
    {
        int n;
        cin >> n;
        if (n == 1)
        {
            cout << 1 << ' ';
            continue;
        }

        if (Miller_Rabin(n))
        {
            cout << n % Mod << " ";
            continue;
        }
        else
        {
            int ans = 1;
            for (int i = 2; i <= 64; i++)
            {
                int t = msqrt(n, i);
                if ((mpow(t, i) == n) and (isp(t)))
                {
                    ans = t;
                    break;
                }
            }
            cout << ans % Mod << " ";
        }
    }
    return 0;
}

Data Generation

题目大意：

给你一个排列，最初的状态 a i = i a_i=i ai​=i,你有 m m m次的 s w a p swap swap操作，求 a i ≠ i a_i \neq i ai​=i的期望

基本思路：

对于整个排列来说， a j = j a_j=j aj​=j,的概率就是整个排列中 a i = i a_i=i ai​=i 的概率，我们只考虑某个位置 j j j,在进行 k k k 次操作后 a j = j a_j=j aj​=j的期望为 E k E_k Ek​

则我们有
E k + 1 = ( n − 1 ) 2 + 1 n 2 E k + 2 n − 2 n 2 n − 1 2 n − 2 ( 1 − E k ) = ( n − 1 ) 2 + 1 n 2 E k + n − 1 n 2 ( 1 − E k ) E k = n − 2 n E k + 2 n 2 E_{k+1}= \frac{(n-1)^2 +1}{n^2} E_k+\frac{2n-2}{n^2} \frac{n-1}{2n-2} (1-E_k)=\frac{(n-1)^2 +1}{n^2} E_k+\frac{n-1}{n^2} (1-E_k)\\ E_k=\frac{n-2}{n} E_k+\frac{2}{n^2} Ek+1​=n2(n−1)2+1​Ek​+n22n−2​2n−2n−1​(1−Ek​)=n2(n−1)2+1​Ek​+n2n−1​(1−Ek​)Ek​=nn−2​Ek​+n22​
令
n − 2 n = a , 2 n 2 = b \frac{n-2}{n}=a,\frac{2}{n^2}=b nn−2​=a,n22​=b
得到
E k = a k + b ( a k − 1 + a k − 2 + ⋯ + a 0 ) = a k + b ( 1 − a k 1 − a ) E_k=a^k+b(a^{k-1}+a_{k-2}+\dots+a^{0})=a^k+b(\frac{1-a^{k}}{1-a}) Ek​=ak+b(ak−1+ak−2​+⋯+a0)=ak+b(1−a1−ak​)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define Paddi ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int mod = 998244353;
int qpow(int a, int b)
{
    int ans = 1;
    while (b)
    {
        if (b & 1)
            ans = ans * a % mod;
        b >>= 1;
        a = a * a % mod;
    }
    return ans % mod;
}
signed main()
{
    Paddi;
    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        n%=mod;
        int invn = qpow(n, mod - 2);
        int a = ((n - 2 + mod) % mod);
        a = a * invn % mod;
        a = qpow(a, m);
        int t1 = (1 - a + mod) % mod;
        t1 = t1 * invn % mod;
        t1 = (t1 + a) % mod;
        int ans = (1 - t1 + mod) % mod;
        ans = (ans * (n % mod)) % mod;
        cout << ans << endl;
    }
    return 0;
}