极度糟糕的发挥，但希望能是一次敲响警钟的机会吧。

[1001 Median Problem]

solution

题面：

做法：

[1002 Kanade Doesn’t Want to Learn CG]

solution

题面：签到。

做法：

[1003 GCD on Tree]

solution

题面：

做法：

[1004 Primality Test]

solution

题面： 表示大于 且最小的质数，给出 ，问 是否是质数。

做法：首先我们知道 后， 肯定都是奇数。而 和 已经是相邻的质数了，所以中间就没有质数了，所以一定是合数。而 的时候是质数。

1
2
3
4
5
6
7
8
9
10
11
12
13
//2021.10.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
namespace MAIN{
    inline void MAIN(){
        res Case=read();
        for(res T=1;T<=Case;T++){
            RG LL x=Read();
            puts(x==1?"YES":"NO");
        }
    }
}

[1005 Monopoly]

solution

题面：给出一个 个点的环，每次只能向顺时针走一步，从 开始走，走到一个新的点就会得到这个点的权值。多次询问，每次询问一个 ，问最少多少步能得到 ？

做法：真的难写这题。

首先想到按一圈的总和取模，大致可以写出一条式子，然后有一些限制。利用这些限制存在的某些单调性维护一下，发现每次可以二分一下，就得出答案了。

具体地我已经忘记了，当时写的好麻烦只记得。时间复杂度 。

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
//2021.10.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e5+10;
namespace MAIN{
    int n,m;
    LL sum;
    int a[N];
    LL s[N];
    vector<pair<LL,int> >P[N],F[N];
    inline LL get(pair<LL,int> x){
        return 1ll*x.se*sum-1ll*n*x.fi;
    }
    map<LL,int> A,M;
    inline LL g(RG LL x,pair<LL,int> y){
        return 1ll*(x-y.fi)/sum*n+y.se;
    }
    inline LL aqua(RG LL x){
        return x<0?x+sum:x;
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            map<LL,int>().swap(A);
            map<LL,int>().swap(M);
            n=read(),m=read(),sum=0;
            for(res i=1;i<=n;i++){
                a[i]=read(),sum+=a[i];
            }
            res fl=0;
            if(sum<0){
                sum=-sum;
                for(res i=1;i<=n;i++)a[i]=-a[i];
                fl=1;
            }
            RG LL S=0;
            for(res i=1;i<=n;i++){
                if(!A.count(S))A[S]=i-1;
                S+=a[i];
            }
            if(!sum){
                while(m--){
                    RG LL x=Read();
                    if(A.count(x))printf("%d\n",A[x]);
                    else puts("-1");
                }
                continue;
            }
            res idx=0;
            if(!M[aqua(s[0]%sum)])M[aqua(s[0]%sum)]=++idx,vector<pair<LL,int> >().swap(P[idx]),vector<pair<LL,int> >().swap(F[idx]);
            P[M[aqua(s[0]%sum)]].pb(mp(s[0],0));
            for(res i=1;i<=n;i++){
                s[i]=s[i-1]+a[i];
                if(!M[aqua(s[i]%sum)])M[aqua(s[i]%sum)]=++idx,vector<pair<LL,int> >().swap(P[idx]),vector<pair<LL,int> >().swap(F[idx]);
                P[M[aqua(s[i]%sum)]].pb(mp(s[i],i));
            }
            for(res i=1;i<=idx;i++)sort(P[i].begin(),P[i].end());
            for(res j=1;j<=idx;j++){
                res sz=int(P[j].size())-1;
                F[j].pb(P[j][0]);
                for(res i=1;i<=sz;i++){
                    if(get(P[j][i])<get(F[j].back()))F[j].pb(P[j][i]);
                }
            }
            while(m--){
                RG LL x=Read();
                if(fl)x=-x;
                RG LL p=M[aqua(x%sum)];
                res l=0,r=int(F[p].size())-1,ret=-1;
                while(l<=r){
                    res mid=(l+r)>>1;
                    if(F[p][mid].fi<=x)l=mid+1,ret=mid;
                    else r=mid-1;
                }
                if(ret==-1)puts("-1");
                else printf("%lld\n",g(x,F[p][ret]));
            }
        }
    }
}

[1006 Nun Heh Heh Aaaaaaaaaaa]

solution

题面：签到。

做法：

[1007 Occupying Grids]

solution

题面：

做法：

[1008 Subpermutation]

solution

题面：把所有 的排序按字典序大小排在一起，问长度为 的排列出现在这个序列里的总次数之和。

做法：当时大概就考虑一个排列要被分成三块，然后枚举了下前两块的长度，然后可以写出一条式子，那条式子是个 ，里面有一些组合数。然后这些组合数拆开一下，发现只用预处理一些简单的东西，就过了，具体都忘了。时间复杂度 。

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
//2021.10.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e6+10;
namespace MAIN{
    int n,m;
    int fac[N],inv[N];
    inline int C(const res &x,const res &y){
        return mul(fac[x],mul(inv[y],inv[x-y]));
    }
    int sum[N];
    inline void MAIN(){
        fac[0]=fac[1]=inv[0]=inv[1]=sum[1]=1;
        for(res i=2;i<=N-10;i++)fac[i]=mul(fac[i-1],i),inv[i]=mul(inv[kcz%i],kcz-kcz/i);
        for(res i=2;i<=N-10;i++)inv[i]=mul(inv[i-1],inv[i]),sum[i]=Add(sum[i-1],inv[i]);
        res Case=read();
        while(Case--){
            n=read(),m=read();
            res ans=mul(mul(fac[m],fac[n-m]),n-m+1);
            add(ans,mul(fac[n-m],mul(fac[m],m-1)));
            add(ans,kcz-mul(fac[m],sum[m-1]));
            printf("%d\n",ans);
        }
    }
}

[1009 Public Transport System]

solution

题面：一张有向图，每条边有权值 ，一条路径设为 ，定义这条路径的长度为 ，求 到其他点的最短路长。

做法：考虑按边数拆点，若将可以减少权值的边直接相连，则边数达到 。但注意到边权值是单调的，所以可以将相邻的拆出的边连一条边，其余只用连到后继即可。边数点数都是 ，总复杂度 。

（ 若没看懂可以看代码

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
//2021.10.12 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=4e5+10;
namespace MAIN{
    int n,m;
    struct E{
        int next,to,val;
        E() {}
        E(res next,res to,res val):next(next),to(to),val(val) {}
    }edge[N<<1];
    int head[N],cnt;
    inline void addedge(const res &u,const res &v,const res &w){
        edge[++cnt]=E(head[u],v,w),head[u]=cnt;
    }
    struct P{
        int to,a,b,id;
        P() {}
        P(res to,res a,res b,res id):to(to),a(a),b(b),id(id) {}
        inline bool operator < (const RG P &x) const {
            return a<x.a;
        }
    };
    int pos[N];
    vector<P> G[N],E[N];
    LL dis[N];
    int vis[N];
    priority_queue<Pair,vector<Pair>,greater<Pair> >Q;
    int du[N],fir[N];
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),m=read(),cnt=0;
            for(res i=1;i<=n+m;i++)head[i]=-1;
            for(res i=1;i<=n;i++)vector<P>().swap(G[i]),vector<P>().swap(E[i]),du[i]=0;
            for(res i=1;i<=m;i++){
                res u=read(),v=read(),a=read(),b=read();
                G[u].pb(P(v,a,b,i)),E[v].pb(P(u,a,b,i)),du[u]++;
            }
            for(res i=1;i<=n;i++)fir[i]=fir[i-1]+du[i-1]+1,sort(G[i].begin(),G[i].end()),sort(E[i].begin(),E[i].end()),reverse(G[i].begin(),G[i].end()),reverse(E[i].begin(),E[i].end());
            for(res x=1;x<=n;x++){
                res i=1;
                for(auto tox:G[x])pos[tox.id]=i++;
            }
            for(res x=1;x<=n;x++){
                res sz=int(G[x].size())-1,i=sz;
                for(res SZ=int(E[x].size())-1,j=SZ;j>=0;j--){
                    while(i>=0&&G[x][i].a<=E[x][j].a)i--;
                    addedge(fir[E[x][j].to]+pos[E[x][j].id],fir[x]+i+1,E[x][j].a-E[x][j].b),addedge(fir[E[x][j].to],fir[x]+i+1,E[x][j].a);
                }
                for(i=0;i<=sz;i++)addedge(fir[x]+i+1,fir[x]+i,0);
            }
            for(res i=1;i<=n+m;i++)dis[i]=INF,vis[i]=0;
            dis[1]=0,vis[1]=1;
            Q.push(mp(dis[1],1));
            while(!Q.empty()){
                res u=Q.top().se;
                Q.pop();
                vis[u]=0;
                for(res i=head[u];~i;i=edge[i].next){
                    res tox=edge[i].to;
                    if(dis[tox]>dis[u]+edge[i].val){
                        dis[tox]=dis[u]+edge[i].val;
                        if(!vis[tox])Q.push(mp(dis[tox],tox)),vis[tox]=1;
                    }
                }
            }
            for(res i=1;i<=n;i++)printf("%lld%c",dis[fir[i]]==INF?-1:dis[fir[i]],i==n?'\n':' ');
        }
    }
}

[1010 Bigraph Extension]

solution

题面：

做法：

[1011 Jumping Monkey]

solution

题面：一棵树，每个点有权值，从一个节点能跳到另一个节点当且仅当另一个节点的权值是这一条路径上的最大值，问最多能跳几次。

做法：考虑 的过程，每次加入一个最小权值的点，那么就可以让他所处的已经存在的连通块的所有点答案加一，于是并查集维护这个过程就好了，有点类似 重构树？时间复杂度 。

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
//2021.10.10 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=2e5+10;
namespace MAIN{
    int n;
    int fa[N];
    Pair a[N];
    int tag[N];
    int idx;
    int rt[N];
    inline int find(res x){
        while(x!=rt[x])x=rt[x]=rt[rt[x]];
        return x;
    }
    vector<int> G[N],E[N];
    int vis[N];
    void dfs(res x){
        vis[x]=1;
        for(auto tox:E[x]){
            tag[tox]+=tag[x],dfs(tox);
        }
    }
    inline void MAIN(){
        res Case=read();
        while(Case--){
            n=read(),idx=n;
            for(res i=1;i<=n;i++)vector<int>().swap(G[i]);
            for(res i=1;i<n;i++){
                res u=read(),v=read();
                G[u].pb(v),G[v].pb(u);
            }
            for(res i=1;i<=n;i++)a[i]=mp(read(),i),fa[i]=0,rt[i]=tag[i]=0;
            sort(a+1,a+n+1);
            for(res i=1;i<=n;i++){
                res x=a[i].se;
                idx++;
                rt[idx]=idx,fa[idx]=0;
                for(auto tox:G[x]){
                    if(!fa[tox])continue;
                    res RT=find(rt[tox]);
                    rt[RT]=idx,fa[RT]=idx;
                }
                rt[x]=idx,fa[x]=idx;
                tag[idx]=1;
            }
            for(res i=1;i<=idx;i++)vector<int>().swap(E[i]),vis[i]=0;
            for(res i=1;i<=idx;i++)E[fa[i]].pb(i);
            for(res i=idx;i;i--){
                if(!vis[i])dfs(i);
            }
            for(res i=1;i<=n;i++)printf("%d\n",tag[i]);
        }
    }
}

[1012 Contest Remake]

solution

题面：给出一个 和 个数，问多少种数的集合，满足它们的积小于等于 且集合的数都不是那 个数。

做法：暴搜，剪枝，可以注意到大于根号的只有一个数，可以 预处理出一部分，反正就是暴搜，只不过我写的没过。