比赛链接:https://codeforces.ml/contest/1744

第一次排名挺高,到了2500+,也是如愿的在定级赛内要上绿了。这次比赛E题的构造题听恶心的,其他发挥的还可以,C题稍微有些失误但不多,还是有些需要注意的点。构造题单独总结一下。

A题:水题,主要是哈希的应用

B题:奇偶数问题,大意是给出一堆数,给出两种操作,令偶数+x或令奇数+x,每次操作后输出所有数的和。

直接分别计算。

C题:WA了两发,需要考虑的情况还是挺多的。给出一个字符串,包含ryb,红绿黄灯。给出现在的灯,求最少需要等多长时间,可以等到下一个绿灯且保证等到。  规律循环。

我们可以每次记录目前的灯到下一个灯的时间,这个只需要遍历一下。

另一边,我们总能通过,最后末尾没有绿的时候的目前灯,到达下一次循环的绿灯。这里比较细节。(第一次考虑的时候是考虑的最后的目前的,没有想到l绿灯问题)(第二次考虑的时候,忘记了遇不到灯的情况,即绿之后再无此灯)

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void solve()
{
	int n;
 	char c;
 	scanf("%d %c",&n,&c);
 	string s;
 	cin>>s;
 	int maxt = -1;
 	int cur = -1;
 	int mopos = -1;
 	for(int i=0;i<s.size();i++){
 		if(s[i]==c&&cur==-1){
 			cur = i;
		}
		if(cur!=-1&&s[i]=='g'){
			maxt = max(maxt,i-cur);
			cur = -1;
		}
	}
	for(int i=s.size()-1;i>=0;i--){
		if(s[i]==c) mopos = i;
		if(s[i]=='g') break;
	}
	if(mopos!=-1){
		s+=s;
		for(int i=mopos;i<s.size();i++){
			if(s[i]=='g'){
				maxt = max(maxt,i-mopos);
				break;
			}
		}
	}
	cout<<maxt<<endl;
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	//ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

D题:给出一堆数,可以使这些数乘以i,求至少多少次这样的操作可以使得乘积 可以 整除2^n。每个位置只能操作一次。不能到达-1.
这个题做的也挺顺利。记录当前数的因子中含有多少个2,然后从大到小考虑i含有多少个2。然后比较,然后从大到小应用操作。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
// 2 4 8 16 32 64     12 11 10
bool cmp(int a,int b){
	return a>b;
}
const int nn = 2*1e5+10;
void solve()
{
	vector<int> ve;
	int n;
	cin>>n;
	int x;
	int sum = 0;
	int tsum = 0;
	for(int i=1;i<=n;i++){
		cin>>x;
		while(x%2==0){
			sum++;
			x/=2;
		}
		int tx = i;
		int ff = 0;
		while(tx%2==0){
			ff++;
			tsum++;
			tx/=2;
		}
		ve.push_back(ff);
	}
	if(sum+tsum<n) cout<<-1<<endl;
	else{
		sort(ve.begin(),ve.end(),cmp);
		int ans = 0;
		int tn = n-sum;
		for(int i=0;i<ve.size();i++){
			if(tn<=0) break;
			tn-=ve[i];
			ans++;
		}
		cout<<ans<<endl;
	} 
}
int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n')
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}