Codeforces Round #804 (Div. 2)

題目鏈接

A  The Third Three Number Problem

題意

給你一個n，讓你求滿足的a，b，c。

 

如果不存在則輸出-1.

思路

 顯然任意a，b，c是不可能得到奇數。

只考慮偶數可以得到一個特殊構造 n/2 , 0 , 0 。

程式碼

#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

題意

構造01矩陣，要求每個數的上下左右最多有兩個數相同。

思路

以這個圖案  為基本構造單元進行擴展，再根據題意所給的範圍截出需要的圖案。

 

程式碼

 

#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

題意

給一個長為n的數組a，內容是0到n-1。定義一個操作MEX為集合c1,c2,.....,ck  中沒有出現的最小非負數。

 例如

 

 讓你求一個數組b，內容也是0到n-1。對任意 都有

 

 

思路

設是s[x]為 x 在a 中的位置

首先考慮0的位置，因為MEX[0]=1,所以0的位置只能是s[0]，可以確定1的位置為s[1]。

接下來確定 2~n-1的方法相同，以 0 和 1 的索引確定區間 [L， R]，如果下一個 數x 的索在入區間 [L， R]，則更新ans為（（區間長度）-（x-1））*ans， 如果 k 的索引位於區間之外則更新L或R增加區間長度。

程式碼

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

 

Tags:

VirMach 便宜 VPS