test16
一个困难的问题difficult
首先区间排序是假的，因为可以冒泡排序，这样子可能好考虑一点。
不难发现可以倒序考虑，要贡献的选择后缀中最小未选择的即可，构造的话可以直接从后往前考虑每次最小值的位置一定在上一个贡献位置的前面，那么直接排序拉到要贡献的位置即可。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define pii pair<int,int>
#define mp make_pairusing namespace std;const int N=100005;int T, n, a[N], Ans, tag[N];
char b[N];void mian() {cin >> n, Ans=0;up(i,1,n) cin >> a[i];cin >> (b+1);priority_queue<int> qwq;dn(i,n,1) {qwq.push(-a[i]);if(b[i]=='1') {Ans-=qwq.top();qwq.pop();}}cout << Ans << '\n';
}signed main() {
// freopen("1.txt","r",stdin);freopen("difficult.in","r",stdin);freopen("difficult.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cin >> T;while(T--) mian();return 0;
}
数字游戏number
设 \(f(n,m)\) 表示还有 \(n\) 轮游戏，钦定 \(m\) 个加法的和是多少，对于第一个人 \((n,m)\) 有唯一常数 \(t\)，对于第二个人有 \(f(n,m)=\min\{f(n-1,m)-p,f(n,m-1)+p\}\)，那么显然 \(p=\frac{f(n-1,m-1)+f(n-1,m)}{2}\)。首先 \(\frac{1}{2}\) 的贡献只跟 \(n\) 相关先不考虑，剩下的部分是一个类杨辉三角，画出来做差分直到好看之后组合意义求解即可。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)using namespace std;const int N=3000005, P=1e9+7;int T, n, m, k, mul[N], inv[N];int C(int n,int m) {if(m<0||n<m) return 0;return mul[n]*inv[m]%P*inv[n-m]%P;
}signed main() {
// freopen("1.txt","r",stdin);freopen("number.in","r",stdin);freopen("number.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);mul[0]=inv[0]=inv[1]=1;up(i,1,3e6) mul[i]=mul[i-1]*i%P;up(i,2,3e6) inv[i]=inv[P%i]*(P-P/i)%P;up(i,2,3e6) inv[i]=inv[i-1]*inv[i]%P;cin >> T;while(T--) {cin >> n >> m >> k;int Ans=0;up(i,1,m) (Ans+=C(n,m-i)*i%P)%=P;up(i,2,n) (Ans*=inv[2])%=P;cout << Ans*k%P << '\n';}return 0;
}
子序列seq
矩阵乘法优化 dp，线段树维护修改即可。
#include<bits/stdc++.h>
#define int long long
#define up(i,l,r) for(int i=l; i<=r; ++i)
#define dn(i,r,l) for(int i=r; i>=l; --i)
#define ls(p) (p<<1)
#define rs(p) (p<<1|1)using namespace std;const int N=200005, M=9;int n, len, q;
char str[N], s[M]={0,'a','b','c','c','d','b'};
struct mat {int n, m, d[M][M];void insert(int u,char v) {n=m=8;memset(d,0,sizeof(d));if(v==s[1]) ++d[7][1]; else ++d[7][6];if(v==s[6]) d[5][8]=len-u+1; //cout << "v = " << n << ' ' << u << ' ' << n-u+1 << '\n';up(i,1,5) if(v==s[i+1]) ++d[i][i+1]; else ++d[i][i];if(v==s[1]) ++d[6][1]; else ++d[6][6];++d[7][7], ++d[8][8];}void clear(int nn,int mm) {n=nn, m=mm;memset(d,0,sizeof(d));}
} tr[N<<2], qwq;mat mul(mat a,mat b) {mat c; c.clear(a.n,b.m);up(i,1,a.n) up(j,1,b.m) up(k,1,a.m) {c.d[i][j]+=a.d[i][k]*b.d[k][j];}return c;
}void build(int p=1,int s=1,int e=n) {if(s==e) {tr[p].insert(s,str[s]);return;}int mid=(s+e)>>1;build(ls(p),s,mid), build(rs(p),mid+1,e);tr[p]=mul(tr[ls(p)],tr[rs(p)]);
} void updata(int x,int p=1,int s=1,int e=n) {if(s==e) {tr[p].insert(s,str[s]);return;}int mid=(s+e)>>1;if(x<=mid) updata(x,ls(p),s,mid);if(x>mid) updata(x,rs(p),mid+1,e);tr[p]=mul(tr[ls(p)],tr[rs(p)]);
}int ans() {mat res=mul(qwq,tr[1]);return res.d[1][8]; // 修改
}mat get(int x,int p=1,int s=1,int e=n) {if(s==e) {return tr[p];}int mid=(s+e)>>1;if(x<=mid) return get(x,ls(p),s,mid);return get(x,rs(p),mid+1,e);
}signed main() {freopen("seq.in","r",stdin);freopen("seq.out","w",stdout); ios::sync_with_stdio(0);cin.tie(0);cin >> (str+1), n=len=strlen(str+1);build(); qwq.n=1, qwq.m=8, qwq.d[1][7]=1;mat res=qwq;
// up(i,0,n) {
// cout << "Round " << i << " : ";
// if(i) res=mul(res,get(i));
// up(j,1,8) cout << res.d[1][j] << ' '; cout << '\n';
// } return 0;cout << ans() << '\n';cin >> q;while(q--) {int x; char v;cin >> x >> v;str[x]=v, updata(x);cout << ans() << '\n';}return 0;
}