abc370

A

阅读理解

signed main() {
    IOS;
    int a, b;
    cin >> a >> b;
    if (a ^ b) {
        if (a == 1 && b ==0) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    } else {
        cout << "Invalid" << endl;
    } 

    return 0;
}

B

#define MAX 105
int a[MAX][MAX];
signed main()
{
    IOS;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> a[i][j];
            //cout << a[i][j] << ' ';
        }
        //cout << endl;
    }
    int op = 1;
    for (int i = 1; i <= n; i++) {
        int x = min(op, i), y = max(op, i);
        op = a[y][x];
        //cout << op << endl;
    }
    cout << op << endl;

    return 0;
}

C

signed main() {
    IOS;
    string S, T;
    cin >> S >> T;
    int len = S.size();
    int ans = 0;
    vector<string> res;
    for (int i = 0; i < len; i++)
    {
        int flag = 0;
        for (int j = 0; j < len; j++)
        {
            if (S[j] > T[j]) {
                S[j] = T[j];
                res.push_back(S);
                flag = 1;
            }
        }
        if (flag) {
            continue;
        }
        for (int j = len - 1; j >= 0; j--) {
            if (S[j] != T[j]) {
                S[j] = T[j];
                res.push_back(S);
                flag = 1;
            }
        }
        if (!flag) {
            break;
        }
    }
    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i++) {
        cout << res[i] << endl;
    }

        return 0;
}

D

感觉利用并查集的思路去建立四个数组是最好的思路

#include <bits/stdc++.h>
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0);                  \
    cout.tie(0)

using namespace std;

void solve()
{
    int h, w;
    cin >> h >> w;
    vector<vector<int>> u(h + 10, vector<int>(w + 10)), d(h + 10, vector<int>(w + 10)),
        r(h + 10, vector<int>(w + 10)), l(h + 10, vector<int>(w + 10)),
        st(h + 10, vector<int>(w + 10));
    for (int i = 0; i <= h + 1; i++)
        for (int j = 0; j <= w + 1; j++)
        {
            u[i][j] = d[i][j] = i;
            l[i][j] = r[i][j] = j;
        }
    int q;
    cin >> q;
    int ans = 0;
    auto gao = [&](int x, int y)
    {
        ++ ans;
        st[x][y] = true;       // 设置当前点已访问
        u[x][y] = u[x - 1][y]; // 更新u数组
        d[x][y] = d[x + 1][y]; // 更新d数组
        l[x][y] = l[x][y - 1]; // 更新l数组
        r[x][y] = r[x][y + 1]; // 更新r数组
    };

    while (q--)
    {
        int x, y;
        cin >> x >> y;
        if (!st[x][y])
        {
            gao(x, y);
        }
        else
        {
            if (u[x][y] != 0)
            {
                int j = u[x][y]; // 下一个
                vector<int> v;
                v.push_back(x);
                while (u[j][y] != j)
                {
                    v.push_back(j);
                    j = u[j][y];
                }
                for (auto k : v)
                    u[k][y] = j;
                if (j != 0)
                {
                    gao(j, y);
                }
            }
            if (d[x][y] != h + 1)
            {
                int j = d[x][y]; // 下一个
                vector<int> v;
                v.push_back(x);
                while (d[j][y] != j)
                {
                    v.push_back(j);
                    j = d[j][y];
                }
                for (auto k : v)
                    d[k][y] = j;
                if (j != h + 1)
                {
                    gao(j, y);
                }
            }
            if (l[x][y] != 0)
            {
                int j = l[x][y]; // 下一个
                vector<int> v;
                v.push_back(y);
                while (l[x][j] != j)
                {
                    v.push_back(j);
                    j = l[x][j];
                }
                for (auto k : v)
                    l[x][k] = j;
                if (j != 0)
                {
                    gao(x, j);
                }
            }
            if (r[x][y] != w + 1)
            {
                int j = r[x][y]; // 下一个
                vector<int> v;
                v.push_back(y);
                while (r[x][j] != j)
                {
                    v.push_back(j);
                    j = r[x][j];
                }
                for (auto k : v)
                    r[x][k] = j;
                if (j != w + 1)
                {
                    gao(x, j);
                }
            }
        }
    }
    cout << h * w - ans;
}

signed main()
{
    IOS;
    int t = 1;
    //    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

E

式子不好推,就是写出DP公式以后推公式后用map优化问题

using Z = mod_int<998244353>;
map<ll, Z> mp;
ll sum;
Z tot;
int n;
ll k;
int main()
{
    cin >> n >> k;
    mp[0] = 1;
    tot = 1;
    for (int i = 1; i <= n; i++)
    {
        ll x;
        cin >> x;
        sum += x;
        Z add = tot - (mp.count(sum - k) ? mp[sum - k] : 0);
        mp[sum] += add;
        tot += add;
        if (i == n)
            return cout << add << endl, 0;
    }
    return 0;
}

F

一个二分加倍增

const int N = 400010, MAX_LOG = 20;
int n,k;
int a[N];
ll s[N];
int f[N][MAX_LOG];
bool g[N];
bool check (int x) {
	for (int i = 1,j = 0;i <= 2 * n;i++) {
		while (j <= 2 * n && s[i] - s[j + 1] >= x) j++;
		if (j >= 2 * n) {
		    break;
		}
		f[i][0] = j;
	}
	for (int j = 1;j < MAX_LOG;j++) {
		for (int i = 1;i <= 2 * n;i++) {
			if (!f[i][j - 1]) f[i][j] = 0;
			else f[i][j] = f[f[i][j - 1]][j - 1];
		}
	}
	bool ans = false;
	for (int i = n + 1;i <= 2 * n;i++) {
		int p = i;
		for (int j = MAX_LOG - 1;j >= 0;j--) {
			if (k >> j & 1) p = f[p][j];
			if (!p) break;
		}
		g[i] = p >= i - n;
		ans |= g[i];
	}
	return ans;
}
int main () {
	cin >> n >> k;
	for (int i = 1;i <= n;i++) cin >> a[i],a[i + n] = a[i];
	for (int i = 1;i <= 2 * n;i++) s[i] = s[i - 1] + a[i];
	int l = 1,r = 2e9;
	while (l + 1 < r) {
		int mid = (LL)l + r + 1 >> 1;
		if (check (mid)) l = mid;
		else r = mid;
	}
	check (l);
	int ans = n;
	for (int i = n + 1;i <= 2 * n;i++) ans -= g[i];
	cout << l << ' ' << ans << endl;
	return 0;
}