2019ICPC徐州网络赛解题日志

2019-09-07

字数统计: 2.7k字 | 阅读时长: 15分

按照过题顺序放代码和思路。

C 签到

复杂度$O(1)$。
好像是codeforces 4A，岑岑以前做过，抢了个一血。

int main(){
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n<=2)printf("NO\n");
        else if(n%2==0)printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

B 动态开点线段树

复杂度$O(mlogn)$。
这题想过可以pdbs+二分，想过可以map+并查集，但是个人感觉，都不如动态开点好写。

那么问题就变成了求对于全局来说，区间内最小未出现的数字是多少便可，经典操作。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+10;
int lson[maxn*20],rson[maxn*20],c[maxn*20];
int tot=0;
int x,y;
void update(int p,int v,int l,int r,int rt){
    if(l==r){
        c[rt]=1;return;
    }int mid = l+r>>1;
    if(p<=mid){
        if(!lson[rt])lson[rt]=++tot;
        update(p,v,l,mid,lson[rt]);
    } else {
        if(!rson[rt])rson[rt]=++tot;
        update(p,v,mid+1,r,rson[rt]);
    }
    c[rt]=c[lson[rt]]+c[rson[rt]];
}
int ans;
void query(int L,int R,int l,int r,int rt){
    if(ans>=L||c[rt]==r-l+1)return;
    int mid = l+r>>1;
    if(L<=l&&R>=r){
        if(c[rt]==r-l+1)return;
        if(l==r){
            ans=l;return;
        }
        query(L,R,l,mid,lson[rt]);
        if(ans>=L)return;
        query(L,R,mid+1,r,rson[rt]);
        return;
    }
    if(L<=mid)query(L,R,l,mid,lson[rt]);
    if(ans>=L)return;
    if(R>mid)query(L,R,mid+1,r,rson[rt]);
}
int main(){
    int n,q;
    cin>>n>>q;++tot;
    while(q--){
    scanf("%d%d",&x,&y);
        if(x==1){
            update(y,1,1,n,1);
        } else {
            ans = -1;
            query(y,n,1,n,1);
            printf("%d\n",ans);
        }
    }
    return 0;
}

D 字符串hash

复杂度$O(\Sigma(|S|+|T|))$。
这题挺显然的，对$S$和$T$分别hash处理一下就好了，看通过率这么高，大胆猜测没有卡hash，直接莽就完事了。

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn = 1e5+10;
int lens,lent;
char t[maxn],s[maxn];
ull base=2333;
ull po[maxn],hs[maxn],ht[maxn];
ull geth(ull h[],int l,int r){
    return (ull)h[r]-po[r-l+1]*h[l-1];
}
int main(){
    po[0]=1;for(int i=1;i<maxn;++i)po[i]=po[i-1]*base;
    scanf("%s",t+1);
    lent = strlen(t+1);
    for(int i=1;i<=lent;++i)ht[i]=ht[i-1]*base+t[i];
    int q;cin>>q;
    while(q--){
        scanf("%s",s+1);
        lens = strlen(s+1);
        if(lens == lent){
            if(strcmp(s+1,t+1)==0){puts("jntm!");}
            else puts("friend!");
        }
        else if(lens < lent){
            ull ss = 0;
            bool ok=0;
            for(int i=1;i<=lens;++i)ss=ss*base+s[i];
            for(int i=lens;(!ok)&&i<=lent;++i){
                if(geth(ht,i-lens+1,i) == ss)ok=1;
            }
            if(ok){
                puts("my child!");
            } else puts("oh, child!");
        }
        else{
            bool ok=0;
            for(int i=1;i<=lens;++i)hs[i]=hs[i-1]*base+s[i];
            for(int i=lent;(!ok)&&i<=lens;++i){
                if(geth(hs,i-lent+1,i) == ht[lent])ok=1;
            }
            if(ok){
                puts("my teacher!");
            } else puts("senior!");
        }
    }
    return 0;
}

E 线段树

复杂度$O(nlogn)$
写的$O(nlogn)$做法，显然$O(nlog^2n)$比较好写，线段树+二分便可，但是怕被卡时间复杂度。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
const int maxn = 5e5+10;
int n,m;
int maxv[maxn<<2];
int a[maxn];
void build(int l,int r,int rt){
    if(l==r){
        scanf("%d",maxv+rt);
        a[l]=maxv[rt];
        return;
    }int mid = l+r>>1;
    build(lson);build(rson);
    maxv[rt] = max(maxv[rt<<1],maxv[rt<<1|1]);
}
int ans;
void query(int L,int R,int lim,int l,int r,int rt){
    if(ans>-1||maxv[rt]<lim)return;
    int mid = l+r>>1;
    if(L<=l&&R>=r){
        if(l==r){
            if(maxv[rt]>=lim)ans = l-L;return;
        }
        if(maxv[rt<<1|1]>=lim)query(L,R,lim,rson);
        else query(L,R,lim,lson);
        return;
    }
    if(R>mid)query(L,R,lim,rson);
    if(ans>-1)return;
    if(L<=mid)query(L,R,lim,lson);
}
int main(){
    cin>>n>>m;
    build(1,n,1);
    for(int i=1;i<=n;++i){
        ans = -1;
        query(i+1,n,a[i]+m+1,1,n,1);
        printf("%d%c",ans," \n"[i==n]);
    }
    return 0;
}

G 回文自动机+前缀和

时间复杂度$O(26*|S|)$。
对于回文自动机里面每个状态$sta$，可以计算它的出现次数$cnt$、长度$len$等信息，那么只需要前缀和维护一下区间$[L,R]$内字符$c$的出现次数便可，那么就可以维护出$sta$对应回文串的贡献$val$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5+10;
const int N = 26;
int pre[maxn][N];
struct pam{
    int val[maxn];
    int nxt[maxn][N],fail[maxn];
    int len[maxn],S[maxn],ppos[maxn];
    int cnt[maxn],num[maxn];
    int last,n,p;
    int newnode(int l){
        memset(nxt[p],0,sizeof nxt[p]);
        cnt[p]=num[p]=0;
        len[p]=l;
        return p++;
    }
    void init(){
        p=0;
        newnode(0);newnode(-1);
        last=n=0;
        S[n]=-1;
        fail[0]=1;
    }
    int get_fail(int x){
        while(S[n-len[x]-1]!=S[n])x=fail[x];return x;
    }
    void add(int c,int pos){
        c-='a';
        S[++n]=c;
        int cur=get_fail(last);
        if(!nxt[cur][c]){
            int now=newnode(len[cur]+2);
            ppos[now]=pos;
            fail[now]=nxt[get_fail(fail[cur])][c];
            nxt[cur][c]=now;
            num[now]=num[fail[now]]+1;
        }
        last=nxt[cur][c];
        cnt[last]++;
        if(len[last]<3)val[last]=1;
        else val[last]=val[cur]+((pre[pos-1][c] - pre[pos - len[last]+1][c]) ==0 );
    }
    void Count(){
        for(int i=p-1;i>=0;--i)cnt[fail[i]]+=cnt[i];
        ll ans = 0;
        for(int i=p-1;i>=0;--i){
            ans += cnt[i]*val[i];
        }printf("%lld\n",ans);
    }
}p;
int len;
char s[maxn];
int main(){
    p.init();
    scanf("%s",s+1);
    len = strlen(s+1);
    for(int i=1;i<=len;++i){
        p.add(s[i],i);
        memcpy(pre[i],pre[i-1],sizeof pre[i]);
        pre[i][s[i]-'a']++;
    }
    p.Count();
    return 0;
}

M 贪心

看了一下代码，好短，队友把它秒了……

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
char s[1000100],t[1000100];
queue<int> q[200];
int main(){
    scanf("%d %d %s %s",&n,&m,s,t);
    int N=max(n,m);
    for(int i=n;i<N;i++) s[i]='a'-1;
    for(int i=m;i<N;i++) t[i]='a'-1;
    int dengyu=0,dayu=0,ans=-1;
    q[t[0]+1].push(0);
    for(int i=0;i<n;i++){
        for(int j='a';j<=s[i];j++){
            while(!q[j].empty()){
                int u=q[j].front();
                q[j].pop();
                ans=max(ans,u+n-i);
            }
        }
        if(s[i]==t[dengyu]) {
            dengyu++;
            q[t[dengyu]+1].push(dengyu);
        }
    }
    printf("%d\n",ans);
    return 0;
}

K 几何？猜结论？

复杂度$O(n^2logn)$
一开始以为是很难的几何，看到$n=1000$，不妨考虑对所有$pair(p[i],p[j])$求出中点$q$，可以知道重复次数最多的$q$就是中心点最佳位置了，显然，因为每次重叠，都减少了一组点的对应点构造。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e3+10;
pair<int,int> p[maxn];
int n;
map<pair<int,int>,int> mp,vis;
pair<int,int> add(pair<int,int> a,pair<int,int> b){
    return make_pair((a.first+b.first)/2,(a.second+b.second)/2);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i){
        scanf("%d%d",&p[i].first,&p[i].second);
        p[i].first*=2;p[i].second*=2;
        vis[p[i]]++;
        for(int j=1;j<i;++j){
            mp[add(p[i],p[j])]++;
        }
    }
    if(n==1){
        puts("0");return 0;
    }
    int ans = n;
    for(auto v:mp)ans = min(ans , n- 2*v.second - vis[v.first]);
    cout<<ans;
    return 0;
}

I 主席树

复杂度$O(nlogn)$。
对于每个$a_i$，贡献的位置是一组$pos_{i,j}$，不妨用主席树维护出来，那么就变成了：查询第$L$棵树到第$R$棵树中间，$L \le pos_{i,j} \le R$的贡献值。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
vector<int> yz[maxn];
int n,m;
int a[maxn],pa[maxn];
int T[maxn],lson[maxn*200],rson[maxn*200];
int c[maxn*200];
int tot;
void update(int &u,int p,int l,int r){
    ++tot;lson[tot]=lson[u];rson[tot]=rson[u];c[tot]=c[u]+1;
    u=tot;
    if(l==r)return;
    int mid=l+r>>1;
    if(p<=mid)update(lson[u],p,l,mid);
    else      update(rson[u],p,mid+1,r);
}
int query(int lrt,int rrt,int L,int R,int l,int r){
    if(L<=l&&R>=r){
        return c[rrt] - c[lrt];
    }int mid = l+r>>1,ret=0;
    if(L<=mid)ret+=query(lson[lrt],lson[rrt],L,R,l,mid);
    if(R>mid) ret+=query(rson[lrt],rson[rrt],L,R,mid+1,r);
    return ret;
}
int main(){
    ++tot;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        scanf("%d",a+i);
        pa[a[i]]=i;
    }
    for(int i=2;i<=n;++i){
        for(int j=1;j*j<=i;++j){
            if(i%j==0){
                yz[i].push_back(pa[j]);
                if(j!=i/j&&i>i/j)yz[i].push_back(pa[i/j]);
            }
        }
    }
    for(int i=1;i<=n;++i){
        T[i]=T[i-1];
        for(auto v:yz[a[i]]){
            update(T[i],v,1,n);
        }
    }
    int l,r;
    while(m--){
        scanf("%d%d",&l,&r);
        printf("%d\n",query(T[l-1],T[r],l,r,1,n));
    }
    return 0;
}

A 博弈找规律

队友发现其实就是个斐波那契数列，然后就冲了。

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int n=cin.nextInt();
        BigInteger M = BigInteger.valueOf(1000000000000000L);
        BigInteger m[]=new BigInteger[n];
        BigInteger b[]=new BigInteger[n];
        BigInteger a[]=new BigInteger[n];
        BigInteger fib[]=new BigInteger[160];
        fib[1]=BigInteger.valueOf(2);fib[2]=BigInteger.valueOf(3);
        for(int i=3;i<=100;i++){
            fib[i]=fib[i-1].add(fib[i-2]);
        }
        for(int i=0;i<n;++i){
            a[i]=BigInteger.ONE;
            m[i]=cin.nextBigInteger();
            b[i]=cin.nextBigInteger();
        }
        BigInteger res = linear(a,b,m,n);
        if(res.equals(BigInteger.valueOf(-1))){
            System.out.println("Tankernb!");
        }
        else if(res.compareTo(M)<=0){
            BigInteger N=res;
            int ok=0;
            for(int i=1;i<=100;i++){
                if(N.equals(fib[i])==true){
                    ok=1;
                }
            }
            if(ok==0) System.out.println("Zgxnb!");
            else System.out.println("Lbnb!");
        }
        else System.out.println("Tankernb!");
    }
}

J 树形dp

“dfs一下求个逆元就出来了”。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
const int mod=1000000007;
vector<int> edge[1000100];
ll qpow(ll a,ll w){
  ll ret=1;
  while(w){if(w&1)ret=ret*a%mod;a=a*a%mod;w>>=1;}return ret;
}
long long ac[1000010];
int deep[1000010];
void dfs(int p,int fa){
  if(edge[p].size()==1&&fa!=-1){
    ac[p]=1;
    deep[p]=0;
  }
  else{
    int k=edge[p].size()-1,maxdeep=-1;
    if(fa==-1) k++;
    for(int i=0;i<edge[p].size();i++){
      int v=edge[p][i];
      if(v!=fa){
        dfs(v,p);
        deep[p]=max(deep[p],deep[v]+1);
        maxdeep=max(maxdeep,deep[v]);
      }
    }
    long long rate=0;
    for(int i=0;i<edge[p].size();i++){
      int v=edge[p][i];
      if(v==fa) continue;
      if(deep[v]!=maxdeep) rate=(rate+qpow(k,mod-2)%mod)%mod;
      else rate=(rate+(1-ac[v]+mod)*qpow(k,mod-2)%mod)%mod;
    }
    rate=qpow(rate,k);
    rate=(1-rate+mod)%mod;
    ac[p]=rate;
  }
}
int main(){
    cin>>n;
    for(int i=1;i<n;i++) {
      int a,b;
      scanf("%d %d",&a,&b);
      edge[a].push_back(b);
      edge[b].push_back(a);
    }
    dfs(1,-1);
    printf("%lld\n",ac[1]);
    return 0;
}