觉得模拟赛题解还是单独放出来比较好。
A.挤压
好像不难？二进制表示下的平方展开没推出来，不然就成简单题了。
首先我们需要知道对于一个数 \(x\)，把它拆成 29 位的二进制形式后，用 \(s_i\) 表示二进制下第 \(i\) 位上的数，那么其实这个数就是 \((\overline{s_{29} s_{28}...s_1 s_0})_2\)，那么有
\[\begin{aligned} (\overline{s_{29} s_{28}...s_1 s_0})^2&=(\sum_{i=0}^{29} s_i\times 2^i)^2 \\ &=\sum_{i,j\in [0,29]} 2^{i+j} (if\ s_i=1\ and\ s_j=1)\end{aligned}\]那么可以知道只有二进制下两位数同时为 1 时才会对答案有贡献，这样我们就可以枚举二进制下的两位 \(i,j\)，在此基础上循环整个序列设 \(f_{k,0/1,0/1}\) 表示前 \(k\) 个数的第 \(i,j\) 位选了奇/偶个的概率，最后计算上 \(f_{n,1,1}\) 对答案的贡献即可。
注意第 \(k\) 个数选或不选的转移有以下几种情况：
-
二进制下的这个数第 \(i,j\) 位都不为 1，那么显然它对答案，直接继承就行；
-
第 \(i\) 位为 1 而 第 \(j\) 位不为 1，那么若选这个数，则只有第 \(i\) 位的奇偶发生变化；反之同理；
-
\(i,j\) 位都为 1，选这个数时，\(i,j\) 两位上的奇偶都发生变化，以此为例：
对于每一组 \(i,j\)，初始化 \(f_{0,0,0}=0\) 即可。
B.工地难题
前缀和优化：设 \(f_i\) 表示最长连续 1 的个数 \(num\le i\) 的方案数，显然对于最长连续 1 的个数恰好等于 \(i\) 的答案就是 \(f_i-f_{i-1}\)。
现在我们考虑如何求 \(f_i\)。我们可以将题目理解为插板的形式：放好了 \(n-m\) 个 0，那么现在有 \(n-m+1\) 个位置可以插入 1，每个位置上都可以放 \([0,m]\) 个 1，问方案数。
设 \(x_j\) 表示第 \(j\) 个位置放了几个 1，那么求 \(f_i\) 其实就是求 \(\sum_{j=1}^{n-m+1} x_j=m\) 的非负整数解的个数。简单容斥一下就好了。
C.星空遗迹
求调！！！
T3 求调，**12：00 之前调成功悬一袋红烧牛肉面 **
#include<bits/stdc++.h>
#define Type int
#define qr(x) x=read()
typedef long long ll;
using namespace std;
inline Type read(){
char c=getchar(); Type x=0;
while(!isdigit(c))c=getchar();
while(isdigit(c))x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x;
}
const int N = 2e5 + 10;
const int mod = 1e9 + 7;
int n, q, f[N];
char s[N];
int P(char A, char B){
if(A == '#' or B == '@') return 1;
if(A == B) return 0;
if(A == 'R'){
if(B == 'S') return 1;
else return -1;
}
else if(A == 'S'){
if(B == 'P') return 1;
else return -1;
}
else{
if(B == 'R') return 1;
else return -1;
}
}
struct tree{
int v, pos, tag;
bool operator < (const tree &A) const{
return v < A.v;
}
}t[N<<3];
namespace Tree
{
#define lson rt<<1
#define rson rt<<1|1
inline void pushup(int rt){
if(t[lson].v < t[rson].v) t[rt].v = t[lson].v, t[rt].pos = t[lson].pos;
else t[rt].v = t[rson].v, t[rt].pos = t[rson].pos;
}
inline void pushdown(int rt){
if(t[rt].tag){
t[lson].tag += t[rt].tag, t[rson].tag += t[rt].tag;
t[lson].v += t[rt].tag, t[rson].v += t[rt].tag;
t[rt].tag = 0;
}
}
inline void build(int rt, int l, int r){
if(l == r){
t[rt].v = f[l], t[rt].pos = l;
return;
}
int mid = (l + r) >> 1;
build(lson, l, mid),
build(rson, mid+1, r);
pushup(rt);
// if(t[rt].pos == 0) cout<<"CTHisSB\n";
}
inline void update(int rt, int l, int r, int pos, int val){
if(pos <= l and r <= n){
t[rt].tag += val, t[rt].v += val;
return;
}pushdown(rt);
int mid = (l + r) >> 1;
if(pos <= mid) update(lson, l, mid, pos, val);
if(n > mid) update(rson, mid+1, r, pos, val);
pushup(rt);
}
inline tree query(int rt, int l, int r, int L, int R){
if(L <= l and r <= R) return t[rt];
pushdown(rt);
int mid = (l + r) >> 1;
if(R <= mid) return query(lson, l, mid, L, R);
else{
if(L > mid) return query(rson, mid+1, r, L, R);
else return min(query(lson, l, mid, L, R), query(rson, mid+1, r, L, R));
}
}
}
signed main(){
freopen("a.in", "r", stdin), freopen("a.out", "w", stdout);
// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
qr(n), qr(q), cin>>(s+1);
f[1] = 1; s[0] = '#', s[n+1] = '@';
for(int i=2; i<=n; i++)
f[i] = f[i-1] + P(s[i-1], s[i]);
Tree::build(1, 1, n);
while(q--)
{
int qr(op);
switch(op){
case 1:{int qr(p); char c; cin>>c; int now = P(s[p-1], c) - P(s[p-1], s[p]);
Tree::update(1, 1, n, p, now); now = P(c, s[p+1]) - P(s[p], s[p+1]);
Tree::update(1, 1, n, p+1, now); s[p] = c; break; }
default:{int qr(l), qr(r); cout<<s[Tree::query(1, 1, n, l, r).pos]<<"\n"; break;}
}
}
return 0;
}
为了方便判断，我让 s[0]='#'，但交到 oj 上却输出了这个：
显然是返回了 0，但是毫无缘由，代码里注释部分是输出树上所有点的 pos，结果没有为 0 的。