比赛网站：https://codeforc.es/contest/1699

这次比赛一道题都没有做出来，A题很像acm省赛第一题那种规律题，B题很像第一次参加泉城赛的矩阵题（都是推导公式）。C题是个区间问题，感觉也不好做。这里只看前三题。

A题：大意就是输入一个数n，然后找到三个数，让它们两两异或相加等于n

这个题当时我看出来了如果是奇数，那么就没有解输出-1。同时我也考虑到了可以找两个相等的数制作0，然后让这个数和第三个数异或出n/2，但是我始终没有把这两个相同的数用0来做实验。昨天的时候一直自认为数据范围是大于1的，读题没有读好，考虑的也不够周到。导致这次周赛卡题了

solution：为偶数则  输出两个0和一个n/2，因为0异或任何数都是原来的数。奇数直接输出-1。

code：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		if(n%2)
		{
			cout<<-1<<endl;
		}else
		{
			cout<<0<<' '<<0<<' '<<n/2<<endl;
		}
	}
 } 

B题：大意就是给出一个棋盘，里面有黑子和白字，你需要填充它，然后保证白子的上下左右有两个是白子，黑子的上下左右有两个是黑子。

一个思维的推导题，很难思考出来。

solution：可以以这么一个基本图形作为基础进行扩展，然后我们去推断这个基本图形黑白子所对应的   公式
我们可以直接列举一下其中一个颜色的  i=1,j=1 ；i=1,j=4;  i=4,j=1; i=4,j=4; 这四种情况，i%4=1和=0时  同时满足  j%4=1和j%4=0时  ，这个情况是黑子。  i=2,j=2;i=2,j=3; i=3,j=2; i=3;j=3 ;  这里的情况是什么？i%4=2和=3  同时满足  j%4=2和=3 也就是说
if(i%4<2&&j%4<2  ||   i%4>=2&&j%4>=2）  这个情况下可以是黑子，那么else就是白子了，因为||前面是两种情况，后面是两种情况（这个公式自己推出来了，不过说实话，cf的大佬压行的代码看着是真难受）
不过最难的一点就是，这个基本图形需要自己有思路去构造出来。这里感觉可以用第一个测试例子，然后来翻转找一个思路。如果明白了基本图思想，能够想到四四结合能构造上下左右有两个同色的，应该就可以构造出基本图形来。

code:

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m,t,i,j;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				if(i%4<2&&j%4<2 || i%4>=2&&j%4>=2)
					cout<<1<<' ';
				else
					cout<<0<<' '; 
			}
			cout<<endl; 
		}
	}
}

C题：一个区间的构造问题。大意是给出一个数组a 里面元素是0-n-1的乱序，我们约定mex(l,r) 的值是没有出现在l到r元素的最小非负整数。然后要求我们构造出个数组b，对于数组b的任意区间l和r  ，都有mexa(l,r)  = mexb(l,r)。要求我们求出数组b的个数。结果mod一个数

这个题很容易让人看着没有头绪，不知道从哪里开始入手。尤其是这种结果要mod一个数的题，处理不好很容易TLE。凡要mod，必有巧。

solution：先考虑0的位置，因为如果范围内只有0，那么mex  =1，所以如果0的位置不一样一定pass。确定好0的位置后，我们在利用0的位置来确定1，因为0周围的区间如果不包含1，那么一定会是1。省下的晚点更，希望早点弄的明白些

———————————— 半小时后~ ——————————————————————————————————————————————

今天必须弄明白！！！

这个题是这样的，前面说了我们很容易得出01必须和数组a保持一直。那么我们一个个来考虑，考虑到2数字，2如果在01区间内，那么2的位置可以放到几个位置，答案是  r-i+1区间数 减去确定的 两个数，这个数正好和i相等。那么可以是r-i+1-i 。这里根据排列组合我们不难想出是需要进行乘法运算。那么如果是区间外呢，那么我们必须保证和原来的数组a位置一直，因为01区间加上周围的数组成的区间，它的mex我们必须要让他和原来数组a保持一致，如果2的位置发生了变化，那么就无法维护原来区间的mex值。3之后的数同理。

这里我们直接看大佬的代码：https://www.cnblogs.com/gosick-ll/p/16445509.html
code：

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const ll N = 1e5, mod = 1e9 + 7;
void solve()
{
    int n;
    cin >> n;
    int sf[n];
    vector<int> s(n);
    for (int i = 0; i < n; i++)
    {
        cin >> sf[i];
        s[sf[i]] = i;
    }
    int l = s[0], r = s[0];
    ll ans = 1;
    for (int i = 1; i < n; i++)
    {
        if (s[i] > r)
            r = s[i];
        else if (s[i] < l)
            l = s[i];
        else
            ans = ans * (r - l + 1 - i) % mod;
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

重点在于这个if else 。如果在已知区间范围内，我们套用之前的那个公式累乘法，否则，我们尝试更新区间，因为不在区间内的方法只有一种。无需更新。

重写了一遍code:

#include<bits/stdc++.h>
using namespace std;
const int maxt = 1e5;
const int mod = 1e9+7;
int main()
{
	int t;
	vector<int>pos(maxt);
	cin>>t;
	while(t--)
	{
		pos.clear();
		int n,x;
		long long ans=1;
		cin>>n;
		for(int i=0;i<n;i++)
		{
			cin>>x;
			pos[x] = i;
		}
		int l=pos[0],r=pos[0];
		for(int i=1;i<n;i++)
		{
			if(pos[i]<l)
				l = pos[i];
			else if(pos[i]>r)
				r = pos[i];
			else
				ans = ans%mod*(r-l+1-i)%mod;
		}
		cout<<ans<<endl;
	}
 }