首页 > 其他分享 >2023.8.12

2023.8.12

时间:2023-08-12 16:13:38浏览次数:44  
标签:10 le int ch read 12 2023.8 define

lgj 放水场。

job

在 \(T\) 个单位时间内,每个单位时间 \(t\) 可以选择一个未选过的 \(i\) 且满足 \(b_i\ge t\),获得 \(a_i\) 的贡献。

求最大贡献。

\(n\le 2\times 10^6\),\(a_i,b_i\le T\le 10^9\).

考虑把 \(a\) 大的 \(i\) 放到前面,开一个 set,弄出来可行的最后一个单位时间,令这个单位时间选择 \(i\) 即可。

时间复杂度 \(O(n\log n)\).

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define ll long long
#define N 2000010
#define sit set<int>::iterator
using namespace std;
int read(){
	int x=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*w;
}
int T,n,m;
struct data{
	int a,b;
	bool operator<(const data &x)const{
		return a==x.a?b>x.b:a>x.a;
	}
}t[N];
set<int>s;
ll ans;
int main(){
	T=read(),n=read();
	for(int i=1,a,b;i<=n;i++){
		b=read(),a=read();
		if(b>n)ans+=a;
		else t[++m]=(data){a,b};
	}
	for(int i=1;i<=n;i++)
		s.insert(i);
	sort(t+1,t+1+m);
	for(int i=1;i<=m;i++){
		sit it=s.upper_bound(t[i].b);
		if(it==s.begin())continue;
		--it,ans+=t[i].a,s.erase(*it);
	}
	printf("%lld\n",ans);
	
	return 0;
}

shop

有 \(n\) 种货币 \(\{v_n\}\)(可以重复),你手上分别有 \(\{c_n\}\) 张,购买价值为 \(M\) 的货物,店主的货币是无限的。

试最小化给钱和找钱的总货币数,输出这个值。

\(n\le 200\),\(M\le 10^5\),\(v_i\le 200\),\(c_i\le 20000\).

考虑 \(f_{i,j}\) 表示考虑了前 \(i\) 种货币凑出 \(j\) 的最小张数。

答案即 \(\min_{k}f_{n,k}+f_{n,k-M}\).

后者应该是完全背包但是我不知道为什么用这个多重背包数组过了。

时间复杂度 \(O(nM\log C)\).

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define N 205
#define L 17
#define R 200010
#define inf 0x3f3f3f3f
using namespace std;
int read(){
	int x=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*w;
}
int n,M,tot;
int _v[N],_c[N];
int f[2][R],o;
struct data{
	int v,c;
}a[N*L];
int main(){
	n=read(),M=read();
	for(int i=1;i<=n;i++)_v[i]=read();
	for(int i=1;i<=n;i++)_c[i]=read();
	for(int i=1,v,c;i<=n;i++){
		v=_v[i],c=_c[i];
		for(int j=1;c;j<<=1){
			if(c>=j)a[++tot]=(data){v*j,j},c-=j;
			else a[++tot]=(data){v*c,c},c=0;
		}
	}
	memset(f,0x3f,sizeof(f)),f[o][0]=0;
	for(int i=1;i<=tot;i++){
		o^=1;
		for(int j=0;j<min(M*2,a[i].v);j++)f[o][j]=f[o^1][j];
		for(int j=a[i].v;j<M*2;j++)
			f[o][j]=min(f[o^1][j],f[o^1][j-a[i].v]+a[i].c);
	}
	int ans=inf;
	for(int i=M;i<M*2;i++)
		ans=min(ans,f[o][i]+f[o][i-M]);
	if(ans==inf)puts("-1");
	else printf("%d\n",ans);
	
	return 0;
}

magic

P5522 [yLOI2019] 棠梨煎雪

\(m\) 个长 \(n\) 的串,分别有 \(0,1\) 和通配符 \(?\),支持:

  • 询问 \([l,r]\) 的串有多少种变为同一个串的方式。

  • 修改一个串。

\(m\le 10^5+7\),\(q\le 10^6+7\),\(n\le 30\),输入字符串的总长度不超过 \(5\times 10^6\).

令 \(0\rightarrow01\),\(1\rightarrow10\),\(?\rightarrow11\).

把它们放进 bitset 里且起来即可。

时间复杂度 \(O(q\frac{n}{\omega}\log m)\).

#include<bits/stdc++.h>
#pragma GCC optimize(3,"Ofast","inline")
#define N 100010
#define M 30
#define bs bitset<M<<1>
using namespace std;
int read(){
	int x=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	return x*w;
}
int gets(){
	char ch=getchar();
	while(ch!='0'&&ch!='1'&&ch!='?')ch=getchar();
	return ch=='0'?0:(ch=='1'?1:2);
}
bs b[N],t[N<<2];
#define ls p<<1
#define rs p<<1|1
void update(int p){
	t[p]=t[ls]&t[rs];
}
void build(int p,int l,int r){
	if(l==r){
		t[p]=b[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	update(p);
}
bs mdf,res;
void modify(int p,int x,int l,int r){
	if(l==r){
		t[p]=mdf;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid)modify(ls,x,l,mid);
	else modify(rs,x,mid+1,r);
	update(p);
}
bs query(int p,int L,int R,int l,int r){
	if(L<=l&&R>=r)return t[p];
	int mid=(l+r)>>1;
	if(R<=mid)return query(ls,L,R,l,mid);
	if(L>mid)return query(rs,L,R,mid+1,r);
	return query(ls,L,R,l,mid)&query(rs,L,R,mid+1,r);
}
int n,m,q;
int ans;
int main(){
	m=read(),n=read(),q=read();
	for(int i=1;i<=n;i++)
		for(int j=0,opt;j<m;j++){
			opt=gets();
			if(opt!=1)b[i].set(j*2);
			if(opt)b[i].set(j*2+1);
		}
	build(1,1,n);
	for(int opt,l,r,x,cnt;q;q--){
		opt=read();
		if(!opt){
			l=read(),r=read();
			res=query(1,l,r,1,n),cnt=0;
			for(int i=0;i<m;i++){
				if(!res[i*2]&&!res[i*2+1]){cnt=-1;break;}
				cnt+=(res[i*2]&&res[i*2+1]);
			}
			if(cnt!=-1)ans^=(1<<cnt);
		}
		else{
			x=read();
			for(int j=0,opt;j<m;j++){
				mdf.reset(j*2),mdf.reset(j*2+1),opt=gets();
				if(opt!=1)mdf.set(j*2);
				if(opt)mdf.set(j*2+1);
			}
			modify(1,x,1,n);
		}
	}
	printf("%d\n",ans);
	
	return 0;
}

peace

在树上选出 \(m\) 条长度不超过 \(k\) 的链 \((x,y),x\le y\),且两条链在端点处不交,树上任意点都不被 \(m\) 条链同时覆盖。

求总方案数对 \(998244353\) 取模的值。

用所有的方案减去不合法的方案,合法的就是长度 \(\le k\) 的路径条数的 \(m\) 次方。

四档极限分:

  1. \(n\le 10^6\),\(m\le 10^3\),\(k=0\).

  2. \(n\le 10^6\),\(m\le 10^3\),\(k=n-1\).

  3. \(n\le 10^6\),\(m\le 10^3\),\(k\le n\),树为一条链。

  4. \(n\le 10^3\),\(m\le 10^9\),\(k\le n\).

不合法的方案路径一定有交,枚举深度最浅的交点。

Part1

记 \(f(p)\) 为经过 \(p\) 且路径两端都在 \(p\) 子树内的长度不超过 \(k\) 的方案数,\(g(p)\) 为经过 \(p\) 且路径两端分别在 \(p\) 子树内外,长度不超过 \(k\) 的方案数。

以 \(p\) 为深度最浅的节点的不合法方案数为

\[\sum_{i=0}^{m-1}\binom{m}{i}g(p)^if(p)^{m-i} \]

即选出 \(i\) 个放到外面,且不能只放 \(m\) 在外面,否则最浅的交点非 \(p\).

时间复杂度 \(O(nm)\).

Part2

想一下怎么计算 \(f\) 和 \(g\).

  • \(O(n^2)\) 方法

对于 \(q\in\operatorname{son}(p)\),递归 \(q\) 的子树,用前缀桶里的信息更新答案,再把新数据扔进桶里,容易计算 \(f\).

计算 \(g(p)\),把子树 \(p\) 以外的看成 \(p\) 的另一颗子树,用类似的方法计算。

  • \(k=0\)

链长为 \(0\),\(f(p)=1\),\(g(p)=0\).

时间复杂度 \(O(n)\).

  • \(k=n-1\)

链可以走遍每个点对,设 \(\displaystyle h(x)=\binom{x}{2}+x\),即在 \(x\) 个点中选出 \(2\) 个点满足终点不小于起点的方案数。

\[f(p)=h(\operatorname{siz}(p))-\sum_{q\in\operatorname{son}(p)}h(\operatorname{siz}(q)) \]

\[g(p)=\operatorname{siz}(p)(n-\operatorname{siz}(p)) \]

时间复杂度 \(O(n)\).

  • 树为一条链

\(f(p)\) 等价与直接向后扩展,和 \(k+1\) 取 \(\min\).

\(g(p)\) 就是前面能扩展的向后扩展,对 \(f(p)\) 作前缀和,再减掉到达不了的 \(f(p)\).

Part3

但是 \(O(nm)\) 的复杂度不支持通过前三档极限分。

再看眼那个求和式

\[\sum_{i=0}^{m-1}\binom{m}{i}g(p)^if(p)^{m-i} \]

这个就是二项式定理的形式,即

\[\sum_{i=0}^{m}\binom{m}{i}g(p)^if(p)^{m-i}-g(p)^m \]

\[=(f(p)+g(p))^m-g(p)^m \]

时间复杂度 \(O(n\log m)\).

最后的答案其实是可以容斥出来的。

code

没标程慢慢写。

标签:10,le,int,ch,read,12,2023.8,define
From: https://www.cnblogs.com/SError0819/p/17624941.html

相关文章

  • 2023.8.12测试
    \[\text{暑假NOIP模拟赛-6}\]终于没挂分了T1打工有\(n\)个工作,做一个工作要消耗一个时间单位,可以获得价值\(a_i\),截止日期\(b_i\),求\(T\)单位时间内最多获得多少价值\(1\leqn\leq10^6\),\(1\leqa_i,b_i\leqT\leq10^9\)先按照时间从小到大排序,然后倒序枚举,将两个时......
  • LGJOI20230812
    LGJ水场。这场总体题比较简单,所以分比较高。A有\(n\)项工作,完成一项工作需要\(1\)单位时间。每项工作有个截止时间\(t\)和报酬\(v\),需要在第\(t\)单位时间前完成工作才能得到\(v\)的报酬。给定\(T\),求\(T\)时间后获得报酬的最大值。solution:简单贪心。将工作......
  • Gitc错误Failed to connect to 127.0.0.1 port 1080 Connection refused拒绝连接错误
    一、git拒绝连接原因分析使用git从远程仓库下载代码出现上述的错误是因为使用了proxy代理,所以要解决该问题,核心操作就是要取消代理二、解决方式1、查看Linux当前有没有使用代理通过git的配置文件查看有无使用代理(没有成功)查询是否使用代理:gitconfig--globalhttp.proxyg......
  • 2023-08-12 记录一则随机密码生成脚本
    <!DOCTYPEhtml><htmllang="en"><head><metacharset="UTF-8"><metahttp-equiv="X-UA-Compatible"content="IE=edge"><metaname="viewport"content="width=......
  • 【230812-1】指数比较大小:16^18 vs 18^16
    ......
  • 【230812-2】指数比较大小:13^17 vs 17^13
    ......
  • 学习平板如何访问外网(2023.8.12)
    嗨!今天我教大家学习平板如何访问外网(这篇文章就是我用学习平板访问外网写的)首先,你要确保你的平板里安装了快对(原快对作业),然后打开它。在“我的”页面中往下滑找到设置,在设置往下滑中找到“第三方信息共享清单”,点进去,点击第一个腾讯的SDK下面的网站,再点击进去,点击右上角的腾讯云......
  • 2023.8.7-2023.8.14暑假第五周博客
    2023.8.7今天人在外,因此博客休息一天图片如下 2023.8.8今天对hive有了进一步的了解首先要明确一个流程当我打开三台虚拟机,用finalshell连接上后首先要使用如下命令1.su-hadoop切换到hadoop用户,大部分操作都必须在hadoop用户中完成,而千万不要再root中,因为root用户一......
  • 2023.8.11
    今天早上起来,还是和往常一样打球,还有几天就离开了,只能假期回来再和兄弟们一起玩了,下午回家有些无聊了,问兄弟们还来不来,他们答应我出来打几个小时,太好了,终于不用在家里待着了,下午打到56点钟就回家了,爸妈还没回来,赶紧把饭蒸好,舒服了,晚上有些累了,躺着突然就睡着了,半夜起来写下这些,明......
  • Linux 发行版 Debian 12.1 发布
    在今年6月初,Debian12“bookworm”发布,而日前Debian迎来了12.1版本,主要修复系统用户创建等多个安全问题。Debian是最古老的GNU/ Linux 发行版之一,也是许多其他基于Linux的操作系统的基础,包括Ubuntu、Kali、MX和树莓派OS等。这个操作系统以稳定性为重,不追......