2021.11.25cf

第一场cf的补题~ wls yyds！参考

A. Make Even

主要意思是说给出了一种翻转操作，问给出的数字经过几次翻转可以得到偶数。

思路：分情况讨论：1、当数字的所有位数全为奇数是，答案是-1，即不可能得到偶数；2、数字原本就是偶数，无需翻转；3、数字是首尾为偶数的奇数，翻转1次得到偶数；4、数字为中间位数含有偶数的奇数，翻转2次得到偶数。

AC代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>
#include <numeric>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t;
int n,cnt,b;
int a[15];

int main()
{
//	freopen("test.in","r",stdin);
    cin>>t;
    while(t--)
    {
    	cnt=0;
    	memset(a,0,sizeof(a));
    	cin>>n;
    	if(n%2==0)
    	cout<<"0"<<'\n';
    	else if(n<10&&n%2==1)
    	cout<<"-1"<<'\n';
    	else 
    	{
    		b=n;
    		while(b)
    		{
    			a[++cnt]=b%10;
    			b/=10;
			}
			if(a[cnt]%2==0)
			cout<<"1"<<'\n';
			else
			{
				for(int i=2;i<=cnt;i++)
				{
					if(a[i]%2==0)
					{
						cout<<"2"<<'\n';
						break;
					}
					else if(i==cnt)
					cout<<"-1"<<'\n';
				}
			}
		}
	}
	return 0;
}

B. Team Composition: Programmers and Mathematicians

主要意思是说规定了一种新的组队方式，4人一队，每队中都必须同时有数学家和程序员，给出两种人员的数量，问可以组成多少队。

思路：可以分为三种情况：1、数学家较多，则三个数学家与一个程序员组队，即满足3程序员<=数学家，队数=程序员；2、程序员较多，则三个程序员与一个数学家组队，即满足3数学家<=程序员，队数=数学家；3、其他情况，输出（数学家+程序员）/4。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
int t,a,b; 

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>a>>b;
    	if(3ll*a<=b)
    	cout<<a<<'\n';
    	else if(3ll*b<=a)
    	cout<<b<<'\n';
    	else 
    	cout<<(a+b)/4<<'\n';
	}
	return 0;
}

废话可跳过：看了wls的讲解，思路非常清晰简单，不像我，我一开始做这个题的时候想的特别麻烦，，，丑陋的代码就不贴上来了QAQ

C. Polycarp Recovers the Permutation

主要意思是说给出一种对数组进行的操作，比较数组左右两侧数字大小，小的取出放到新数组相应一侧，最后一个数字可以置于新数组左侧或右侧，给出操作完成后的新数组，求任意一种满足条件的原数组。

思路：根据操作规则，新数组最左侧或者最右侧的数一定是原数组中最大的数，那么可以这样想：若在原数组中该数就在最左侧或最右侧，那么它会把另一侧的所有数全部置于新数组的同一侧，而根据顺序，新数组中这些较小数的顺序是原数组这些数取反，而最大数还是可以在原来的一侧。那么可以先判断给出数组最左侧或最右侧是否为最大数，若不是则直接输出-1，若是，则将其他数按照相反顺序输出，最后在同一侧放置最大数即可。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2e5+8;
int t,n;
int a[N],b[N]; 

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	int cnt=0;
    	memset(a,0,sizeof(a));
    	memset(b,0,sizeof(b));
    	for(int i=1;i<=n;i++) 
		{
			cin>>a[i];
			b[++cnt]=a[i];
		}
    	int m=a[1],p=a[n];
    	sort(b+1,b+1+cnt);
    	if(m==b[n])
    	{
    		cout<<a[1];
    		for(int i=n;i>=2;i--)
    		cout<<' '<<a[i];
    		cout<<'\n';
		}
		else if(p==b[n])
		{
			for(int i=n-1;i>=1;i--)
			cout<<a[i]<<' ';
			cout<<a[n]<<'\n';
		}
		else
		cout<<"-1"<<'\n';
	}
	return 0;
}

废话可跳过：这个题一开始做的时候有同学考虑出来了这个思路，，，tql

D. Weights Assignment For Tree Edges

主要意思是说给出一棵树中子节点与父节点之间的关系以及所有节点到根节点之间距离递增排列的数组，求任意一组满足题意的每条边权值的数组。

思路：不妨考虑最简单的思路，即按照顺序，距离根节点最近的必是它本身，d=0；次近的d=1，依次排列，则距离根节点的距离为d=i-1，但是要满足子节点与父节点的关系，若某一子节点距离根节点小于父节点，那必不成立，输出-1。

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2e5+8;
int t,n;
int b[N],p[N],r[N],d[N];
              //r[N]记录每个节点距离根节点距离的顺序 
        
int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n;
    	for(int i=1;i<=n;i++)
    	cin>>b[i];
    	int root=0;
    	for(int i=1;i<=n;i++)
    	{
    		if(b[i]==i)
    		root=i;
		}
    	for(int i=1;i<=n;i++)
    	cin>>p[i];
    	for(int i=1;i<=n;i++)
        r[p[i]]=i;
        bool flag=true;
        if(p[1]!=root) flag=false;
        d[root]=0;
        for(int i=2;i<=n;i++)
        {
        	if(r[b[p[i]]]>i)//父节点的距离大于子节点 
        	flag=false;
			else
			d[p[i]]=i- r[b[p[i]]];
		}
		if(!flag) cout<<"-1"<<'\n';
		else
		{
			for(int i=1;i<=n;i++)
			cout<<d[i]<<" \n"[i==n];
		}
	}
	return 0;
}

废话可跳过：一开始看这个题的时候以为是图论的题，，，结果就用了一点点图的知识。图的部分问题太严重了。

F. ATM and Students

主要意思是说现在有一台ATM机，有很多人排队使用，a[i]为正值时为向其中存入钱，为负时从其中取出钱，当ATM机中的钱数不够某一人取出的钱数时，ATM机被关闭，问它在任意时刻被打开时，最多可以服务多少人。

思路：对于维护一段满足条件的区间，想到用双指针。先固定左端点，不断更新右端点，当无法再更新时，移动左端点再次更新，取出满足条件的最大的左右端点的值。参考

AC代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=2e5+8;
int t,n,ansl,ansr,maxn;
ll a[N],sum,now;

int main()
{
//	freopen("test.in","r",stdin);
//  freopen("output.in", "w", stdout);
    cin>>t;
    while(t--)
    {
    	cin>>n>>sum;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	int t=1;
    	while(sum+a[t]<0) t++;//左端点为t，不满足条件后左端点移动
    	ansl=ansr=0;
    	maxn=0;
    	now=a[t];
    	for(int l=t,r=t;l<=n;l++)
    	{
    		while(r+1<=n&&sum+now+a[r+1]>=0)
    		now+=a[++r];//满足条件的情况下钱数直接加入右端点值
    		if(sum+now>=0&&maxn<r-l+1)//更新左右端点和区间长度
    		{
    			ansr=r,ansl=l;
    			maxn=r-l+1;
			}
			now-=a[l];//左端点移动，减去左端点值
		}
		if(maxn<=0) cout<<"-1"<<'\n';
		else
		cout<<ansl<<' '<<ansr<<'\n';
	}
	return 0;
}

废话可跳过：双指针的使用感觉和结训赛的一个尺取法类似，只不过尺取法区间长度不变而双指针区间长度会改变。

若有错误请赐教

Orz

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

20211125cf补题，不全待补

A. Make Even

B. Team Composition: Programmers and Mathematicians

C. Polycarp Recovers the Permutation

D. Weights Assignment For Tree Edges

F. ATM and Students

FEATURED TAGS

FRIENDS