Codeforces Round ＃804 (Div. 2)

Topic link

A  The Third Three Number Problem

The question

To give you one n, Let you be satisfied Of a,b,c.

 

If not, output -1.

Ideas

  Obviously arbitrary a,b,c It is impossible to get odd numbers .

Considering only even numbers, we can get a special structure n/2 , 0 , 0 .

Code

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const ll N = 1e6;
void solve()
{
    int n;
    cin >> n;
    if (n % 2 == 1)
        cout << "-1\n";
    else
        cout << n / 2 << " 0 0\n";
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

 

B - Almost Ternary Matrix

The question

structure 01 matrix , It is required that at most two numbers of each number are the same .

Ideas

With this pattern    Extend the basic construction unit , Then cut out the required pattern according to the scope given by the meaning of the topic .

 

Code

 

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long ll;
const ll N = 1e6;
int s[10][65];
void solve()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
            cout << s[i % 4][j] << " ";
        cout << endl;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    s[1][1] = 1, s[1][2] = 0, s[1][3] = 0, s[1][4] = 1;
    s[1][0] = 1;
    s[2][1] = 0, s[2][2] = 1, s[2][3] = 1, s[2][4] = 0;
    s[2][0] = 0;
    for (int i = 1; i <= 60; i++)
    {
        s[0][i] = s[1][i % 4];
        s[1][i] = s[1][i % 4];
        s[2][i] = s[2][i % 4];
        s[3][i] = s[2][i % 4];
    }
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}

 

 

C - The Third Problem

The question

Give a long for n Array of a, The content is 0 To n-1. Define an operation MEX For collection c1,c2,.....,ck   The minimum non negative number that does not appear in .

  for example

 

  Let you find an array b, The content is also 0 To n-1. To any   There are

 

 

Ideas

Set yes s[x] by x stay a Position in

First consider 0 The location of , because MEX[0]=1, therefore 0 The position of can only be s[0], Can be determined 1 The location of the for s[1].

Let's make sure 2~n-1 The same way , With 0 and 1 The index of determines the interval  [L, R], If the next Count x The rope is in the entry section [L, R], Update ans by （（ Interval length ）-（x-1））*ans, If k If the index of is outside the interval, it will be updated L or R Increase the interval length .

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;
}