Codeforces 632(Div.2)

A题

题意：B是有白格子相邻的黑格子数，W是有黑格子相邻的白格子数，合法涂色方案为B=W+1。

思路：这道题的话，给定了矩阵，那么只需要一个角落的格子为白色，其余都为黑色即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t, n, m;
    cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (i == 0 && j == 0)
                    cout << "W";
                else
                    cout << "B";
            }
            cout << endl;
        }
    }
    return 0;
}

B题

题意：给定$a、b$序列，如果$i>j$，若则可以进行操作$a_{j}=a_{i}+a_{j}$，问能不能使a序列变成b序列。

这道题的话，因为我们是通过操作使得a序列变成b序列，所以我们从后面开始看，如果$b[i]>a[i]$的话，要让$a[i]$变大的话，前面一定要有1；如果$b[i]<a[i]$的话，要让$a[i]$变小的话，前面一定要有-1，否则不合法。然后我们记住最左面的1和-1的位置判断即可。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
int a[maxx], b[maxx];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        int ans = inf, cnt = inf;
        for (int i = 0; i < n; i++)
        {
            cin >> a[i];
            if (a[i] == 1 && ans == inf)
                ans = i;
            if (a[i] == -1 && cnt == inf)
                cnt = i;
        }
        int flag = 1;
        for (int i = 0; i < n; i++)
        {
            cin >> b[i];
            if (b[i] > a[i] && ans >= i)
                flag = 0;
            if (b[i] < a[i] && cnt >= i)
                flag = 0;
        }
        if (flag)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

C题

题意：如果一个序列的所有非空子序列的和都不为零，则称该序列是一个好序列。现给定一个序列，求有多少个非空子序列是好序列。

思路：这道题的话，首先区间$[i,j]$和为$0$,可以得到:$sum[i]=sum[j]$，然后如果一个区间$[i,j]$和为$0$那么从$j+1$开始才存在好区间，最后用$cnt$记录上一个可以包含的左端,那么每次加上$i-cnt$,遍历完就是答案。

AC代码：

#include <bits/stdc++.h>
typedef long long ll;
const int maxx = 100010;
const int inf = 0x3f3f3f3f;
using namespace std;
map<ll, ll> mapp;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    mapp[0] = 1;
    ll m, ans = 0, sum = 0, cnt = 0;
    for (ll i = 1; i <= n; i++)
    {
        cin >> m;
        sum += m;
        cnt = max(cnt, mapp[sum]);
        ans += (i - cnt);
        mapp[sum] = i + 1;
    }
    cout << ans << endl;
    return 0;
}

赏

×

纯属好玩

扫码打赏，你说多少就多少

打开支付宝扫一扫，即可进行扫码打赏哦