Codeforces Round #756 (Div. 3) 个人题解

Codeforces Round #756 (Div. 3) 个人题解

纪念小飞龙CF上蓝！（关于为什么小飞龙这个菜逼打了这么多把才刚上蓝这件事）

比赛链接：Codeforces Round #756 (Div. 3)

A题 Make Even

题目大意：

给你一个不包含 \(0\) 的数，每一次操作你可以选择这个数的一个前缀翻转它，问最小操作次数能够使得这个数为偶数，不能则输出 \(-1\)

思路解析：

显然，如果一个数中每一位都是奇数，那么一定是 \(-1\)

如果这个数本身就是偶数，那么不需要操作，即为 \(0\)

否则，如果第一位是偶数的话我们可以将整个数翻转，答案即为 \(1\)

否则的话，我们需要多用一次操作把中间的一个偶数翻转到头上来，转化为上一种情况，答案为 \(2\)

AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n'
#define pii pair
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;


int main(){
    IOS
    int t;
    cin>>t;
    while(t--){
        string s;
        cin>>s;
        int n=s.size();
        if((s[n-1]-'0')%2==0)cout<<0<

B题 Team Composition: Programmers and Mathematicians

题目大意：

我们有 \(a\) 个数学家和 \(b\) 个程序员，每个队四个人，但是不能全是数学家或者程序员，问最大的组队数量

思路解析：

简单的数学问题，显然答案一定是 \(min(min(a,b),(a+b)/4)\)

AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n'
#define pii pair
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;



int main(){
    IOS
    int t;
    cin>>t;
    while(t--){
        ll a,b;
        cin>>a>>b;
        ll ans=min(min(a,b),(a+b)/4);
        cout<

C题 Polycarp Recovers the Permutation

题目大意：

我们有一个数组 \(p\) 和一个数组 \(a\) ，一开始p是一个 \(1-n\) 的排列， \(a\) 是空的，我们每次把 \(p\) 两端小的那个元素弹出放到同侧的 \(a\) 当中，直到 \(p\) 中没有元素

现在给出了操作后的a数组，构造一个可行的 \(p\) ，如果不能输出 \(-1\)

思路解析：

我们首先考虑 \(-1\) 的情况，我们发现每一次都是取小的那一个，所以原排列中最后弹出的一定是 \(n\) ，所以在 \(a\) 中如果 \(n\) 在中间的话一定不可行

对于一个可行解，我们可以直接把 \(a\) 倒退，用 \(deque\) 模拟即可

AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n'
#define pii pair
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

int a[maxn];

int main(){
    IOS
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        dequeq;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        if(a[1]!=n&&a[n]!=n){
            cout<<-1<a[r])q.push_front(a[l++]);
            else q.push_back(a[r--]);
        }
        while(q.size()){
            cout<

D题 Weights Assignment For Tree Edges

题目大意：

给出一颗树（有向），给出 \(p\) 数组，满足 \(dis[p[i]] （ \(dis\) 表示到根节点的距离）

你需要构造一棵树，输出每条边的权值（即当前点到其父亲节点的距离），如果不能输出 \(-1\)

思路解析：

对于这道题，小飞龙的思路很简单粗暴，核心就是判断冲突

我们直接构造一个 \(dis[p[i]]=dis[p[i-1]]+1\) 人，然后在树上 \(dfs\) ，找冲突，即当前点 \(u\) 的子树中有存在一个点 \(v\) 满足 \(dis[v] ，如果存在这样的情况，答案一定是 \(-1\) ，否则我们当前的构造就是可行的，输出 \(dis[i]-dis[fa[i]]\) 即可

（附一份我队友zc聚聚写得简介思路，直接判断）

我的AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n'
#define pii pair
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

int a[maxn],p[maxn];
ll dis[maxn];
int e[maxn],nex[maxn],h[maxn],id;
int rt,ok,q[maxn];

void add(int x,int y){
    e[++id]=y;
    nex[id]=h[x];
    h[x]=id;
}

void dfs(int x){
    q[x]=dis[x];
    for(int i=h[x];i;i=nex[i]){
        int j=e[i];
        dfs(j);
        q[x]=min(q[x],q[j]);
    }
    if(q[x]>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n+5;i++)h[i]=0,dis[i]=0,q[i]=0;
        id=0;
        rt=0;ok=1;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(a[i]==i){
                rt=i;
                continue;
            }
            add(a[i],i);
        }
        for(int i=1;i<=n;i++){
            cin>>p[i];
            dis[p[i]]=i-1;
        }
        dfs(rt);
        if(!ok){
            cout<<-1<

zc聚聚的思路

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n'
#define pii pair
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

int a[maxn],p[maxn];
ll dis[maxn];
int e[maxn],nex[maxn],h[maxn],id;
int rt,ok,q[maxn],in[maxn];

void add(int x,int y){
    e[++id]=y;
    nex[id]=h[x];
    h[x]=id;
}

void dfs(int x){
    q[x]=dis[x];
    for(int i=h[x];i;i=nex[i]){
        int j=e[i];
        dfs(j);
        q[x]=min(q[x],q[j]);
    }
    if(q[x]>t;
    while(t--){
        int n;
        cin>>n;
        for(int i=1;i<=n+5;i++)dis[i]=-1;
        ok=1;
        for(int i=1;i<=n;i++){
            cin>>a[i];
        }
        for(int i=1;i<=n;i++)
            cin>>p[i];
        for(int i=1;i<=n;i++){
            dis[p[i]]=i-1;
            if(dis[a[p[i]]]<0){
                cout<<-1<

E1题 Escape The Maze (easy version

题目大意：

有一颗树，小 \(V\) 在 \(1\) 号点，他有 \(k\) 个朋友分别在 \(x_i\) 号点，每一秒他们移动一步，小 \(V\) 成功的条件是他可以走到任意一个叶节点，如果他在途中被他的朋友抓到，那么他就输了，问小 \(V\) 是否能成功

思路解析：

显然我们可以用两次 \(bfs\) 来解决这道问题：

第一次 \(bfs\) 我们处理出朋友们到达每个点的最短时间，假设为 \(dis[i]\)

第二次 \(bfs\) 我们处理小 \(V\) 到达每个点的时间，我们假设为 \(d[i]\) ,如果在某个点 \(x\) ， \(d[x]>=dis[x]\) ，那么就说明如果小 \(V\) 走这个点一定会被抓到，显然我们就可以在 \(bfs\) 中剪掉这一枝，剪掉 \(x\) 的子树

那么小 \(V\) 胜利的条件就是在 \(bfs\) 中能到达任何一个叶节点，然后判断即可

AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n'
#define pii pair
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

int e[maxn],nex[maxn],h[maxn],id;
int pos[maxn],dis[maxn],d[maxn],in[maxn];

void add(int x,int y){
    e[++id]=y;
    nex[id]=h[x];
    h[x]=id;
}

int main(){
    IOS
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n+10;i++){
            h[i]=0;dis[i]=-1;d[i]=-1;
            in[i]=0;
        }
        id=0;
        queueq;
        for(int i=1;i<=m;i++){
            int x;
            cin>>x;
            dis[x]=0;
            q.push(x);
        }
        for(int i=1;i>x>>y;
            add(x,y);
            add(y,x);
            in[x]++;
            in[y]++;
        }
        while(q.size()){
            int top=q.front();
            q.pop();
            for(int i=h[top];i;i=nex[i]){
                int j=e[i];
                if(dis[j]==-1){
                    dis[j]=dis[top]+1;
                    q.push(j);
                }
            }
        }
        queueqq;
        qq.push(1);
        d[1]=0;
        int ok=0;
        while(qq.size()){
            int top=qq.front();
            qq.pop();
            if(in[top]==1&&top!=1)ok=1;
            for(int i=h[top];i;i=nex[i]){
                int j=e[i];
                if(d[j]==-1){
                    d[j]=d[top]+1;
                    if(dis[j]<=d[j])continue;
                    qq.push(j);
                }
            }
        }
        if(ok)cout<<"YES"<

E2题 Escape The Maze (hard version)

题目大意：

和 \(E1\) 基本相同，只是你需要输出在小 \(V\) 失败的情况下，能够抓到小 \(V\) 所需的最小人数

思路解析：

有了上一题的基础，我们会发现我们在第一次 \(bfs\) 中每剪掉一颗子树，就需要一个人，此时必要人数 \(tot++\)

\(tot\) 即为答案，输出 \(tot\) 即可

AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n'
#define pii pair
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

int e[maxn],nex[maxn],h[maxn],id;
int pos[maxn],dis[maxn],d[maxn],in[maxn];

void add(int x,int y){
    e[++id]=y;
    nex[id]=h[x];
    h[x]=id;
}

int main(){
    IOS
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n+10;i++){
            h[i]=0;dis[i]=-1;d[i]=-1;
            in[i]=0;
        }
        id=0;
        queueq;
        for(int i=1;i<=m;i++){
            int x;
            cin>>x;
            dis[x]=0;
            q.push(x);
        }
        for(int i=1;i>x>>y;
            add(x,y);
            add(y,x);
            in[x]++;
            in[y]++;
        }
		int sum=0;
		for(int i=1;i<=n;i++)if(in[i]==1)sum++;
        while(q.size()){
            int top=q.front();
            q.pop();
            for(int i=h[top];i;i=nex[i]){
                int j=e[i];
                if(dis[j]==-1){
                    dis[j]=dis[top]+1;
                    q.push(j);
                }
            }
        }
        queueqq;
        qq.push(1);
        d[1]=0;
        int ok=0,tot=0;
        while(qq.size()){
            int top=qq.front();
            qq.pop();
            if(in[top]==1&&top!=1)sum--,ok=1;
            for(int i=h[top];i;i=nex[i]){
                int j=e[i];
                if(d[j]==-1){
                    d[j]=d[top]+1;
                    if(dis[j]<=d[j]){
						tot++;
						continue;
					}
                    qq.push(j);
                }
            }
        }
		if(ok)cout<<-1<

F题 ATM and Students

题目大意：

给出一台 \(ATM\) 机，一开始里面有 \(s\) 块钱，有 \(n\) 个人存钱或者取钱，问最大的连续子段使得能够满足子段中每个人的需求（即不会出现取钱钱不够的情况）

思路解析：

尺取，维护当前区间和 \(+s>=0\) 即可

(附一份队友 \(tbw\) 聚聚 的 **\(ST\) 表+二分代码 （经典赛后过题）)

我的AC代码：

#include
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#define endl '\n'
#define pii pair
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int maxn=1e6+5;

ll n,a[maxn],s,sum[maxn];

int main(){
    IOS
    int t;
    cin>>t;
    while(t--){
        cin>>n>>s;
        for(int i=1;i<=n;i++)cin>>a[i];
        for(int i=1;i<=n;i++)sum[i]=sum[i-1]+a[i];
        ll now=0;
        ll l=1,r=1,x=0,y=0,sz=-1;
        while(l<=r&&r<=n){
            now+=a[r++];
            if(now+s>=0&&r>sz+l)sz=r-l,x=l,y=r;
            while(now<-s)now-=a[l++];
        }
        if(sz==-1)cout<

tbw聚聚的代码

#include 
using namespace std;
typedef long long ll;
#define int ll
const int N=2e5+10,M=18;

int n,s;
int a[N];
int b[N];

int f[N][M];

void init()
{
    for(int j=0;j ans;

int query(int l,int r)
{
    int len=r-l+1;
    int k=log(len)/log(2);
    return min(f[l][k],f[r+1-(1<=(-t)) return true;
			else if(t>=0) return true;
	    }
	}
	return false;
}

void solve(){
	vector ans;
	//ans.clear();
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		b[i]=b[i-1]+a[i];
	}
	init();
	int l=0,r=n;
	while(l>1;
		if(check(mid)) l=mid;
		else r=mid-1;
	}
    if(!r){
        cout<<"-1\n";
        return;
    }
    for(int i=1;i<=n;i++){
        if(i+r-1<=n){
			int t=query(i,i+r-1)-b[i-1];
			if(t<0&&s>=(-t)||t>=0){
			    cout<>T;while(T--)
	solve();
	return 0;
}

推广一波小飞龙博客：戳这里@不会飞的小飞龙

Codeforces题解

相关

标签

一品网 冀ICP备14022925号-6