CF756div3 vp

又被薄纱了，rk就不放了，好丢人QwQ

Dashboard - Codeforces Round 756 (Div. 3) - Codeforces

A. Make Even

小分类讨论

题意：

给定一个数，每次操作可以选取其前缀然后翻转其前缀，问你最少操作几次可以把该数变为偶数

思路：

对次数分类讨论即可

如果本来就是偶数，就是0次

如果s[1]是偶数，翻转一整个就行

如果没有偶数位，就是-1

其余都是两次

Code：

#include <bits/stdc++.h>
//#define int long long
#define LL long long
const int mxn=1e6+10;
const int mxe=2e5+10;
const int mod=1e9+7;
using namespace std;string s;
void solve(){s.clear();cin>>s;int n=s.size();s=" "+s;if((s[n]-'0')%2==0) cout<<0<<'\n';else if((s[1]-'0')%2==0) cout<<1<<'\n';else{int ok=0;for(int i=1;i<=n;i++){if((s[i]-'0')%2==0) ok=1;}if(ok) cout<<2<<'\n';else cout<<-1<<'\n';}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;//p_init(1e6);while(__--)solve();return 0;
}

B. Team Composition: Programmers and Mathematicians

贪心

题意：

有a个数学家和b个计算机学家，4个人一组组队，每组至少包含两种学科，问最多能组几队

谢谢，不会小学数学

思路：

要使队伍数尽可能多，就让少的那个学科每队派一人，然后和另一个队组队

那么答案就是min(min(a,b),(a+b)/4)

Code：

#include <bits/stdc++.h>
//#define int long long
#define LL long long
const int mxn=1e6+10;
const int mxe=2e5+10;
const int mod=1e9+7;
using namespace std;int a,b;
void solve(){cin>>a>>b;cout<<min(min(a,b),(a+b)/4)<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;//p_init(1e6);while(__--)solve();return 0;
}

C. Polycarp Recovers the Permutation

构造+排列

题意：

思路：

一开始写了一小时的双指针模拟操作，然后写了一坨错了

这是构造题，考虑将一些一般条件特殊化，一般来说这种一般条件都是比较难处理的，像之前过年那会有个子序列，它就直接选了一整个序列，对于这种难处理的一般条件，我们考虑将其特殊化

注意到答案的排列（即原来的排列）的两端一定是最大值，否则就是无解

这道题就是把 双指针每次选小的那个 这个条件 转化成 固定一个指针动另一个，固定的那个指针大小一定为n，直接将其翻转即可

Code：

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize(2)
#define close();  ios::sync_with_stdio(false);
#define endl '\n'
#define rep(i, l, r) for(int i = l; i <= r; i++)
#define dwn(i, r, l) for(int i = r; i >= l; i--)
typedef long long LL;
const int N = 3e5+100;
int a[N];
int b[N]; 
void solve()
{int n; cin >> n;rep(i, 1, n) cin >> a[i];if(a[1] == n || a[n] == n){dwn(i, n, 1) cout << a[i] << " "; cout << endl;}else cout << -1 << endl;}int main()
{close();int T; cin >> T;while(T--) solve();// system("pause");
}

F. ATM and Students

尺取法

题意：

找出最长的连续子串使得其前缀和+s>=0

思路：

尺取法模板题，这道题居然有*1800，逆

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn=2e5+10;int n,s;
int a[mxn],sum[mxn];
void solve(){memset(sum,0,sizeof(sum));cin>>n>>s;for(int i=1;i<=n;i++) cin>>a[i],sum[i]=sum[i-1]+a[i];int ans=-1,ansl,ansr;for(int l=1,r=1;l<=n;l++){while(r<=n&&sum[r]-sum[l-1]>=-s) r++;r--;if(ans<r-l+1){ans=r-l+1;ansl=l;ansr=r;}}if(ans==-1||ansl>ansr) cout<<-1<<'\n';else cout<<ansl<<" "<<ansr<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}

D. Weights Assignment For Tree Edges

构造

题意：

给定一棵树

又给了一个排列，对于p[i]满足dis[p[i]]>dis[p[i-1]]

dis是该结点的树上前缀和，w是边权

要你给这棵树的边权w赋值，使得能满足p排列的条件

思路：

模拟一下样例发现，我们可以遍历p[i]排列，把边权变成公差为1 的等差数列（特殊化边权）

如果父亲结点在p[i]中出现的id大于结点i，那么父亲结点的dis必然小于结点i，矛盾，所以这种情况无解

否则就去递推出p[i]的dis和w

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn=2e5+10;int n,rt;
int fa[mxn],w[mxn],dis[mxn],id[mxn],p[mxn];
void solve(){memset(dis,0,sizeof(dis));memset(w,0,sizeof(w));cin>>n;for(int i=1;i<=n;i++){cin>>fa[i];if(fa[i]==i) rt=i;}for(int i=1;i<=n;i++){cin>>p[i];id[p[i]]=i;}if(p[1]!=rt) cout<<-1<<'\n';else{int ok=1;for(int i=2;i<=n;i++){if(id[p[i]]<id[fa[p[i]]]) ok=0;w[p[i]]=dis[p[i-1]]+1-dis[fa[p[i]]];dis[p[i]]=dis[fa[p[i]]]+w[p[i]];}if(!ok) cout<<-1<<'\n';else{for(int i=1;i<=n;i++) cout<<w[i]<<" \n"[i==n];}}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}

E1. Escape The Maze (easy version)

BFS

题意：

有一棵树，Vlad和n个朋友玩游戏，Vlad位于节点1，n个朋友位于其他节点，第i个朋友位于xi。每个时刻，每个人都能沿着树边到达另一个点，或者留在原地。如果Vlad到达叶子节点，则Vlad赢。如果在其到达叶子前和其他人碰面（叶子也不能有其他人），则Vlad输。问最少需要保留多少个人能够保证Vlad输，即选取朋友的一个最小的子集，使得Vlad不能赢。

思路：

直接去BFS模拟过程，一格格染色，如果能把叶子结点染成1就是赢

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mxn=2e5+10;
const int mxe=2e5+10;
struct ty{int to,next;
}edge[mxe<<1];
queue<int> q;int n,k,u,v;
int tot=0,ok=0;
int x[mxn],d[mxn],head[mxn],mark[mxn],vis[mxn];
void add(int u,int v){edge[tot].to=v;edge[tot].next=head[u];head[u]=tot++;
}
void init(){tot=0;ok=0;for(int i=0;i<=n;i++){x[i]=0;head[i]=-1;d[i]=0;mark[i]=0;vis[i]=0;}
}
bool bfs(){for(int i=1;i<=k;i++) q.push(x[i]),vis[x[i]]=1;q.push(1);vis[1]=1;mark[1]=1;while(!q.empty()){int u=q.front();q.pop();if(d[u]==1&&mark[u]==1&&u!=1) ok=1;for(int i=head[u];~i;i=edge[i].next){if(vis[edge[i].to]) continue;vis[edge[i].to]=1;q.push(edge[i].to);mark[edge[i].to]=mark[u];}}return ok;
}
void solve(){cin>>n>>k;init();for(int i=1;i<=k;i++) cin>>x[i];for(int i=1;i<=n-1;i++){cin>>u>>v;add(u,v);add(v,u);d[v]++;d[u]++;}//for(int i=1;i<=n;i++) if(d[i]==1) cout<<i<<'\n';if(bfs()) cout<<"YES"<<'\n';else cout<<"NO"<<'\n';
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int __=1;cin>>__;while(__--)solve();return 0;
}