要求严格小于和严格大于,且数字范围是 因此结果只能是1 2....2 3
那么直接 即可 前 个以 结尾的方案数
首先当前数不加入
如果当前数是 那么
如果当前数是 那么
如果当前数是 那么
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
*/
首先保证长度为偶数且数据合法, 也就是说每个数都是成对出现
长度为n 一定可以, 然后考虑缩短
缩短的时候注意跨对称轴
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能对上 不需要管
不能对上则至少保留一边
枚举保留那一边?
跨界可以调整中间对称
*/
正保留右边, 负保留左边
所以最终的操作序列一定是正.....正负负.....负
做个前后缀和, 然后枚举分界点即可
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;
}
/*
正保留右边
负保留左边
正正....负负
*/
从右往左吃, 每次价值变成异或, 只有大于等于才能吃
注意到的最高位只会从 变成 也就是说只会变次
那么考虑每次位置变化应该是吃一段区间,这段区间数的最高位小于的最高位 因此二分即可
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
*/
只考虑这位的话, 可以发现把这位变成 操作不会超过 次
所以考虑把一个数字连续操作 次取出现的最少次数
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 次以内
*/
A说明是一个有一个环的有向图
B就是容易两点可达
观察样例
? 1 5 ? 5 1
发现只需问两次相反的询问
如果是B模型,那么两次询问的结果应该是一样,如果是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
两个不是排列
*/