传送门

C Darkness I

这个题就是找出一种放最少几个黑块能全部变黑，我么可以沿着对角线放，先以最小的那一边的正方形用对角线的方法放完，然后再两隔一列放一个，但是要注意向上取整。

#include<bits/stdc++.h>

#define int long long
#define fi first
#define se second

using namespace std;

const int N = 100010;
const int M = 998244353;

int n, m;
int a[N];
int ans[N];

void solve() {
    cin >> n >> m;
    if (n > m)swap(n, m);
    int cnt = m - n;
    cout << n + (cnt + 1) / 2;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int h_h;
    //cin >> h_h;
    h_h = 1;
    while (h_h--)solve();
    return 0;
}

F Inverse Manacher

这个题就是先初始化一个字符串为"&|a"，然后从第三个开始，每次判断一下位置，偶数是放|，奇数是放字母，每次将回文串复制到右边并移动指针，因为题目保证一定有解，但是放|的时候回文串的长度为1那么左右两边的字母会不一样，而且数组要注意开两倍。

#include<bits/stdc++.h>

#define int long long
#define fi first
#define se second

using namespace std;

const int N = 2000010;
const int M = 998244353;

int n, m;
int a[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= 2 * n + 2; i++)cin >> a[i];
    string sans = " &|a";
    for (int i = 4; i <= 2 * n + 2; i++) {
        if (i % 2 == 0)sans += '|';
        else {
            if (a[i - 1] == 1) {
                if (sans[i - 2] == 'a')sans += 'b';
                else sans += 'a';
            } else {
                if (sans[i - 2] == 'a')sans += 'a';
                else sans += 'b';
            }
        }
        if (a[i] == 1)continue;
        int pos = i - a[i] + 1;
        string s = sans.substr(pos, a[i] - 1);
        reverse(s.begin(), s.end());
        sans += s;
        i += a[i] - 1;
    }
    string ans;
    for (auto i: sans) {
        if (i == '&' || i == '|' || i == ' ')continue;
        ans += i;
    }
    cout << ans << endl;
    if (sans.size() > n + 1) {
        while (sans.size() != n + 1)sans.pop_back();
    }
}
/*5
1 1 2 1 4 1 2 3 4 3 2 1
& | a | b | a | a | a |
 */
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int h_h;
    //cin >> h_h;
    h_h = 1;
    while (h_h--)solve();
    return 0;
}

H Binary Craziness

这个题如果暴力枚举会超时，但是我们可以把每个点的度求出来，并用map存下来每个度出现的次数，因为两个数计算，这两个数相同的次数可能会出现很多次，如果遇见度数相同的就按照n*(n+1)/2来计算它的贡献即可，而如果两个数不相同对答案的贡献是两个数出现的次数乘积，但只能计算一次，不能重复计算。

#include<bits/stdc++.h>

#define int long long
#define fi first
#define se second

using namespace std;

const int N = 1000010;
const int M = 998244353;

int n, m;
int dg[N];
map<int,int> mp;
map<pair<int,int>,int> mp1;

void solve() {
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        dg[a]++;
        dg[b]++;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)mp[dg[i]]++;
    //cout << endl;
    //for (auto i: mp)cout << i.first << endl;
    for (auto i: mp) {
        for (auto j: mp) {
            int cnt = 0;
            auto a = i.fi;
            auto b = j.fi;
            if(a>b)swap(a,b);
            if (a == b) cnt = (i.se + 1) * i.se / 2;
            else if (!mp1.count({a, b}))cnt = i.se * j.se, mp1[{a, b}] = 1;
            ans += (i.fi ^ j.fi) * (i.fi | j.fi) * (i.fi & j.fi) * cnt;
            ans %= M;
        }
    }
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int h_h;
    //cin >> h_h;
    h_h=1;
    while (h_h--)solve();
    return 0;
}

J Expansion

读了好才读懂题目，意思就是先把数字处理前缀和，最开始是在第一个单元格，在哪个单元格资源的增长就是这个单元格的值，呀保证在走完全部的单元格的过程中，资源总是非负，然后无论然后都不能保证输出-1，如果第一个和最后一个为负数则肯定不能满足，否则如果是正数就直接走，然后是负数，走完这个各自以后目前的资源为负，那要在前面值为正的单元停留增长资源，直到能够走过这个为负的单元格，题目要求最少，则我们就找前面资源增长最大的即可。

#include<bits/stdc++.h>

#define int long long
#define fi first
#define se second

using namespace std;

const int N = 100010;
const int M = 998244353;

int n, m;
int a[N], s[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> a[i], s[i] = s[i - 1] + a[i];
    if (s[1] < 0 || s[n] < 0) {
        cout << -1 << endl;
        return;
    }
    int ans = 0, mx = 0, cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt += s[i];
        ans++;
        mx = max(mx,s[i]);
        if (cnt < 0) {
            if(mx==0){
                cout<<-1<<endl;
                return ;
            }
            ans += (abs(cnt) + mx - 1) / mx;
            cnt += (abs(cnt) + mx - 1) / mx * mx;
        }
    }
    cout << ans << endl;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int h_h;
    //cin >> h_h;
    h_h = 1;
    while (h_h--)solve();
    return 0;
}

K Dice Game

是一个概率问题，问有n个人玩m个面的色子，问在第一人点数确定的情况下，它的点数为1，2，3，...m的情况下的输的概率，相同约等于无效，而这个问题的答案就是q=ksm(m-i,n),p=ksm(m-1,n),按照题目写个快速幂输出即可。

#include<bits/stdc++.h>

#define int long long
#define fi first
#define se second

using namespace std;

const int N = 100010;
const int M = 998244353;

int n, m;
int a[N];
int ans[N];

int ksm(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1)res = res * x % M;
        x = x * x % M;
        y >>= 1;
    }
    return res % M;
}

void solve() {
    cin >> n >> m;
    ans[1] = 1;
    ans[m] = 0;
    for (int i = 2; i <= m; i++) {
        int q = ksm(m - i, n) % M;
        int p = ksm(m - 1, n) % M;
        ans[i] = q % M * ksm(p, M - 2) % M;
    }
    for (int i = 1; i <= m; i++)cout << ans[i] << ' ';
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int h_h;
    //cin >> h_h;
    h_h = 1;
    while (h_h--)solve();
    return 0;
}

M Different Billing

签到题，而迷局b或c都可以

#include<bits/stdc++.h>

#define int long long
#define fi first
#define se second

using namespace std;

const int N = 100010;
const int M = 998244353;

int n, m;
int a[N];
int ans[N];

int ksm(int x, int y) {
    int res = 1;
    while (y) {
        if (y & 1)res = res * x % M;
        x = x * x % M;
        y >>= 1;
    }
    return res % M;
}

void solve() {
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        int cnt = m - 1000 * i;
        if (cnt % 2500 == 0 && i + cnt / 2500 <= n) {
            cout << n - i - cnt / 2500 << ' ' << i << ' ' << cnt / 2500 << endl;
            return;
        }
    }
    cout << -1 << endl;
}

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    int h_h;
    //cin >> h_h;
    h_h = 1;
    while (h_h--)solve();
    return 0;
}