Beautiful Sequence

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

那么直接$dp$ 即可 $dp_{ij}$ 前$i$ 个以$j$ 结尾的方案数

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

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

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

如果当前数是$3$ 那么$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 一定可以, 然后考虑缩短

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

缩短的时候注意跨对称轴

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

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

注意到$x$的最高位只会从$1$ 变成 $0$ 也就是说只会变$log$次

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

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

只考虑这位的话, 可以发现把这位变成$7$ 操作不会超过$20$ 次

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

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模型可能要绕环或者不可达

先考虑不可达

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

考虑绕环

• 说明其他点都有出边
• 但是一个环长最多只有$n-1$ 那么我们考虑问 $x_i = 1, x_j = n$这样$B$的返回结果一定 大于等于 $n-1$ 且两个数相等, 而$A$ 模型是不可能的

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

两个不是排列 

*/