BZOJ #2700 聚会 & #4269 再见 Xor & #4247 挂饰 & #4576 [Usaco2016 Open]262144 & #2460 [BeiJing2011]元素 & #3039 玉蟾宫 & #4543 [POI2014]Hotel 加强版 & #2396 神奇的矩阵 & #1213 [HNOI2004]高精度开根
|
4,516
|
3
|
OI

2126 字
|
9 分钟

#2700 聚会

Description

Alice 正在组织一次有 $M$ 位同学参加的同学聚会。Alice 有 $N$ 种不同的茶，每种茶有各自的单价和类别（红茶或绿茶）。每隔一单位时间，聚会上都有一个同学离开。Alice 希望安排一种泡茶的方案，每单位时间都给所有剩下的同学们泡同一种之前没有泡过的茶，花费就是此茶的单价乘以剩余的同学数。同时，他不希望连续三次泡的茶都是红茶或都是绿茶。请你找出一种方案，在满足上面的条件下使得总花费最小。如果有多种方案，找出任意一种。保证存在解。

Solution

设 $f[x][y][a][b]$ 表示有 $x$ 杯茶，其中 $y$ 杯事 红 茶，$a(a=0/1)$ 种茶一共连续喝了 $b$ 次。

$$f[i][j][0][1]=min\{f[i-1][j-1][1][1],f[i-1][j-1][1][2]\}+(n-i+1)*a[j] (j>=1)$$ $$f[i][j][0][2]=f[i-1][j-1][0][1]+(n-i+1)*a[j] (j>=2)$$ $$f[i][j][1][1]=min\{f[i-1][j][0][1],f[i-1][j][0][2]\}+(n-i+1)*b[i-j] (i-j>=1)$$ $$f[i][j][1][2]=f[i-1][j][1][1]+(n-i+1)*b[i-j] (i-j>=2)$$

Code

#include<bits/stdc++.h>
using namespace std;
long long n,m,f[1005][1005][2][3],a[1005],b[1005];
int main(){
	cin>>n>>m;
	for (int i=1;i<=m;i++){
		a[i]=b[i]=1145141919810;
	}
	for (int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		if (y==0){
			b[++a[0]]=x;
		}else{
			a[++b[0]]=x;
		}
	}
	sort(a+1,a+1+m);
	sort(b+1,b+1+m);
	memset(f,127,sizeof(f));
	f[0][0][0][1]=0;
	f[0][0][0][1]=0;
	f[0][0][0][2]=0;
	f[0][0][1][1]=0;
	f[0][0][1][2]=0;
	for (int i=1;i<=n;i++){
		for (int j=0;j<=i;j++){
			if (j>=1){
				f[i][j][0][1]=min(f[i-1][j-1][1][1],f[i-1][j-1][1][2])+(n-i+1)*a[j];
			}
			if (j>=2){
				f[i][j][0][2]=f[i-1][j-1][0][1]+(n-i+1)*a[j];
			}
			if (i-j>=1){
				f[i][j][1][1]=min(f[i-1][j][0][1],f[i-1][j][0][2])+(n-i+1)*b[i-j];
			}
			if (i-j>=2){
				f[i][j][1][2]=f[i-1][j][1][1]+(n-i+1)*b[i-j];
			}
		}
	}
	long long ans=1145141919810;
	for (int i=0;i<=n;i++){
		ans=min(ans,min(min(f[n][i][0][1],f[n][i][0][2]),min(f[n][i][1][1],f[n][i][1][2])));
	}
	cout<<ans;
}

#4269 再见

Description

给定 $N$ 个数，你可以在这些数中任意选一些数出来，每个数可以选任意多次，试求出你能选出的数的异或和的最大值和严格次大值。

Solution

线性基模板题，次大值为最大值异或线性基内最小的元素

Code

#include<bits/stdc++.h>
using namespace std;
long long p[100];
void solve(long long x){
	for (long long i=62;i>=0;i--){
		if ((long long)x>>(long long)i){
			if (!p[i]){
				p[i]=(long long)x;
				return;
			}else{
				x^=(long long)p[i];
			}
		}
	}
}
long long n,x;
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>x;
		solve(x);
	}
	long long ans=0,dd=11451419198102333;
	for (long long i=62;i>=0;i--){
		if (((long long)ans^(long long)p[i])>(long long)ans){
			ans^=(long long)p[i];
		}
		if (p[i]>0){
			dd=min(dd,p[i]);
		}
	}
	cout<<ans<<" "<<(ans^dd);
}

#4247 挂饰

Description

JOI 君有 $N$ 个装在手机上的挂饰，编号为 $1…N$。JOI 君可以将其中的一些装在手机上。
JOI 君的挂饰有一些与众不同——其中的一些挂饰附有可以挂其他挂件的挂钩。每个挂件要么直接挂在手机上，要么挂在其他挂件的挂钩上。直接挂在手机上的挂件最多有1个。
此外，每个挂件有一个安装时会获得的喜悦值，用一个整数来表示。如果 JOI 君很讨厌某个挂饰，那么这个挂饰的喜悦值就是一个负数。
JOI 君想要最大化所有挂饰的喜悦值之和。注意不必要将所有的挂钩都挂上挂饰，而且一个都不挂也是可以的。

Solution

同样事 DP，设 $f[i][j]$ 表示前 $i$ 个挂饰，剩下 $j$ 个钩子的最大喜悦值。

Code

#include<bits/stdc++.h>
using namespace std;
int n,f[2500][2500];
struct node{
	int a,b;
};
node s[3000];
bool cmp(node a,node b){
	return a.a>b.a;
}
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>s[i].a>>s[i].b;
	}
	sort(s+1,s+1+n,cmp);
	memset(f,-63,sizeof(f));
	f[0][1]=0;
	for (int i=1;i<=n;i++){
		for (int j=0;j<=n;j++){
			f[i][j]=max(f[i-1][j],f[i-1][max(j-s[i].a,0)+1]+s[i].b);
		}
	}
	int ans=0;
	for (int i=0;i<=n;i++){
		ans=max(ans,f[n][i]);
	}
	cout<<ans;
}

#4576 [Usaco2016 Open]262144

Description

给定一个长度为 $n$（$n<=2^18$）的序列，初始元素值为 $1$ 到 $40$ 之间的整数，每次操作可以将两个相邻的并且大小相同的正整数替换成一个比原数大一的正整数。要求最大化最终数列中的最大值。

Solution

区间 DP，设 $f[i][j]$ 表示第 i 个位置 $j$ 大小的数能组成的那一串数的右侧位置。

Code

#include<bits/stdc++.h>
using namespace std;
int n,f[60][300000],ans=0;
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		int x;
		cin>>x;
		f[x][i]=i+1;
	}
	for (int i=1;i<=59;i++){
		for (int j=1;j<=n;j++){
			if (!f[i][j]){
				f[i][j]=f[i-1][f[i-1][j]];
			}
			if (f[i][j]){
				ans=max(ans,i);
			}
		}
	}
	cout<<ans;
}

#2460 [BeiJing2011]元素

Description

相传，在远古时期，位于西方大陆的 Magic Land 上，人们已经掌握了用魔法矿石炼制法杖的技术。那时人们就认识到，一个法杖的法力取决于使用的矿石。
一般地，矿石越多则法力越强，但物极必反：有时，人们为了获取更强的法力而使用了很多矿石，却在炼制过程中发现魔法矿石全部消失了，从而无法炼制出法杖，这个现象被称为“魔法抵消” 。特别地，如果在炼制过程中使用超过一块同一种矿石，那么一定会发生“魔法抵消”。后来，随着人们认知水平的提高，这个现象得到了很好的解释。经过了大量的实验后，著名法师 Dmitri 发现：如果给现在发现的每一种矿石进行合理的编号（编号为正整数，称为该矿石的元素序号），那么，一个矿石组合会产生“魔法抵消“当且仅当存在一个非空子集，那些矿石的元素序号按位异或起来
为零。 （如果你不清楚什么是异或，请参见下一页的名词解释。 ）例如，使用两个同样的矿石必将发生“魔法抵消”，因为这两种矿石的元素序号相同，异或起来为零。 并且人们有了测定魔力的有效途径，已经知道了：合成出来的法杖的魔力等于每一种矿石的法力之和。人们已经测定了现今发现的所有矿石的法力值，并且通过实验推算出每一种矿石的元素序号。
现在，给定你以上的矿石信息，请你来计算一下当时可以炼制出的法杖最多有多大的魔力。

Solution

贪心+线性基，按照魔力值从大到小排序，将编号插入线性基，如果无法插入则不统计，可以插入则累计魔力值。

Code

#include<bits/stdc++.h>
using namespace std;
long long p[100];
bool solve(long long x){
	for (long long i=62;i>=0;i--){
		if ((long long)x>>(long long)i){
			if (!p[i]){
				p[i]=(long long)x;
				return true;
			}else{
				x^=(long long)p[i];
			}
		}
	}
	return false;
}
struct node{
	long long x,y;
};
node s[1500];
bool cmp(node a,node b){
	return a.y>b.y;
} 
long long n,x,y,ans=0;
int main(){
	cin>>n;
	for (int i=1;i<=n;i++){
		cin>>s[i].x>>s[i].y;
	}
	sort(s+1,s+1+n,cmp);
	for (int i=1;i<=n;i++){
		if (solve(s[i].x)){
			ans+=s[i].y;
		}
	}
	cout<<ans;
}

#3039 玉蟾宫

Description

有一天，小猫 rainbow 和 freda 来到了湘西张家界的天门山玉蟾宫，玉蟾宫宫主蓝兔盛情地款待了它们，并赐予它们一片土地。
这片土地被分成 $N*M$ 个格子，每个格子里写着’R’或者’F’，R 代表这块土地被赐予了 rainbow，F 代表这块土地被赐予了 freda。
现在 freda 要在这里卖萌……它要找一块矩形土地，要求这片土地都标着’F’并且面积最大。
但是 rainbow 和 freda 的 OI 水平都弱爆了，找不出这块土地，而蓝兔也想看 freda 卖萌（她显然是不会编程的……），所以它们决定，如果你找到的土地面积为$ S$，它们每人给你 $S$ 两银子。

Solution

裸的悬线法

#4543 [POI2014]Hotel 加强版

Description

一棵树 $n(n<100000)$ 个点，求三个点距离两两相等的种类数。

Solution

设 $f[x][y]$ 表示 $x$ 子树下深度为 $y$ 的点的个数，$g[x][y]$ 表示 $x$ 子树下的点对个数，满足到其 $LCA$ 的距离为 $d$ ，$LCA$ 深度为 $d-y$

$$f[x][y]=\sum f[s][a-1]$$ $$g[x][y]+=\sum g[s][a+1]+f[x][a]*f[y][a]$$ $$ans+=\sum f[x][y]*g[s][y+1]+g[x][y]*f[y][y-1]$$

其中 $s$ 为 $x$ 的子结点

但是这么直接 DP 时间复杂度是过高的，需要启发式合并优化

长链剖分后继承重儿子的结果，使用指针来平移

Code

#include<bits/stdc++.h>
#define MAXN 114514
using namespace std;
int last[MAXN*2],to[MAXN*2],nextt[MAXN*2],topp=0;
int fa[MAXN],d[MAXN],son[MAXN],s[1919810];
int *f[MAXN],*g[MAXN],*now=&s[1];
int n,ans=0;
void add(int a,int b){
    nextt[++topp]=last[a];
    to[topp]=b;
    last[a]=topp;
}
void dfs1(int x){
	for (int i=last[x];i;i=nextt[i]){
		int t=to[i];
		if (t==fa[x]){
			continue;
		}
		fa[t]=x;
		dfs1(t);
		d[x]=max(d[x],d[t]+1);
		if (d[t]>d[son[x]]){
			son[x]=t;
		}
	}
}
void calc(int x){
	f[x]=now;
	now+=d[x]+1;
	g[x]=now+d[x]+1;
	now+=d[x]*2+2;
}
void dfs2(int x){
	if (son[x]){
		f[son[x]]=f[x]+1;
		g[son[x]]=g[x]-1;
		dfs2(son[x]);
	}
	f[x][0]=1;
	ans+=g[x][0];
	for (int i=last[x];i;i=nextt[i]){
		int t=to[i];
		if (t==fa[x]||t==son[x]){
			continue;
		}
		f[t]=now;
		calc(t);
		dfs2(t);
		for (int j=d[t];j>=0;j--){
			if (j){
				ans+=f[x][j-1]*g[t][j];
			}
			ans+=f[t][j]*g[x][j+1];
			g[x][j+1]+=f[x][j+1]*f[t][j];
		}
		for (int j=0;j<=d[t];j++){
			if (j){
				g[x][j-1]+=g[t][j];
			}
			f[x][j+1]+=f[t][j];
		}
	}
}
int main(){
	cin>>n;
	for (int i=1;i<=n-1;i++){
		int a,b;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs1(1);
	calc(1);
	dfs2(1);
	cout<<ans;
}

#2396 神奇的矩阵

Description

给出三个行数和列数均为$N$ 的矩阵 $A$、$B$、$C$，判断 $A*B=C$ 是否成立。

Solution

随机化，同乘一个 $1*n$ 的随机矩阵判断

Code

#include<bits/stdc++.h>
using namespace std;
int n,a[1005][1005],b[1005][1005],c[1005][1005],d[1005];
int x[1005],y[1005],z[1005];
int main(){
	srand(time(0));
	while(cin>>n){
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				cin>>a[i][j];
			}
		}
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				cin>>b[i][j];
			}
		}
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				cin>>c[i][j];
			}
		}
		for (int i=1;i<=n;i++){
			d[i]=rand()*114514;
		}
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				x[i]+=d[j]*b[i][j];
			}
		}
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				y[i]+=x[j]*a[i][j];
			}
		}
		for (int i=1;i<=n;i++){
			for (int j=1;j<=n;j++){
				z[i]+=d[j]*c[i][j];
			}
		}
		bool check=0;
		for (int i=1;i<=n;i++){
			if (y[i]!=z[i]){
				check=1;
				break;
			}
		}
		if (check){
			cout<<"No"<<endl;
		}else{
			cout<<"Yes"<<endl;
		}
	}
}

#1213 [HNOI2004]高精度开根

Description

晓华所在的工作组正在编写一套高精度科学计算的软件，一些简单的部分如高精度加减法、乘除法早已写完了，现在就剩下晓华所负责的部分：实数的高精度开 $m$ 次根。因为一个有理数开根之后可能得到一个无理数，所以这项工作是有较大难度的。现在要做的只是这项工作的第一步：只对自然数进行开整数次根，求出它的一个非负根，并且不考虑结果的小数部分，只要求把结果截断取整即可。程序需要根据给定的输入，包括需要开根的次数，以及被开根的整数；计算出它的非负根取整后的结果。

Code

py 大法好

m=int(input())
n=int(input())
l=0
r=1
while (r**m<=n):
	l=r
	r=r*2
while (l<=r):
	mid=(l+r)//2
	if (mid**m<=n):
		l=mid+1
	else:
		r=mid-1
for i in range(l-2,l+2):
	x=i**m
	if (x==n):
		print(i)
		break
	if (x>n):
		print(i-1)
		break
作者: solstice23
本文采用 CC BY-NC-SA 4.0 协议
DP区间DP启发式合并数论树形DP矩阵线性基贪心长链剖分随机化高精度

评论

  1. 九凌网络
    Windows Chrome
    11月前
    2022-12-14 9:44:12

    是我门外了吗，感觉题目都好变态(´இ皿இ｀)

  4. Evan
    Macintosh Chrome
    2年前
    2022-2-14 16:17:57

    代码bug了

  7. DrBlack
    Windows Chrome
    4年前
    2020-5-20 21:24:19

    a[i]=b[i]=1145141919810;
    1145141919810
    要 素 察 觉

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: Telegram @AmashiroNatsukiEars_NoWord Sticker
Source: Telegram Animated Emojis
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
AmashiroNatsukiEars
Telegram Emojis
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
暴力数据结构 : 珂朵莉树 (ODT)

							
							

							
[NOI Online 3 提高组] 魔法值 题解

							
							

							
BZOJ #4070 [Apio2015]雅加达的摩天楼

							
							

							
BZOJ #1999 [Noip2007]Core 树网的核 & #2936 [Poi1999]降 水 & #1907 树的路径覆盖 & #1270 [BeijingWc2008]雷涛的小猫

							
							

							
[ZJOI2010]网络扩容

							
							

							
[SDOI2009]晨跑

							
							

							
网络流 24 题 – 分配问题

							
							

							
网络流 24 题 – 负载平衡问题

							
							

							
P2774 方格取数问题

							
							

							
[ZJOI2009]狼和羊的故事