2023杭电多校第一场

手还是有点生(

随便写点东西.jpg

1001

实际上把链找出来之后就可以把树扔了(

然后在某个位置上出现的点它的出现位置就可以表示为$k*dis+b$，$b$是位置

对于$S$的每个数字，找它在$T$的位置，能拿到两个同余方程，形如$x = t_1(mod n)$和$x = t_2 (mod m)$找最小正整数解即可。

代码是学弟写的，摸了(

1002

$f[i][0/1/2]$表示当前点不选且被覆盖/选了/不选且不被覆盖

转移挺好写的

#include <bits/stdc++.h>
#define int long long
using namespace std;
int T;
const int inf = 1e9+7;
const int mx = 2e5+5;
int a[mx];
vector<int> G[mx];
int dp[mx][3];
void dfs(int Now,int fa){
    dp[Now][1] = a[Now];
    dp[Now][0] = dp[Now][2] = 0;
    bool flag = false;
    int chg = inf;
    for (auto v : G[Now]){
        if (v == fa) continue;
        dfs(v,Now);
        dp[Now][1] += min(dp[v][0],min(dp[v][1],dp[v][2]));
        dp[Now][2] += min(dp[v][1],dp[v][0]);
        if (dp[v][1]  > dp[v][0]){
            dp[Now][0] += dp[v][0];
            chg = min(chg,dp[v][1]-dp[v][0]);    
        }else{
            flag = true;
            dp[Now][0] += dp[v][1];
        }
    }
    if (!flag)
        dp[Now][0] += chg;
}
signed main(){
    scanf("%lld",&T);
    while (T--){
        int N;
        scanf("%lld",&N);
        for (int i = 1 ; i <= N ; i ++){
            scanf("%lld",&a[i]);
            G[i].clear();
            dp[i][0] = dp[i][1] = dp[i][2] = 0;
        }
        for (int i = 1 ; i < N ; i ++){
            int x,y;
            scanf("%lld%lld",&x,&y);
            G[x].push_back(y);
            G[y].push_back(x); 
        }
        dfs(1,1);
        printf("%lld\n",min(dp[1][1],dp[1][0]));
    }
    return 0;
}

1005

把串二倍延长一下，实际上枚举$M$个位置就可以把所有的可能串给枚举上

字符串哈希一下，存一下最小的$hash$值，最后直接比较即可。

*998244353被卡了，差评

#include<bits/stdc++.h>
using namespace std;
const int mx = 2e5+10;
const unsigned long long P = 429496729;
int N,M;
int T;
unsigned long long tt[mx]; 
unsigned long long p[mx];
unsigned long long pref[mx];
unsigned long long GetHash(int l, int r) {
    return pref[r] - pref[l - 1] * p[r - l + 1];
}
unsigned long long Hash[mx];
int main(){
    p[0] = 1;
    for (int i = 1 ; i <= mx - 10 ; i ++)
        p[i] = p[i-1] * P;
    cin >> T;
    while (T--){
        scanf("%d%d",&N,&M);
        for (int i = 1 ; i <= N ; i ++){
            Hash[i] = 0;
        }
        for (int i = 1 ; i <= N ; i ++){
            string ss;
            cin >> ss;
            ss = ss + ss;
            ss = ' ' + ss;
            int Len = ss.length();
            pref[0] = 0;
            for (int j = 1 ; j <= Len ; j ++){
                pref[j] = pref[j-1] * P + ss[j];
            }
            Hash[i] = pref[M];
            unsigned long long mn = Hash[i];
            for (int j = 1 ; j <= M ; j ++){
                unsigned long long x = GetHash(j,j+M-1); 
                mn = min(mn,x);
            }
            tt[i] = mn;
        }
        int Q;
        cin >> Q;
        while (Q--){
            int x,y;
            scanf("%d%d",&x,&y);
            if (tt[x] == tt[y]) printf("Yes");
            else printf("No");
            if (T!=0 || Q != 0) printf("\n"); 
        }
    }
} 

1008

签到，跳过.jpg

1012

根据树删边博弈，SG[x] = (SG[v]+1)的xor和

$v$是$x$的所有儿子

SG[root]如果是0先手赢

然后暴力换个根就好了，看有多少点的SG不是0

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int cnt = 0;
int read(){
    int f=1,k=0;
    char c=getchar();
    while(c<'0'||c>'9'){
        c=getchar(); 
    }
    while(c>='0'&&c<='9'){
        k=k*10+c-'0';
        c=getchar();
    }
    return f*k;
}
const int mx = 2e5+10;
const int MOD =1e9+7;
vector<int> G[mx]; 
int T;
int N;
ll SG[mx];
int Fa[mx];
ll Pow(int x,int y){
    ll ans = 1;
    for (;y;y>>=1){
        if (y&1) ans = (ans * 1ll * x) %MOD;
        x = 1ll*x * x %MOD;
    }
    return ans;
}
void dfs(int Now,int fa){
    Fa[Now] = fa;
    SG[Now] = 0;
    for (auto v:G[Now]){
        if (v == fa) continue;
        dfs(v,Now);
        SG[Now] ^= (SG[v]+1);
    }
}
void dfs1(int Now,int fa){
    if (Now != 1){
        SG[fa] ^= (SG[Now]+1);
        SG[Now] = SG[Now] ^ (SG[fa] + 1);
    }
    if (SG[Now] != 0) cnt ++;
    for (auto v : G[Now]){
        if (v == fa) continue;
        dfs1(v,Now);
    }
    if (Now != 1){
        SG[Now] ^= (SG[fa]+1);
        SG[fa]^=(SG[Now] + 1);
    }
}
signed main(){
    T=read();
    while (T--){
        N = read(); 
        for (int i = 1 ; i <= N ; i ++){
            Fa[i] = 0;
            SG[i] = 0;
            G[i].clear();
        }
        for (int i = 1 ; i < N ; i ++){
            int x,y;
            x=read(),y=read();
            G[x].push_back(y);
            G[y].push_back(x);
        }
        dfs(1,1);
        cnt = 0;
        dfs1(1,1);
        ll inv = Pow(N,MOD-2);
        printf("%lld\n",1ll*inv*cnt%MOD);
    }
    return 0;
}