526互联

The 2023 ICPC Asia Hong Kong Regional Programming Contest (AEFHKL)

发布时间 2023-12-05 00:46:03作者: liyishui

在考试周打比赛就像在刀尖上跳舞，在赌桌上下筹码

我只希望专业课它别挂

不然搞钱吃饭就麻烦了

====================

A.TreeScript

学弟写的，阅读理解题，读对了就是简单树dp

#include<bits/stdc++.h>
using namespace std;
const int N=2e5;
int n,f[N+5];
vector<int> e[N+5];
void dfs(int x)
{
    int Mx1=0,Mx2=0;
    for(int i=0,lim=e[x].size();i<lim;++i)
    {
        int y=e[x][i];
        dfs(y);
        if(f[y]>=Mx1) Mx2=Mx1,Mx1=f[y];
        else if(f[y]>Mx2) Mx2=f[y];
    }
    f[x]=max(Mx1,Mx2+1);
}
void Kafka()
{
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        int tmp;
        cin>>tmp;
        if(tmp) e[tmp].push_back(i);
    }
    dfs(1);
    cout<<f[1]<<endl;
    for(int i=1;i<=n;++i) e[i].clear();
}
signed main()
{
    int T;
    cin>>T;
    while(T--) Kafka();
    return 0;
}
/*
4
3
0 1 2
7
0 1 2 2 1 4 1
3
0 1 2
7
0 1 2 2 1 4 1
 */

 

E.Goose, Goose, DUCK?

发现可以固定右端点->

在右端点往右移动的过程中其实影响的只有一个数，撤销掉之前的操作，再补上新的即可

（显然一个数对答案的影响是一段连续区间）

转化成数据结构，区间加法，求区间内有多少为0的个数

线段树可以做，除了常规区间操作外加一个维护最小值和最小值个数，显然0的个数==最小值为0时最小值的个数

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int cnt=0,n,k;
vector<int>v[maxn];
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
// 区间加
struct seg_tree{
    int mi,micnt;// 区间最小值 最小值个数
    int cnt0;// 区间为0的个数和
    int lazy;// lazy tag
}t[maxn<<2];

void dowwn(int rt,int val){
    t[rt].mi+=val;
    if(t[rt].mi==0) t[rt].cnt0=t[rt].micnt;
    else t[rt].cnt0=0;
    t[rt].lazy+=val;
    
}
void down(int rt){
    if(!t[rt].lazy) return ;
    dowwn(ls,t[rt].lazy);
    dowwn(rs,t[rt].lazy);
    t[rt].lazy=0;
}
void up(int rt){
    int tmp=min(t[ls].mi,t[rs].mi);
    t[rt].mi=tmp;
    
    t[rt].micnt=0;
    if(t[ls].mi==tmp) t[rt].micnt+=t[ls].micnt;
    if(t[rs].mi==tmp) t[rt].micnt+=t[rs].micnt;
    
    if(t[rt].mi==0) t[rt].cnt0=t[rt].micnt;
    else t[rt].cnt0=0;
    //cout<<rt<<" rt "<<t[rt].mi<<" "<<t[rt].micnt<<endl;
}
void update(int ql,int qr,int val,int rt=1,int l=1,int r=n){
//    cout<<ql<<" "<<qr<<" "<<l<<" "<<r<<endl;
    if(l>=ql&&r<=qr){
        dowwn(rt,val);
        return ;
    }
    down(rt);
    if(ql<=mid) update(ql,qr,val,ls,l,mid);
    if(qr>mid) update(ql,qr,val,rs,mid+1,r);
    up(rt);
}

int query(int ql,int qr,int rt=1,int l=1,int r=n){
    if(l>=ql&&r<=qr){
        return t[rt].cnt0;    
    }
    down(rt);
    int ans=0;
    if(ql<=mid) ans+=query(ql,qr,ls,l,mid);
    if(qr>mid) ans+=query(ql,qr,rs,mid+1,r);
    up(rt);
    return ans;
}

void build(int rt=1,int l=1,int r=n){
   t[rt].mi=0;
   t[rt].micnt=r-l+1;
   t[rt].cnt0=r-l+1;
   t[rt].lazy=0;
   if(l==r) {
       return;
   }
   build(ls,l,mid);
   build(rs,mid+1,r);
}

int vis[maxn],p[maxn],sz[maxn],a[maxn];
int main(){
    
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    cin>>n>>k;
    
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(!vis[x]){
            vis[x]=++cnt;
            p[cnt]=1;// 指向0
            v[cnt].push_back(-1);
            v[cnt].push_back(i);
            sz[cnt]=1;
        }
        else {
            sz[vis[x]]++;
            v[vis[x]].push_back(i);
        }
        a[i]=x;
    }
    
    build();

    long long tot=0;
    for(int i=1;i<=cnt;i++){
        int l=p[i]+k-1;
        if(l<=sz[i]) {
            int r;
            if(l==sz[i]) r=n;
            else r=v[i][l+1]-1;
        //    cout<<v[i][l]<<" ??"<<r<<endl;
            update(v[i][l],r,1);
        }
    }

//    cout<<query(1,n)<<endl;
    tot+=query(1,n);

    for(int i=2;i<=n;i++){
        
        int id=vis[a[i-1]];
        int l=p[id]+k-1,r;
    //    cout<<i<<" :"<<endl;
        if(l<=sz[id]) {
        //    cout<<l<<" "<<sz[id]<<" "<<v[id][l+1]-1<<endl;
            if(l==sz[id]) r=n;
            else r=v[id][l+1]-1;
        //    cout<<v[id][l]<<" "<<r<<endl;
            update(v[id][l],r,-1);
        }
        
        p[id]++;
        l=p[id]+k-1;
        if(l<=sz[id]) {
            if(l==sz[id]) r=n;
            else r=v[id][l+1]-1;
            update(v[id][l],r,1);
        }
        
        //cout<<i<<" #"<<6<<endl;
    //    cout<<"ans: "<<i<<" "<<query(i,n)<<endl;
        
        tot+=query(i,n);
    }
    
    cout<<tot<<endl;
}

F.Sum of Numbers

最开始贪心的想法是每段均分，然后有的多一，暴力dfs

但其实有问题，记上一段的长度为x，第i段的范围应该为[x-1,x+1]（当然要判下能否取到

然后就是高精的问题，用acwing vector的模板t掉了，换成手写数组

那场的金牌题，vp时开了来不及写，赛后补的，交了20发，最开始有点想当然了，写得不用心

#include<bits/stdc++.h>
using namespace std;
int n,k,avg;
int ans[20];
string s;
int a[10][(int)2e5+10];
int sum[(int)2e5+10];
int out[(int)2e5+10],l=0;
void dfs(int step,int tot){
    //    cout<<step<<" "<<tot<<endl;
    
    if(step==k+2){
        if(tot!=0) return;
        int last=n-1,len=0;
        for(int i=1;i<=k+1;i++) len=max(len,ans[i]);
        for(int i=1;i<=len+5;i++)sum[i]=0;
        
        for(int i=1;i<=k+1;i++){
            for(int j=1;j<=ans[i];j++){
                a[i][j]=(s[last]-'0');
                last--;
            }
            for(int j=ans[i]+1;j<=len+5;j++) a[i][j]=0;
        }
        
         for(int i=1;i<=len+2;i++) {
             sum[i]=0;
             for(int j=1;j<=k+1;j++){
                 sum[i]+=a[j][i];
             }
         }
             
        for(int i=1;i<=len;i++) {
            int d=sum[i]/10;
            sum[i]%=10;
            sum[i+1]+=d;
        }

        if(sum[len+1]) len++;    
        
        
        if(sum[len]>=10) {
            len++;
            sum[len]+=sum[len-1]/10;
            sum[len-1]%=10;
        }
        if(sum[len]>=10) {
            len++;
            sum[len]+=sum[len-1]/10;
            sum[len-1]%=10;
        }
    
        if(len<l){
            l=len;
            for(int i=1;i<=len;i++) out[i]=sum[i];
        }
        else if(l==len){
            int flag=1;
            for(int i=l;i>=1;i--){
                if(sum[i]!=out[i]){
                    if(sum[i]>out[i]) {}
                    else flag=0;
                }
                if(sum[i]!=out[i]) break;
            }
            if(flag==0){
                for(int i=1;i<=len;i++) out[i]=sum[i];
            }
        }        
        return ;
    }
    if(step!=1){
        for(int i=max(1,ans[step-1]-1);i<=min(tot,ans[step-1]+1);i++){
            if(tot>=i){
                ans[step]=i;
                dfs(step+1,tot-i);
            }
        }

    }
    else {
        ans[step]=avg-1;
        dfs(step+1,tot-(avg-1));
        ans[step]=avg;
        dfs(step+1,tot-avg);
        ans[step]=avg+1;
        dfs(step+1,tot-(avg+1));
        ans[step]=avg+2;
        dfs(step+1,tot-(avg+2));
    }
}
void solve(){
    cin>>n>>k;
    cin>>s;
    l=2e5+3;
    avg=n/(k+1);
    dfs(1,n);
    for(int i=l;i>=1;i--) cout<<out[i];
    cout<<endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
//    freopen("lys.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}

H.Another Goose Goose Duck Problem

签到，好像是个简单数学，没看，直接丢该队友了

#include<bits/stdc++.h>
using namespace std;
int l,r,b,k;
int ans;
signed main()
{
	cin>>l>>r>>b>>k;
	if(l<=b) ans=b;
	else if(l%b==0) ans=l;
	else ans=(l/b+1)*b;
	cout<<1LL*ans*k<<endl;
	return 0;
}

K.Maximum GCD

签到，数学，没看，学弟写的

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
int n,a[N+5],Min;
signed main()
{
    Min=2e9;
    cin>>n;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        Min=min(Min,a[i]);
    }
    int ans=-1;
    for(int i=1;i<=n;++i)
    {
        if(a[i]==Min||a[i]>=Min*2) continue;
        ans=0;
    }
    ans=ans?Min:Min/2;
    cout<<max(1,ans)<<endl;
    return 0;
}

L - Permutation Compression

首先n>m+k无解

其次如果出现的先后顺序不一样也无解（这个一直没有考虑到，做的不好

然后是判断有无解：

显然删除的顺序会影响到答案，从最大的数开始删最优

对于某数x，它合法的删除范围为(左边第一个大于它的数，右边第一个大于它的数）

预处理出每个数的合法删除范围（写个线段树上二分），然后跟手上有的操作数排完序跑双指针

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int n,m,k,a[maxn],b[maxn],l[maxn],vis[maxn],need[maxn],to[maxn];

#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
struct seg_tree{
    int mx,real_len;
    int l,r;
}t[maxn<<2];
void up(int rt){
    t[rt].real_len=t[ls].real_len+t[rs].real_len;
    t[rt].mx=max(t[ls].mx,t[rs].mx);
}
void build(int rt=1,int l=1,int r=n){
    t[rt].l=l,t[rt].r=r;
    t[rt].real_len=r-l+1;
    if(l==r) {
        t[rt].mx=a[l];
        return;
    }
    build(ls,l,mid);build(rs,mid+1,r);
    up(rt);
}
void del(int pos,int rt=1,int l=1,int r=n){
    if(l==r){
        t[rt].mx=-2333;
        t[rt].real_len=0;
        return;
    }
    if(pos<=mid) del(pos,ls,l,mid); 
    else del(pos,rs,mid+1,r);
    up(rt);
}
int query(int ql,int qr,int rt=1,int l=1,int r=n){
    if(l>=ql&&r<=qr){
        return t[rt].mx;
    }
    int ans=-2333;
    if(ql<=mid) ans=max(ans,query(ql,qr,ls,l,mid));
    if(qr>mid) ans=max(ans,query(ql,qr,rs,mid+1,r));
    up(rt);
    return ans;
}
const int INF=1e9+7;
int ask_R(int ql,int qr,int val,int rt=1,int l=1,int r=n){
    if(ql>qr) return INF;
    if(l==r){
        return t[rt].mx>=val ? l : INF; 
    }
    int res=INF;
    if(ql<=mid){
        if(t[ls].mx>=val) res=ask_R(ql,qr,val,ls,l,mid);
        if(res==INF&&t[rs].mx>=val) res=ask_R(ql,qr,val,rs,mid+1,r);
    }
    else if(t[rs].mx>=val){
        res=ask_R(ql,qr,val,rs,mid+1,r);
    }
    return res;
}
int ask_L(int ql,int qr,int val,int rt=1,int l=1,int r=n){
    if(ql>qr) return INF;
    if(l==r){
        return t[rt].mx>=val ? l : INF; 
    }
    int res=INF;
    if(qr>mid){
        if(t[rs].mx>=val) res=ask_L(ql,qr,val,rs,mid+1,r);
        if(res==INF&&t[ls].mx>=val) res=ask_L(ql,qr,val,ls,l,mid);
    }
    else if(t[ls].mx>=val){
        res=ask_L(ql,qr,val,ls,l,mid);
    }
    return res;
}
int askNum(int ql,int qr,int rt=1,int l=1,int r=n){
    if(ql>qr) return 0;
    if(l>=ql&&r<=qr){
        return  t[rt].real_len;
    }
    int ans=0;
    if(ql<=mid) ans+=askNum(ql,qr,ls,l,mid);
    if(qr>mid) ans+=askNum(ql,qr,rs,mid+1,r);
    up(rt);
    return ans;
}
struct node{
    int pos,val;
}q[maxn];
bool cmp(node a,node b){
    return a.val>b.val;
}
bool mycmp(int a,int b){
    return a>b;
}
void solve(){
    cin>>n>>m>>k;
    
    for(int i=1;i<=n;i++) vis[i]=0;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
        to[a[i]]=i;
    }
    for(int i=1;i<=m;i++) {
        cin>>b[i];
        vis[b[i]]=1;
        
    }
    for(int i=1;i<=k;i++) {
        cin>>l[i];
    }
    
    if(n>m+k) {
        cout<<"NO"<<endl;
        return ;
    }
    for(int i=1;i<m;i++){
        if(to[b[i]]>to[b[i+1]]) {
            cout<<"NO"<<endl;
            return;
        }
    }
    
    build();
    
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(!vis[a[i]]){ // need to be delet
            cnt++;
            q[cnt].pos=i,q[cnt].val=a[i];
        }
    }
    
    sort(q+1,q+1+cnt,cmp);
    
    for(int i=1;i<=cnt;i++){
        int len=0;
        int ans;
//        cout<<q[i].pos<<" # "<<endl;
        ans=ask_R(q[i].pos+1,n,q[i].val);
//        cout<<"R: "<<ans<<endl;
        if(ans==INF) ans=n;
        else ans--;
        len+=askNum(q[i].pos,ans);
        
        ans=ask_L(1,q[i].pos-1,q[i].val);
//        cout<<"L: "<<ans<<endl;
        if(ans==INF) ans=1;
        else ans++;
        len+=askNum(ans,q[i].pos);
        len--;
//        cout<<"len: "<<len<<endl;
        del(q[i].pos);
        need[i]=len;
    }
    
    sort(need+1,need+cnt+1,mycmp);
    sort(l+1,l+k+1,mycmp);

    
    int p=1,flag=1;
    l[k+1]=0;
    for(int i=1;i<=cnt;i++){
        while(l[p]>need[i]) p++;
        if(p==k+1) {
            flag=0;break;
        }
        else     p++;
    }
    
    if(flag) cout<<"YES"<<endl;
    else cout<<"NO"<<endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    //freopen("lys.in","r",stdin);
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}