T1 自然数

手玩数据可以知道，对于 \(012、01、0\) 这样的每次删去后面数的序列的 \(\text{mex}\) 值是单调不降的。并且每次删去前面一个数 \(val\) 的时候，产生影响的区间只是那些只有一个 \(val\) 的序列，影响是如果该区间的 \(\text{mex}>val\) 那么就把它设置为 \(val\)。

so，先 \(\mathcal{O}(n)\) 维护出原始序列每次删后面的一个数的 mex，作为线段树 \(n\) 个节点的值。再预处理出每个 \(val\) 再序列中的位置 \(pos1,pos2,\dots\)，那么修改的区间就是 \(pos1\sim pos2-1\) 和 序列里第一个 \(\text{mex} >= val\) 的位置取交集。

需要维护区间最大值，区间和，区间修改。

#include<bits/stdc++.h>
using namespace std;
#define int long long
constexpr int N = 2e5 + 5;
int n, a[N], b[N], pos[N], mx, bas[N], ans, s, cnt[N];
stack<int> P[N];
namespace ST{
	#define ls (id << 1)
	#define rs (id << 1 | 1)
	struct node{ int l, r, sum, mx, tag; }t[N<<2];
	inline void pushup(int id){
		t[id].mx = max(t[ls].mx, t[rs].mx);
		t[id].sum  = t[ls].sum + t[rs].sum;
	}
	inline void addtag(int id, int val){
		t[id].sum = val * (t[id].r - t[id].l + 1);
		t[id].mx = t[id].tag = val;
	}
	inline void pushdown(int id){
		if(t[id].tag != -1) addtag(ls, t[id].tag), addtag(rs, t[id].tag);
		t[id].tag = -1;
	}
	inline void build(int id, int l, int r){
		t[id].l = l, t[id].r = r, t[id].tag = -1;
		if(l == r) return (void)(t[id].mx = t[id].sum = bas[l]);
		int mid = (l + r) >> 1;
		build(ls, l, mid), build(rs, mid+1, r);
		pushup(id);
	}
	inline void modify(int id, int l, int r, int val){
		if(l > r) return;
		if(l <= t[id].l && t[id].r <= r) return addtag(id, val);
		pushdown(id); int mid = (t[id].l + t[id].r) >> 1;
		if(l <= mid) modify(ls, l, r, val);
		if(r >  mid) modify(rs, l, r, val);
		pushup(id);
	}
	inline int find(int id, int val){
		if(t[id].l == t[id].r) return t[id].l;
		pushdown(id);
		if(t[ls].mx >= val) return find(ls, val);
		else return find(rs, val); 
	}
}
signed main(){
	freopen("mex.in", "r", stdin), freopen("mex.out", "w", stdout);
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n; for(int i=1; i<=n; ++i) cin>>a[i], b[i] = a[i];
	sort(b+1, b+1+n);
	int len = unique(b+1, b+1+n) - b - 1;
	for(int i=0; i<=len; ++i) if(b[i+1] != i){
		bas[n] = i; break;
	}
	for(int i=1; i<=n; ++i) P[i].push(n+1);
	for(int i=n; i>=1; --i){
		pos[i] = lower_bound(b+1, b+1+len, a[i]) - b;
		++cnt[pos[i]]; P[pos[i]].push(i);
	}
	for(int j=n-1; j>=1; --j){
		bas[j] = bas[j+1]; --cnt[pos[j+1]];
		if(b[pos[j+1]] < bas[j] && !cnt[pos[j+1]]) bas[j] = b[pos[j+1]];
	}
	ST::build(1, 1, n+1); ans += ST::t[1].sum;
	for(int i=1; i<=n; ++i){
		ST::modify(1, i, i, 0);
		int l = ST::find(1, a[i]), r = P[pos[i]].top();
		P[pos[i]].pop(); int r2 = P[pos[i]].top() - 1;
		ST::modify(1, max({l, r, i}), r2, a[i]);
		ans += ST::t[1].sum;
	} return cout<<ans, 0;
}

T2 钱仓

每 mol 钱只能运一次，可以知道是贪心了。由题目可知，在这个环里一定存在某一个断点，使得这个断点之前的钱运不到断点处。也就是从断点之后开始枚举转移可以铺满所有位置，这个断点不唯一，找到一个即可。考虑每个点的钱往哪里运，肯定是往距离自己最小的地方（包括自己）运。那就把每个点加到队列里去，先进队列的先运出去即可。复杂度 \(\mathcal{O}(n)\)

#include<bits/stdc++.h>
using namespace std;
constexpr int B = 1 << 23;
char buf[B], *p1 = buf, *p2 = buf, obuf[B], *O = obuf;
#define gt() (p1==p2 && (p2=(p1=buf) + fread(buf, 1, B, stdin), p1==p2) ? EOF : *p1++)
template <typename T> inline void rd(T &x){
	x = 0; int f = 0; char ch = gt();
	for(; !isdigit(ch); ch = gt()) f ^= ch == '-';
	for(; isdigit(ch); ch = gt()) x = (x<<1) + (x<<3) + (ch^48);
	x = f ? -x : x;
}
#define pt(ch) (O-obuf==B && (fwrite(obuf, 1, B, stdout), O=obuf), *O++ = (ch))
template <typename T> inline void wt(T x){
	if(x < 0) pt('-'), x = -x;
	if(x >= 10) wt(x / 10); pt(x % 10 ^ 48);
}
#define fw fwrite(obuf, 1, O - obuf, stdout)
#define int long long
constexpr int N = 2e5 + 5;
int n, c[N], sum, bg, pos = 1, mx, ans;
queue<int> q;
signed main(){
	freopen("barn.in", "r", stdin), freopen("barn.out", "w", stdout);
	rd(n); for(int i=1; i<=n; ++i) rd(c[i]), c[i+n] = c[i];
	for(int i=1; i<=n; ++i){
		sum += c[i] - 1;
		if(sum < mx) mx = sum, bg = i+1;
	}
	for(int i=bg; i<=bg+n-1; ++i){
		while(c[i]--) q.push(i);
		int top = q.front(); q.pop();
		ans += (i - top) * (i - top);
	} return cout<<ans, 0;
}

T3 游戏

solution 1

对于 \(n = 1\)。

100 pts

令 \(A_{n}\) 表示 Alice 先手取胜的概率， \(B_n\) 表示 Alice 后手取胜的概率。

• 对于 \(A_{n-1}\le B_{n-1}\) 的情况，显然两人都取正面最优，所以有：

  \[\left\{\begin{matrix} A_n=pB_{n-1}+(1-p)B_n \\ B_n=qA_{n-1}+(1-q)A_n \end{matrix}\right. \]

  化简得：

  \[\left\{\begin{matrix} A_n=\cfrac{q(1-p)A_{n-1}+pB_{n-1}}{p+q-pq} \\ B_n=\cfrac{qA_{n-1}+p(1-q)B_{n-1}}{p+q-pq} \end{matrix}\right. \]

  可以得到转矩阵：

  \[P = \begin{bmatrix} \cfrac{q(1-p)}{p+q-pq} & \cfrac{q}{p+q-pq}\\ \cfrac{p}{p+q-pq} & \cfrac{p(1-q)}{p+q-pq} \end{bmatrix} \]

  将 \(A_n - B_n\) 得：

  \[\cfrac{pq(B_{n-1}-A_{n-1})}{p+q-pq} \ge0 \]

  所以这种情况下他俩的大小关系会交换。

• 对于 \(A_{n-1}\ge B_{n-1}\) 的情况：

  \[\left\{\begin{matrix} A=(1-p)B_{n-1}+pB_n \\ B=(1-q)A_{n-1}+qA_n \end{matrix}\right. \]

  化简得：

  \[\left\{\begin{matrix} A_n=\cfrac{p(1-q)A_{n-1}+(1-p)B_{n-1}}{1-pq} \\ B_n=\cfrac{(1-q)A_{n-1}+q(1-p)B_{n-1}}{1-pq} \end{matrix}\right. \]

  可以得到转移矩阵：

  \[Q = \begin{bmatrix} \cfrac{p(1-q)}{1-pq} & \cfrac{1-q}{1-pq}\\ \cfrac{1-p}{1-pq} & \cfrac{q(1-p)}{1-pq} \end{bmatrix} \]

  将 \(A_n - B_n\) 得：

  \[\cfrac{(1-p)(1-q)(B_{n-1}-A_{n-1})}{1-pq} \le 0 \]

  所以这种情况下两者关系也会互换。

所以每进行一次递推，大小关系会互换。具体地，当前递推奇数次的时候，最后一次为情况1， 反之为情况2。根据矩阵乘法的结合律，使用矩阵快速幂即可，复杂度 \(\mathcal{O}(8t\log n)\)。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
constexpr int M = 1e9 + 7, Inv = 571428574;
struct Mate{ int m[2][2]; }P, Q, bas;
Mate operator * (const Mate &a, const Mate &b){
	Mate c;	memset(c.m, 0, sizeof(c.m));
	for(int i=0; i<2; ++i) for(int j=0; j<2; ++j) for(int k=0; k<2; ++k)
		c.m[i][j] = ((ll)a.m[i][k] * b.m[k][j] % M + c.m[i][j]) % M;
	return c;
}
Mate qpow(Mate a, int k){
	Mate ans = a; --k;
	while(k){
		if(k & 1) ans = ans * a;
		a = a * a; k >>= 1;
	} return ans;
}
int qpow(int a, int k){
	int ans = 1;
	while(k){
		if(k & 1) ans = (ll)ans * a % M;
		a = (ll)a * a % M; k >>= 1;
	} return ans;
}
int t, n, p, q;
int main(){
	freopen("game.in", "r", stdin), freopen("game.out", "w", stdout);
	ios::sync_with_stdio(0), cout.tie(0), cout.tie(0);
	cin>>t; while(t--){
		cin>>n>>p>>q;
		p = (ll)p * Inv % M, q = (ll)q * Inv % M;
		int fp = ((1 - p) % M + M) % M, fq = ((1 - q) % M + M) % M;
		int inv = (((ll)p + (ll)q - (ll)p * q % M) % M + M) % M;
		int finv = ((1ll - (ll)p * q % M) % M + M) % M;
		inv = qpow(inv, M - 2); finv = qpow(finv, M - 2);
		P.m[0][0] = (ll)q * fp % M * inv % M; P.m[0][1] = (ll)q * inv % M;
		P.m[1][0] = (ll)p * inv % M; P.m[1][1] = (ll)p * fq % M * inv % M;
		Q.m[0][0] = (ll)p * fq % M * finv % M; Q.m[0][1] = (ll)fq * finv % M;
		Q.m[1][0] = (ll)fp * finv % M; Q.m[1][1] = (ll)q * fp % M * finv % M;
		bas.m[0][0] = 0, bas.m[0][1] = 1; 
		if(n>>1) bas = bas * qpow(P*Q, n>>1);
		if(n & 1) bas = bas * P;
		cout<<bas.m[0][0]<<'\n';
	} return 0;
}

T4 暴雨

改不出来了~ 咕