【BZOJ 4419】发微博

链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4419
神犇题解:http://www.cnblogs.com/ziliuziliu/p/5470337.html

题解

我的想法是把关系修改扔到map里面去
然后log(n)的时间查询上一个修改是多久
这样问题就变成了询问时间l到r中点c进行了多少次+1操作
这个用主席树就可以了

然而看了题解之后发现,似乎用暴力搞就可以了?
用前缀和的思想:
关系建立的时候减去,关系解除时加回来
最后再用set处理一下剩下的就可以辣!

【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 2342】[Shoi2011] 双倍回文

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

manacher自己做的第一题! 2A! 撒花! *★,°*:.☆\( ̄▽ ̄)/$:*.°★*
最开始看这个题:树套树?二维偏序的既视感……然而树套树求取区间最值的空间复杂度绝对过不了
于是可耻看题解,瞄了一眼:用set就可以水掉QAQ
于是再自己推一推,确定两个set连起来就可以搞
搞一搞520ms水过去了
再一看题解,还可以只用一个set水过去QAQ
不过跑出来反而比hzwer的一个set快一点……..

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;

const int MAXN = 1200000; 

char pat[MAXN],BUF[MAXN];
int p[MAXN],rt,n,len,vout;

inline void manacher(){
	len = n*2+1; 
	for (int i=1,p1,p2;i<=len;i++){ if (p[rt]+rt > i) p[i] = min(p[rt*2-i],p[rt]+rt-i);
		else p[i] = 0; p1 = i+p[i]; p2 = i-p[i];
		while (pat[++p1] ==  pat[--p2]) p[i]++;
		if (pat[rt]+rt < p[i]+i) rt = i;
	}
}

inline void init(){
	scanf("%d%s",&n,BUF+1);
	for (int i=1;i<=n;i++){
		pat[i*2-1] = '@';
		pat[i*2] = BUF[i];
	} pat[n*2+1] = '@';
	pat[0] = '#'; pat[n*2+2] = '$';
}

struct cmp{
	bool operator () (const int &a, const int &b){
		return a+p[a] < b+p[b];
	}
}; 

set<int> por;
set<int,cmp> list;
set<int>::iterator itr;
set<int,cmp>::iterator ITR;
pair<set<int,cmp>::iterator,bool> TMP;

inline void solve(){
	for (int i=3;i<=len;i+=2){
		int p1 = i-p[i]/2,buf=0;
		itr = por.lower_bound(p1);
		if (itr != por.end()){  
			buf = (i-*itr+1)/2;
			vout = max(vout, buf*4);
		}
			
		TMP = list.insert(i);
		if (TMP.second) por.insert(i);		
		
		ITR = list.begin();
		while (!list.empty() && *ITR+p[*ITR] < i+2) 
			por.erase(*ITR), list.erase(ITR),ITR = list.begin();
	}
	printf("%d",vout);
}

int main(){
	init();
	manacher();
	solve(); 
	return 0;	
}