A-G题解

A

#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef long long LL;

void solve() {
    int x;
    cin >> x;
    int cnt = 0;
    while(x % 10 != 0) x ++, cnt ++;
    cout << cnt;
}

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

B

枚举一下即可

#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef long long LL;

void solve() {
    string s;
    cin >> s;
    LL sum = 0, ans = 0;
    for(auto t : s) sum += t - '0';
    for(int i = s.size() - 1; i >= 0; i -- ) {
    	if(sum % 9 == 0) ans ++;
    	sum -= s[i] - '0';
    }
    cout << ans;
}

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

C

用尽可能长的连续的相同字符取构造即可

#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef long long LL;

void solve() {
    LL n, k;
    cin >> n >> k;
    char c = 'd';
    int cnt = 0;
    for(LL i = n; i >= 2; i -- ) {
    	LL t = i * (i - 1) / 2;
    	while(k >= t) {
    		k -= t;
    		for(LL j = 0; j < i; j ++ ) cout << c, cnt ++;
    		c ++;
    	}
    }
    //while(k) k --, cout << c << c, c ++;
    //cout << k << '\n';
    string s = "abc";
    for(; cnt < n; cnt ++ ) cout << s[cnt % 3];
}

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

D

如果数组中所有相邻点间隔的最大值等于k，则答案为0
如果小于k，则答案为1，因为可以在任意两个点之间加上一个数，是其与较小的数的差值等于k
如果大于k，则需要计算每一个间隔大于k对答案的贡献

#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef long long LL;

int n, k;
int a[N];

void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; i ++ ) cin >> a[i];
    LL cnt = 0;
 	int mx = 0;
    for(int i = 2; i <= n; i ++ ) {
    	int d = abs(a[i] - a[i - 1]);
    	mx = max(mx, d);
    	if(d > k) {
    		d -= k;
    		cnt += (d + k - 1) / k;
    	}
    }
    if(mx < k) cnt = 1; 
    cout << cnt;
}

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

E

枚举 $i$ ，对于当前 $a_i$ ，假设j是其因数，将j作为公比，则我们只需要log次就可以判断出以当前 $a_i$ 为等比数列的最后一个点的最长等比数列。复杂度是远远低于上界 $n*\sqrt{n}*log2(n)$
注意公比为1的情况，需要特判一下

#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef long long LL;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    vector<int> f(N);
    for(int i = 1; i <= n; i ++ ) cin >> a[i], f[a[i]] ++;
    
	sort(a.begin() + 1, a.end());
	int res = *max_element(f.begin(), f.end());
	//vector<int> ff(N);
	for(int i = 1; i <= n; i ++ ) {
		int x = a[i];

		for(int j = 1; j <= sqrt(x); j ++ ) {
			if(x % j == 0) {
				int t = x, cnt = 1;
				while(t % j == 0 && f[t / j] && j > 1) t /= j, cnt ++;
				res = max(res, cnt);
				if(x / j != j) {
					t = x, cnt = 1;
					while(t % (x / j) == 0 && f[t / (x / j)]) t /= (x / j), cnt ++;
					res = max(res, cnt);
				}
			}
		}

		res = max(res, f[x]);
	}

	cout << res;
}

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

F

这个题莫队显然可做，所以就懒得想了

莫队做法：对于一个区间来说，如果存在>2的回文子序列，则需满足：

某一个数出现三次及以上(个数为f1)
某一个数出现两次(个数为f2)，但不连续出现

第一种情况好讨论，重点是第二种。我们可以多维护一个sum，即区间内相邻两点相同的数的个数，如果说满足sum==f2显然第二种情况不成立
为了O(1)维护莫队中的信息，我们需要将数组中的值离散化一下

#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 2e5 + 10;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef long long LL;

struct node{
	int l, r, id;
}Q[N];

int n, q;
int a[N], f1, f2;
int ans[N], cnt[N];

void add(int x) {
	cnt[a[x]] ++;
	if(cnt[a[x]] == 2) f1 ++;
	else if(cnt[a[x]] == 3) f2 ++;
}

void del(int x) {
	if(cnt[a[x]] == 2) f1 --;
	else if(cnt[a[x]] == 3) f2 --;
	cnt[a[x]] --;
}

void solve() {
    cin >> n >> q;
    vector<int> nums;
    for(int i = 1; i <= n; i ++ ) cin >> a[i], nums.pb(a[i]);
    
    for(int i = 0; i < q; i ++ ) 
    	cin >> Q[i].l >> Q[i].r, Q[i].id = i;

    sort(nums.begin(), nums.end());
    nums.erase(unique(nums.begin(), nums.end()), nums.end());

    auto find = [&](int x) {
    	return lower_bound(nums.begin(), nums.end(), x) - nums.begin() + 1;
    };

    for(int i = 1; i <= n; i ++ ) a[i] = find(a[i]);

    auto get = [&](int x) {
    	return x / sqrt(n);
    };

    sort(Q, Q + q, [&](node a, node b) {
    	int l = get(a.l), r = get(b.l);
    	if(l != r) return l < r;
    	return a.r < b.r;
    });

    int sum = 0;
    for(int i = 0, R = 0, L = 1; i < q; i ++ ) {
    	auto [l, r, id] = Q[i];
    	while(R < r) {
    		add(++ R);
    		if(a[R] == a[R - 1]) sum ++;
    	}
    	while(R > r) {
    		del(R --);
    		if(a[R] == a[R + 1]) sum --;
    	}
    	while(L < l) {
    		del(L ++ );
    		if(a[L] == a[L - 1]) sum --;
    	}
    	while(L > l) {
    		add(-- L);
    		if(a[L] == a[L + 1]) sum ++;
    	}
    	//cout << f1 << ' ' << f2 << ' ' << sum << '\n';
    	if(f2) ans[id] = 1;
    	if(f1 == sum) continue;
    	if(f1) ans[id] = 1;
    }

    for(int i = 0; i < q; i ++ )
    	if(ans[i]) puts("YES");
    	else puts("NO");
}

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

G

逆序对问题一般都是用树状数组处理，对于该问题的解决你需要先了解一下如何用树状数组求逆序对

我们可以维护一对双指针 $l$ 和 $r$ ，对r进行枚举，维护以r结尾最长的可删除区间的长度，即l的最左延申。
我们可以用一个两个树状数组 $pre$ 和 $suf$ ，来维护l前和r后的信息,tot为当前删除区间外的逆序对数，如果逆序对数小于k，则l向右移动，减小可删除区间的长度

#include <bits/stdc++.h>

#define x first
#define y second
#define pb push_back

using namespace std;

const int N = 1e6 + 10;
const int P = 1e9 + 7, INF = 0x3f3f3f3f;

typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef long long LL;

int pre[N], suf[N];
int n;
LL k;

int lowbit(int x) {
	return x & -x;
}

void add(int x, int v, int tr[]) {
	for(int i = x; i < N; i += lowbit(i) ) 
		tr[i] += v;
}

LL sum(int x, int tr[]) {
	LL res = 0;
	for(int i = x; i; i -= lowbit(i) )
		res += tr[i];
	return res;
}

void solve() {
    cin >> n >> k;
    
    LL tot = 0, ans = 0;
	int m = 1e6;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i ++ ) {
    	cin >> a[i];
    	add(a[i], 1, suf);
    	tot += sum(m, suf) - sum(a[i], suf);
    }
    if(tot >= k) ans ++;
    //cout << tot << '\n';
	int r = 1, l = 1;
	while(r <= n) {
		add(a[r], -1, suf);
		tot -= sum(a[r] - 1, suf) + sum(m, pre) - sum(a[r], pre);
		//if(r == 3) cout << tot << '\n';
		while(tot < k && l <= r) {
			add(a[l], 1, pre);
			tot += sum(m, pre) - sum(a[l], pre);
			tot += sum(a[l] - 1, suf);
			l ++;
		}
		//cout << l << ' ' << r << ' ' << tot << '\n';
		ans += r - l + 1;
		r ++;
	}
	cout << ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
    int T = 1;
    //cin >> T;
    while(T -- ) {
        solve();
    }
    return 0;
}

题解 | #A-G#

A

B

C

D

E

F

莫队做法：对于一个区间来说，如果存在>2的回文子序列，则需满足：

G