2020牛客暑期多校第九场

MorphLing 8月 16, 2020

A.Groundhog-and-2-Power-Representation

标签：高精度、递归读入

递归处理括号内的输入，cnt[i]表示$2^i$的个数，由答案范围可知i小于1000，也就是只需要统计出cnt数组之后再做高精度就可以得到答案。

#include<bits/stdc++.h>
using namespace std;

const int N=2e4+5;

int p;

char s[N];

int cnt[N],pw[20],ans[N],top;

void init() {
    p=0;
    pw[0]=1;
    for (int i=1;i<20;i++) pw[i]=pw[i-1]*2;
}

int dfs() {
    p++;
    int res=0,tmp=0;
    while(s[p]!=')') {
        if (s[p]=='2') {
            tmp=1;
            p++;
            if (s[p]=='(') tmp=dfs();
            else p--;
            res+=pw[tmp];
        }
        p++;
    }
    return res;
}

void mul(int v) {
    for (int i=top;i>=0;i--) {
        ans[i]=ans[i]*v;
    }
    for (int i=0;i<=top-1;i++) {
        ans[i+1]+=ans[i]/10;
        ans[i]%=10;
    }
    while(ans[top]>=10) {
        ans[top+1]+=ans[top]/10;
        ans[top]%=10;
        top++;
    }
}

void add(int v) {
    ans[0]+=v;
    int t=0;
    while(ans[t]>=10) {
        ans[t+1]=ans[t]/10;
        ans[t]%=10;
    }
    top=max(top,t);
}

int main() {
    scanf("%s",s);
    init();
    int len=strlen(s);
    while (p<len) {
        if (s[p]=='2') {
            int res=1;
            p++;
            if (s[p]=='(') res=dfs();
            else p--;
            cnt[res]++;
        }
        p++;
    }
    for (int i=2000;i>=0;i--) {
        mul(2);
        if (cnt[i]) add(cnt[i]);
    }
    for (int i=top;i>=0;i--) printf("%d",ans[i]);
    return 0;
}

F.Groundhog-Looking-Dowdy

标签：尺取问题

把所有点排序之后放在一根数轴上，不断调整区间的左右端点，保证区间内包含了m种不同的日期，取长度最短的区间即为答案。

#include<bits/stdc++.h>
using namespace std;

const int N=2e6+5;

struct Node {
    int v,ty;
}a[N];

int n,m,tot,ans;

int ct[N];

int main() {
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        int k;
        scanf("%d",&k);
        for (int j=1;j<=k;j++) {
            int x;
            scanf("%d",&x);
            a[++tot].v=x;
            a[tot].ty=i;
        }
    }
    sort(a+1,a+1+tot,[&](Node a,Node b){return a.v<b.v;});
    int l=1,r=0,cnt=0;
    ans=INT_MAX;
    while(r!=tot){
        while(cnt<m && r!=tot) {
            r++;
            ct[a[r].ty]++;
            if (ct[a[r].ty]==1) {
                cnt++;
            }
        }
        while(cnt==m) {
            ans=min(ans,a[r].v-a[l].v);
            ct[a[l].ty]--;
            if (ct[a[l].ty]==0) {
                cnt--;
            }
            l++;
        }
    }
    printf("%d\n",ans);
}

K.The-Flee-Plan-of-Groundhog

标签：模拟

Groundhog一定先走到orange所在的那条链上的某一点，然后往与orange不同的方向走到尽可能深的点。那么枚举orange所在的链上的每一个点，并判断Groundhog是走到最深处之前就被追上还是在最深处等待，再计算出答案，取最大值。

#include<bits/stdc++.h>
using namespace std;

const int N=2e6+5;

vector<int>G[N];

vector<int>vc;

bool online[N];

int n,t,dep[N],mxdep[N];

int ans;

void dfs(int x,int f) {
    if (x==n) {
        online[x]=1;
        mxdep[x]=1;
        return;
    }
    if (G[x].size()==1 && f!=-1) {
        mxdep[x]=dep[x];
        return;
    }
    for (auto to:G[x]) {
        if (to==f) continue;
        dep[to]=dep[x]+1;
        dfs(to,x);
        if (online[to]==1) {
            vc.push_back(to);
            online[x]=1;
        }
        if (!online[to]) mxdep[x]=max(mxdep[x],mxdep[to]);
    }
}

int main() {
    cin>>n>>t;
    for (int i=1;i<=n-1;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        G[u].push_back(v);
        G[v].push_back(u);
    }
    for (int i=1;i<=n;i++) mxdep[i]=1;
    dep[1]=1;
    dfs(1,-1);
    vc.push_back(1);
    int nd=t+1;
    for (auto x:vc) {
        if (dep[x]<=nd) {
            int gap=dep[n]-nd;
            int len=nd-dep[x]+(mxdep[x]-dep[x]);
            ans=max(ans,min((gap+len+1)/2,gap));
        }
        if (dep[x]>nd) {
            int gap=dep[n]-nd-(dep[x]-nd)*3;
            if (!gap) continue;
            int len=mxdep[x]-dep[x];
            ans=max(ans,min((gap+len+1)/2,gap)+dep[x]-nd);
        }
    }
    printf("%d\n",ans);
}

首先对x和y质因数分解之后发现，对于每个质因数都是一个独立的问题。
假设当前质因数为p，x能拆成e个p，y能拆成f个p，也就是$x=p^e···,y=p^f···$那么$gcd((p^e)^i,(p^f)^j)$只取决于$ei和fj$的大小关系。考虑每一个i的取值（从a到b），分别判断j能满足ei<=fj的取值范围，此时gcd的取值为$p^{ei}$同样，考虑每一个j的取值（从c到d），判断i满足ei>fj的取值范围，此时gcd的取值为$p^{fj}$
对每个质因数都这样进行判断，根据数据范围，质因数个数不超过10个

#include<bits/stdc++.h>
#define LL long long
#define uLL unsigned long long
using namespace std;

const int N=1e5+5,MOD=998244353;

int a,b,c,d,x,y,n,ans;

int vis[N],pr[N],countPrime;
void getPrime() {
    for (int i=2;i<N;i++) {
        if (!vis[i]) pr[++countPrime]=i;
        for (int j=1;j<=countPrime;j++) {
            if (i*pr[j]>=N) break;
            vis[i*pr[j]]=1;
            if (i%pr[j]==0) break;
        }
    }
}
int bin(int b,uLL p) {
    int res=1;
    for (;p;p>>=1,b=(1ll*b*b)%MOD){
        if (p&1) res=(1ll*res*b)%MOD;
    }
    return res;
}
int ask(int a,int b,int c,int d) {
    if (a>b) return 0;
    if (b<c) return 0;
    if (a>d) return 0;
    if (a<c) a=c;
    if (b>d) b=d;
    return b-a+1;
}
int main() {
    cin>>a>>b>>c>>d>>x>>y;
    getPrime();
    ans=1;
    for (int i=1;i<=countPrime;i++) {
        if (x%pr[i]==0 && y%pr[i]==0) {
            int cntx=0,cnty=0,now=pr[i];
            int tmp,sum;
            uLL cnt;
            while(x%now==0) {
                x/=now;
                cntx++;
            }
            while(y%now==0) {
                y/=now;
                cnty++;
            }
            cnt=0;tmp=bin(now,cntx);
            for (int j=a;j<=b;j++) {
                int tot=j*cntx;
                int bod=tot/cnty+1;
                if (tot%cnty==0) bod--;
                int ak=ask(bod,d,c,d);
                   if (ak) cnt+=1ll*j*ak;

            }
            ans=1ll*ans*bin(tmp,cnt)%MOD;
            cnt=0;tmp=bin(now,cnty);
            for (int j=c;j<=d;j++) {
                int tot=j*cnty;
                int bod=tot/cntx+1;
                int ak=ask(bod,b,a,b);
                if (ak) cnt+=1ll*j*ak;

            }
            ans=1ll*ans*bin(tmp,cnt)%MOD;
        }
        while(x%pr[i]==0) {
            x/=pr[i];
        }
        while(y%pr[i]==0) {
            y/=pr[i];
        }
    }
    if (x!=1 && y!=1 && x==y) {
        int cntx=0,cnty=0,now=x;
        int tmp,sum;
        uLL cnt;
        while(x%now==0) {
            x/=now;
            cntx++;
        }
        while(y%now==0) {
            y/=now;
            cnty++;
        }
        if (cntx!=0 && cnty!=0){
            cnt=0;tmp=bin(now,cntx);
            for (int j=a;j<=b;j++) {
                int tot=j*cntx;
                int bod=tot/cnty+1;
                if (tot%cnty==0) bod--;
                int ak=ask(bod,d,c,d);
                if (ak) cnt+=1ll*j*ak;
            }
            ans=1ll*ans*bin(tmp,cnt)%MOD;
            cnt=0;tmp=bin(now,cnty);
            for (int j=c;j<=d;j++) {
                int tot=j*cnty;
                int bod=tot/cntx+1;
                int ak=ask(bod,b,a,b);
                if (ak) cnt+=1ll*j*ak;
            }
            ans=1ll*ans*bin(tmp,cnt)%MOD;
        }
    }
    printf("%d\n",ans);
}

B.Groundhog-and-Apple-Tree

标签：树形dp，相邻交换最优原则(?)

tot[i]表示走完i这颗子树之后hp的变化量
dp[i]表示在走i这颗子树过程中最多损失多少hp（或者说需要多少hp才能走完i这颗子树）
需要注意的是这道题同时包含了点值和边值两种权值，需要定义清楚到底包含了哪些点和边（代码里tot[i]和dp[i]都包含了i这个点连向父结点的那条边）

目标就是安排访问子树的顺序，使得dp[1]尽可能小。

比较显然的是一定先走tot[x]>0的子树，再走tot[x]<0的子树（不理解的话可以考虑一下只有两颗子树，一颗tot[x]>0一颗tot[x]<0的情形），且对于tot[x]>0的子树内部一定按照dp[x]的大小从小到大排序，问题的关键是如何安排tot[x]<0的子树的内部顺序。

此处重点是有一个所谓的相邻交换最优原则（借用题解上面的说法）：考虑任意相邻的i和j（先走i，再走j），交换i和j的顺序只会对这两颗子树产生影响，那么什么情况下交换i和j的顺序后一定是更优的呢？即$min\{dp[i],dp[j]-tot[i]\}>min\{dp[j],dp[i]-tot[j]\}$，那么交换后一定比当前的顺序更优。由于只考虑tot[x]<0的情况，于是可以把这个不等式转化一下，也就是$tot[i]+dp[i]<tot[j]+dp[j]$

这样一来，我们把所有子树根据tot[x]+dp[x]从大到小排序后的顺序一定是最优解之一，因为对于其他的情况，根据相邻交换最优原则，总是可以通过一系列的相邻交换，最终使得顺序安排是有序的，且每一步相邻交换都可以确保是使得结果更优的。（所以这个结论的证明其实是一个反证法）至于tot[x]+dp[x]相同的点，它们之间的顺序其实无关紧要。

#include<bits/stdc++.h>
#define debug(x) cerr<<#x<<" : "<<x<<endl;
#define LL long long
using namespace std;

const int N=1e5+5;

struct Edge{
    int to,v;
};

vector<Edge>G[N];

int T,n,a[N];

LL tot[N],dp[N];

void init() {
    for (int i=1;i<=n;i++) {
        G[i].clear();
        dp[i]=tot[i]=0;
    }
}

void dfs(int x,int f,int val) {
    tot[x]+=a[x]-2LL*val;
    if (G[x].size()==1 && f!=-1) {
        dp[x]=max(1LL*val,2LL*val-a[x]);
        return;
    }
    vector<int>vc1,vc2;
    for (auto T:G[x]) {
        int to=T.to,v=T.v;
        if (to==f) continue;
        dfs(to,x,v);
        tot[x]+=tot[to];
        if (tot[to]>=0) vc1.push_back(to);
        else vc2.push_back(to);
    }
    sort(vc1.begin(),vc1.end(),[&](int u,int v){return dp[u]<dp[v];});
    sort(vc2.begin(),vc2.end(),[&](int u,int v){return dp[u]+tot[u]>dp[v]+tot[v];});
     LL sum=0;
    for (auto now:vc1) {
        dp[x]=max(dp[x],dp[now]-sum);
        sum+=tot[now];
    }
    for (auto now:vc2) {
        dp[x]=max(dp[x],dp[now]-sum);
        sum+=tot[now];
    }
    dp[x]=max(1LL*val,max(dp[x]+val-a[x],2LL*val-a[x]-sum));
}

void solve() {
    scanf("%d",&n);
    init();
    for (int i=1;i<=n;i++) {
        scanf("%d",&a[i]);
    }
    for (int i=1;i<=n-1;i++) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        G[u].push_back({v,w});
        G[v].push_back({u,w});
    }
    dfs(1,-1,0);
    printf("%lld\n",max(0LL,dp[1]));
}

int main() {
    cin>>T;
    while(T--) solve();
    return 0;
}

J.The-Escape-Plan-of-Groundhog

标签：二维前缀和

暴力枚举行区间，然后用前缀和维护列，遇到整列都是1的情况就在cnt里记录当前的前缀和，并根据之前的记录情况计算答案。遇到行上的1不连续时就清空cnt。

#include<bits/stdc++.h>
using namespace std;

const int N=5e2+5;

int n,m;

int row[N][N],col[N][N],tot[N][N],a[N][N];

int sum,ans;

int cnt[N*N*2];

vector<int>ls;

void modify(int sum) {
    ans+=cnt[sum-1]+cnt[sum]+cnt[sum+1];
}

void cnt_clear() {
    for (auto x:ls) cnt[x]=0;
    ls.clear();
}

int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            scanf("%d",&a[i][j]);
            if (a[i][j]==0) a[i][j]=-1;
            row[i][j]=row[i][j-1]+a[i][j];
            col[i][j]=col[i-1][j]+a[i][j];
            tot[i][j]=tot[i-1][j]+tot[i][j-1]-tot[i-1][j-1]+a[i][j];
        }
    }
    for (int i=1;i<=n-1;i++) {
        for (int j=i+1;j<=n;j++) {
            for (int k=1;k<=m;k++) {
                if (a[i][k]==-1 || a[j][k]==-1) {
                    cnt_clear();sum=0;continue;
                }
                if (col[j][k]-col[i-1][k]==j-i+1) {
                    modify(sum+N*N);
                    sum+=col[j-1][k]-col[i][k];
                    if (cnt[sum+N*N]==0) ls.push_back(sum+N*N);
                    cnt[sum+N*N]++;
                }
                else {
                    sum+=col[j-1][k]-col[i][k];
                }
            }
            cnt_clear();sum=0;
        }
    }
    printf("%d\n",ans);
    return 0;
}

A.Groundhog-and-2-Power-Representation

F.Groundhog-Looking-Dowdy

K.The-Flee-Plan-of-Groundhog

E.Groundhog-Chasing-Death

B.Groundhog-and-Apple-Tree

J.The-Escape-Plan-of-Groundhog