T1 字符交换

可以枚举每个字符作为中心位置的情况，
然后贪心地把相同的字符拽到这个中心位置
求出在限制内的最大值，即最终解
我的做法是：定义dp[i]为达到i的最小交换次数
对于26个字符分别考虑
对于相同字符把它们尽量向中间的那个换一定最优
长度为偶数的中间两个字符都可能作为最优方案
而长度为奇数的话一定都换到中间那个字符的左右一定最优
于是可以枚举m值的大小，再枚举一下起点
那么我们如何做到\(O(1)\)求这个最小的交换次数
用前缀和维护一下位置的和即可
时间复杂度：\(O(n^2)\)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#define rint register int
using namespace std;

const int maxn=4005;
int pos[30][maxn],cnt[30],dp[maxn],sum[30][maxn];
char s[maxn];

int Find(rint id,rint l,rint r){
    int len=r-l+1;
    int suml,sumr;
    int ans,mid=(l+r)/2;
    int midlen=(len-1)/2;
    if(len&1){
        suml=pos[id][mid]*midlen-(sum[id][mid-1]-sum[id][l-1])-(1+midlen)*midlen/2;
        sumr=(sum[id][r]-sum[id][mid])-pos[id][mid]*midlen-(1+midlen)*midlen/2;
        return suml+sumr;
    }else{
        suml=pos[id][mid]*(mid-l)-(sum[id][mid-1]-sum[id][l-1])-(1+mid-l)*(mid-l)/2;
        sumr=(sum[id][r]-sum[id][mid])-pos[id][mid]*(r-mid)-(1+r-mid)*(r-mid)/2;
        ans=suml+sumr;
        mid++;
        suml=pos[id][mid]*(mid-l)-(sum[id][mid-1]-sum[id][l-1])-(1+mid-l)*(mid-l)/2;
        sumr=(sum[id][r]-sum[id][mid])-pos[id][mid]*(r-mid)-(1+r-mid)*(r-mid)/2;
        ans=min(ans,suml+sumr);
        return ans;
    }
}

int main(){
    memset(dp,0x3f,sizeof(dp));
    dp[1]=0;
    int n,m;scanf("%d%d",&n,&m);
    scanf("%s",s+1);
    for(rint i=1;i<=n;i++){
        int id=s[i]-'a'+1;
        pos[id][++cnt[id]]=i;
        sum[id][cnt[id]]=sum[id][cnt[id]-1]+i;
    }
    for(rint js=1;js<=26;js++){
        for(rint i=2;i<=cnt[js];i++){
            for(rint j=1;j<=cnt[js]-i+1;j++){
                int l=j,r=j+i-1;
                dp[i]=min(dp[i],Find(js,l,r));
            }
        }
    }
    int ans=0;
    for(rint i=1;i<=n;i++) if(dp[i]<=m) ans=i;
    printf("%d\n",ans);
    return 0;
}

T2 平方数

一个数要想与其他数成为平方数
把这个数质因子分解后，
这个数本身的所有平方因子都是没有意义的
就可以把这些平方因子都筛掉，只保留奇数次幂的质因子
开个桶记录这个值，就可以了
但是直接这样做的复杂度并不优秀:\(O(n\sqrt n)\)。跟暴力一个分
再优化一下的话可以筛出\(\sqrt n\)以内的所有质数，大概有3000个，可以拿到70的好成绩
正解的思路更妙：我们只筛掉1000以内的所有质数
剩下的那个数最多只含有两个质因子的，因为我们已经筛完了所有1e3以下的质因子
若有3个及以上大于1000的质因子就爆掉1e9的范围了
只要判断一下剩下的数是否是个平方数就好了

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cmath>
#include <map>
#define rint register int
using namespace std;
typedef long long ll;

const int maxn=3e5+5;
const int maxm=1000;
ll ans;
int a[maxn],pri[maxm+5],cnt;
bool vis[maxm+5];
map<int,int> mp;

void Init(){
    for(rint i=2;i<=maxm;i++){
        if(!vis[i]) pri[++cnt]=i;
        for(rint j=1;j<=cnt&&pri[j]*i<=maxm;j++){
            vis[i*pri[j]]=1;
            if(i%pri[j]==0) break;
        }
    }
}

int main(){
    int n;scanf("%d",&n);
    Init();
    for(rint i=1;i<=n;i++){
        scanf("%d",&a[i]);
        int base=1;
        for(rint j=1;j<=cnt;j++){
            int num=0;
            while(a[i]%pri[j]==0) a[i]/=pri[j],num++;
            if(num%2) base*=pri[j];
        }
        int sq=sqrt(a[i]);
        if(a[i]!=1&&a[i]!=sq*sq) base*=a[i];
        ans+=mp[base];
        mp[base]++;
    }
    printf("%lld\n",ans);
    return 0;
}

T3 多维网络

部分分很足，大概没手都能拿到80pts
正解是容斥，用所有方案减掉不合法方案即可
所有方案用组合数随便写，但要注意这个题稍微卡内存
而我们只需要用到阶乘和阶乘的逆元，只处理这两个东西就行
(不开long long不建图的话好像也可以开的下，但比较危险)
剩下的问题就是怎么不重不漏的求出不合法的情况
我们去枚举某条不合法路径经过的第一个坏点
那么对于某个坏点来说，能与它构成偏序关系的才有可能被在它前面被走到
比如二维情况下，要想第一次走到（3，3），中间有可能会先走到（1，1），这个东西需要容斥出来
我们设这个点为u，它前面某个具有偏序关系的点为v，原点是o，终点是x，dis(a,b)表示从a点到b点的所有方案数
那么第一次经过u点的方案就是\((dis(o,u)-\sum\limits_{v}dis(o,v))*dis(u,x)\)
显然这个具有拓扑关系，可以建出图来跑个拓扑维护这个限制关系
但其实并不用，直接将每个点的坐标累加，把坏点sort按照这个总和sort一下，
没有偏序关系的话，坐标相减一定会出现负数，直接在求组合数的时候判成0就可以解决
这样做常数更小，时间空间开销都不大，能快十倍左右
时间复杂度\(O(n^2d)\)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#define rint register int
using namespace std;
typedef long long ll;

const int maxn=1e7+5;
const int mod=1e9+7;
int d,n,a[105],ans,f[505];
int suma,jc[maxn],ny[maxn],jcny[maxn];

struct Node{
    int x[105];
    int sumx;
    friend bool operator < (Node aa,Node bb){
        return aa.sumx<bb.sumx;
    }
}b[505];

int qpow(rint y,rint x){
    int base=y,ans=1;
    while(x){
        if(x&1) ans=1LL*ans*base%mod;
        base=1LL*base*base%mod;
        x>>=1;
    }
    return ans;
}

void Init(){
    jc[0]=jc[1]=jcny[0]=jcny[1]=1;
    for(rint i=2;i<=suma;i++) jc[i]=1LL*jc[i-1]*i%mod;
    jcny[suma]=qpow(jc[suma],mod-2);
    for(rint i=suma-1;i>=2;i--) jcny[i]=1LL*jcny[i+1]*(i+1)%mod;
}

int C(rint x,rint y){
    if(x<0||y<0) return 0;
    return 1LL*jc[x]*jcny[y]%mod*jcny[x-y]%mod;
}

int Calc(rint x){
    int base=1,sum=b[x].sumx,num;
    for(rint i=1;i<=d;i++){
        base=1LL*base*C(sum,b[x].x[i])%mod;
        sum-=b[x].x[i];
    }
    for(rint i=1;i<x;i++){
        num=1,sum=b[x].sumx-b[i].sumx;
        for(rint j=1;j<=d;j++){
            num=1LL*num*C(sum,b[x].x[j]-b[i].x[j])%mod;
            sum-=b[x].x[j]-b[i].x[j];
        }
        base=(base-1LL*num*f[i]%mod+mod)%mod;
    }
    f[x]=base;
    num=1,sum=suma-b[x].sumx;
    for(rint i=1;i<=d;i++){
        num=1LL*num*C(sum,a[i]-b[x].x[i])%mod;
        sum-=a[i]-b[x].x[i];
    }
    base=1LL*base*num%mod;
    return base;
}

int main(){
    scanf("%d%d",&d,&n);
    for(rint i=1;i<=d;i++)
        scanf("%d",&a[i]),suma+=a[i];
    Init();
    for(rint i=1;i<=n;i++)
        for(rint j=1;j<=d;j++){
            scanf("%d",&b[i].x[j]);
            b[i].sumx+=b[i].x[j];
        }
    sort(b+1,b+n+1);
    ans=1;
    int sum=suma;
    for(rint i=1;i<=d;i++){
        ans=1LL*ans*C(sum,a[i])%mod;
        sum-=a[i];
    }
    for(rint i=1;i<=n;i++) ans=(ans-Calc(i)+mod)%mod;
    printf("%d\n",ans);
    return 0;
}