B.Graph Theory Class—min25筛

题意：给定一个 n 个点的完全图，边权为 lcm(i+1,j+1)，求最小生成树的边权和

思路：设一点的值为 x（x>=3）

  • 若 x 为素数，则能找到的最小边为与点 1 的连边，权值为 2*x ；
  • 若 x 为合数，则一定可以找到一个因数 y+1，使得权值为 lcm(x+1,y+1)=x+1

因此只要求 2~n+1 的和，再加上该区间的素数和即可。记 tot 为 2~n+1 的所有素数的和

难点在于数据范围很大（1e10），时间复杂度为 O(n) 都会TLE。已知的方法有两种，第一个是分块打表，第二个是用 min25筛。在这里使用 min25筛

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1000010;

ll nn,mod;
//下面都是min25筛用到的辅助成员
ll prime[N],id1[N],id2[N],flag[N],ncnt,m;
ll g[N],sum[N],a[N],T,n;

//下面都是min25辅助函数
inline ll ID(ll x){
    return x <= T ? id1[x] : id2[n / x];
}

inline ll calc(ll x){
    return x * (x + 1) / 2 - 1;
}

inline void _min25(){
    //memset(flag,0,sizeof(flag));
    //memset(id1,0,sizeof(id1));
    //memset(id2,0,sizeof(id2));
    m=ncnt=0;
    T = sqrt(n + 0.5);
    for (ll i = 2; i <= T; i++) {
        if (!flag[i]) prime[++ncnt] = i, sum[ncnt] = sum[ncnt - 1] + i;
        for (ll j = 1; j <= ncnt && i * prime[j] <= T; j++) {
            flag[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 <= ncnt; i++)
        for (ll j = 1; j <= m && (ll)prime[i] * prime[i] <= a[j]; j++)
            g[j] = g[j] - (ll)prime[i] * (g[ID(a[j] / prime[i])] - sum[i - 1]);
}

inline ll getsum(ll x){//获得2~x内素数和
    n=x;
    _min25();
    return g[ID(n)]%mod;
}

ll quick_pow(ll a,ll b){//矩阵快速幂
    ll res=1,base=a%mod;
    while(b){
        if(b&1)
            res=(base*res)%mod;
        base=(base*base)%mod;
        b>>=1;
    }
    return res;
}

inline ll inv(ll a){//求逆元
    return quick_pow(a,mod-2);//求逆元
}

inline void solve(){
    cin>>nn>>mod;
    ll ans=((nn%mod)*(nn%mod)%mod+3*(nn%mod)%mod-8)%mod;
    ans=ans*inv(2)%mod;
    ans+=getsum(nn+1)%mod;
    ans%=mod;
    cout<<ans<<endl;
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

C.Express Mail Taking—思维+签到

题意：小孩要去取快件，有一排序号从 1 到 n 的柜子，相邻的柜子距离是 1，出入口在编号为 1 的柜子处。每次去快递前都要先去编号为 k 的柜子处输入口令来打开其他柜门（保证这个柜子不放东西并且每个柜子只放一个快件）再前往打开的柜门处取快件。拿完最后一个快件小孩就走向出入口。现在有 m 个快件要拿，给出 k 的位置，让你找出短的取完所有快件的路的长度

思路：除去去取第一个快件需要先走到 K 号柜以及取最后一个快件不用折返，其他取快件的操作可以分组看成快件与 K 号柜之间的折返操作，这些走过的距离是固定的，那么最短路就取决于在最后一次取快件的路径长短（因为最后一个快件的选择直接决定了是否需要走多余的折返路径）。

以下面为例：3 号柜相当于 K 号柜，那么选择一号柜的快件（距离出口最近的）作为最后一次取是最优解的，其他的快件都看成和 3 号柜之间的折返操作，而最后一次取快件在 K 号柜左边，和之前没算上的距离正好是起点和 3 号柜之间距离的折返，但是注意若是最后一次取快件的柜子还是在 K 号柜的右边，那么还是相当于多走了一个和 K 号柜之间距离的折返。所以真正能够缩小走过的距离的情况是最后一次取快件的柜子在 K 号柜左侧

综上：对于每个快件的柜子，都加和其和 K 号柜之间距离的二倍，再加上起点和 K 号柜之间距离的二倍。然后若是最近的一个柜子编号比 K 号柜小那么结果再减去其和 K 号柜之间距离的二倍。

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll read(){//快读后时间982ms很紧
    ll s=0,w=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-')w=-1;
    for(;isdigit(c);c=getchar())s=(s<<1)+(s<<3)+(c^48);
    return s*w;
}

inline void solve(){
    int n,m,k;
    n=read(),m=read(),k=read();
    int pos=1e9+100;//记录距离起点最近的快件柜子编号
    ll sum=0;//统计结果
    for(register int i=1;i<=m;i++){
        ll x;x=read();
        sum+=abs(x-k)*2;//到K号柜距离二倍 
        if(x<pos)pos=x;//更新pos
    }
    if(pos<k)sum-=abs(pos-k)*2;//如果pos比K小，可以少走一个折返距离
    sum+=2*(k-1);
    printf("%lld\n",sum);
}

signed main()
{
    ios::sync_with_stdio(false),cin.tie(0);
    int t;t=read();
    while(t--){
        solve();
    }
    return 0;
}

E.Lunch—Nim博弈

G.CCPC Training Class—签到

题意：语文阅读理解题——输出字符串中出现字符最多的数量

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<iostream>
#include<cstring>
using namespace std;
const int maxn=1e5+5;
char s[maxn];
int a[30];
int main()
{
    int t,k=1;
    cin>>t;
    while(t--)
    {
        cin>>s;
        memset(a,0,sizeof(a));
        int max=0;
        for(int i=0;s[i]!=0;i++)
        {
            a[s[i]-'a']++;
        }
        for(int i=0;i<26;i++)
          if(a[i]>max)
            max=a[i];
        printf("Case #%d: ",k++);
        cout<<max<<endl;
    }
}

J.Reports—签到

题意：麒麟臂筛选题——字符串中不能出现连续相同的字符，出现输出 NO

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<iostream>
using namespace std;

const int N=55;
int a[N];

signed main(){
    int t;cin>>t;
    while(t--){
        int n,f;
        scanf("%d",&n);
        f=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            if(i>0&&a[i]==a[i-1])
                f=1;
        }
        if(f)cout<<"NO"<<endl;
        else cout<<"YES"<<endl;
    }
 }

K.3x3 Convolution—思维+签到

题意：有一个 nxn 的矩阵 A 和一个 3x3 的矩阵 K，均为非负矩阵，并且 K 是一个和为 1 的分数矩阵。定义一个操作，对于矩阵 A，用矩阵 K 对 A 中的每个元素进行卷积操作——K 的左上角遍历 A 中每个元素，每一次覆盖对 A 中 3x3 范围内（范围不够的在 A 的边缘补上足够多的 0）的矩阵在 K 的作用下作带权求和运算。现在将矩阵 K 固定，拿 C 套娃无限次，求最终得到的矩阵

思路：用两个例子做实验，发现当且仅当 K11=1 时，无限套娃所得为原矩阵，否则每一次套娃所得矩阵的和越来越小，最终趋于 0（即零矩阵），因为左上角不是 1，那么肯定导致数在不断变小最终整个矩阵变为 0

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>
const int maxn = 55;
int A[maxn][maxn];
int K1[4][4];

signed main (){
    int T;scanf("%d", &T);
    while (T--){
        int n;scanf("%d", &n);
        //input matrix A and K'
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                scanf("%d", &A[i][j]);
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j)
                scanf("%d", &K1[i][j]);
        
        //solve
        int sum = 0;
        for (int i = 1; i <= 3; ++i)
            for (int j = 1; j <= 3; ++j)
                sum += K1[i][j];
        bool full_zero = true;//判断是否会最终矩阵趋于0
        if (K1[1][1] == sum) //K[1][1] == 1
            full_zero = false;
        
        //output
        for (int i = 1; i <= n; ++i){
            bool first = true;
            for (int j = 1; j <= n; ++j) {
                if (!first)
                    printf(" ");
                first = false;
                if (full_zero)
                    printf("0");
                else
                    printf("%d", A[i][j]);
            }
            printf("\n");
        }
        
    }
    return 0;
}