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

总结:可做的题还是有的。DEHJ没有去尝试。没什么太多思路。


这些应该是可补的题,外加一个J题,很好的思维题不会做但可以学

B题明显是个状压dp。但是没有推导出来分组关系这里的问题。

C题莫队板子题。拿莫队板子没跳出来。被卡了第6个样例。

G题应该有加乘除三种操作需要模拟。同样没调出来,被卡了第三个样例。应该是有一些情况没想出来。

I题做了几组数据都没问题。应该是有情况考虑欠缺。目标点其实就是每个元素能达到的点。达到范围可能需要考虑一下。


A题:大意是给出偶数数量武将。人和电脑去进行选择。两个武将之间产生武力值。电脑的选择永远都是选择我们已经选择的可匹配的最大武力值的另一个武将。在选择完之后,进行pk。每次选择双方最大的武力进行pk。胜利则获取ans 为武力值的数。求最大ans。

思路:很明显在任何情况下我们都无法选择最大的武力值。所以我们只能选择次大武力值,因为电脑是一种盲目跟风,所以我们总能选到次大。而电脑不会因为我们选了次大而构造最大,因为电脑不会构造只会卡我们的最大。所以答案就是次大武力值之间的最大武力值,最开始读题有点问题,以为求的是两个武力的差值。感觉有点麻烦就去做F了。其实只要读好题并不麻烦(最后AC了发现不需要判断相等情况。。。。)

code:


int n;
	cin>>n;
	ll x;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			cin>>x;
			mapt[i][j] = x;
			mapt[j][i] = x;
		}
	}
	vector<ll> ve;
	for(int i=1;i<=n;i++){
		sort(mapt[i]+1,mapt[i]+n+1,cmpmax);
		ve.push_back(mapt[i][2]);
	}
	sort(ve.begin(),ve.end());
	int p = ve.size()-1;//这里有点多余,题中最后的话告诉了不存在这种情况。且当这种情况存在时,还需要额外考虑次次大
	if(ve[p]>ve[0])
	cout<<1<<endl<<ve[p]<<endl;
	else cout<<0<<endl;


F题:大意是给出一个0的n*n的矩阵,你可以让任意行或列添加一个正整数。可以不限次数操作。最后将某个元素隐藏起来,令它为-1。求隐藏的数字。

思路:想了好几种做法都错了。最后想的是通过同行相邻和同列相邻的数来构造隐藏元素。

它的值为同行元素 + 同列元素 - 这行列对应元素的值。

我们设一个2*2矩阵为[a,b] [c,d]

其中我们要求a的值

那么a就等同于b的行增加+c的列增加。d等于b的列增加+c的行增加

b+c等于  a的行增加+d的列增加+a的列增加+d的行增加

再减去一个d就是a的行增加+a的列增加。证明完毕

然后需要处理一堆边界问题,就很烦,这里就分类讨论吧。因为要求的值一定是非负整数。所以直接abs吧。

没写abs的时候被卡了第12个点。不知道这个点是什么样子的。。。。。

code:

int n;
	cin>>n;
	int ti,tj;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>mapt[i][j];
			if(mapt[i][j]==-1) ti=i,tj=j;
		}
	}
	if(ti==n&&tj==n){
		cout<<abs(mapt[ti-1][tj]+mapt[ti][tj-1] - mapt[ti-1][tj-1])<<endl;
	}else if(ti==n){
		cout<<abs(mapt[ti][tj+1]+mapt[ti-1][tj] - mapt[ti-1][tj+1])<<endl;
	}else if(tj==n){
		cout<<abs(mapt[ti-1][tj]+mapt[ti][tj-1] - mapt[ti+1][tj-1])<<endl;
	}else{
		cout<<abs(mapt[ti][tj+1]+mapt[ti+1][tj] - mapt[ti+1][tj+1])<<endl;
	}