当前位置: 首页 > news >正文

时时想起 寸步难行 叩问自己 无人回应 若我离去 若我死去 枯萎于这幽暗的井底 长眠不醒

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;
}
http://www.hskmm.com/?act=detail&tid=28921

相关文章:

  • 有限空间作业安全无死角!AI 视觉守护人员与操作合规
  • 2025抖音推广服务商最新推荐榜:精准引流与高效转化的营销利
  • 2025甘肃西服定制店推荐榜单:匠心工艺与贴心服务的完美结合
  • 完整教程:计算机毕业设计免费领源码-教师教学进度管理及建议系统的设计与实现
  • 2025表面瑕疵检测设备厂家最新推荐:精准高效,工业品质之选
  • 战略、运营、经营三循环:企业卓越绩效的密码 - 智慧园区
  • 2025书包柜定做厂家推荐:杰尚家具专业定制,品质卓越!
  • 2025环氧板定制厂家推荐:一博科技材料,专业定制品质卓越!
  • 2025农机带实力厂家推荐:浙江三星胶带,品质卓越供货无忧!
  • 打不动十个
  • CSP-S模拟29 2025.10.11
  • 2025风机盘管优质厂家推荐:洛卡尔环境科技,高效节能首选!
  • 最简单实用的SQL注入检测方法:Break Repair技巧详解
  • 2025拉伸器厂家最新推荐榜:专业制造与优质服务的行业佼佼者
  • 个性化推荐系统技术解析
  • NOIP20251009E
  • 2025七水硫酸锌订做厂家推荐榜:品质保证与客户信赖之选
  • 2025螺杆泵厂家最新推荐榜:高效稳定与优质服务的行业首选!
  • 2025南通婚纱摄影最新推荐榜:创意拍摄与贴心服务的完美结合
  • 语义slam - MKT
  • 尝试茶叶数据集
  • 2025氧化镁供应厂家推荐:松辽镁业高纯度优质选择!
  • 2025硅藻土订制厂家口碑推荐:品质卓越与专业服务的双重保障
  • 20251011
  • 2025数控滚齿机源头厂家推荐榜:高精度与高效能的首选!
  • (第四次)回归与决策树
  • 2025数控滚齿机订做厂家推荐:吉莱特智能装备,精准高效品质
  • 2025机械加工实力厂家推荐:鑫铭机械专业制造,品质卓越首选
  • 高考语文做法
  • 2025机械加工优质厂家推荐榜:技术精湛与高效服务的行业先锋