【2022杭电多校1】2022“杭电杯”中国大学生算法设计超级联赛（1）

2022“杭电杯”中国大学生算法设计超级联赛（1）

hdu7138-7149

1001 String

利用exkmp把s的每个后缀与s的lcp求出来

设后缀 $[i, n]$ 和 $s$ 的 $l c p$ 长度为 $x$

那么只有当 $\le x$ 时，会产生贡献，中间重合部分为 $k$ 的倍数的时候有贡献
找到第一个和最后一个 $k$ 的倍数的位置，把贡献差分一下即可

#include
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+5;
char s[maxn];
int n,z[maxn],k;
ll tag[maxn];
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        for(int i=1;i<=n;i++) z[i]=tag[i]=0;
        z[1]=n;
        for(int i=2,l=0,r=0;i<=n;i++)
        {
            if(i<=r) z[i]=min(z[i-l+1],r-i+1);
            while(i+z[i]<=n && s[i+z[i]]==s[z[i]+1]) z[i]++;
            if(i+z[i]-1>r) l=i,r=i+z[i]-1;
        }
        scanf("%d",&k);
        for(int i=0;i=i+k)
            {
                com=((com-i)/k)*k;
                tag[2*i+k]++;
                if(2*i+k+com<=n) tag[2*i+k+com]--;
            }
        }
        ll ans=1;
        for(int i=1;i<=n;i++)
        {
            if(i+k<=n) tag[i+k]+=tag[i];
            ans=ans*(tag[i]+1)%mod;
        }
        printf("%lld\n",ans);
    }
    return 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

1002 Dragon slayer

直接暴力枚举边集的选择情况，然后dfs判断是否能到达即可

时间复杂度 $O(2^nn^2)$

#include
using namespace std;
typedef long long ll;
int n,m,k;
int sx,sy,ex,ey;
int ans;
int p[18];
int ax[18],ay[18],bx[18],by[18];
int ban[257][257],id[16][16],cnt;
int vis[18][18];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void dfs(int x,int y)
{
    vis[x][y]=1;
    // printf("%d\n",n);
    for(int d=0;d<4;d++)
    {
        int tox=x+dx[d];
        int toy=y+dy[d];
        if(tox<0 || toy<0 || tox>=n || toy>=m || ban[id[x][y]][id[tox][toy]]) continue;
        if(vis[tox][toy]) continue;
        dfs(tox,toy);
    }
}
bool check()
{
    // printf("%d\n",n);
    for(int i=1;i<=k;i++)
    {
        if(p[i]) continue;
        if(ax[i]==bx[i])
        {
            int ymin=min(ay[i],by[i]);
            int ymax=max(ay[i],by[i]);
            for(int j=ymin;jans) return;
        if(check()) ans=gs;
        // printf("[%d :%d]\n",gs,vis[ex][ey]);
        return;
    }
    p[step+1]=0; dfs(step+1);
    p[step+1]=1; dfs(step+1);
}
int main()
{
    // freopen("a.in","r",stdin);
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        cnt=0;
        for(int i=0;i<=n;i++)
            for(int j=0;j<=m;j++)
                id[i][j]=++cnt;
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
        for(int i=1;i<=k;i++)
            scanf("%d%d%d%d",&ax[i],&ay[i],&bx[i],&by[i]);
        ans=k;
        dfs(0);
        // printf("[%d]\n",n);
        printf("%d\n",ans);
        // return 0;
    }
    return 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
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

1003 Backpack

n个物品，有体积和价值，给定容量为m的包，询问把包装满的最大xor价值

设 $f [i] [j] [k]$ 表示前i个物品，异或和为j，体积为k的是否可行

那么对于一个物品 $(v, w)$ ，转移为 $f[i][j][k]=f[i-1][j][k]|f[i-1][j\ xor\ v][k-v]$

可以用bitset优化

#include
using namespace std;
int n,m;
bitset <1025> f[2][1025],emp;
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        int x,y;
        for(int i=0;i<1024;i++)
            f[0][i]=f[1][i]=emp;
        int p=1;
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&x,&y);
            for(int j=0;j<1024;j++)
                f[p][j]=f[p^1][j]|(f[p^1][j^y]<

1004 Ball

给定坐标范围为 $(1, 1) - (m, m)$ 的n个点，求有多少三个无序点对满足曼哈顿距离的中位数是质数

我们把 $n^2$ 条边拿出来排序，把遍历过的边设成黑色，未经历过的设成白色，那么我们要求的就是一个点，到当前边的两个点 $(u, v)$ ，一条黑一条白的，每个点维护2个bitset表示连接点是黑/白的点集

时间复杂度 $O(\frac{n^3}{w})$

#pragma GCC optimize(3)
#include
using namespace std;
const int maxn=2e3+5;
int n,m;
bool vis[200005];
int pr[200005],cnt,tot;
inline int read()
{
    int x=0,f=1;
    char cc=getchar();
    while(cc!='-' && (cc<'0' || cc>'9')) cc=getchar();
    if(cc=='-') f=-1,cc=getchar();
    while(cc>='0' && cc<='9') x=x*10+cc-'0',cc=getchar();
    return x*f;
}
void init()
{
    vis[1]=1;
    for(int i=2;i<2e5+5;i++)
    {
        if(!vis[i])
            pr[++tot]=i;
        for(int j=1;j<=tot && 1ll*pr[j]*i<2e5+5;j++)
        {
            vis[i*pr[j]]=1;
            if(i%pr[j]==0) break;
        }
    }
}
struct point
{
    int x,y;
}p[maxn];
struct edge
{
    int x,y;
    int len;
}e[maxn*maxn];
bool cmp(edge x,edge y)
{
    return x.len W[maxn],B[maxn];
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int T; scanf("%d",&T);
    init();
    while(T--)
    {
        scanf("%d%d",&n,&m); cnt=0;
        // for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read();
        for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);
        for(int i=1;i<=n;i++) B[i].reset(),W[i].reset();
        for(int i=1;i<=n;i++)
            for(int j=i+1;j<=n;j++)
            {
                e[++cnt].x=i,e[cnt].y=j,e[cnt].len=dist(p[i],p[j]);
                W[i].set(j); W[j].set(i);
            }
        // printf("[%d]\n",cnt);
        sort(e+1,e+cnt+1,cmp);
        long long ans=0;
        for(int i=1;i<=cnt;i++)
        {
            // printf("%d\n",e[i].len);
            if(!vis[e[i].len]) ans+=(W[e[i].x]&B[e[i].y]).count()+(W[e[i].y]&B[e[i].x]).count();
            W[e[i].x].set(e[i].y,0); W[e[i].y].set(e[i].x,0);
            B[e[i].x].set(e[i].y,1); B[e[i].y].set(e[i].x,1);
        }
        printf("%lld\n",ans);
    }
    return 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
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

1006 Travel plan

题目规定了所有简单环都是奇环，所以不存在有环贴环（任意两个环没有公共边）

否则，若有公共边，两个环剩下的部分奇偶性相同，会有成一个新的偶环，不合题意

那么我们的图就是一个仙人掌

利用莫反可以把 $\gcd =k$ 的问题转换为求 $k\ | \gcd$ 的问题

我们把所有 $i$ 的倍数边拿出来，缩边双后，在DAG上dp计算路径数量

#include
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=2e5+5;
const int maxv=1e5+5;
int n,m,L;
struct edge
{
    int u,v,w;
}e[maxn];
int pr[maxv],cnt,mu[maxn];
bool vis[maxv];
vector  fac[maxv],q[maxn];
void init()
{
    mu[1]=1;
    for(int i=2;i G[maxn],GG[maxn<<1];
int dfn[maxn],low[maxn],dfstime;
int tot,st[maxn],top;
ll d[maxn];
void tarjan(int u,int fa)
{
    dfn[u]=low[u]=++dfstime;
    d[u]=0; st[++top]=u;
    for(int to:G[u])
    {
        if(!dfn[to])
        {
            tarjan(to,u);
            low[u]=min(low[u],low[to]);
            d[u]+=d[to];
            if(low[to]==dfn[u]) // bridge edge
            {
                ++tot;
                GG[tot].clear();
                int v=st[top];
                while(v!=to)
                {
                    GG[tot].push_back(v);
                    GG[v].push_back(tot);
                    top--; v=st[top];
                }
                top--; GG[tot].push_back(to);
                GG[to].push_back(tot);
                GG[tot].push_back(u);
                GG[u].push_back(tot);
            }
        }
        else
        {
            low[u]=min(low[u],dfn[to]);
            if(to!=fa) d[u]++,d[to]--;
        }
    }
}
ll f[maxn<<1];
void add(ll &x,ll y)
{
    x=(x+y)%mod;
}
void calc(int u,int fa,int id)
{
    for(int to:GG[u])
    {
        if(to==fa) continue;
        calc(to,u,id);
    }
    if(u<=n)
    {
        f[u]=1;
        for(int to:GG[u])
        {
            if(to==fa) continue;
            add(ans[id],f[u]*f[to]%mod);
            add(f[u],f[to]);
        }
    }
    else if(GG[u].size()==2)
    {
        f[u]=0;
        for(int to:GG[u])
        {
            if(to==fa) continue;
            add(f[u],f[to]);
        }
    }
    else
    {
        f[u]=0;
        for(int to:GG[u])
        {
            if(to==fa) continue;
            add(ans[id],f[u]*f[to]%mod);
            add(f[u],2ll*f[to]%mod);
        }
    }
}
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int T; scanf("%d",&T);
    init();
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&L);
        int x,y,z;
        for(int i=1;i<=L;i++) ans[i]=0,q[i].clear();
        for(int i=1;i<=m;i++)
        {
            scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
            for(int j:fac[e[i].w]) q[j].push_back(i);
        }
        vector  p;
        for(int i=1;i<=L;i++)
        {
            p.clear();
            for(int id:q[i])
            {
                int u=e[id].u,v=e[id].v;
                G[u].clear(); G[v].clear();
                GG[u].clear(); GG[v].clear();
                dfn[u]=dfn[v]=0; p.push_back(u); p.push_back(v);
            }    
            for(int id:q[i])
            {
                int u=e[id].u,v=e[id].v;
                G[u].push_back(v); G[v].push_back(u);
            }
            tot=n; dfstime=top=0;
            for(int u:p)
                if(!dfn[u]) tarjan(u,0),calc(u,0,i);
            // printf("[%d]:%d %lld\n",i,tot,ans[i]);
            // for(int j=1;j<=tot;j++)
            // {
            //     printf("%d: ",j);
            //     for(int k:GG[j]) printf("%d ",k);
            //     printf("\n");
            // }
        }
        for(int i=1;i<=L;i++) 
        {
            for(int j=2;i*j<=L;j++)
                ans[i]+=1ll*mu[j]*ans[i*j];
            ans[i]=(ans[i]%mod+mod)%mod;
        }
        ll res=0;
        for(int i=1;i<=L;i++) res^=ans[i];
        printf("%lld\n",res);
    }
    return 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
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168

1007 Treasure

我们先建立kruskal重构树

那么一次询问就相当于查询子树内所有类型的物品最大价值的和

注意到每种物品最多出现10次，我们对一个种类的物品建立虚树，维护每个点的上一个同种祖先的位置，给链做加法统计贡献，利用树状数组维护单点修改，子树求和即可

修改操作同理

时间复杂度 $O(10n\log n)$

#include 
using namespace std;
typedef long long ll;
const int maxn=400005;
struct edge
{
    int u,v,w;
}e[maxn];
int n,m,fa[21][maxn],w[21][maxn],q;
int f[maxn],c[maxn];
int dfn[maxn],mx[maxn],dep[maxn];
int sta[maxn],top,pos[maxn],dfstime;
ll val[maxn],C[maxn];
vector id[maxn],F[maxn],G[maxn];
vector V[maxn];
bool cmp(int a,int b)
{   
    return dfn[a]=0;i--)
    {
        int to=G[u][i];
        dep[to]=dep[u]+1,dfs(to);
    }
    mx[u]=dfstime;
}
int lca(int u,int v)
{
    if(dep[u]=0;i--) if(dep[fa[i][u]]>=dep[v]) u=fa[i][u];
    if(u==v) return u;
    for(int i=20;i>=0;i--) if(fa[i][u]!=fa[i][v]) u=fa[i][u],v=fa[i][v];
    return fa[0][u];
}
int lowbit(int x)
{
    return x&(-x);
}
void update(int x,ll z)
{
    // printf("[%d %lld]",x,z);
    while(x<=n)
    {
        C[x]+=z;
        x+=lowbit(x);
    }
}
ll query(int x)
{
    ll res=0;
    while(x)
    {
        res+=C[x];
        x-=lowbit(x);
    }
    return res;
}
int father(int x) { return (f[x]==x)?x:(f[x]=father(f[x])); }
bool cmpp(edge x,edge y)
{
    return x.w=0;i--)
                    id[u].push_back(lca(id[u][i],id[u][i+1]));
                sort(id[u].begin(),id[u].end(),cmp);
                tot=unique(id[u].begin(),id[u].end())-id[u].begin();
                while(id[u].size()>tot) id[u].pop_back();
                F[u].clear();
                int top=-1;
                for(int i=0;i=0 && dfn[id[u][i]]>mx[id[u][sta[top]]]) top--;
                    F[u].push_back((top==-1)?-1:sta[top]),sta[++top]=i;
                }
                V[u].clear();
                for(int i=0;i=0;i--)
                {
                    if(id[u][i]<=tn)
                        pos[id[u][i]]=i,V[u][i]=max(V[u][i],val[id[u][i]]);
                    if(F[u][i]!=-1) V[u][F[u][i]]=max(V[u][F[u][i]],V[u][i]);
                }
                for(int i=0;i=0;i--)
                    if(w[i][u]<=v)
                        u=fa[i][u];
                printf("%lld\n",query(mx[u])-query(dfn[u]-1));
            }
            else
            {
                // continue;
                int i,z;
                for(i=c[u],u=pos[u],z=V[i][u]+v;u!=-1 && z>V[i][u];u=F[i][u])
                {
                    update(dfn[id[i][u]],z-V[i][u]);
                    if(F[i][u]!=-1)
                        update(dfn[id[i][F[i][u]]],V[i][u]-z);
                    V[i][u]=z;
                }
            }
        }
    }
    return 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
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175

1009 Laser

如果确定了一个点在水平线上，也就是一个米子和横

那么我们结合另一个点就能讨论得到三个中心位置，依次判断是否能射到所有的n个点即可

我们再讨论第一个点所在直线的四种情况，可以理解为坐标系旋转 $45\degree$

共计12次判断，时间复杂度 $O (12 n)$

#include
using namespace std;
const int maxn=5e5+5;
int px[maxn],py[maxn];
int tx[maxn],ty[maxn];
int n;
bool ok(int x,int y)
{
    return (!x || !y || x==y || x==-y);
}
bool check(int x,int y)
{
    for(int i=1;i<=n;i++)
    {
        if(!ok(px[i]-x,py[i]-y))
            return 0;
    }
    return 1;
}
int main()
{
    int T; scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d%d",&tx[i],&ty[i]),px[i]=tx[i],py[i]=ty[i];
        int now=1;
        while(now

1011 Random

直接输出 $\frac{n-m}{2}$ 即可

#include
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
ll qpow(ll a,ll b)
{
    ll res=1;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
ll inv2=qpow(2,mod-2);
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    int T; scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        printf("%lld\n",1ll*(n-m)*inv2%mod);
    }
    return 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

1012 Alice and Bob

发现如果1个0，那么Alice必胜

如果有2个1/4个2/…，Alice必胜

如果有 $2^i$ 个 $i$ ，相当于一个 $i$ ，看最后是否能凑够一个0即可

注意爆longlong的问题，倒着写会好一点

#include
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
int c[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=0;i<=n;i++) scanf("%d",&c[i]);
        ll gs=1;
        int flag=0;
        for(int i=0;i<=n;i++)
        {
            if(c[i]>=gs)
            {
                flag=1;
                break;
            }
            gs-=c[i];
            gs*=2;
            if(gs>1000000) break;
        }
        if(flag) printf("Alice\n");
        else printf("Bob\n");
    }
    return 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