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

A题:水题

B题:水题

C题:思维+审题。 大意是给出一个8*8的矩阵,每次操作可以画一行红色或者是一列蓝色,每次绘制可以覆盖之前的颜色。求出最后画的是哪一笔?题目保证给出一个正确解。

这个题WA了9发,导致没时间做F和G题。看着是一个很简单的题,第一眼直接暴力。这是障眼法。
RRRRRRRR RRRRRRRR RRRRRRRR RRRRRRRR RRRRRRRR RRRRRRRR RRRRRRRR BBBBBBBB
我们总能通过这个样例看到一个极端情况,就是B一定不可能画在行上,且红一定不可能画在列上,所以我们不能暴力相等条件,因为RB存在冲突。

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()
{
	string a[10];
	//cin.ignore(numeric_limits<streamsize>::max(),'\n'); 
	for(int i=0;i<8;i++){
		cin>>a[i];
	}
	char c = 'B';
	for(int i=0;i<8;i++){
		if(a[i] == "RRRRRRRR"){
			c = 'R';
			break;
		}
	}
	cout<<c<<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题:给出一组数据,如果两个数互质,产生的值为这两个数之和,求出最大的值,特判1。不存在输出-1。

第一个开的题,上来就有思路,一发AC。
暴力这个题,将是一个n^2的一个复杂度。从单个ai的角度来看,这个数就很小了,只有1000以内,标记数并暴力获得。

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;
}
const int nn = 2*1e5+10;
int sign[1100];
void solve()
{
	memset(sign,0,sizeof sign);
	int n;
	cin>>n;
	int x;
	for(int i=1;i<=n;i++){
		cin>>x;
		sign[x] = i;
	}
	int maxt = -1;
	if(sign[1]) maxt = sign[1]+sign[1];
	for(int i=1;i<=1000;i++){
		for(int j=i+1;j<=1000;j++){
			if(sign[i]&&sign[j]&&__gcd(i,j)==1){
				maxt = max(maxt,sign[i]+sign[j]);
			}
		}
	}
	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();
	}
}


E题:前缀和+二分。给出一组数据,每组数据代表当前楼梯比之前一个高多少,给出一组数据,每组数据为你可以跨过的高度。求出每个数据能够跨过总数多长的楼梯。

思路:前缀和+map记录每个跨越高度可以到达的总数,不断更新它。二分查找这个值。

code:(代码写拉了,手写二分了。可以一个数组记录前缀和,一个数组记录每个bi能够到达的位置,最后二分查找最后的位置所对应的前缀和即可)


#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;
}
map<ll,ll> mp;
struct data{
	ll tx;	
	ll ts;
};
void solve()
{
	mp.clear();
	int n,q;
	cin>>n>>q;
	ll maxt = 0;
	ll s = 0;
	ll x;
	for(int i=1;i<=n;i++){
		cin>>x;
		s+=x;
		maxt = max(maxt,x);
		mp[maxt] = s; 
	}
	map<ll, ll>::iterator iter;	
	vector<data>ve;
	ve.push_back({0,0});
	iter = mp.begin();
	while(iter != mp.end()){
		ll key = iter->first;
		ll val = iter->second;
		ve.push_back({key,val});
		iter++;
	}
	ll mx;
	for(int i=1;i<=q;i++){
		cin>>mx;
		ll l = 0,r = ve.size();
		while(l<r){
			ll mid = (l+r)>>1;
			if(ve[mid].tx<=mx)
				l=mid+1;
			else if(ve[mid].tx>mx)
				r=mid-1;
		}
		if(l>=ve.size()) cout<<ve[ve.size()-1].ts<<' ';
		else
		if(l+1<ve.size()&&mx>=ve[l+1].tx)
		{
			cout<<ve[l+1].ts<<' ';
		}
		else if(l-1>=0&&mx<ve[l].tx){
			cout<<ve[l-1].ts<<' ';
		}
		else cout<<ve[l].ts<<' ';
	}
	cout<<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();
	}
}


F题:由于C题耽误的时间很长,没时间看F题,赛后F第三发过了。大意是给出一个字符串s和t。前缀都是'a',给出两种操作。
给s加上k个新字符串,给t加上k个新字符串。求是否存在s和t的一种排列,使得s的字典序比t小。可以yes不可以no

思路:这个题代码也写拉了,我是开数组分别记录每个s和t中元素出现的数量。正序存储s,倒序存储t。使得贪心最优可能性。
然后开始判断,如果s的字符c小,那么直接ok。如果大,直接no。同样大且数量相同继续看。
同样大且s的少,如果s存在其他no,否则yes。同样大且t的少,如果t存在其他那么no。反复如此。

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;
}
ll a[200];
ll b[200];
struct data{
	int c;
	ll cnt;
};
// 2a 2b
// 11a 3b 3c 
void solve()
{
	memset(a,0,sizeof a);
	memset(b,0,sizeof b);
	a['a'] = 1;
	b['a'] = 1;
	int q;
	cin>>q;
	int op,x;
	string s;
	while(q--){
		cin>>op>>x>>s;
		if(op==1){
			for(int i=0;i<s.size();i++)
				a[s[i]]+=x;
		}else{
			for(int i=0;i<s.size();i++)
				b[s[i]]+=x;
		}
		bool flag = false;
		vector<data> va;
		vector<data> vb;
		for(int i='a';i<='z';i++)
		{
			if(a[i])
				va.push_back({i,a[i]});
		}
		for(int i='z';i>='a';i--){
			if(b[i])
				vb.push_back({i,b[i]});
		}
		int mint = min(va.size(),vb.size());
		for(int i=0;i<mint;i++){
			if(va[i].c<vb[i].c){
				flag = true;
				break;
			}else if(va[i].c>vb[i].c){
				flag = false;
				break;
			}else{
				if(va[i].cnt>vb[i].cnt){
					if(i+1<vb.size()){
						flag = true;
						break;
					}else{
						flag = false;
						break;
					}
				}
				
				if(va[i].cnt<vb[i].cnt){
					if(i+1<va.size())
					{
						flag = false;
						break;
					}else{
						flag = true;
						break;
					}
				}
				
			}
		}
		printf("%s\n",flag?"YES":"NO");
	}
}
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();
	}
}


G题:读错了!!!或运算读成了异或运算,真服了。大意是给出n个数,定义数组b为n个数的前缀或,求n的一个排列使得前缀或b字典序最大。

或运算如果存在一个1,那么之后都是1.我们只想考虑1是否能带来怎样的效应,找到当前前缀或没有的1的数。最多存在31个这样的情况。剩下随意输出,因为前缀和已经永远满足一个最大。

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;
}
struct data{
	int x;
	int s;
};
void solve()
{
	int n;
	cin>>n;
	vector<int> a(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	int ors = 0; 
	vector<bool> sign(n+10,false);
	vector<int> ve;
	for(int i=1;i<min(n+1,32);i++){
		int mx = 0, pos = -1;
		for(int j=1;j<=n;j++){
			if(sign[j]) continue;
			if((ors|a[j])>mx){
				mx = (ors|a[j]);
				pos = j;
			}
		}
		sign[pos] = true;
		ors = a[pos]|ors;
		ve.push_back(a[pos]);
	}
	for(int i=0;i<ve.size();i++){
		cout<<ve[i]<<' ';
	}
	for(int i=1;i<=n;i++){
		if(!sign[i]) cout<<a[i]<<' ';
	}
	cout<<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();
	}
}