[数据结构与算法]AtCoder Regular Contest 题解

arc138

比赛传送门

A

值域线段树动态开点
先读入k个数字，插入
然后读入剩下的数字x，查询比我小的最大下标，维护ans
如果答案ans大于等于n输出-1

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
int x,n,k,root,o,ans=1e9;
struct node{
    int s[2];
    int mx=-1e9;
    #define ls tr[u].s[0]
    #define rs tr[u].s[1]
}tr[N*20];
void pushup(int u){
    tr[u].mx=max(tr[ls].mx,tr[rs].mx);
}
void update(int &u,int x,int v,int l=1,int r=1e9){
    if(!u)u=++o;
    if(l==r)return tr[u].mx=max(tr[u].mx,v),void();
    int mid=l+r>>1;
    if(x<=mid)update(ls,x,v,l,mid);
    else update(rs,x,v,mid+1,r);
    pushup(u);
}
int query(int u,int ql,int qr,int l=1,int r=1e9){
    if(!u)return -1e9;
    if(l>qr||r<ql)return -1e9;
    if(l>=ql&&r<=qr)return tr[u].mx;
    int mid=l+r>>1;
    int a=query(ls,ql,qr,l,mid);
    int b=query(rs,ql,qr,mid+1,r);
    return max(a,b);
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=k;i++){
        cin>>x;
        update(root,x,i);
    }
    for(int i=k+1;i<=n;i++){
        cin>>x;
        if(x==1)continue;
        ans=min(ans,i-query(root,1,x-1));
    }
    if(ans>=n)ans=-1;
    cout<<ans;
}

如果A题不用值域线段树的话还有一种更好的线性解法（不sort的话）
因为值从大到小，位置从小到大排列
这样的话，一定能合法更新：我在左边，凡是我去更新的一定都是大于我的；我在右边不断更新合法的离中线最近的下标值

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
struct node{
    int v,i;
    bool operator<(const node&t)const{
        if(v==t.v)return i<t.i;
        else return v>t.v;
    }
}a[N];
int n,k;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++){cin>>a[i].v;a[i].i=i;}
    sort(a,a+n);
    int ans=1e9;
    int p=1e9;
    for(int i=0;i<n;i++){
        int x=a[i].i;
        if(x>=k)p=min(p,x);
        else ans=min(ans,p-x);
    }
    if(ans>=n)cout<<"-1";
    else cout<<ans;
}

B

用deque去倒着模拟
还是很不错的题目

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int mp[2],n,x;
deque<int>q;
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    mp[0]=0;
    mp[1]=1;
    for(int i=1;i<=n;i++){
        cin>>x;
        q.push_back(x);
    }
    while(n--){
        if(mp[q.back()]==0)q.pop_back();
        else if(mp[q.front()]==0){
            q.pop_front();
            swap(mp[0],mp[1]);
        }
    }
    if(q.empty())cout<<"Yes";
    else cout<<"No";
}

C

很nice的一道构造题
首先要猜一个结论，不限置换次数的话，一定要可以拿到前n/2大的数字
假设我要拿的是-1，我不拿的是1，做一个前缀和
构造之后的序列的要求是要任一个位置前缀和非负（要让1尽量塞到前面
求出前缀和序列最小值sum[x] 下标k=x，然后左移k次就好了（我也不知道为啥这样就行了
（大概是因为想削弱前面的一个个-1对前缀和的贡献，把他们都塞到后面去之后，前面的一个个1会削弱这些-1对前缀和的贡献
（对于的实际物理意义就是把小的塞到前面让对手先拿

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,x,ans;
int b[N],s[N];
struct node{
    int v,id;
    bool operator<(const node&t)const{
        return v>t.v;
    }
}a[N];
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){cin>>a[i].v;a[i].id=i;}
    sort(a+1,a+1+n);
    for(int i=1;i<=n/2;i++)b[a[i].id]=-1,ans+=a[i].v;
    for(int i=n/2+1;i<=n;i++)b[a[i].id]=1;
    for(int i=1;i<=n;i++)s[i]=s[i-1]+b[i];
    cout<<min_element(s+1,s+n+1)-s<<" "<<ans;
}

D

跟luogu7949撞题了
一般的格雷码都是每一个都与前一个间隔1位，这个是间隔k位
如果有解输出序列
什么时候无解？
如果k是偶数的时候或者k>=n的时候无解
n=1，k=1的时候要特判一下

#include<bits/stdc++.h>
using namespace std;
#define For(i,j,k) for(int i=j;i<=k;i++)
#define N (1<<20)
int a[N];
void solve(int n,int k){
	int len=1<<n;
	if(n==k+1){
		For(i,0,len-1)
			if(i&1) a[i]=i^(i>>1)^(len-1);
			else a[i]=i^(i>>1);
		return ;
	}
	solve(n-1,k);
	int pos=1<<(n-1),val=(1<<n)-(1<<(n-k));
	For(i,pos,len-1) a[i]=a[--pos]^val;
}
signed main(){
	int n,k,len;
	scanf("%d%d",&n,&k);
	len=1<<n;
	if(n==1 && k==1){puts("Yes\n0 1");return 0;}
	if(n<=k || !(k&1)){puts("No");return 0;}
	puts("Yes");
	solve(n,k);
	For(i,0,len-1) printf("%d ",a[i]);
}

E

F

arc137

A

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
    int l,r;
    cin>>l>>r;
    for(int d=r-l;d>=1;d--){
        for(int i=l;i+d<=r;i++){
            int j=i+d;
            if(__gcd(i,j)==1){
                cout<<d;
                return 0;
            }
        }
    }
}

B

答案一定是沿着初始sum向左右两边扩张的序列
所以求一下序列中0比1多的最大值和1比0多的最大值加起来再+1就是答案ans

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int a[N],n,sum;
int x,y,ans;
int f[N];
int cal(int a[]){
    int maxx=0,minn=0;
    for(int i=1;i<=n;i++){
        if(a[i]==1)f[i]=f[i-1]+1;
        if(a[i]==0)f[i]=f[i-1]-1;
        maxx=max(maxx,f[i]-minn);
        minn=min(minn,f[i]);
    }
    return maxx;
}
signed main(){
    ios::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ans+=cal(a);
    for(int i=1;i<=n;i++)a[i]=1-a[i];
    ans+=cal(a);
    cout<<ans+1;
}

C

打表找规律

D

子集和dp

E

费用流裸题

F

多项式，求生成函数的第n项

arc136

A

#include<bits/stdc++.h>
using namespace std;
int n;
string s;
int t=0;
signed main(){
    cin>>n>>s;
    for(auto x:s){
        if(x=='C'){
            if(t==1)putchar('B');
            t=0;
            putchar('C');
        }
        if(x=='B'){
            if(t==1)putchar('A'),t=0;
            else t++;
        }
        if(x=='A'){
            if(t==1)putchar('A');
            else putchar('A');
        }
    }
    if(t==1)putchar('B');
}

B

#include<bits/stdc++.h>
using namespace std;
const int N=5050;
int n;
int a[N],b[N];
int tr[N];
void add(int x,int c){
    for(int i=x;i<=5051;i+=i&-i)tr[i]+=c;
}
int sum(int x){
    int ans=0;
    for(int i=x;i;i-=i&-i)ans+=tr[i];
    return ans;
}
int cal(int a[]){
    memset(tr,0,sizeof tr);
    int ans=0;
    for(int i=n;i>=1;i--){
        ans+=sum(a[i]-1+1);
        add(a[i]+1,1);
    }
    return ans&1;
}
signed main(){
    //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    int t1=cal(a);
    int t2=cal(b);
    
    sort(a+1,a+n+1),sort(b+1,b+n+1);
    for(int i=1;i<=n;i++){
        if(a[i]!=b[i]){
            cout<<"No";
            return 0;
        }
    }
    for(int i=2;i<=n;i++){
        if(a[i]==a[i-1]){
            cout<<"Yes";
            return 0;
        }
    }
    if(t1==t2)cout<<"Yes";
    else cout<<"No";
}

C

#include<bits/stdc++.h>
using namespace std;
#define int long long
int ans,n;
const int N=2e5+10;
int a[N],b[N],ma;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ma=a[1];
    a[n+1]=a[1];
    for(int i=2;i<=n+1;i++){
        int t=a[i]-a[i-1];
        if(t>0)ans+=t;
        ma=max(ma,a[i]);
    }
    ans=max(ans,ma);
    cout<<ans;
}

D

给定一个数组，求序列里有多少个数对相加没有进位，a[i[=(1~1e6)

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
#define int long long
int a[N],n,ans;
int tr[11][11][11][11][11][11];
int v[6];
void init(int x,int v[]){
    for(int k=0;k<6;k++){
        v[k]=x%10;
        x/=10;
    }
    for(int i=0;i<6;i++)v[i]++;
}
void add(int i){
    // vector<int>v;
    // for(int k=0;k<6;k++){
    //     int x=a[i]%10;
    //     a[i]/=10;
    //     v.push_back(x+1);
    // }
    int x0=v[0];
    int x1=v[1];
    int x2=v[2];
    int x3=v[3];
    int x4=v[4];
    int x5=v[5];
    for(int i0=x0;i0<=10;i0+=i0&-i0)
    for(int i1=x1;i1<=10;i1+=i1&-i1)
    for(int i2=x2;i2<=10;i2+=i2&-i2)
    for(int i3=x3;i3<=10;i3+=i3&-i3)
    for(int i4=x4;i4<=10;i4+=i4&-i4)
    for(int i5=x5;i5<=10;i5+=i5&-i5)
    tr[i0][i1][i2][i3][i4][i5]+=1;
}
int sum(int i){
    // vector<int>v;
    // for(int k=0;k<6;k++){
    //     int x=a[i]%10;
    //     a[i]/=10;
    //     v.push_back(9-x+1);
    // }
    int x0=v[0];
    int x1=v[1];
    int x2=v[2];
    int x3=v[3];
    int x4=v[4];
    int x5=v[5];
    long long ans=0;
    for(int i0=x0;i0;i0-=i0&-i0)
    for(int i1=x1;i1;i1-=i1&-i1)
    for(int i2=x2;i2;i2-=i2&-i2)
    for(int i3=x3;i3;i3-=i3&-i3)
    for(int i4=x4;i4;i4-=i4&-i4)
    for(int i5=x5;i5;i5-=i5&-i5)
    ans+=tr[i0][i1][i2][i3][i4][i5];
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        
        cin>>a[i];
        init(999999-a[i],v);
        ans+=sum(i);
        init(a[i],v);
        add(i);
    }
    cout<<ans;
}

E

F