比赛链接:https://vjudge.csgrandeur.cn/contest/538238#overview

这次比赛做出了六道题。需要手动计算的题有点多,有点恶心,计算题就做了一个G题,主要是规律已经发现了做不出来有点可惜,BC目测应该也需要手动算一下。

BC感觉自己不会,没有做(其实就是自己不会)。

E题没看,应该是不难。H题没看,div2的C应该不简单,但不是不可做。

中间开小摊+刷抖音,应该是有大约两个半小时在做题(或许是做完atcoder打的太累了,emm~一定是这样的)。G题有点卡,D题题目太长了不想读题就一直在玩样例导致罚时较长。

A题:分类讨论。大意是给出一个数,根据性质分类,比较简单,直接代码吧。

code:


int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n');
	ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
	int n;
	cin>>n;
	bool flag1=false,flag2=false;
	if(n%2==0) flag1=true;
	if(n>4&&n<=12) flag2=true;
	if(flag1&&flag2) cout<<1<<' ';
	else cout<<0<<' ';
	if(flag1||flag2) cout<<1<<' ';
	else cout<<0<<' ';
	if((flag1||flag2)&&!(flag1&&flag2)) cout<<1<<' ';
	else cout<<0<<' ';
	if(!flag1&&!flag2) cout<<1<<' ';
	else cout<<0<<' ';
	
}


D题:大意是给出密文和原文的对照,求一组密文解密后的原文,不能存在题目中说的冲突情况。

因为没有好好读题,所以这种密文和原文的冲突情况可能存在很多。怎么算冲突,一对多还是多对一,还是双向冲突算冲突?根据最后AC应该是只能一对一且不满足26个字母的解密也不符合条件。
解决方法:map存字符映射,sign标记一下对一情况。

code:


int main()
{
 	//cin.ignore(numeric_limits<streamsize>::max(),'\n');
	ios_base::sync_with_stdio(0); cin.tie(0); //cout.tie(0);
	string s1,s2,s3;
	cin>>s1>>s2>>s3;
	for(int i=0;i<s1.size();i++){
		if(!mp[s1[i]]&&!sign[s2[i]]||mp[s1[i]]==s2[i]) mp[s1[i]] = s2[i],sign[s2[i]]=true;
		else{
			cout<<"Failed"<<endl;
			return 0;
		}
	}
	if(mp.size()<26){
		cout<<"Failed"<<endl;
		return 0;
	}
	vector<char> ve;
	for(int i=0;i<s3.size();i++){
		if(mp[s3[i]]){
			ve.push_back(mp[s3[i]]);
		}else{
			cout<<i<<endl;
			cout<<"Failed"<<endl;
			return 0;
		}
	}
	for(int i=0;i<ve.size();i++){
		cout<<ve[i];
	}
}


F题:大意是给出一个数组。我们可以选择其中两个数a,b。对于a*b = x*y.可以将x和y替换到a和b。最后求得到的最大钱数。最大钱数等于所有数的和。

思路:很明显可以贪,直接分成1*(a*b)即可。所以最后答案等于所有数相乘再加去(n-1)。因为通过贪心操作存在n-1个1.

code:


void solve()
{
	int n;
	cin>>n;
	ll ans = 1;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		ans*=a[i];
	}
	ans+=(n-1);
	cout<<ans*2022<<endl;
}


G题:大意是存在n*n的格子,对于下标i、j。每个格子的敌人数量是i*j。求从(1,1)走到(n,n)遇到的敌人数量。只能向右或向下走。

思路:最开始想的是走到最右边在一直向下走。答案不对。通过分析发现应该是先右在下一直循环往复。
但是数据量很大,很明显暴力不行。那么就需要在纸上去解方程。

向右的为(1*2)+(2*3)+(3*4)...((n-1)*n),往下的就是(1*1)+(2*2)+(3*3)。
然后就是这两个公式化简之后。有个坑就是化简之后会有一个/6的操作。因为存在模除情况,所以强行除以6必须要乘以6的逆元,且6为合数,这样必须扩展欧几里得算法来求逆元。但是存在*2022操作,而2022又正好整除6,所以最后答案可以直接*(2022/6)

code:


void solve()
{
	ll n;
	cin>>n;;
	ll ans = 0;
	// 1 2 3 4 5 6 
	// 1²+2²+3²+.+n²=n(n+1)(2n+1)/6                 n*(n+1)*(n-1);
	// n*(n+1)*(2*n+1) + 3*(n+1)
	// n*(n+1)*(2*n+4)  
	// n*(n+1)*(n+2)/3
	// n*(n+1)*(4*n-1)/3/2
	ans = n*(n+1)%mod7*(4*n-1)%mod7;
	ans = ans*(2022/6)%mod7;
	cout<<ans%mod7<<endl;
}


I题:常见位运算套路题。大意就是给出一个数组。你可以选择两个数,去交换他们的二进制的某一位,可以进行无限次操作。最后求数组最大的数减最小的数的最大的情况值。

思路:很明显,我们可以构造最大的数为所有数的存在的二进制1.这里直接或运算所有的数。
最小的数应该怎么构造。最小的数肯定是把身上的1都舍去。那么我们考虑无法舍去的数。怎么才能无法舍去?我们考虑如果在交换中,无法换到0,那么无法舍去。也就是某一位不存在任何数的二进制位为0.直接与运算起来就好了。

code:


void solve()
{
	int n;
	cin>>n;
	int maxt = 0;
	int mint = 0;
	int x;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		maxt|=a[i];
	}
	mint = a[1];
	for(int i=2;i<=n;i++){
		mint&=a[i];
	}
	cout<<maxt-mint<<endl;
}


J题:大意是给出一些怪物,这些怪物存在两个值,血量和能力。你拿着武器去消灭他们。武器威力值为k。每次令所有敌人减少k血量。每次攻击后,k的威力值减少,减少量为还存活的怪物的能力值最低的量。求能否消灭所有敌人。

思路:优先队列去维护所有怪物的数据,自定义排序规则以能力排序作小顶堆。然后直接模拟一遍。

code:


const int nn = 1e5+10;
int h[nn];
int p[nn];
struct tdata{
	ll x;
	ll nl;
};
struct cmp {
	bool operator() (tdata& a, tdata& b) {
		return a.nl>b.nl;
	}
};
void solve()
{
	priority_queue<tdata,vector<tdata>,cmp> pr;
	ll n,k;
	cin>>n>>k;
	ll sum = 0;
	for(int i=1;i<=n;i++) cin>>h[i];
	for(int i=1;i<=n;i++) cin>>p[i];
	for(int i=1;i<=n;i++){
		pr.push({h[i],p[i]});
	}
	while(!pr.empty()&&k>0){
		sum+=k;
		while(!pr.empty()&&pr.top().x<=sum) pr.pop();
		if(!pr.empty()) k-=pr.top().nl;
	}
	if(pr.empty()) cyes;
	else cno;
}