CF链接 VP过了5题，其中我做了两题，Cu。

L题 Recover Statistics

签到、简单构造

L题签到题我居然WA了4发。。。

CPP

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
ll n, m;
int T;
ll gcd(ll a, ll b) {
    return b > 0 ? gcd(b, a % b) : a;
}
int main() {
    ios::sync_with_stdio(0);
    int a, b, c;
    cin >> a >> b >> c;
    cout << 100 << endl;
    for (int i = 1; i <= 50; i++)cout << 1 << " ";
    for (int i = 51; i <= 95; i++)cout << a+1 << " ";
    for (int i = 96; i <= 99; i++)cout << b+1 << " ";
    cout << c + 1;
}

J题 Grand Prix of Ballance

签到、模拟

太简单了，而且是队友做的，代码就不贴了。

A题 Arrow a Row

构造

CPP

#include<bits/stdc++.h>
using namespace std;
#define  ll long long
#define IOS cin.tie(0);cout.tie(0);ios::sync_with_stdio(0)
#define  pll pair<long long,long long>
ll t, n,ed;
string s;
int main()
{
	IOS;
	cin >> t;
	while (t--)
	{
		vector<pll>ans;
		cin >> s;
		n = s.length();
		s = " " + s;
		ll cnt = 0;
		for (ll i = n; i >=1; i--)
		{
			if (s[i] == '>')
				cnt++;
			else break;
		}
		ed = 0;
		for (ll i = n - cnt; i >=1; i--)
		{
			if (s[i] == '>')
			{
				ed = i;
				break;
			}
		}
		ll sum = 0;
		if (cnt >= 3 and s[1] == '>' and cnt != n)
		{
			cout << "Yes ";
			ll i = 1, j = n - 2;
			while (i != ed or j != n - cnt + 1)
			{
				sum++;
				ans.push_back({ i,j-i+3 });
				j = max(j - 3, n - cnt + 1);
				while (s[++i] == '-');
				i = min(i, ed);
			}
			ans.push_back({ i,j-i+3 });
			sum++;
			cout << sum << '\n';
			for (auto e : ans)
				cout << e.first << ' ' << e.second << '\n';
		}
		else
		{
			cout << "No\n";
		}
	}
}

B题 Athlete Welcome Ceremony

动态规划、前缀和

题意

给你一个由a,b,c和?构成的串，你要将所有?变成a,b,c之一，使其成为没有相邻字符相同的串。

有

Q

个询问，每次给你一组

x

y

z

，问你最多用

x

个a,

y

个b 和

z

个c能构成多少合法串。输入保证合法且有解。

题解

我还不会下次补。。。代码先不贴了。

G题 Expanding Array

位运算

VP的时候做到这题已经猜到结论了，但是写了一半代码出去上了个很长时间的厕所，被队友怀疑偷看题解了（然而我是在刷王者荣耀视频QAQ）

题意

一个整数数组，可以无限次进行以下操作：选择两个相邻的数，将其按位与、或、异或的三个结果中的一个插入到这两个数之间。问最后数组元素个数的最大值。

题解

可以猜到证明对于相邻的两个数

x,y

在无限次操作后能产生的数只有：

\begin{cases} x\operatorname{and} y, x\operatorname{or} y, x\operatorname{xor} y\\ x \operatorname{or} y \operatorname{xor} x, x \operatorname{or} y \operatorname{xor} y\\ 0 \end{cases}

全部放进set里，输出size()即可。VP时我为了谨慎起见还加了很多额外的数进去，不影响结果和复杂度。

CPP

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
ll n, m;
int a[100005];
set<int> s;
int main() {
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        s.insert(a[i]);
    }
    for (int i = 0; i < n - 1; i++) {
        int x = a[i] ^ a[i + 1];
        int y = a[i] & a[i + 1];
        int z = a[i] | a[i + 1];
        s.insert(x);
        s.insert(y);
        s.insert(z);
        s.insert(x & y);
        s.insert(x & z);
        s.insert(y & z);
        s.insert(x ^ y);
        s.insert(x ^ z);
        s.insert(y ^ z);
        s.insert(x | y);
        s.insert(x | z);
        s.insert(y | z);
        s.insert(a[i] & x);
        s.insert(a[i] & y);
        s.insert(a[i] & z);
        s.insert(a[i] ^ x);
        s.insert(a[i] ^ y);
        s.insert(a[i] ^ z);
        s.insert(a[i] | x);
        s.insert(a[i] | y);
        s.insert(a[i] | z);
        s.insert(a[i + 1] & x);
        s.insert(a[i + 1] & y);
        s.insert(a[i + 1] & z);
        s.insert(a[i + 1] ^ x);
        s.insert(a[i + 1] ^ y);
        s.insert(a[i + 1] ^ z);
        s.insert(a[i + 1] | x);
        s.insert(a[i + 1] | y);
        s.insert(a[i + 1] | z);
    }
    s.insert(0);
    cout << s.size();
}

I题 Good Partitions

数学、线段树

这题做出来应该就有Ag了，可惜可惜。

题意

给定一个长度为

n

的序列，如果从第一项开始每

k

个元素一组将其划分为

\lceil \frac{n}{k} \rceil

个子序列（最后一个子序列元素个数可能不满

k

个），且每个子序列都是单调不减的，则称这种划分为好的划分。

有

q

次修改，每次修改序列中一个位置的元素值。询问每次修改前后好的划分的数量。

n,q\le 2\times 10^5

。

题解

设所有满足

a_i>a_i+1

的下标

i

组成集合

S

,答案就是

\gcd(S)

。

用线段树维护

\gcd

，复杂度

O(n\log^2 n)

。

CPP

#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;

const int N = 2e5 + 5;
int d[N];
void init(int n) {
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; j += i)++d[j];
}

int __gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

#define lc (x<<1)
#define rc (x<<1|1)
#define mid ((l+r)>>1)
int n, q, x, y, a[N], s[N * 4];
void bld(int x, int l, int r) {
    if (l == r) { s[x] = a[l] > a[l + 1] ? l : 0; return; }
    bld(lc, l, mid), bld(rc, mid + 1, r);
    s[x] = __gcd(s[lc], s[rc]);
}
void upd(int x, int l, int r, int p, int v) {
    if (l == r) { s[x] = v; return; }
    if (p <= mid)upd(lc, l, mid, p, v);
    else upd(rc, mid + 1, r, p, v);
    s[x] = __gcd(s[lc], s[rc]);
}

void solve() {
    cin >> n >> q, d[0] = n;
    for (int i = 1; i <= n; ++i)cin >> a[i];
    if (n == 1) {
        cout << 1 << '\n';
        while (q--)cin >> x >> y, cout << 1 << '\n';
        return;
    }
    bld(1, 1, n - 1);
    cout << d[s[1]] << '\n';
    while (q--) {
        cin >> x >> y;
        if (x > 1 && a[x - 1] > a[x] && a[x - 1] <= y)upd(1, 1, n - 1, x - 1, 0);
        if (x > 1 && a[x - 1] <= a[x] && a[x - 1] > y)upd(1, 1, n - 1, x - 1, x - 1);
        if (x<n && a[x]>a[x + 1] && y <= a[x + 1])upd(1, 1, n - 1, x, 0);
        if (x<n && a[x] <= a[x + 1] && y>a[x + 1])upd(1, 1, n - 1, x, x);
        a[x] = y;
        cout << d[s[1]] << '\n';
    }
}

int main() {
    init(2e5);
    ios::sync_with_stdio(0); cin.tie(0);
    int T;
    cin >> T;
    while (T--)solve();
}

ICPC 2024 成都站

文章操作