1002 Graph Theory Class

题意：

给定一个 $n$ 个结点的完全无向图， $i,j$ 结点间的权值为 $lcm(i+1,j+1)$ ，求最小生成树的值

题解：

分析可以发现一个合数的贡献就是它本身，而质数和 $2 \sim n+1$ 的 $lcm$ 为两倍的质数，因此最终结果就是 $3 \sim n+1$ 中所有合数的和加上两倍的所有质数的和。那么就是 $3 \sim n+1$ 加上质数和， $3 \sim n+1$ 的和就是 $\frac{(n+1)·(n+2)}{2}-3$ ，而质数和可用min25筛求。
要注意 $\frac{(n+1)·(n+2)}{2}$ 用long long会爆精度。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000010;
ll prime[maxn], id1[maxn], id2[maxn], f[maxn];
ll g[maxn], sum[maxn], a[maxn],T,n,p;
ll findID(ll x){return x <= T ? id1[x] : id2[n / x];}
ll calc(ll x){return x * (x + 1) / 2 - 1;}
void print(__int128 x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}

inline void init()
{
    ll cnt = 0,m = 0;
    T = sqrt(n + 0.5);
    for (ll i = 2; i <= T; i++)
    {
        if (!f[i])
        {
            prime[++cnt] = i;
            sum[cnt] = sum[cnt - 1] + i;
        }
        for (ll j = 1; j <= cnt && i * prime[j] <= T; j++)
        {
            f[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
    for (ll l = 1; l <= n; l = n / (n / l) + 1)
    {
        a[++m] = n / l;
        if (a[m] <= T)
            id1[a[m]] = m;
        else
            id2[n / a[m]] = m;
        g[m] = calc(a[m]);
    }
    for (ll i = 1; i <= cnt; i++)
        for (ll j = 1; j <= m && (ll)prime[i] * prime[i] <= a[j]; j++)
            g[j] = g[j] - (ll)prime[i] * (g[findID(a[j] / prime[i])] - sum[i - 1]);
}

int main()
{
    int TT;
    scanf("%d",&TT);
    while(TT--)
    {
        scanf("%lld%lld", &n,&p);
        n++;
        init();
        print(((__int128)n*(n+1)/2-5+g[findID(n)])%p);
        puts("");
        //printf("%lld\n",(calc(n)-4+g[findID(n)])%p);
    }
    return 0;
}

1003 Express Mail Taking

题意：

有 $n$ 个快递柜，其中要去 $m$ 个快递柜 $a_m$ 中取快递，每次只能取一个快递，而且每次取快递前都要先去指定的第 $k$ 个快递柜解锁，从 $1$ 号点进入，并且要从 $1$ 号点离开，求取快递花费的最少距离

题解：

贪心，只要保证最后一次取的快递离 $1$ 号点最近即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+5;
int a[maxn];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=m;i++)
            scanf("%d",&a[i]);
        sort(a+1,a+m+1);
        ll ans = 0;
        if(a[m]<=k)
        {
            ans = 2*(k-1);
            for(int i=m;i>=2;i--)
                ans+=2*(k-a[i]);
        }
        else if(a[1]>=k)
        {
            ans = a[m]-1+(a[m]-k);
            for(int i=2;i<m;i++)
                ans += 2*(a[i]-k);
            ans += (a[1]-k)+(a[1]-1);
        }
        else
        {
            ans = a[m]-1+(a[m]-k);
            for(int i=2;i<m;i++)
                ans += 2*abs(a[i]-k);
            ans += k-1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

1005 Lunch

题意：

给定 $n$ 个数字，每次操作可以选择一个数字 $x$ ，把它变成 $k$ 个 $\frac{x}{k}$ ( $k$ 是 $x$ 的因子）。选择的数不能为 $1$ .因此当只剩 $1$ 时则判为输

题解：

对于一个数 $x$ 来说，它由若干个质因子组成。对于一个奇数质因子 $y$ ， $x$ 被拆成 $y$ 个 $\frac{x}{y}$ ，因为 $y$ 是奇数，相当于变成了 $1$ 个 $\frac{x}{y}$ 的情况。因此最多只能操作 $x$ 的奇数质因子次，会变成 $2^{m}$ 次，当遇到 $2^{m}$ 时，一个人操作后，另一个人跟着做同样操作则必输。因此每个数相当于一堆为（奇数质因子个数+ [ $x$ 为偶数]）个数的石子，因此问题就转化为标准的nim博弈

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100;
int isp[maxn], p[maxn];
void init()
{
    for (int i = 2; i < maxn; i++)
    {
        if (isp[i] == 0)
            p[++p[0]] = i;
        for (int j = 1; j <= p[0] && i * p[j] < maxn; j++)
        {
            isp[i * p[j]] = 1;
            if (i % p[j] == 0)
                break;
        }
    }
}
int main(void)
{
    init();
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;
        scanf("%d", &n);
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            int x;
            scanf("%d", &x);
            int num = 0;
            if (x % 2 == 0)
            {
                num++;
                while (x % 2 == 0)
                    x /= 2;
            }
            for (int j = 2; p[j] * p[j] <= x; j++)
                if (x % p[j] == 0)
                {
                    num++, x /= p[j];
                    while (x % p[j] == 0)
                        num++, x /= p[j];
                }
            if (x > 1)
                num++;
            ans ^= num;
        }
        puts(ans ? "W" : "L");
    }
    return 0;
}

1006 Robotic Class

题意：

定义 $n$ 个分段函数

$f(t,x) = \begin{cases} f(d_{t,0},c_{t,0}x+b_{t,0}) & x \leq a_{t,0}\\ f(d_{t,1},c_{t,1}x+b_{t,1}) & a_{t,0} \leq x \leq a_{t,1}\\ & \vdots \\ f(d_{t,k_{t-1}},c_{t,k_{t-1}}x+b_{t,k_{t-1}}) & a_{t,k_{t-2}} \leq x \leq a_{t,k_{t-1}} \\ f(d_{t,k_{t}},c_{t,k_{t}}x+b_{t,k_{t}}) & a_{t,1} < x \end{cases}$
其中 $f(n,x)=x$ ，判断 $\forall{i},1 \leq i \leq n,f(i,x)$ 是否为连续函数

$t$ 之间会形成 $DAG$ ，只有 $n$ 没有出边

题解：

$t$ 之间形成 $DAG$ ,因此考虑到从后往前拓扑排序，每次都判断一下 $f(d_{t,i},c_{t,i}a_{t,i}+b_{t,i})=f(d_{t,i+1},c_{t,i+1}a_{t,i}+b_{t,i+1})$ ，即左右边界的极限
模拟即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, K[505];
int a[505][2020], b[505][2020], c[505][2020], d[505][2020];
ll gao(int t, ll x, int cc)
{
    if (t == n)
        return x;
    int pos = lower_bound(a[t], a[t] + K[t], x) - a[t];
    if (pos < K[t] && x == a[t][pos] && cc == 1)
        pos++;
    return gao(d[t][pos], c[t][pos] * (ll)x + b[t][pos], c[t][pos] * cc);
}
int main()
{
    int T;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++)
    {
        printf("Case #%d: ", cas);
        scanf("%d", &n);
        for (int i = 1; i < n; i++)
        {
            scanf("%d", &K[i]);
            for (int j = 0; j <= K[i]; j++)
            {
                scanf("%d%d%d", &c[i][j], &b[i][j], &d[i][j]);
                if (j < K[i])
                    scanf("%d", &a[i][j]);
            }
        }
        int flag = 1;
        for (int i = n - 1; i >= 1; i--)
        {
            for (int j = 0; j < K[i]; j++)
            {
                ll left = gao(i, a[i][j], -1);
                ll right = gao(i, a[i][j], 1);
                ll mid = gao(i, a[i][j], 0);
                if (left != right || left != mid)
                {
                    flag = 0;
                    break;
                }
            }
            if (!flag)
                break;
        }
        puts(flag ? "YES" : "NO");
    }
    return 0;
}

1007 CCPC Training Class

题解：

看过了的人很多，观察样例猜一个出现最多次的字母次数就过了

#include <bits/stdc++.h>
using namespace std;
int a[26];
int main(){
    int t;cin>>t;
    for(int cas=1;cas<=t;cas++){
        string s;
        cin>>s;
        memset(a,0,sizeof a);
        for(int i=0;i<s.length();i++){
            a[s[i]-'a']++;
        }
        sort(a,a+26);
        printf("Case #%d: %d\n",cas,a[25]);
    }
    return 0;
}

1010 Reports

题意：

给定一个长度为 $n$ 的序列，询问序列是否不存在相邻且相等的元素

题解：

模拟即可

#include <bits/stdc++.h>
using namespace std;
int a[110];
int main(){
    int t;cin>>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>a[i];
        }
        bool flag=true;
        for(int i=1;i<n;i++){
            if(a[i]==a[i-1]){
                flag=false;
                break;
            }
        }
        puts(flag?"YES":"NO");
    }
    return 0;
}

1011 3x3 Convolution

题意：

给定一个 $n*n$ 的矩阵 $A$ 和一个 $3*3$ 的矩阵 $C$ ， $C_{x,y}=\sum_{i=1}^{min(n-x+1,3)}\sum_{j=1}^{min(n-y+1,3)}A_{x+i-1,y+j-1}K_{i,j}$ ， $C^{m}(A,K)=C(C^{m-1}(A,K),K)$ ,求 $lim_{t-> \infty}C^{t}(A,K)$

题解：

可以发现当除 $K[1][1]$ 外有不为 $0$ 的数时，值一定会流失，最终只能变为全 $0$ 矩阵。因此只有当 $K[1][1]$ 不为 $0$ 时才会为原矩阵。
具体证明：
图片说明

#include <bits/stdc++.h>
using namespace std;
int a[55][55],k[4][4];
int main(){
    int t;cin>>t;
    for(int cas=1;cas<=t;cas++){
        int n;
        cin>>n;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&a[i][j]);
            }
        }
        int sum=0;
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                scanf("%d",&k[i][j]);
                sum+=k[i][j];
            }
        }
        if(sum==k[0][0]){
            for(int i=0;i<n;i++){
                for(int j=0;j<n-1;j++){
                    printf("%d ",a[i][j]);
                }
                printf("%d\n",a[i][n-1]);
            }
        }
        else{
            for(int i=0;i<n;i++){
                for(int j=0;j<n-1;j++){
                    printf("0 ");
                }
                printf("0\n");
            }
        }
    }
    return 0;
}

2020CCPC网络选拔赛