【BZOJ 4345】[POI2016] Korale

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4345
神犇题解:http://sr16.com:8081/【bzoj4345】【poi2016】korale/

解题报告

这题看到$k$这么玄学,那就一定是与$k$相关辣!
想一想可不可以用线段树合并做。或者可持久化Treap?
然而似乎都不好做。

我们考虑暴搜的搜索树,如果我们使用$BFS$加上小根堆,显然没有问题
于是我们定义二元组$(i,j)$表示当前集合的权值为$i$,最大的元素编号为$j$
类比搜索树,则转移为 $(i,j) \Rightarrow (i + a[j + 1],j + 1)\& (i + a[j + 1] – a[j],j + 1)$
于是我们就可以求出第$k$小的值$ans$了!

然后我们再来考虑如何输出方案:我们暴搜方案,将结果$>ans$的直接剪掉就可以啦!
考虑这样复杂度为什么是对的,因为 $ \le ans$ 的方案数不会超过$k$个啊!

—————————— UPD 2017.3.22 ——————————
今天考试考了这个题,然后wuvin说直接那k短路来做也是对的
想一想正确性确实很对,不过似乎会炸内存?

【BZOJ 2006】[NOI2010] 超级钢琴

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2006
数据传送门:noi_2010_piano

这题很经典!很好!
首先肯定是求前缀和,然后搞n个结构体,第i个表示左端点在i的线段的最值
每次取出最大的结构体进行拓展,需要用函数式线段树来支持区间k大
时间复杂度:O(k*log(值域))
另外这题还有ST表的做法,但还不是很会 qwq

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 500000+9;
const int M = 20000000+9;
const int BAS = 500000010;
const int INF = 1000010000;

int n,k,L,R,arr[N];
struct Query{
	int pos,num,val;
	bool operator < (const Query & B) const {
		return val < B.val;
	}
};
priority_queue<Query> que;

namespace Chair_Tree{
	#define CT Chair_Tree
	int ch[M][2],sum[M],cnt,root[N],ans_tmp;
	
	void insert(int p, int &w, int l, int r, int v) {
		w = ++cnt; sum[w] = sum[p] + 1;
		memcpy(ch[w],ch[p],sizeof(ch[0]));
		if (l < r) {
			int mid = l + r + 1 >> 1;
			if (v < mid) insert(ch[p][0], ch[w][0], l, mid-1, v);
			else insert(ch[p][1], ch[w][1], mid, r, v);
		} 
	} 
	
	inline void insert(int p, int w) {
		insert(root[p-1], root[p], 1, INF, w);
	} 
	
	void query(int p, int w, int l, int r, int num) {
		if (l == r) ans_tmp = l;
		else {
			int mid = l + r + 1 >> 1;
			if (sum[ch[w][1]] - sum[ch[p][1]] >= num) query(ch[p][1], ch[w][1], mid, r, num);
			else query(ch[p][0], ch[w][0], l, mid-1, num - (sum[ch[w][1]] - sum[ch[p][1]]));
		}
	}
	
	inline int query(int l, int r, int num) {
		query(root[l-1],root[r],1,INF,num);
		return ans_tmp;
	}
};

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){
	n = read(); k = read(); L = read(); R = read();
	for (int i=1;i<=n;i++) arr[i] = arr[i-1] + read();
	for (int i=1;i<=n;i++) CT::insert(i,arr[i] + BAS);
	for (int i=1;i+L-1<=n;i++) {
		Query tmp; tmp.pos = i; tmp.num = 1;
		tmp.val = CT::query(i+L-1, min(n,i+R-1), 1) - BAS - arr[i - 1];
		que.push(tmp);
	}
	
	LL vout = 0;
	for (int i=1,p;i<=k;i++) {
		Query tmp = que.top(); que.pop();
		vout += tmp.val; 
		if (tmp.num < R - L + 1) {
			tmp.num++; p = tmp.pos;
			if (n - (p+L-1) + 1 < tmp.num) continue;
			tmp.val = CT::query(p+L-1, min(n,p+R-1), tmp.num) - arr[p - 1] - BAS;
			que.push(tmp);
		}
	}
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 4524】[CQOI2016] 伪光滑数

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4524
正常题面及题解:http://blog.csdn.net/huanghongxun/article/details/51181809

解题报告

考虑按最大的质因子分类
那么每一次就是用次大的质因子去替换最大的质因子
再用堆来维护一下就好了

Code

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

LL n; int k;
int pri[]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127},tot=31;
struct Data{
	LL w; int k,MX,nxt;
	inline Data() {}
	inline Data(LL a, int b, int c, int d):w(a),k(b),MX(c),nxt(d) {}
	inline bool operator < (const Data &B) const {return w < B.w;}
};
priority_queue<Data> que; 

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret*f;
}

int main(){
	cin>>n>>k;
	for (int i=1;i<=tot;i++) {
		LL w = pri[i]; int t = 1;
		while (w <= n) {
			que.push(Data(w,t,i,i-1)),
			w *= pri[i]; t++;
		}
	}
	for (int j=1;j<k;j++) {
		Data t = que.top(); que.pop();
		if (t.k > 1) for (int i=1;i<=t.nxt;i++) {
			LL tmp = t.w / pri[t.MX] * pri[i];
			que.push(Data(tmp,t.k-1,t.MX,i));
		}
	}
	cout<<que.top().w;
	return 0;
}