Codeforces Round #756 (Div. 3) 个人题解
纪念小飞龙CF上蓝！（关于为什么小飞龙这个菜逼打了这么多把才刚上蓝这件事）
比赛链接：Codeforces Round #756 (Div. 3)
A题 Make Even
题目大意：
给你一个不包含 $0$ 的数，每一次操作你可以选择这个数的一个前缀翻转它，问最小操作次数能够使得这个数为偶数，不能则输出 $-1$
思路解析：
显然，如果一个数中每一位都是奇数，那么一定是 $-1$
如果这个数本身就是偶数，那么不需要操作，即为 $0$
否则，如果第一位是偶数的话我们可以将整个数翻转，答案即为 $1$
否则的话，我们需要多用一次操作把中间的一个偶数翻转到头上来，转化为上一种情况，答案为 $2$
AC代码：
#include<bits/stdc++.h>
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<int,int>
#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<<endl;
else {
int sum=0;
for(int i=0;i<n;i++){
int j=s[i]-'0';
if(j%2==1)sum++;
}
if(sum==n){
cout<<-1<<endl;
continue;
}
if((s[0]-'0')%2==0)cout<<1<<endl;
else cout<<2<<endl;
}
}
}
B题 Team Composition: Programmers and Mathematicians
题目大意：
我们有 $a$ 个数学家和 $b$ 个程序员，每个队四个人，但是不能全是数学家或者程序员，问最大的组队数量
思路解析：
简单的数学问题，显然答案一定是 $min(min(a,b),(a+b)/4)$
AC代码：
#include<bits/stdc++.h>
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<int,int>
#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<<ans<<endl;
}
}
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<bits/stdc++.h>
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<int,int>
#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;
deque<int>q;
for(int i=1;i<=n;i++){
cin>>a[i];
}
if(a[1]!=n&&a[n]!=n){
cout<<-1<<endl;
continue;
}
int l=1,r=n;
while(l<=r){
if(a[l]>a[r])q.push_front(a[l++]);
else q.push_back(a[r--]);
}
while(q.size()){
cout<<q.front()<<" ";
q.pop_front();
}
cout<<endl;
}
}
D题 Weights Assignment For Tree Edges
题目大意：
给出一颗树（有向），给出 $p$ 数组，满足 $dis[p[i]]<dis[p[i+1]]$ （ $dis$ 表示到根节点的距离）
你需要构造一棵树，输出每条边的权值（即当前点到其父亲节点的距离），如果不能输出 $-1$
思路解析：
对于这道题，小飞龙的思路很简单粗暴，核心就是判断冲突
我们直接构造一个 $dis[p[i]]=dis[p[i-1]]+1$ 人，然后在树上 $dfs$ ，找冲突，即当前点 $u$ 的子树中有存在一个点 $v$ 满足 $dis[v]<dis[u]$ ，如果存在这样的情况，答案一定是 $-1$ ，否则我们当前的构造就是可行的，输出 $dis[i]-dis[fa[i]]$ 即可
（附一份我队友zc聚聚写得简介思路，直接判断）
我的AC代码：
#include<bits/stdc++.h>
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<int,int>
#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]<dis[x])ok=0;
}
int main(){
IOS
int t;
cin>>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<<endl;
continue;
}
for(int i=1;i<=n;i++){
cout<<dis[i]-dis[a[i]]<<" ";
}
cout<<endl;
}
}
zc聚聚的思路
#include<bits/stdc++.h>
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<int,int>
#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]<dis[x])ok=0;
}
int main(){
IOS
int t;
cin>>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<<endl;
ok=0;
break;
}
}
if(ok==0)continue;
for(int i=1;i<=n;i++){
cout<<dis[i]-dis[a[i]]<<" ";
}
cout<<endl;
}
}
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<bits/stdc++.h>
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<int,int>
#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;
queue<int>q;
for(int i=1;i<=m;i++){
int x;
cin>>x;
dis[x]=0;
q.push(x);
}
for(int i=1;i<n;i++){
int x,y;
cin>>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);
}
}
}
queue<int>qq;
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"<<endl;
else cout<<"NO"<<endl;
}
}
E2题 Escape The Maze (hard version)
题目大意：
和 $E1$ 基本相同，只是你需要输出在小 $V$ 失败的情况下，能够抓到小 $V$ 所需的最小人数
思路解析：
有了上一题的基础，我们会发现我们在第一次 $bfs$ 中每剪掉一颗子树，就需要一个人，此时必要人数 $tot++$
$tot$ 即为答案，输出 $tot$ 即可
AC代码：
#include<bits/stdc++.h>
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<int,int>
#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;
queue<int>q;
for(int i=1;i<=m;i++){
int x;
cin>>x;
dis[x]=0;
q.push(x);
}
for(int i=1;i<n;i++){
int x,y;
cin>>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);
}
}
}
queue<int>qq;
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<<endl;
else cout<<tot<<endl;
}
}
F题 ATM and Students
题目大意：
给出一台 $ATM$ 机，一开始里面有 $s$ 块钱，有 $n$ 个人存钱或者取钱，问最大的连续子段使得能够满足子段中每个人的需求（即不会出现取钱钱不够的情况）
思路解析：
尺取，维护当前区间和 $+s>=0$ 即可
(附一份队友 $tbw$ 聚聚 的 **$ST$ 表+二分代码 （经典赛后过题）)
我的AC代码：
#include<bits/stdc++.h>
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<int,int>
#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<<sz<<endl;
else cout<<x<<" "<<y-1<<endl;
}
}
tbw聚聚的代码
#include <bits/stdc++.h>
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<M;j++)
for(int i=1;i+(1<<j)-1<=n;i++)
if(!j) f[i][j]=b[i];
else f[i][j]=min(f[i][j-1],f[i+(1<<(j-1))][j-1]);
}
vector<int> 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<<k)][k]);
}
bool check(int mid){
for(int i=1;i<=n;i++){
if(i+mid-1<=n){
int t=query(i,i+mid-1)-b[i-1];
if(t<0&&s>=(-t)) return true;
else if(t>=0) return true;
}
}
return false;
}
void solve(){
vector<int> 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<r){
int mid=(l+r+1)>>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<<i<<' '<<i+r-1<<endl;
return;
}
}
}
}
signed main(){
int T;cin>>T;while(T--)
solve();
return 0;
}
G题 Robot and Candies
没开到，好像是个 $DP$ 吧
改天补（逃）
AC代码
//假装这里有代码
！！！tql
能上蓝就庆祝hh
QAQ
E2思路好棒！Orz
好耶！