hydd的博客

博客

NOIP 2020 Editorial

2020-12-20 15:49:00 By hydd

排水系统（water）

  • 先把前 $m$ 个的权值设为 $1$。
  • 拓扑排序，将它的权值平分给它所有的出点。
  • 输出所有出度为 $0$ 的点的权值。
  • 这个思路没有错，但题目里说起点到终点中间点数不超过 $10$，也就是分母可以达到 $60^{11}$。
  • 这样就要写高精度，但是高精度 $\gcd$ 不是一件容易的事情。
  • 有这么一种处理方法：钦定所有权值的分母都为 $60^{11}$，到最后再约分。因为分母一定是 $60^{11}$ 的约数。
  • 那么，过程中只要做高精度除单精度，高精度加高精度即可。
  • 最后约分的话，因为分母是 $2^{22}\times 3^{11}\times 5^{11}$，直接判断原数是不是 $2,3,5$ 的倍数，试除即可。
  • 高精度可以直接压 $10^{11}$ 进制，那么这个高精度数的四则运算是 $O(1)$ 的。（只需两个 $\texttt{long long}$ 存）
  • 代码并不长。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll lim=100000000000ll;//1e11
int n,m,d[110000],ind[110000],v[110000][6];
queue<int> que;
struct node{
    //x%lim, x/lim
    ll v[2];
    node(){
        v[0]=0ll; v[1]=0ll;
    }
    void work(){
        v[0]=0ll; v[1]=362797056ll;
    }
    void div(int x){
        v[0]=((v[1]%x)*lim+v[0])/x;
        v[1]=v[1]/x;
    }
    void add(const node &x){
        v[0]+=x.v[0]; v[1]+=x.v[1];
        if (v[0]>=lim) v[0]-=lim,v[1]++;
    }
    bool check2() const{ return !(v[0]&1);}
    bool check3(){ return !((v[0]+v[1])%3);}
    bool check5(){ return !(v[0]%5);}
    void print(){
        if (v[1]) printf("%lld%011lld",v[1],v[0]);
        else printf("%lld",v[0]);
    }
} a[110000];
void print(node x){
    node y; y.work();
    if (!x.v[0]&&!x.v[1]){ puts("0 1"); return;}//这里其实不用特判
    for (int i=1;i<=22;i++)
        if (x.check2()){
            x.div(2);
            y.div(2);
        } else break;
    for (int i=1;i<=11;i++)
        if (x.check3()){
            x.div(3);
            y.div(3);
        } else break;
    for (int i=1;i<=11;i++)
        if (x.check5()){
            x.div(5);
            y.div(5);
        } else break;
    x.print(); putchar(' '); y.print(); putchar('\n');
}
int main(){
//    freopen("water.in","r",stdin);
//    freopen("water.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++) a[i].work();
    for (int u=1;u<=n;u++){
        scanf("%d",&d[u]);
        for (int i=0;i<d[u];i++){
            scanf("%d",&v[u][i]);
            ind[v[u][i]]++;
        }
    }

    for (int i=1;i<=n;i++)
        if (!ind[i]) que.push(i);
    while (!que.empty()){
        int u=que.front(); que.pop();
        if (!d[u]) continue;
        a[u].div(d[u]);

        for (int i=0;i<d[u];i++){
            a[v[u][i]].add(a[u]);
            ind[v[u][i]]--;
            if (!ind[v[u][i]]) que.push(v[u][i]);
        }
    }

    for (int i=1;i<=n;i++)
        if (!d[i]) print(a[i]);
    return 0;
}

字符串匹配（string）

  • 枚举 $AB$ 的长度 $len$。用桶维护当前 $F(A)=0,1,2,\cdots,26$ 有多少个。
  • 在从左往右扫的过程中，二分求出 $i_{\max}$ 表示最大的 $i$ 满足原串可以表示为 $(AB)^iC$。（$AB$ 的长为 $len$）
  • 那么，对于 $i=1,3,5,\cdots$，它们对应的 $F(C)$ 都一样；对于 $i=2,4,6,\cdots$，它们对应的 $F(C)$ 也一样。
  • 可以直接求前缀和计算答案，但是维护前缀和不能用树状数组，这样会多一个 $\log$。可以用两个指针分别维护 $i$ 为奇数和偶数的前缀和，每次，奇数的指针，$F(C)$ 的变化量为 $1$，偶数的指针变化量为 $0/2$，所以是常数复杂度。
  • 总时间复杂度为 $O(T\sum_{i=1}^n \log(\frac n i))=O(Tn)$。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int Mod1=998244353;
const int Mod2=1e9+7;
const int bas1=233;
const int bas2=23333;
int T,n,tot[31],num[31],F[1100000]; char s[1100000];
ll hs0[1100000],hs1[1100000],p0[1100000],p1[1100000],ans;
inline bool check(int l0,int r0,int l1,int r1){
    return (hs0[r0]+(Mod1-p0[r0-l0])*hs0[l0])%Mod1==(hs0[r1]+(Mod1-p0[r1-l1])*hs0[l1])%Mod1
        && (hs1[r0]+(Mod2-p1[r0-l0])*hs1[l0])%Mod2==(hs1[r1]+(Mod2-p1[r1-l1])*hs1[l1])%Mod2;
}
int pos0,s0,pos1,s1;
inline void add(int x){
    num[x]++;
    if (x<=pos0) s0++;
    if (x<=pos1) s1++;
}
inline int gets0(int x){
    while (pos0<x) pos0++,s0+=num[pos0];
    while (pos0>x) s0-=num[pos0],pos0--;
    return s0;
}
inline int gets1(int x){
    while (pos1<x) pos1++,s1+=num[pos1];
    while (pos1>x) s1-=num[pos1],pos1--;
    return s1;
}
void initF(){
    for (int i=0;i<=26;i++) tot[i]=0;
    int tmp=0;
    for (int i=n;i>=1;i--){
        tmp-=tot[s[i]-'a'];
        tot[s[i]-'a']^=1;
        tmp+=tot[s[i]-'a'];
        F[i]=tmp;
    }
}
void solve(){
    pos0=0; s0=0; pos1=0; s1=0;
    for (int i=0;i<=26;i++) tot[i]=0,num[i]=0;

    int tmp=1; tot[s[1]-'a']=1;
    ans=0;
    for (int i=2;i<n;i++){
        add(tmp);

        tmp-=tot[s[i]-'a'];
        tot[s[i]-'a']^=1;
        tmp+=tot[s[i]-'a'];

        int l=0,r=(n-1)/i-1;
        while (l<r){
            int mid=(l+r+1)>>1;
            if (check(0,mid*i,i,(mid+1)*i)) l=mid;
            else r=mid-1;
        }

        ans+=gets0(F[i+1])*(r/2+1);
        if (2*i+1<=n) ans+=gets1(F[2*i+1])*((r+1)/2);
    }
}
int main(){
//    freopen("string.in","r",stdin);
//    freopen("string.out","w",stdout);
    p0[0]=1; p1[0]=1;
    for (int i=1;i<=1000005;i++) p0[i]=p0[i-1]*bas1%Mod1;
    for (int i=1;i<=1000005;i++) p1[i]=p1[i-1]*bas2%Mod2;
    scanf("%d",&T);
    while (T--){
        scanf("%s",s+1); n=(int)strlen(s+1);
        for (int i=1;i<=n;i++){
            hs0[i]=(hs0[i-1]*bas1+(s[i]-'a'+1))%Mod1;
            hs1[i]=(hs1[i-1]*bas2+(s[i]-'a'+1))%Mod2;
        }
        initF(); solve();
        printf("%lld\n",ans);
    }
    return 0;
}

移球游戏（ball）

  • 分治。假设现在 $[l,r]$ 的球在 $[l,r]$ 的柱子上，要让 $[l,mid]$ 的球在 $[l,mid]$ 的柱子上。
  • 如果可以使得 $[l,mid]$ 中那些 $[mid+1,r]$ 的球放到当前堆的最上面，$[mid+1,r]$ 中那些 $[l,mid]$ 的球放到当前堆的最上面，那么就可以通过 $n+1$ 堆两两交换，满足条件。
  • 有一种方法，在不改变其它堆的球情况下，把当前堆所有“要移动的球”移到最上面。

  • 具体做法，先随便取一个不为当前堆的临时堆 $tmp$：

  • 统计当前堆要放到最上面的球的个数 $a$。

  • 判断是否需要移动，即是否要移的已经在最上面（其实这步也可以不需要）。
  • 把 $tmp$ 中移 $a$ 个球到 $n+1$。（现在 $tmp$ 空余 $a$ 个位置，$n+1$ 空余 $m-a$ 个位置）
  • 将当前堆的球依次移出，其中“要移动的球”放到 $tmp$，其它球放到 $n+1$，直到当前堆为空。（现在 $tmp$ 和 $n+1$ 满了）
  • 将 $n+1$ 中最上面的 $m-a$ 个球移回当前堆。（这些球显然是原来当前堆的球，$n+1$ 还剩 $a$ 个球）
  • 将 $tmp$ 中最上面的 $a$ 个球移回当前堆。（这些球显然是原来当前堆的球，$tmp$ 还剩 $m-a$ 个球，当前堆满了）

  • 将 $n+1$ 的 $a$ 个球移回当前堆。（这些球显然是原来当前堆的球，$tmp$ 满了，$n+1$ 空了）

  • 分析一下可以发现，当前堆要移的球到了当前堆的最上面，其它堆没有变化（$tmp$ 中的球也是按移出的顺序移回的）。

  • 之后，就可以枚举右边的每一个堆，让它和左边的堆的球交换即可。这可以简单的实现。
  • 那么就可以分治下去做这个过程了。当 $l=r$ 时，则代表颜色为 $l$ 的球已经在柱子 $l$ 上，直接返回即可。
  • 操作次数/时间复杂度为 $O(n\log n\times m)$。
#include<bits/stdc++.h>
using namespace std;
int n,m,a[55][410],sz[55],tot[55];
int ans,Ansx[1100000],Ansy[1100000];
void mymove(int x,int y,int k=1){
    while (k--){
        ans++; Ansx[ans]=x; Ansy[ans]=y;
        sz[y]++;
        a[y][sz[y]]=a[x][sz[x]];
        sz[x]--;
    }
}
void work(int x,int y){
    if (tot[x]>tot[y]) swap(x,y);
    mymove(y,n+1,tot[y]);
    mymove(x,y,tot[x]);
    mymove(n+1,x,tot[x]);
    mymove(n+1,y,tot[y]-tot[x]);
    tot[y]-=tot[x]; tot[x]=0;
}
void solve(int l,int r){
    if (l==r) return;
    int mid=(l+r)>>1,tmp;
    for (int i=l;i<=r;i++){
        tmp=(i==l?r:l); tot[i]=0;
        for (int j=m;j>=1;j--)
            if ((i<=mid)!=(a[i][j]<=mid)) tot[i]++;
        mymove(tmp,n+1,tot[i]);
        for (int j=m;j>=1;j--)
            if ((i<=mid)!=(a[i][j]<=mid)) mymove(i,tmp);
            else mymove(i,n+1);
        mymove(n+1,i,m-tot[i]); mymove(tmp,i,tot[i]); mymove(n+1,tmp,tot[i]);
    }
    int j=l;
    for (int i=mid+1;i<=r;i++)
        while (tot[i]){
            while (j<=mid&&!tot[j]) j++;
            work(i,j);
        }
    solve(l,mid); solve(mid+1,r);
}
int main(){
//    freopen("ball.in","r",stdin);
//    freopen("ball.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
        sz[i]=m;
    }
    solve(1,n);
    printf("%d\n",ans);
    for (int i=1;i<=ans;i++) printf("%d %d\n",Ansx[i],Ansy[i]);
    return 0;
}

微信步数（walk）

  • 首先，如果在第一轮或第二轮直接走完，那么模拟即可。
  • 如果模拟两轮之后没有走完，记第一轮结束时，每一维合法的坐标数分别为 $a_i$，第二轮结束时，每一维合法的坐标数分别为 $b_i$，那么第 $k(k\geq 2)$ 轮结束后，每一维合法的坐标数分别为 $b_i-(a_i-b_i)\times k$。
  • 那么，枚举 $i$，表示现在计算在第 $t+2(t\geq 1)$ 轮（满足 $t+2$ 轮后仍合法）第 $i$ 步之后的答案之和。
  • 然后式子就类似于 $\sum_{x=1}^t\prod_j (tot[j][i]-(a[j]-b[j])*x)$。其中 $tot[j][i]$ 表示第一轮做完后，第二轮做了 $i$ 步，第 $j$ 维剩下的合法坐标数。
  • 这个 $t$ 是可以计算出来的，即 $\min_{j,b[j]\neq 0} \frac{a[j][i]}{b[j]}$。
  • 将 $x$ 看做一个变量，求出 $f(x)=\prod_j (tot[j][i]-(a[j]-b[j])*x)$ 的表达式，设其为 $f(x)=\sum_i c_ix^i$，那么答案即为 $\sum_i c_i(\sum_{x=1}^tx^i)$，后面这个是个自然数幂之和的形式。
  • 当 $k\leq 3$ 时，自然数幂和有简洁的式子。
  • 当 $k>3$ 时，那么 $t\leq \max w_i=10^6$，可以直接预处理自然数幂和。
  • 总时间复杂度 $O(nk^2)$，可以优化求 $f(x)$ 的过程（即每次的变化量极少）可以做到 $O(nk)$。
  • 只给出 $O(nk^2)$ 的实现。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int Mod=1e9+7;
const int inv2=(Mod+1)/2;
const int inv6=(Mod+1)/6;
int n,k,w[1100000],c[1100000],d[1100000];
int b[1100000],a[11][1100000];
int L[1100000],R[1100000],l[1100000],r[1100000];
ll ans,num[11][1100000],f[1100000],g[1100000];
ll qpow(ll x,int a){
    ll res=1;
    while (a){
        if (a&1) res=res*x%Mod;
        x=x*x%Mod; a>>=1;
    }
    return res;
}
inline ll sqr(ll x){ return x*x%Mod;}
ll calc(int k,ll x){//1^k+2^k+3^k+...+x^k
    switch (k){
        case 0: return x;
        case 1: return (x*(x+1)%Mod*inv2%Mod);
        case 2: return (x*(x+1)%Mod*(x<<1|1)%Mod*inv6%Mod);
        case 3: return sqr(x*(x+1)%Mod*inv2%Mod);
        default: return num[k-4][x];
    }
}
void init(){
    ll tmp;
    for (int i=1;i<=1000000;i++){
        tmp=sqr(i); tmp=sqr(tmp);
        num[0][i]=(num[0][i-1]+tmp)%Mod; tmp=tmp*i%Mod;
        num[1][i]=(num[1][i-1]+tmp)%Mod; tmp=tmp*i%Mod;
        num[2][i]=(num[2][i-1]+tmp)%Mod; tmp=tmp*i%Mod;
        num[3][i]=(num[3][i-1]+tmp)%Mod; tmp=tmp*i%Mod;
        num[4][i]=(num[4][i-1]+tmp)%Mod; tmp=tmp*i%Mod;
        num[5][i]=(num[5][i-1]+tmp)%Mod; tmp=tmp*i%Mod;
        num[6][i]=(num[6][i-1]+tmp)%Mod;
    }
}
bool flag;
int main(){
//    freopen("walk.in","r",stdin);
//    freopen("walk.out","w",stdout);
    init();
    scanf("%d%d",&n,&k); ll now=1;
    for (int i=1;i<=k;i++){
        scanf("%d",&w[i]);
        L[i]=1; R[i]=w[i];
        now=now*w[i]%Mod;
    }
    for (int i=1;i<=n;i++) scanf("%d%d",&c[i],&d[i]);
    bool flag=false;
    ans=now;
    for (int i=1;i<=n;i++){
        now=now*qpow(R[c[i]]-L[c[i]]+1,Mod-2)%Mod;
        L[c[i]]+=d[i]; R[c[i]]+=d[i];
        L[c[i]]=max(L[c[i]],1); R[c[i]]=min(R[c[i]],w[c[i]]);
        if (L[c[i]]>R[c[i]]){
            flag=true;
            break;
        }
        now=now*(R[c[i]]-L[c[i]]+1)%Mod;
        ans=(ans+now)%Mod;
    }
    if (flag){
        printf("%lld\n",ans);
        return 0;
    }


    for (int i=1;i<=k;i++) b[i]=R[i]-L[i]+1;

    flag=false;
    for (int i=1;i<=n;i++){
        now=now*qpow(R[c[i]]-L[c[i]]+1,Mod-2)%Mod;
        L[c[i]]+=d[i]; R[c[i]]+=d[i];
        L[c[i]]=max(L[c[i]],1); R[c[i]]=min(R[c[i]],w[c[i]]);
        if (L[c[i]]>R[c[i]]){
            flag=true;
            break;
        }
        now=now*(R[c[i]]-L[c[i]]+1)%Mod;
        for (int j=1;j<=k;j++) a[j][i]=R[j]-L[j]+1;
        ans=(ans+now)%Mod;
    }
    if (flag){
        printf("%lld\n",ans);
        return 0;
    }

    for (int i=1;i<=k;i++){
        b[i]-=(R[i]-L[i]+1);
        if (b[i]) flag=true;
    }
    if (!flag){
        puts("-1");
        return 0;
    }

    for (int i=1;i<=n;i++){
        //\prod_j a[j][i]-b[j]  +  \prod_j a[j][i]-b[j]*2  + ... + a[j][i]-b[j]*t
        //a[j][i]-b[i]*t=0   ==>   t=a[j][i]/b[j]
        int tmp=INF;
        for (int j=1;j<=k;j++)
            if (b[j]) tmp=min(tmp,a[j][i]/b[j]);
        //\prod_j a[j][i]-b[j]*x

        f[0]=1; for (int j=1;j<=k;j++) f[j]=0;
        for (int j=1;j<=k;j++){
            for (int t=0;t<j;t++){
                g[t]=(g[t]+f[t]*a[j][i])%Mod;//long long !!!
                g[t+1]=(g[t+1]+f[t]*(Mod-b[j])%Mod)%Mod;
            }
            for (int t=0;t<=j;t++) f[t]=g[t],g[t]=0;
        }

        for (int j=0;j<=k;j++) ans=(ans+f[j]*calc(j,tmp))%Mod;//long long !!!
    }
    printf("%lld\n",ans);
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户，mike会被高亮显示。如果你真的想打“@”这个字符，请用“@@”。

English 繁體中文 简体中文

Server Time: 2024-11-24 09:20:30 | OpenSource Project