@exut 2024-10-16T06:08:05.000000Z 字数 6285 阅读 150

HNFMS week6 任务

刷题

[CSP-J2019 江西] 非回文串

逆天数据范围，只开 $2000$ 发神经属于

逆天相同字母算不同方案

直接求好像不是很典，但是可以试试正难则反

任意摆放的总方案数是 $n!$ ，毋庸置疑

考虑重排为回文的方案数

注意到字符间有区别，所以方案数为（ $t_i$ 为该字符出现次数）

$(n/2)!\prod_{i=1}^{26} A_{t_i}^{t_i/2}=\prod_{1}^{26}\frac{t_i!}{(t_i/2)!}$

然后发现做完了已经

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int s[26];
signed main(){
    int n;cin>>n;
    int ans=1;
    for(int i=1;i<=n;i++){
        ans*=i;ans%=mod;
        char x;cin>>x;
        s[x-'a']++;
    }
    int cnt=0;
    for(int i=0;i<26;i++)if(s[i]%2==1)cnt++;
    if(cnt>1){
        cout<<ans;return 0;}
    else{
        long long cnt2=1;
        for(int i=1;i<=n/2;i++) cnt2*=i,cnt2%=mod;
        for(int i=0;i<26;i++){
            for(int j=s[i]/2+1;j<=s[i];j++){
                cnt2*=j;cnt2%=mod;
            }
        }
        cout<<(ans-cnt2+mod)%mod;
    }
    return 0; 
}

懒得写逆元了水一些复杂度 $O(n^2)$ ，随便可以优化到线性

CF920F

看着很势能一道题，容易想到一个数的正约数个数不超过 $2\sqrt n$ ，然后类似花神势能线段树或者分块就行

每次处理约数好像有点慢，可以线性筛一下或者预处理出来

使用分块， $O(n\sqrt n \log\log n)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int num[1000005];
bool vis[1000005];
int prime[1000005];
int d[1000005];
int mx[1000005];
int cnt;
void init(){
    num[1]=1;
    for(int i=2;i<=1000000;i++){
        if(!vis[i]){
            num[i]=2,d[i]=1;
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt and i*prime[j]<=1000000;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                num[i*prime[j]]=num[i]/(d[i]+1)*(d[i]+2);
                d[i*prime[j]]=d[i]+1;
                break;  
            }
            else{
                num[i*prime[j]]=num[i]*2;
                d[i*prime[j]]=1;
            }
        }
    }
}
int bl[N];
int sum[N];
int a[N];
int B,n,m;
int L[N],R[N];
void modi(int l,int r){
    if(bl[l]==bl[r]){
        for(int i=l;i<=r;i++){
            a[i]=num[a[i]];
        }
        mx[bl[l]]=sum[bl[l]]=0;
        for(int i=L[bl[l]];i<=R[bl[l]];i++) mx[bl[l]]=max(mx[bl[l]],a[i]),sum[bl[l]]+=a[i];
        return ;
    }
    for(int i=l;bl[i]==bl[l];i++){
        a[i]=num[a[i]];
    }
    mx[bl[l]]=sum[bl[l]]=0;
    for(int i=L[bl[l]];i<=R[bl[l]];i++) mx[bl[l]]=max(mx[bl[l]],a[i]),sum[bl[l]]+=a[i];
    for(int i=r;bl[i]==bl[r];i--){
        a[i]=num[a[i]];
    }
    mx[bl[r]]=sum[bl[r]]=0;
    for(int i=L[bl[r]];i<=R[bl[r]];i++) mx[bl[r]]=max(mx[bl[r]],a[i]),sum[bl[r]]+=a[i];
    for(int yzy=bl[l]+1;yzy<bl[r];yzy++){
        if(mx[yzy]<=2) continue;
        for(int i=L[yzy];i<=R[yzy];i++){
            a[i]=num[a[i]];
        }
        mx[yzy]=sum[yzy]=0;
        for(int i=L[yzy];i<=R[yzy];i++) mx[yzy]=max(mx[yzy],a[i]),sum[yzy]+=a[i];
    } 
}
int query(int l,int r){
    int ret=0;
    if(bl[l]==bl[r]){
        for(int i=l;i<=r;i++){
            ret+=a[i];
        }
        return ret;
    }
    for(int i=l;bl[i]==bl[l];i++){
        ret+=a[i];
    }
    for(int i=r;bl[i]==bl[r];i--){
        ret+=a[i];
    }
    for(int i=bl[l]+1;i<bl[r];i++){
        ret+=sum[i];
    }
    return ret;
}
signed main(){
    init();
    cin>>n>>m; 
    int B=sqrt(n);
    for(int i=1;i<=n;i++){
        bl[i]=(i-1)/B+1;
        R[bl[i]]=i;
        if(!L[bl[i]]) L[bl[i]]=i;
        cin>>a[i];
        sum[bl[i]]+=a[i];
        mx[bl[i]]=max(mx[bl[i]],a[i]);
    }
    while(m--){
        int l,r,opt;
        cin>>opt>>l>>r;
        if(opt==1){
            modi(l,r);
        }
        else{
            cout<<query(l,r)<<"\n";
        }
    }
}

CF1870E

这个众所周知MEX和异或和都不是什么好维护的东西，考虑上dp试试

虽然题目问的是一个最优化问题，但是这个最优化啊看着不是很可做，我们不妨考虑转化成判定性问题：设 $f_{i,j}$ 表示在 $i$ 之前，能否凑出异或和为 $j$

我们首先可以 $O(n^2)$ 地预处理求出任意区间的MEX

(需要注意的是答案的上界大概在 $2n$ 的样子，所以数组第二维开两倍～)

于是我们可以写出一个暴力dp

#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int f[N][N*2];
int t,n;
int ton[N*2];
int mex[N][N];
int a[N];
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for (int i=1;i<=n;i++) 
            for(int j=0;j<=n*2;j++)
                mex[i][j]=N,f[i][j]=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        f[0][0]=1;
        for(int l=1;l<=n;l++){//init mex
            int x=0;
            for(int r=l;r<=n;r++){
                ton[a[r]]++;
                while(ton[x]) x++;
                mex[l][r]=x;
            }
            for(int r=l;r<=n;r++){
                ton[a[r]]--;
            }
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=i;j++){
                for(int k=0;k<=2*n;k++){
                    f[i][k]|=f[j-1][k^mex[j][i]];
                }
            }
        }
        for(int i=2*n;i>=0;i--){
            if(f[n][i]){cout<<i<<"\n";break;}
        }
    }
}

这个转移式子的异或导致完全不能用数据结构来优化这个dp，我们也没法贪心...吗？

欸贪心，不妨考虑一下什么情况我们可以舍弃一个区间：

$\forall l_0,r_0$ ，如果 $\exists l,r$ 使得 $l_0\le l\le r \le r_0$ 并且 $mex(l,r)=mex(l_0,r_0)$ ，那么我们必定不会选取 $l_0,r_0$ ，选取 $l,r$ 一定是更优的

容易得出，对于每个 $l$ 至多有一个 $r$ 使得 $[l,r] and \ a_l>a_r$ 是一个好区间，反之同样

复杂度 $O(n^2)$

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=5015;
bool f[N][N*2];
int t,n;
int ton[N*2];
int a[N];
vector<pii> g[N];
int main(){
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++){
            g[i].clear();
            cin>>a[i];
        }
        for(int i=1;i<=n;i++){
            if(!a[i]) g[i].emplace_back(mp(i,1));
        }
        for(int l=1;l<=n;l++){//init mex
            memset(ton, 0, sizeof(int) * (n + 5));
            int x=0;
            for(int r=l;r<=n;r++){
                ton[a[r]]++;
                while(ton[x]) x++;
                if(x>a[l] and a[r]<a[l]){
                    g[r].push_back(mp(l,x));
                    break;
                }
            }
        }
        for(int r=1;r<=n;r++){//init mex
            memset(ton, 0, sizeof(int) * (n + 5));
            int x=0;
            for(int l=r;l>=1;l--){
                ton[a[l]]++;
                while(ton[x]) x++;
                if(x>a[r] and a[l]<a[r]){
                    g[r].push_back(mp(l,x));
                    break;
                }
            }
        }
        memset(f[0],0,sizeof(bool)*((n<<1)+5));
        f[0][0]=1;
        for(int i=1;i<=n;i++){
            memcpy(f[i],f[i-1],sizeof(bool)*((n<<1)+5));
            for(pii j:g[i]){
                for(int k=0;k<=(n<<1);k++){
                    if((k^j.second)<=(n<<1))f[i][k]|=f[j.first-1][k^j.second];
                }
            }
            // for(int j=0;j<=2*n;j++) cerr<<f[i][j]<<" ";
            // cerr<<endl;
        }
        for(int i=2*n;i>=0;i--){
            if(f[n][i]){cout<<i<<"\n";break;}
        }
    }
}

CF1553G

观察到一个奇妙的性质：答案不会比 $2$ 大

为什么，注意到从一个点生成的点一定和自己连边，同时偶数点之间都互相连边

欸，一个数乘自己加一，百分百偶数的

于是对两个点各生成一次 一定可以连通

所以答案 最大只有2

初始的连通性其实用一个并查集是可以维护的吧，考虑筛一下质数然后对于所有质数枚举倍数

这一部分筛的复杂度是 $O(n)$ ，枚举倍数大概 $O(A)$ (其实应该略小一些吧) 然后合并应该不占复杂度或者占一个 $O(\log n)$ ，其实真的是很健康的不是吗

欸我们枚举倍数的时候顺便把这个质数自己（哪怕不在给定中，不在就加点编号）塞到并查集里

这一部分咱大概当作 $O(A\log n)$ 罢

现在只需要考虑在初始不连的情况下，生成一个点能不能连就行嘻嘻

容易发现这个 $a(a+1)$ 中 $a$ 是完全没用的，本来有的质因数不能连通更多的点的说

于是只需要考虑 $a+1$ 的质因数会有什么后果——我们只需要把 $a$ 和 $a+1$ 的质因数中不同的考虑一下，而定位这些质因子所在的连通块是非常容易的因为塞进并查集了！

那么打标记即可，如果从 $s$ 出发标了 $t$ 所在的集合或者反过来那就答案为 $1$ ，再不行 $2$ 呗

所以至多也就 $7$ 个的样子的质因数，然后枚举质因数set维护一下可达性

不能直接只改被查的两个集合

复杂度比较奇怪吧，感觉上界是 $(A+q)\log n$ 带一个有点大的常数

#include<bits/stdc++.h>
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int N=2e6+5;
const int A=1e6+1;
bool vis[N];
int prime[N],cnt;
void init(){
    for(int i=2;i<=A;i++){
        if(!vis[i]){
            prime[++cnt]=i;
        }
        for(int j=1;j<=cnt and i*prime[j]<=A;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0){
                break;  
            }
        }
    }
}
int n,q;
int a[N];
int rev[N];//back from val to num~ 
int nb;
int fa[N];
int find(int x){
    return (x==fa[x]?x:fa[x]=find(fa[x]));
}
void merge(int x,int y){
    x=find(x),y=find(y);
    if(x==y) return;
    fa[x]=y;
}
vector<int> py[N];
vector<pii > dui;
set<pii> S;
int main(){
    init();
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    nb=n;
    for(int i=1;i<=n;i++) cin>>a[i],rev[a[i]]=i,fa[i]=i;
    for(int t=1;t<=cnt;t++){
        int p=prime[t];
        if(!rev[p]){
            a[++nb]=p;
            rev[p]=nb;
            fa[nb]=nb;
        }
        for(int i=p;i<=A;i+=p){
            py[i].push_back(p);
            if(rev[i])merge(rev[p],rev[i]);
        }
    }
    for(int i=1;i<=n;i++){
        vector<int> cjb;
        cjb.clear();
        cjb.push_back(find(i));
        for(int v:py[a[i]+1]){
            cjb.push_back(find(rev[v]));
        }
        sort(cjb.begin(),cjb.end());
        cjb.erase(unique(cjb.begin(),cjb.end()),cjb.end());
        for(int i=0;i<cjb.size();i++){
            for(int j=i;j<cjb.size();j++){
                S.insert(mp(cjb[i],cjb[j]));
            }
        }
    }
    // for(pii v:S){
    //     cerr<<v.first<<" "<<v.second<<endl;
    // }
    // cerr<<endl;
    for(int i=1;i<=q;i++){
        int s,t;
        cin>>s>>t;
        s=find(s),t=find(t);
        pii xzy=mp(min(s,t),max(s,t));
        // cerr<<find(s)<<" "<<find(t)<<endl;
        // cerr<<min(s,t)<<" "<<max(s,t)<<endl;
        if(s==t){
            cout<<"0\n";
            continue;
        }
        else if(S.count(xzy)){
            cout<<"1\n";
        }
        else cout<<"2\n";
    }
}