Codeforces Round ＃804 (Div. 2)

A. The Third Three Number Problem

A. The Third Three Number Problem
大意：给你一个n，让你求满足 的abc
做法就是用0呗，奇数1凑不出来，偶数0 0 n/2

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long 
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
 
signed main()
{
    
	int t, n;
	cin >> t;
	while(t --)
	{
    
		cin >> n;
		if(n & 1)
			cout << -1 << endl;
		else cout << 0 << " " << 0 << " " << n / 2 << endl;
	}
	return 0;
}

B. Almost Ternary Matrix

B. Almost Ternary Matrix
就是构造，但是注意，是它的邻居有且仅有两个跟他不一样，白wa3发

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long 
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
 
signed main()
{
    
	int t, n, m;
	cin >> t;
	while(t --)
	{
    
		cin >> n >> m;
		m /= 2; 
		for(int i=1; i<=n; i++)
		{
    
			for(int j=1; j<=m; j++)
			{
    
				if(i % 4 == 1) 
					if(j & 1) cout << "1 0";
					else cout <<"0 1";
				else if(i % 4 == 2)
					if(j & 1) cout <<"0 1";
					else cout << "1 0";
				else if(i % 4 == 3) 
					if(j & 1) cout <<"0 1";
					else cout << "1 0";
				else
					if(j & 1) cout << "1 0";
					else cout <<"0 1";
				if(j == m) cout << endl;
				else cout <<" ";
			}
		}
	}
	return 0;
}

C. The Third Problem

C. The Third Problem

好题啊
一道题让我rk飙升

大意就是给你一个长为n的数组，内容是0到n-1，然后给你mex定义，说如果两组数中任意区间这俩的mex都相等，就说这两组数是相似的，然后给你一个数组，问你这个数组的相似数组有多少，包含他自己本身

做法：不知道叫啥，举个样例吧

8
1 3 7 2 5 0 6 4

用0和1位置不变先确定初始区间
一开始区间1 ~ 6，2的可能位置是数6-2=4，3的可能位置数是6-3=3，4在区间外面，所以4的可能位置数是1，然后这时候扩大区间，把4，扩进来，因为4已经确定位置了(可以这么想，枚举到4的时候，4前面的都在区间内被确定了，所以4就是外面最小的，它一动mex肯定变，所以它不能动，也就是位置固定)，区间扩大为1~8，5的可能位置是8-5=3，6的可能位置2，7的可能位置8-7=1，332*4=72

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <map>
#include <string>
#include <cstring>
#include <cmath>
#include <stack>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%d",a) 
#define endl "\n"
#define int long long
#define mem(a,b) memset(a,b,sizeof a)
#define ull unsigned long long
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define LL long long 
#define lowbit(x) x&(-x)
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PI acos(-1)
#define pb push_back
#define x first
#define y second
const double eps = 1e-6;
const int mod = 998244353;
const int MOD = 1e9 + 7;
const int N = 1e5 + 10;
int a[N]; 
map<int, int> mp;
set<int> s;
signed main()
{
    
	int t, n, m;
	cin >> t;
	while(t --)
	{
    
		cin >> n;
		int l1 = 0, r1 = 0, mex;
		mp.clear();
		s.clear();
		for(int i=1; i<=n; i++)
		{
    
			cin >> a[i];
			mp[a[i]] = i;
			if(a[i] == 0) l1 = i;
			if(a[i] == 1) r1 = i;
		}
// for(int i=0; i<n; i++) 
		if(l1 > r1) swap(l1, r1);
// cout << "---"<< l1 <<" " << r1 << endl;
		int res = 1;
		
		for(int i=2; i<n; i++)
		{
    
			if(mp[i] < l1) l1 = mp[i];
			else if(mp[i] > r1) r1 = mp[i];	
			else res *= r1 - l1 + 1 - i;
			res %= MOD;
		}
		
		cout << res << endl;
		for(int i=1; i<=n; i++) a[i] = 0;
	}
	return 0;
}