【Codeforces 715C】Digit Tree

相关链接

题目传送门:http://codeforces.com/problemset/problem/715/C
官方题解:http://codeforces.com/blog/entry/47169

解题报告

要求统计树上路径,那么基本上确定是DP或者树分治了
想一想,好像DP的状态不好表示的样子,于是就直接点分治啦!

考虑对于每一个中心,统计经过该点符合要求的路径数
很明显需要将路径剖成两半,一半扔到map里,另一半直接查

但这题还有需要注意的就是如何去掉两段都在同一子树的非法情况
似乎直接像之前一样在子树的根部调用cal()直接剪掉的方法不管用了
于是可以先DFS一遍,统计所有信息
然后再处理每一个子树的时候,先DFS一遍,把该子树的信息给去掉
查询完成之后,再DFS一遍把信息给加回去

Code

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

const int N = 200000 + 9;

int head[N],nxt[N],cost[N],to[N],REV[N];
int n,MOD; LL vout;

inline int read() {
	char c=getchar(); int f=1,ret=0;
	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 void Add_Edge(int u, int v, int w) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
	to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w; 
}

void gcd(int a, LL &x, int b, LL &y) {
	if (!b) {x = 1, y = 0;}
	else {gcd(b,y,a%b,x);y-=a/b*x;}
}

inline int gcd(int a, int b) {
	static LL x,y;
	gcd(a,x,b,y);
	return (x % MOD + MOD) % MOD;
} 

namespace Node_Decomposition{
	#define ND Node_Decomposition
	const int INF = 1e9;
	int tot,node_sz,root,cur;
	int sum[N],dep[N],vis[N];
	map<int,int> cnt;
	
	void Get_Root(int w, int f) {
		sum[w] = 1; int mx = 0;
		for (int i=head[w];i;i=nxt[i]) {
			if (to[i] != f && !vis[to[i]]) {
				Get_Root(to[i], w);
				sum[w] += sum[to[i]];
				mx = max(mx, sum[to[i]]);
			}
		}
		mx = max(mx, node_sz - sum[w]);
		if (mx < cur) cur = mx, root = w;
	}
	
	void DFS(int w, int f, int delta, LL p, int val) {
		cnt[val] += delta; 
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				DFS(to[i], w, delta, p * 10 % MOD, (val + cost[i] * p) % MOD);
			}
		}
	}
	
	void cal(int w, int f, int t, LL val) {
		vout += cnt[(-val*REV[t]%MOD+MOD)%MOD]; 
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]] && to[i] != f) {
				cal(to[i], w, t+1, (val * 10 + cost[i]) % MOD);
			}
		}
	}
	
	void solve(int w, int sz) {
		vis[w] = 1; cnt.clear(); 
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
			}
		}
		vout += cnt[0]; cnt[0]++;
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				DFS(to[i], w, -1, 10 % MOD, cost[i] % MOD);
				cal(to[i], w, 1, cost[i] % MOD);
				DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
			}
		}
		for (int i=head[w];i;i=nxt[i]) {
			if (!vis[to[i]]) {
				node_sz = sum[to[i]] > sum[w] ? sz - sum[w] : sum[to[i]];
				cur = INF; Get_Root(to[i], w);
				solve(root, node_sz);
			}
		}
	}
	
	inline void solve() {
		cur = INF; node_sz = n;
		Get_Root(1,1);
		solve(root,n);
	}
};

int main() {
	n = read(); MOD = read();
	for (int i=1,u,v,w;i<n;i++) {
		u = read(); v = read(); w = read();
		Add_Edge(u + 1, v + 1, w);
	}
	REV[0] = 1; REV[1] = gcd(10, MOD);
	for (int i=2;i<=n;i++)
		REV[i] = (LL)REV[i-1] * REV[1] % MOD;
	ND::solve();
	printf("%lld\n",vout);
	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;	
} 

【Tricks】STL容器使用指南

1.set.insert() 的返回值是 pair;, 其中bool表示是否插入成功
2.set/map当中的earse() 是完全没有检查机制的(我TM都比他写得好!),使用的时候一定要小心
3.set/map/priority_queue可以仅重载其中的比较符号,例如:

struct CMP{
	bool operator () (const int &a, const int &b){
		return a < b;
	}
};

set<int,CMP> S;
map<int,int,CMP> M;
priority_queue<int,vector<int>,CMP> Q;

4.map使用[]进行访问的时候,即使仅仅是查询、不是赋值,map仍然会新建一个节点
5.sort排序传进去的尾地址不会参与排序