编辑
2025-02-24
acm
00
请注意,本文编写于 55 天前,最后修改于 54 天前,其中某些信息可能已经过时。

目录

Beautiful Sequence
Palindrome Shuffle
Remove the Ends
Eating
Devyatkino
Object Identification

Beautiful Sequence

要求严格小于和严格大于,且数字范围是[13][1-3] 因此结果只能是1 2....2 3

那么直接dpdp 即可 dpijdp_{ij}ii 个以jj 结尾的方案数

首先当前数不加入dpij=dpi1,jdp_{ij} = dp_{i-1,j}

如果当前数是11 那么dpi1+=1dp_{i1} += 1

如果当前数是22 那么dpi2+=dpi1,2+dpi1,1dpi2 += dp_{i-1,2}+dp_{i-1,1}

如果当前数是33 那么dpi3+=dpi1,2 dpi3 += dp_{i-1,2}

c++
#include<bits/stdc++.h> #define int long long using namespace std; #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl << endl; } template<class T, class... Ts> void err(T arg, Ts ... args) { cout << fixed << setprecision(10) << arg << ' '; err(args...); } template<const int T> struct ModInt { const static int mod = T; int x; ModInt(int x = 0) : x(x % mod) {} // ModInt(long long x) : x(int(x % mod)) {} int val() { return x; } ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); } ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); } ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % mod); } ModInt operator / (const ModInt &a) const { return *this * a.inv(); } bool operator == (const ModInt &a) const { return x == a.x; } bool operator != (const ModInt &a) const { return x != a.x; } void operator += (const ModInt &a) { x += a.x; if (x >= mod) x -= mod; } void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += mod; } void operator *= (const ModInt &a) { x = 1LL * x * a.x % mod; } void operator /= (const ModInt &a) { *this = *this / a; } friend ModInt operator + (int y, const ModInt &a){ int x0 = y + a.x; return ModInt(x0 < mod ? x0 : x0 - mod); } friend ModInt operator - (int y, const ModInt &a){ int x0 = y - a.x; return ModInt(x0 < 0 ? x0 + mod : x0); } friend ModInt operator * (int y, const ModInt &a){ return ModInt(1LL * y * a.x % mod); } friend ModInt operator / (int y, const ModInt &a){ return ModInt(y) / a; } friend ostream &operator<<(ostream &os, const ModInt &a) { return os << a.x; } friend istream &operator>>(istream &is, ModInt &t){ return is >> t.x; } ModInt pow(long long n) const { ModInt res(1), mul(x); while(n){ if (n & 1) res *= mul; mul *= mul; n >>= 1; } return res; } ModInt inv() const { int a = x, b = mod, u = 1, v = 0; while (b) { int t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } if (u < 0) u += mod; return u; } }; constexpr int mod = 998244353; using mint =ModInt<mod>; void solve(){ int n; cin >> n; vector<int> a(n + 1); for(int i = 1; i <= n; i++) cin >> a[i]; vector dp(4, vector<mint>(n + 1)); for(int i = 1; i <= n; i++){ for(int j = 1; j <= 3; j++)dp[j][i] = dp[j][i - 1]; if(a[i] == 1){ dp[1][i] += 1; }else if(a[i] == 2){ dp[2][i] = dp[2][i] * 2 + dp[1][i]; }else{ dp[3][i] += dp[2][i]; } } cout << dp[3][n] << '\n'; return ; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int t = 1; cin >> t; while(t--)solve(); return 0; } /* 1 2...2 ...3 */

Palindrome Shuffle

首先保证长度为偶数且数据合法, 也就是说每个数都是成对出现

长度为n 一定可以, 然后考虑缩短

  • 如果头和尾相同,那么两边都缩短没关系
  • 如果不同这时候一端肯定要固定住了, 枚举固定左端点还是右端点另一边继续缩短checkcheck 是否可以就行

缩短的时候注意跨对称轴

c++
#include<bits/stdc++.h> #define int long long using namespace std; #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl << endl; } template<class T, class... Ts> void err(T arg, Ts ... args) { cout << fixed << setprecision(10) << arg << ' '; err(args...); } void solve(){ string s; cin >> s; int n = s.size(); s = ' ' + s; vector<int> a(n + 1); for(int i = 1; i <= n; i++){ a[i] = s[i] - 'a'; } int ans = n; int l = 1, r = n; while(l <= r && a[l] == a[r]){ l++; r--; ans -= 2; } vector<int> cnt1(26, 0), cnt2(26, 0); for(int i = l; i <= r; i++){ cnt1[a[i]]++; } int mid = n / 2; for(int i = l; i <= r; i++){ cnt1[a[i]]--; cnt2[a[i]]++; if(i > mid){ if(a[i] == a[mid - (i - mid - 1)]){ cnt2[a[i]] -= 2; } } if(cnt2[a[i]] > cnt1[a[i]])break; ans = min(ans, (r - i)); } for(int i = 0; i < 26; i++){ cnt1[i] = cnt2[i] = 0; } for(int i = l; i <= r; i++){ cnt1[a[i]]++; } for(int i = r; i >= l; i--){ cnt1[a[i]]--; cnt2[a[i]]++; if(i <= mid){ if(a[i] == a[mid + (mid - i + 1)]){ cnt2[a[i]] -=2; } } if(cnt2[a[i]] > cnt1[a[i]])break; ans = min(ans, (i - l)); } cout << ans << '\n'; return ; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int t = 1; cin >> t; while(t--)solve(); return 0; } /* 长度为偶数也就是说成对出现 反转子串 那么一开始是 1 - n 如何1和n能对上 不需要管 不能对上则至少保留一边 枚举保留那一边? 跨界可以调整中间对称 */

Remove the Ends

正保留右边, 负保留左边

所以最终的操作序列一定是正.....正负负.....负

做个前后缀和, 然后枚举分界点即可

c++
#include<bits/stdc++.h> #define int long long using namespace std; #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl << endl; } template<class T, class... Ts> void err(T arg, Ts ... args) { cout << fixed << setprecision(10) << arg << ' '; err(args...); } void solve(){ int n; cin >> n; vector<int> a(n + 1); for(int i = 1; i <= n; i++) cin >> a[i]; vector<int> b(n + 1); for(int i = 1; i <= n; i++){ if(a[i] < 0)b[i] = 0; else b[i] = 1; } vector pre(2, vector<int>(n + 1)); for(int i = 1; i <= n; i++){ for(int j = 0; j <= 1; j++){ pre[j][i] += pre[j][i - 1]; } pre[b[i]][i] += abs(a[i]); } int ans = 0; // dbg(ans); ans = pre[0][n]; for(int i = 1; i <= n; i++){ int res = pre[1][i] + pre[0][n] - pre[0][i]; ans = max(ans, res); } cout << ans << '\n'; return ; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int t = 1; cin >> t; while(t--)solve(); return 0; } /* 正保留右边 负保留左边 正正....负负 */

Eating

从右往左吃, 每次价值变成异或, 只有大于等于才能吃

注意到xx的最高位只会从11 变成 00 也就是说只会变loglog

那么考虑每次位置变化应该是吃一段区间,这段区间数的最高位11小于xx的最高位11 因此二分即可

c++
#include<bits/stdc++.h> #define int long long using namespace std; #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl << endl; } template<class T, class... Ts> void err(T arg, Ts ... args) { cout << fixed << setprecision(10) << arg << ' '; err(args...); } template<class T, class Cmp = std::less<T>> struct ST{ int n, k; const Cmp cmp = Cmp(); vector<vector<T>> st; ST(){} ST(const vector<T> &a){ init(a); } void init(const vector<T> &a){ n = a.size() - 1; k = __lg(n); st.resize(k + 1, vector<T>(n + 1)); for(int i = 1; i <= n; i++){ st[0][i] = a[i]; } for(int s = 1; s <= k; s++){ for(int i = 1; i + (1 << s) <= n + 1; i++){ st[s][i] = min(st[s - 1][i], st[s - 1][i + (1 << (s - 1))], cmp); } } } T get(int l, int r){ int d = __lg(r - l + 1); return min(st[d][l], st[d][r - (1 << d) + 1], cmp); } }; void solve(){ int n, q; cin >> n >> q; vector<int> a(n + 1); for(int i = 1; i <= n; i++) cin >> a[i]; vector<int> p(n + 5); for(int i = 1; i <= n; i++){ p[i] = p[i - 1] ^ a[i]; } p[n + 1] = p[n]; vector<int> b(n + 1); for(int i = 1; i <= n; i++){ for(int j = 29; j >= 0; j--){ if(a[i] >> j & 1){ b[i] = j; break; } } } ST<int, greater<int>> st(b); for(int i = 1; i <= q; i++){ int x; cin >> x; int now = n; for(int j = 29; j >= 0; j--){ if(now == 0 || x < a[now])break; if(x >> j & 1){ int l = 1, r = now; int res = now + 1; while(l <= r){ int mid = (l + r) >> 1; if(st.get(mid, r) < j){ res = mid; r = mid - 1; }else l = mid + 1; } x ^= (p[now] ^ p[res - 1]); now = res - 1; if(now == 0)break; if(x >= a[now]){ x ^= a[now]; now--; } } } cout << n - now << ' '; } cout << '\n'; return ; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int t = 1; cin >> t; while(t--)solve(); return 0; } /* 往左吃,值变异或 先看最高位的1 */

Devyatkino

只考虑这位的话, 可以发现把这位变成77 操作不会超过2020

所以考虑把一个数字连续操作2020 次取出现77的最少次数

c++
#include<bits/stdc++.h> #define int long long using namespace std; #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl << endl; } template<class T, class... Ts> void err(T arg, Ts ... args) { cout << fixed << setprecision(10) << arg << ' '; err(args...); } void solve(){ int n; cin >> n; int t = n; int ans = 20; auto check = [&]() -> bool{ string res = to_string(n); return res.find('7') != -1; }; if(check())ans = 0; int p = 9; for(int i = 1; i <= 10; i++){ n = t; for(int j = 1; j <= 20; j++){ n += p; if(check())ans = min(ans, j); } p = p * 10 + 9; } cout << ans << '\n'; return ; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int t = 1; cin >> t; while(t--)solve(); return 0; } /* 20 次以内 */

Object Identification

A说明是一个有一个环的有向图

B就是容易两点可达

观察样例

? 1 5 ? 5 1

发现只需问两次相反的询问

如果是B模型,那么两次询问的结果应该是一样,如果是A模型可能要绕环或者不可达

先考虑不可达

  • 如果一个点没有任何出边,那么他到不了其他点, 也就是说AA模型会返回一个00, 而BB模型一定会返回大于00的数

考虑绕环

  • 说明其他点都有出边
  • 但是一个环长最多只有n1n-1 那么我们考虑问 xi=1,xj=nx_i = 1, x_j = n这样BB的返回结果一定 大于等于 n1n-1 且两个数相等, 而AA 模型是不可能的
c++
#include<bits/stdc++.h> #define int long long using namespace std; #define dbg(x...) \ do { \ cout << #x << " -> "; \ err(x); \ } while (0) void err() { cout << endl << endl; } template<class T, class... Ts> void err(T arg, Ts ... args) { cout << fixed << setprecision(10) << arg << ' '; err(args...); } void solve(){ int n; cin >> n; vector<int> a(n + 1); for(int i = 1; i <= n; i++) cin >> a[i]; vector<int> cnt(n + 1); for(int i = 1; i <= n; i++){ cnt[a[i]]++; } int x = -1, y = -1; for(int i = 1; i <= n; i++){ if(cnt[i] == 0) x = i; else y = i; } auto query = [&](int x, int y) -> int{ cout << "? " << x << ' ' << y << endl; int dis; cin >> dis; return dis; }; if(x != -1){ int dis1 = query(x, y); int dis2 = query(y, x); if(dis1 && dis2){ cout << "! B" << endl; }else{ cout << "! A" << endl; } }else{ for(int i = 1; i <= n; i++){ if(a[i] == 1)x = i; if(a[i] == n)y = i; } int dis1 = query(x, y); int dis2 = query(y, x); if(dis1 >= n - 1 && dis2 >= n - 1 && dis1 == dis2){ cout << "! B" << endl; }else{ cout << "! A" << endl; } } return ; } signed main(){ ios::sync_with_stdio(false); cin.tie(0); int t = 1; cin >> t; while(t--)solve(); return 0; } /* A 带环图 B 两个点可以达 x,y != y,x 那么肯定是A 两个不是排列 */