Codeforces Round ＃809 (Div. 2)【VP记录】

A Another String Minimization Problem

简单思维

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=2e5+200;
const ll INF=1e15+5;
char a[Max];
int main(){
    int t;sc(t);
    while(t--){
        int n;sc(n);int m;sc(m);
        for(int i=1;i<=m;i++) a[i]='B';
        
        for(int i=1;i<=n;i++){
            int k;sc(k);
            // if(m%2==1){
                if(k>m/2){
                    if(a[m+1-k]=='B') a[m+1-k]='A';
                    else a[k]='A';
                }else{
                    if(a[k]=='B') a[k]='A';
                    else a[m+1-k]='A';
                }
            // }else{

            // }
        }
        for(int i=1;i<=m;i++) cout<<a[i];
        cout<<endl;
    }
}

B Making Towers

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=2e5+200;
const ll INF=1e15+5;
int a[Max];
int num[Max];
int vis[Max];
int main(){
    int t;sc(t);
    while(t--){
        int n;sc(n);
        for(int i=1;i<=n;i++) sc(a[i]),vis[i]=-1,num[i]=0;
        for(int i=1;i<=n;i++){
            if(vis[a[i]]==-1){
                vis[a[i]]=i;
                num[a[i]]++;
            }else{
                // cout<<i<<' '<<vis[a[i]]<<"--\n";
                if((i-vis[a[i]])%2==1) num[a[i]]++,vis[a[i]]=i;;
            }
        }
        for(int i=1;i<=n;i++){
            printf("%d ",num[i]);
        }printf("\n");
    }
}

C Qpwoeirut And The City

前缀和+后缀和

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=2e5+200;
const ll INF=1e15+5;
ll a[Max];
ll pre[Max];
ll sum[Max];
int main(){
    int t;sc(t);
    while(t--){
        int n;sc(n);
        for(int i=1;i<=n;i++) sl(a[i]);
        for(int i=0;i<=n+100;i++) sum[i]=0,pre[i]=0;
        ll ans=0;
        if(n%2==1){
            for(int i=2;i<=n-1;i+=2){
                ll maxa=max(a[i-1],a[i+1]);
                if(a[i]<=maxa) ans+=(maxa-a[i]+1);
            }
        }else{
            ans=1e18;
            for(int i=2;i<=n-1;i+=2){
                int maxa=max(a[i-1],a[i+1]);
                if(a[i]<=maxa) pre[i]=maxa-a[i]+1;
                pre[i]+=pre[i-2];
            }
            for(int i=n-1;i>=2;i-=2){
                ll maxa=max(a[i-1],a[i+1]);
                if(a[i]<=maxa) sum[i]=maxa-a[i]+1;
                // cout<<i<<' '<<sum[i]<<' '<<sum[<<"---\n";
                sum[i]+=sum[i+2];
            }
            for(int i=1;i<=n;i+=2){
                // printf("%lld ",pre[i-1]+sum[i+2]);
                ans=min(ans,pre[i-1]+sum[i+2]);
            }
        }
        printf("%lld\n",ans);
    }
}

D1 Chopping Carrots (Easy Version)

枚举最小值

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
//#define rep(i,a,b) for(int i=a;i<=b;i++)
//#define rep2(i,a,b) for(int i=a;i>=b;i--)
///* run this program using the console pauser or add your own getch, system("pause") or input loop */
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=2e5+200;
const ll INF=1e15+5;
int a[Max];
int main(){
    int t;sc(t);
    while(t--){
        int n;sc(n);int k;sc(k);
        int maxa=0,mina=Max;
        for(int i=1;i<=n;i++){
            sc(a[i]);
        }
        sort(a+1,a+1+n);
        int ans=Max;
        for(int j=1;j<=3000;j++){
            int mid=j;
            maxa=0,mina=Max;
            for(int i=n;i>=1;i--){
                int v=a[i];
                int num=v/mid;
                if(num<=k&&num!=0) v/=num;
                else v/=k;
                maxa=max(maxa,v);
                mina=min(mina,v);
            }
            ans=min(ans,maxa-mina);
        }
        printf("%d\n",ans);
    }
}

D2 Chopping Carrots (Hard Version)

E Qpwoeirut and Vertices

        st表+LCA+并查集，Kruskal重构树

       然后我们就可以求出最小生成树，进行重构树，然后我们利用LCA求出没对i-1结点和i结点之间的最大权值（就是f数组），最后查询即可运用st表求出【l，r】之间的最大权值。

#include<bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define sl(x) scanf("%lld",&x)
#define ll long long
#define pb push_back
typedef pair<int,int>PII;
const int Max=2e5+200;
const ll INF=1e15+5;
const int N = 2e5+10;
int a[N],st[N][25],Log[N];//2^20就过一百万了，完全够用 
//初始化st表 
int n,m;
void init(){
	Log[1] = 0;//预处理log函数 
	for(int i = 2;i <= n+1;i++) Log[i] = Log[i/2]+1;
	for(int i = 1;i <= n;i++) st[i][0] = a[i];
	for(int j = 1; (1<<j) <= n;j++){	//涉及到位运算多加括号! 
		for(int i = 1;i + (1<<(j-1)) <= n;i++){
			st[i][j] = max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
}
int ask(int l,int r){
    if(l>r) return 0;
	int k = Log[r-l+1];
	int mx = max(st[l][k],st[r-(1<<k)+1][k]);
	//printf("%d %d\n",k,mx);
	return mx;
}
int vis[Max];
int father(int x){
    if(x==vis[x]) return x;
    return vis[x]=father(vis[x]);
}
void link(int x,int y){
    vis[father(x)]=father(y);
}
struct node{
    int to;
    int data;
};
vector<node>mp[Max];
int depth[Max];
int fa[Max][25];
int fa_max[Max][25];
void bfs(int x){
    int start=x;
    queue<int>q;
    q.push(start);
    depth[start]=1;
    while(!q.empty()){
        start=q.front();
        q.pop();
        for(auto u:mp[start]){
            int v=u.to;
            if(depth[v]==-1){
                depth[v]=depth[start]+1;
                q.push(v);
                fa[v][0]=start;
                fa_max[v][0]=u.data;
                for(int i=1;i<=20;i++){
                    fa[v][i]=fa[fa[v][i-1]][i-1];
                    fa_max[v][i]=max(fa_max[v][i-1],fa_max[fa[v][i-1]][i-1]);
                }
            }
        }
    }
}
int lca(int x,int y){
    int maxa=0;
    if(x==y) return maxa;
    if(depth[x]<depth[y]) swap(x,y);
    for(int i=20;i>=0;i--){
        if(depth[fa[x][i]]>=depth[y]){
            maxa=max(maxa,fa_max[x][i]);
            x=fa[x][i];
        }
    }
    if(x==y) return maxa;
    for(int i=20;i>=0;i--){
        if(fa[x][i]!=fa[y][i]){
            maxa=max(maxa,fa_max[x][i]);
            maxa=max(maxa,fa_max[y][i]);
            x=fa[x][i];
            y=fa[y][i];
        }
    }
    maxa=max(maxa,fa_max[x][0]);
    maxa=max(maxa,fa_max[y][0]);
    return maxa;
}
int tmp[Max];
int main(){
    int t;sc(t);
    while(t--){
        int q;
        sc(n);sc(m);sc(q);
        for(int i=1;i<=n;i++) a[i]=0,vis[i]=i,depth[i]=-1;
        for(int i=1;i<=m;i++){
            int u,v;
            sc(u);sc(v);
            if(father(u)!=father(v)){
                // cout<<u<<' '<<v<<"----\n";
                link(u,v);
                mp[u].pb({v,i});
                mp[v].pb({u,i});
            }
        }
        bfs(1);
        // for(int i=1;i<=n;i++){
        //     for(int j=1;j<=20;j++){
        //         printf("%d ",fa_max[i][j]);
        //     }cout<<endl;
        // }
        for(int i=2;i<=n;i++){
            a[i]=lca(i-1,i);
            // cout<<a[i]<<" ";
        }
        // cout<<endl;
        init();
        for(int i=1;i<=q;i++){
            int l,r;
            sc(l);sc(r);
            a[i]=ask(l+1,r);
        }
        for(int i=1;i<=q;i++){
            printf("%d ",a[i]);
        }
        printf("\n");
        for(int i=1;i<=n;i++) mp[i].clear();
    }
}