Codeforces Round 896 (Div. 2)题解

前言:

3 solved of 7 A、B、C,太菜了，写B题的时候，常数设成1e5了，一直卡在Test 4,没想到一直提示我TLE，没有提示RE，导致我浪费了很多时间在B题上，最后时间太晚了交了TLE了一发睡觉去了

A-Make It Zero 

A - Make It Zero

题目分析：选取l,和r，并将l~r当中所有值转化为他们异或和

只需要知道2个相同的数异或和为0，这题就已经解决了

偶数:1~n两次操作必为0

奇数:1~2两次操作保证1位上为0，2~n两次操作，保证2~n为零，至此整个数列s全为0

代码：

#include
using namespace std;
const int N =1e5;
int a[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);
 
int t;cin>>t;int tmp;
while(t--)
{
    int n;cin>>n;int x;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
    }
    if(n%2==0)
    {
        
        
            cout<<"2"<
            cout<<"1 "<
            cout<<"1 "<
    }
    else
    {
        cout<<"4"<
        cout<-1<<" "<
        cout<-1<<" "<
        cout<<"1 "<-1<
        cout<<"1 "<-1<
    }
 
 
 
}
}

B - 2D Traveling 

B - 2D Traveling 

 

 

题目分析：

a到b城市，费用为二者坐标x,y之差的绝对值,同时前k个城市为maincity,也就是图中标红的点，miancity到maincity是不需要任何费用的，求最优解

1.a,b均为主要城市此时费用为0

2.a or b 为主要城市，并且图上还有至少一个主要城市 此时a~mainc or b~mainc 的费用为零，计算另一个城市到该mainc的费用并和直接a~b取min求解

3. a,b不为mainc ,图上至少有两个mainc, 这时候可以直接统计a,b两个局部最优解，也即 a~距离a最近的mainc+ b~距离b最近的mainc 和直接a~b取min求解

4.无mainc,直接输出 a~b费用

代码：

#include
using namespace std;
const int N =2e5+7;
typedef long long ll;
int a,b;
struct ss 
{
    int xi,yi;
}s[N],mainc[N];
bool cmp1(ss s1 ,ss s2)
{
    ll xii=s[a].xi;
    ll yii=s[a].yi;
    return abs(xii-s1.xi)+abs(yii-s1.yi)<abs(xii-s2.xi)+abs(yii-s2.yi);
}
bool cmp2(ss s1 ,ss s2)
{
    ll xii=s[b].xi;
    ll yii=s[b].yi;
    return (abs(xii-s1.xi)+abs(yii-s1.yi))<(abs(xii-s2.xi)+abs(yii-s2.yi));
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);
 
int t;cin>>t;
while(t--)
{
   int n,k;cin>>n>>k>>a>>b;
   ll o=1;
    for(ll i=1;i<=n;i++)
    {
        cin>>s[i].xi>>s[i].yi;
        if(i<=k)
        {
            mainc[o].xi=s[i].xi;
            mainc[o++].yi=s[i].yi;
        }
    }
    if(a<=k&&b<=k)cout<<"0"<
   else{
       ll ans=(ll)abs(s[a].xi-s[b].xi)+abs(s[a].yi-s[b].yi);
    if(o==2&&(a>k&&b>k))cout<
    else if(o>=1)
    {
        sort(mainc+1,mainc+o,cmp1);
        ll ans2=0;
        if(a>k)ans2+=(ll)abs(s[a].xi-mainc[1].xi)+(ll)abs(s[a].yi-mainc[1].yi);
        sort(mainc+1,mainc+o,cmp2);
        if(b>k)ans2+=(ll)abs(s[b].xi-mainc[1].xi)+(ll)abs(s[b].yi-mainc[1].yi);
        cout<<min(ans,ans2)<
    }
       
       
   }
}
}

C - Fill in the Matrix 

C - Fill in the Matrix 

题目分析：

n*m的矩阵M每一行 都必须由 0~m-1的数组成

并且每一列都会进行一个MEX函数操作，即得到不存在于整个数组当中的最小非负整数

接着对每一列求出的MEX值再进行一次MEX操作,最终得到ans，目标使得ans最大

对于ans的值有三种情况

1.以样例2为例:一行，则这一行必定是0~m-1,那么取出的值就为0 0 ....1 ...0 0 0，其中1的位置是由零决定的，那么我们在此基础上假设n=2的情况，我们可以设计第一行为0的位置，第二行为1，然后将第二行的0放在第一行当中及不为0也不为1的位置，那么第一次MEX的结果为 0 0...1 2 ...0 0，这样最终MEX的值也就是ans为3，我们可以想象出n=3、n=4..的情况了，也就是 ans=n+1。

2.我们知道由于m由0~m-1组成，所以第一次MEX的值最多为{0,1,2,3,4...m-1}第二次MEX为m,这也就说明了ans最大值为ans,如果上面的(n+1)超过了m,这是不合法的，所以我们取min(n+1,m)为最终ans

3.若m==1，那么第一次MEX=1，第二次MEX =0,然后这个矩阵只能由0组成，输出就很方便了

输出：

知道ans，是第一步，最关键的一步是我们怎么设计整个矩阵，除去上面第三种情况，其实我们都可以以这样的形式输出：（以6为例）

代码：

#include
using namespace std;
int t,n,m;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
	cin>>t;
	while(t--){
		cin>>n>>m;
		if(m==1){
			for(int i=0;i<=n;i++)cout<<0<<"\n";
		}else{
			cout<<min(n+1,m)<<"\n";
			for(int i=0;i
				for(int j=0;j
					cout<<(i%(m-1)+j)%m<<" ";
				}
				cout<<"\n";
			}
		}
	}
}