【BZOJ 4198】[NOI2015] 荷马史诗

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4198

解题报告

k叉哈夫曼树
注意最大化儿子不满的那个结点的深度

Code

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

struct Data{
	LL apt, mx;
	inline Data() {
	}
	inline Data(LL a, LL c):apt(a), mx(c) {
	}
	inline Data operator + (const Data &d) {
		return Data(apt + d.apt, max(mx, d.mx + 1));
	}
	inline bool operator < (const Data &d) const {
		return apt > d.apt || (apt == d.apt && mx > d.mx); 
	}
};
priority_queue<Data> que;

inline LL read() {
	char c=getchar(); LL 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() {
	int n = read(), k = read();
	for (int i = 1; i <= n; i++) {
		que.push(Data(read(), 0));
	} 
	LL ans = 0;
	for (bool frt = (n - 1) % (k - 1); (int)que.size() > 1; frt = 0) {
		Data np(0, 0);
		for (int i = frt? 1 + (n - 1) % (k - 1): k; i; --i) {
			np = np + que.top();
			que.pop();
		}
		ans += np.apt;
		que.push(np);
	}
	printf("%lld\n%lld\n", ans, que.top().mx);
	return 0;
}

【日常小测】回转寿司

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/07/20170623_statement.pdf

解题报告

看到这题我们不难想到分块
更进一步,对于每一个块来说,块内的数的相对大小不变
于是我们只需要用堆便可维护块内有哪些数

再稍加观察,我们发现只要再用一个堆记录块内的操作,然后从左向右扫一遍便可更新具体的数
于是我们就可以在:$O(n^{1.5} \log n)$的时间复杂度内解决这个问题了

另外priority_queue的构造函数是$O(n)$的

Code

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

const int N = 400009;
const int M = 25009;
const int S = 1000;
const int B = N / S + 10; 

int n, sn, m, arr[N];
priority_queue<int> val[B];
vector<int> opr[B];

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

inline void get_element(int w) {
	if (opr[w].empty()) {
		return;
	}
	priority_queue<int, vector<int>, greater<int> > heap(opr[w].begin(), opr[w].end()); 
	for (int i = max(1, w * S), lim = min((w + 1) * S - 1, n); i <= lim; i++) {
		if (arr[i] > heap.top()) {
			heap.push(arr[i]);
			arr[i] = heap.top();
			heap.pop();
		}
	}	
	opr[w].clear();
}

inline int modify_element(int w, int s, int t, int v) {
	get_element(w);
	int tmp = -1;
	for (int i = s; i <= t; i++) {
		if (v < arr[i]) {	
			tmp = arr[i];
			swap(v, arr[i]);
		}
	}
	val[w] = priority_queue<int>(arr + max(1, w * S), arr + 1 + min(n, (w + 1) * S - 1));
	return v;
}

inline int modify_block(int w, int v) {
	val[w].push(v);
	int ret = val[w].top();
	val[w].pop();
	if (v != ret) {
		opr[w].push_back(v);
	}
	return ret;
}

inline int solve(int s, int t, int v) {
	int ss = s / S, st = t / S;
	v = modify_element(ss, s, min(t, (ss + 1) * S - 1), v);
	if (ss != st) {
		for (int i = ss + 1; i < st; i++) {
			v = modify_block(i, v);
		}
		v = modify_element(st, st * S, t, v);
	}
	return v;
}

int main() {
	n = read(); m = read();
	sn = n / S;
	for (int i = 1; i <= n; i++) {
		arr[i] = read();
	}
	for (int i = 0; i <= sn; i++) {
		val[i] = priority_queue<int>(arr + max(1, i * S), arr + 1 + min(n, (i + 1) * S - 1));
	}
	for (int tt = 1; tt <= m; tt++) {
		int s = read(), t = read(), v = read();
		if (s <= t) {
			v = solve(s, t, v);		
		} else {
			v = solve(s, n, v);
			v = solve(1, t, v);
		}
		printf("%d\n", v);
	}
	return 0;
}

【BZOJ 4716】假摔

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4716
神犇题解:http://blog.csdn.net/pure_w/article/details/53428070

解题报告

我们注意到权值是非负的
于是我们先把每一个点作为右上角的最小矩阵扔到小根堆中
之后每一次取出最小的,拓展一行一列,之后再扔回去就可以辣!

一开始没有看到权值非负
以为要像超级钢琴一样用个数据结构维护什么的
结果活生生没有想出来 QwQ

Code

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

const int N = 1009;

int n,m,mnx,mny,k,arr[N][N],sum[N][N];
struct Squre{
	int x,y,lx,ly,val;
	inline bool operator < (const Squre &B) const {
		return val > B.val;
	}	
}; 
priority_queue<Squre> que;	
set<pair<int,int> > s[N][N];
	
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;
}

inline int cal(int x, int y, int lx, int ly) {
	return (LL)sum[x][y] - sum[x][y-ly] - sum[x-lx][y] + sum[x-lx][y-ly];
} 

int main(){
	m = read(); n = read();
	mny = read(); mnx = read(); k = read();
	for (int j=1;j<=m;j++) {
		for (int i=1;i<=n;i++) {
			arr[i][j] = read(); 
			sum[i][j] = (LL)sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + arr[i][j];
			if (i >= mnx && j >= mny) 
				que.push((Squre){i,j,mnx,mny,cal(i, j, mnx, mny)});
		}
 	}
 	for (int i=1;i<k;i++) {
		Squre w = que.top(); que.pop();
		if (w.x > w.lx && !s[w.x][w.y].count(make_pair(w.lx+1, w.ly))) {
			que.push((Squre){w.x,w.y,w.lx+1,w.ly,cal(w.x,w.y,w.lx+1,w.ly)});
			s[w.x][w.y].insert(make_pair(w.lx+1, w.ly));
		}
		if (w.y > w.ly && !s[w.x][w.y].count(make_pair(w.lx, w.ly+1))) {
			que.push((Squre){w.x,w.y,w.lx,w.ly+1,cal(w.x,w.y,w.lx,w.ly+1)});
			s[w.x][w.y].insert(make_pair(w.lx, w.ly+1));
		}
	}
	printf("%d\n",que.top().val+1);
	return 0;
}

后记

现在问题来了,如果权值可以为负数怎么做?

【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短路来做也是对的
想一想正确性确实很对,不过似乎会炸内存?

【UVa 11134】Fabled Rooks

题目传送门:https://uva.onlinejudge.org/external/111/11134.pdf
中文题面:《算法竞赛·入门经典·训练指南》P81

首先这题的行列无关,所以肯定可以分开考虑
于是就转化为了一维的情况

之后的事情,貌似网络流+线段树结构优化建图也能A?
我人懒,写的贪心 QAQ

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

const int N = 5000+9;

int xl[N],xr[N],yr[N],yl[N],X[N],Y[N],n;
deque<pair<int,int> > beg[N]; deque<int> End[N];
priority_queue<pair<int,int> ,vector<pair<int,int> >, greater<pair<int,int> > > 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;
}

inline bool solve(int *l, int *r, int *ret) {
	memset(ret,0,sizeof(X));
	while (!que.empty()) que.pop();
	for (int i=1;i<=n;i++) {
		beg[i].clear(); 
		End[i].clear();
	}
	for (int i=1;i<=n;i++) {
		beg[l[i]].push_back(make_pair(r[i],i));
		End[r[i]].push_back(i);
	}
	
	for (int i=1;i<=n;i++) {
		while (!beg[i].empty()) {
			pair<int,int> w = beg[i].front(); 
			beg[i].pop_front();
			que.push(make_pair(w.first,w.second));
		}
		
		if (que.empty()) return false;
		ret[que.top().second] = i;
		que.pop();
		
		while (!End[i].empty()) {
			if (!ret[End[i].front()]) 
				return false;
			End[i].pop_front();
		}
	}
	return true;
}

int main(){
	for (n=read();n;n=read()) {
		for (int i=1;i<=n;i++) {
			xl[i] = read(); yl[i] = read();
			xr[i] = read();	yr[i] = read();
		}
		
		if (!solve(xl,xr,X)) {puts("IMPOSSIBLE"); continue;}
		if (!solve(yl,yr,Y)) {puts("IMPOSSIBLE"); continue;}
		
		for (int i=1;i<=n;i++) 
			printf("%d %d\n",X[i],Y[i]);
	}
	return 0;
}

【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 3832】[POI2014] Rally

相关链接:

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3832

解题报告

这题真的是妙不可言!
0MYHX~N~(WNGO)B6[N8ZL40
POI的题目质量真的还不错啊!

先DP预处理一下:
f[]表示顺着走能走多远
g[]表示反着走能走多远
对于边(u,v)给一个权值g[u]+f[v]
不难发现,一个图的最长链此时为权值最大的那一条边

考虑删点,如果会影响到最长链的话
新的最长链一定是从拓扑序小于他的连向拓扑序大于他的某条边的权值
于是搞一搞堆来维护这个东西即可

Code

代码方面,我偷懒写的set+map的写法
想要常数小,请参见:https://blog.sengxian.com/solutions/bzoj-3832

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

const int N = 500000+9;
const int M = 4000000+9; 
const int INF = 100000000;

int head[N],nxt[M],to[M],rhead[N],n,m,S,T;
int f[N],g[N],in[N],rin[N],vout=INF,Point;
struct CMP{inline bool operator () (const int a, const int b) {return b<a;}};
set<int,CMP> cur; unordered_map<int,int> CNT; queue<int> que;

inline void Add_Edge(int u, int v) {
	static int TT = 1; in[v]++; rin[u]++;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT;
	to[++TT] = u; nxt[TT] = rhead[v]; rhead[v] = TT;
}

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;
}

void solve(int w, int *frt, int *ret, int *cnt) {
	if (w != S && w != T) que.push(w);
	for (int i=frt[w];i;i=nxt[i]) {
		ret[to[i]] = max(ret[to[i]],ret[w]+1);
		if (!--cnt[to[i]]) solve(to[i],frt,ret,cnt);
 	}
}

int main(){
	n = read(); m = read(); S = 0; T = n+1;
	for (int i=1;i<=n;i++) Add_Edge(S,i), Add_Edge(i,T);
	for (int i=1,u,v;i<=m;i++) u = read(), v = read(), Add_Edge(u,v); 
	solve(S,head,f,in); solve(T,rhead,g,rin);
	for (int i=1;i<=n;++i) if (!CNT[g[i]]++) cur.insert(g[i]);
	for (int op=1;op<=n;op++) {
		int w = que.front(); que.pop(); 
		for (int i=rhead[w];i;i=nxt[i]) if (!--CNT[f[to[i]]+g[w]]) cur.erase(f[to[i]]+g[w]);
		if (vout > *(cur.begin())) vout = *(cur.begin()), Point = w; 
		for (int i=head[w];i;i=nxt[i]) if (!CNT[g[to[i]]+f[w]]++) cur.insert(g[to[i]]+f[w]);
	} printf("%d %d\n",Point,vout-1);
	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;
}