Category: 其他

【Codeforces 732E】Sockets

Qizy 26 Comments

题目传送门：http://codeforces.com/contest/732/problem/E

这题的费用流做法很显然吧？
但我们可以做得更优：

将插座排序后从小到大进行处理，枚举使用多少次转换器
仔细想一想：如果此时扫描到有未匹配的电脑那么直接匹配不会使答案变劣
于是就这么贪心一下就行啦

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

const int N = 200000+9;
const double EPS = 1e-8;

struct Socks{
	int id,val;
	inline bool operator < (const Socks &tmp) const {
		return val < tmp.val;
	}
}s[N];
int p[N],n,m,nxt[N],num[N],v1[N],v2[N];
map<int,int> head;

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 void insert(int w, int v) {
	static int T = 0;
	nxt[++T] = head[w]; num[T] = v;
	head[w] = T;
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) p[i] = read();
	for (int i=1;i<=m;i++) s[i].val = read(), s[i].id = i;
	for (int i=1;i<=n;i++) insert(p[i],i);
	sort(s+1,s+1+m);
	for (int i=1;i<=m;i++) {
		for (int w=0,cur=s[i].val;;cur=(int)(ceil((double)cur/2)+EPS),w++) {
			if (head[cur]) {
				v1[s[i].id] = w;
				v2[num[head[cur]]] = s[i].id;
				head[cur] = nxt[head[cur]];
				break;
			}
			if (cur == 1) break;
		}
	}
	int vout1 = 0, vout2 = 0;
	for (int i=1;i<=m;i++) vout1 += v1[i];
	for (int i=1;i<=n;i++) vout2 += (v2[i] > 0);
	cout<<vout2<<' '<<vout1<<endl;
	for (int i=1;i<=m;i++) printf("%d ",v1[i]); cout<<endl;
	for (int i=1;i<=n;i++) printf("%d ",v2[i]); 
	return 0;
}

【BZOJ 2095】[Poi2010] Bridges

Qizy 252 Comments

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

这个题目啊！瞄一眼就知道是二分吧？
接下来就是给你一些有向边&无向边，让你判断是否存在欧拉回路

对于有向边，没有悬念，直接记录对于出度入度的贡献
只与有向边嘛，不妨先随便定一个向，然后考虑使用网络流进行调整
具体细节可以参见：http://blog.csdn.net/wzq_qwq/article/details/48651379

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

const int N = 2000+9;
const int M = 10000+9;
const int INF = 1e9;

struct Edge{int u,v,w1,w2;}edge[M];
int n,m,MX,MN=INF,in[N],out[N],cur[M];
int S,T,dis[N],flow[M],head[N],nxt[M],to[M],TT; 
queue<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 void Add_Edge(int u, int v, int f) {
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0;
} 

inline bool BFS(){
	memset(dis,-1,sizeof(dis));
	dis[S] = 0; que.push(0);
	
	while (!que.empty()) {
		int w = que.front(); que.pop();
		for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) {
			dis[to[i]] = dis[w] + 1;
			que.push(to[i]);
		}
	}
	
	return ~dis[T];
}

int DFS(int w, int f) {
	if (w == T) {
		return f;
	} else {
		int ret = 0;
		for (int &i=cur[w],tmp;i && f;i=nxt[i]) { 
			if (dis[to[i]] == dis[w] + 1) {
				tmp = DFS(to[i], min(f, flow[i]));
				ret += tmp; f -= tmp;
				flow[i] -= tmp; flow[i^1] += tmp;
			}
		}
		return ret;
	}
}

inline int Dinic(){
	int ret = 0;
	while (BFS()) {
		memcpy(cur,head,sizeof(head));
		ret += DFS(S,INF);
	}
	return ret;
}

inline bool judge(int lim){
	memset(in,0,sizeof(in));
	memset(out,0,sizeof(out));
	memset(head,0,sizeof(head));
	S = 0; T = N - 1; TT = 1;
	int tot = 0;
	
	for (int i=1;i<=m;i++) {
		if (lim < edge[i].w1) {
			continue;
		} else if (lim < edge[i].w2) {
			in[edge[i].v]++;
			out[edge[i].u]++;
		} else {
			in[edge[i].v]++;
			out[edge[i].u]++;
			Add_Edge(edge[i].u, edge[i].v, 2);
		}
	}
	
	for (int i=1;i<=n;i++) {
		if (abs(in[i]-out[i]) & 1) {
			return false;
		} else if (in[i] < out[i]) {
			Add_Edge(S,i,out[i]-in[i]);	
			tot += out[i] - in[i];
		} else if (in[i] > out[i]) {
			Add_Edge(i,T,in[i]-out[i]);
		}
	}
	
	return Dinic() == tot;
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=m;i++) {
		edge[i].u = read();
		edge[i].v = read();
		edge[i].w1 = read();	
		edge[i].w2 = read();
		if (edge[i].w1 > edge[i].w2) {
			swap(edge[i].w1, edge[i].w2);
			swap(edge[i].u, edge[i].v);
		}
		MX = max(MX, edge[i].w2);
		MN = min(MN, edge[i].w1);
	}
	
	int l = MN, r = MX, mid, ret = -1;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid)) ret = mid, r = mid - 1;
		else l = mid + 1;
	}
	if (~ret) printf("%d\n",ret);
	else puts("NIE");
	return 0;
}

【Codeforces 309B】Context Advertising

Qizy 6,350 Comments

题目传送门：http://codeforces.com/problemset/problem/309/B

鏼爷给的倍增的例题
先滑动窗口搞出每个单词开始的合法解
然后搞一搞倍增
于是枚举起点，总体O(nlogn)

然而我是面向数据编程的…..
感觉会被叉掉 ╥﹏╥…

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

const int N = 6000000+9;
const int M = 1000000+9;

char pat[N];
int n,r,c,sta[M],len[M],trans[M][18],position,vout;

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(); r = read(); c = read();
	gets(pat+1);
	for (int i=1,tmp=strlen(pat+1);i<=tmp;i++) if (pat[i] == ' ') {
		pat[i] = 0;
	}
	for (int i=1,w=0;i<=n;i++) {
		sta[i] = ++w;
		len[i] = strlen(pat+w);
		w += len[i];
	}
	for (int i=1,tail=1,tmp=len[1];i<=n;i++) {
		if (len[i] > c) {
			tail = (i + 1) % (n + 1);
			tmp = len[tail];
		} else { 
			while (tail < n && tmp + len[tail+1] + 1 <= c) {
				tmp += len[++tail] + 1;
			}
			trans[i][0] = tail + 1;
			tmp -= len[i] + (tail > i);
			if (!tmp) {
				tail = (i + 1) % (n + 1);
				tmp = len[tail];
			}
		}
	}
	trans[n][0] = n;
	for (int t=1;t<=17;t++) {
		for (int i=1;i<=n;i++) {
			trans[i][t] = max(trans[i][t-1],trans[trans[i][t-1]][t-1]);
		} 
	}
	
	for (int i=1,tmp=0,p=i;i<=n;tmp=0,p=++i) {
		for (int j=17,w=1<<17;~j;j--,w>>=1) if (tmp+w <= r){
			tmp += w;
			p = max(p,trans[p][j]);
			if (p == n+1) break;
		}
		if (p - i > vout) {
			vout = p - i;
			position = i;
		}
 	}
	
	if (vout) for (int i=1,beg=position,end;i<=r&&beg<=n;i++) {
		end = trans[beg][0] - (beg != n || len[trans[beg][0]] > c);
		if (end < beg) break;
		for (int j=beg;j<=end;j++) {
			printf("%s%c",pat+sta[j],j==end?'\n':' ');
		}
		beg = end + 1;
	}
	return 0;
}

【BZOJ 3829】[POI2014] FarmCraft

Qizy 26 Comments

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

来来来，让我们来%Claris：http://www.cnblogs.com/clrs97/p/4403170.html

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

const int N = 500000+9;
const int M = 1000000+9;

int head[N],nxt[M],to[M],g[N],f[N];
int n,tmp[N],beg[N],end[N],tot,C1;

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 void Add_Edge(int u, int v) {
	static int T = 0;
	to[++T] = v; nxt[T] = head[u]; head[u] = T;
	to[++T] = u; nxt[T] = head[v]; head[v] = T;
}

inline bool CMP(const int &a, const int &b) {
	return max(f[a],g[a]+2+f[b]) < (f[b],g[b]+2+f[a]);
}

void DP(int w, int fa) {
	int cnt = 0;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != fa) cnt++;
	}
	beg[w] = tot + 1; 
	end[w] = (tot += cnt); cnt = -1;
	for (int i=head[w];i;i=nxt[i]) if (to[i] != fa) {
		DP(to[i],w);
		g[w] += g[to[i]] + 2;
		tmp[beg[w]+(++cnt)] = to[i];
	}
	if (beg[w] <= end[w]) {
		sort(tmp+beg[w],tmp+end[w]+1,CMP);
	}
	for (int i=beg[w],sum=0;i<=end[w];i++) {
		f[w] = max(f[w], f[tmp[i]] + sum + 1);
		sum += g[tmp[i]] + 2;
	}
}

int main(){
	n = read();
	for (int i=1;i<=n;i++) {
		f[i] = read();
	}
	C1 = f[1];
	for (int i=1;i<n;i++) {
		Add_Edge(read(),read());
	}
	DP(1,1);
	printf("%d\n",max(g[1]+C1,f[1]));
	return 0;
}

【NOIP十连测】[D3T1] 平均数

Qizy 277 Comments

题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/10/test3_problem.pdf
官方题解：http://oi.cyo.ng/wp-content/uploads/2016/10/solution.pdf

这题被挖出是大原题了：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1711
另外™鬼畜出题人硬生生把NOIP搞成NOI Professional有意思吗？
YLUL)A7V{OMTL8]~RL2VL$8

std也是二分，然后搞归并排序
不过我有一种更自然的方法，复杂度一样，常数较大：
首先求出前缀和，记为ai
二分最后的答案记为x
不难发现,平均值大于x的需要满足一下条件：\(\frac{{{a_i} – {a_j}}}{{i – j}} \le x\)
然后化简一下得到：\({a_i} – x \cdot i \le {a_j} – x \cdot j\)
换一句话来说，把ai-x*i作为新序列求逆序对的个数就好啦！
结果被卡常了…..
管他的，51nod上能过

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

const int N = 100000+9;
const double EPS = 0.00001;

LL arr[N],k;
double tmp[N];
int n,Rank[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;
}

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int cnt[N],tot,lim;
	
	inline void init(int w){
		memset(cnt,0,sizeof(cnt));
		tot = 1; lim = n+1; 
		for (int i=w;i<=lim;i+=lowbit(i)) {
			cnt[i]++;
		}
	}
	
	inline int query(int sta) {
		int ret = 0;
		for (int i=sta;i;i-=lowbit(i)) {
			ret += cnt[i];
		}
		return tot - ret;
	}
	
	inline void insert(int w) {
		tot++;
		for (int i=w;i<=lim;i+=lowbit(i)) {
			cnt[i]++;
		}
	}
};

bool judge(double sta) {
	for (register int i=1;i<=n;++i) {
		tmp[i] = arr[i] - sta*i;
	}
	tmp[n+1] = 0;
	sort(tmp+1,tmp+1+n+1);
	for (register int i=0;i<=n;++i) {
		Rank[i] = lower_bound(tmp+1,tmp+1+n+1,arr[i]-sta*i) - tmp;
	} 
	LL ret = 0;
	BIT::init(Rank[0]);
	for (int i=1;i<=n;i++) {
		ret += BIT::query(Rank[i]);
		BIT::insert(Rank[i]);
	}
	return ret >= k;
}

int main(){
	n = read(); cin>>k;
	k = (LL)n*(n+1) / 2 - k + 1;
	for (int i=1;i<=n;i++) {
		arr[i] = arr[i-1] + read();
	}
	double L = 0, R = 1e9, mid;
	while (R - L > EPS) {
		mid = (L + R) / 2;
		if (judge(mid)) {
			R = mid;
		} else {
			L = mid;
		}
	}
	printf("%.4lf",(R+L)/2);
	return 0;
}

【NOIP十连测】[D1T2] Tourist Attractions

Qizy 2 Comments

相关链接

题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/10/noip_test1_statements.pdf

解题报告

虽然没能A掉
但明明是70分的dp却交成了40分的暴力
仍然不高兴 ＞︿＜

四个点的话，就是三条边
考虑枚举中间的那一条边
则其对答案的贡献就是两点入度的乘积
但3元环不符合题意
于是搞一搞bitset可以在O(n/32)的时间复杂度内统计三元环

Code

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

const int N = 1500+9;

LL vout; 
int n,in[N];
bitset<N> edg[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;
}

int main(){
	n = read(); char pat[N];
	for (int j=1;j<=n;j++) {
		scanf("%s",pat+1);
		for (int i=1;i<=n;i++) 
			edg[j][i] = pat[i] - '0',
			in[i] += pat[i] - '0';
	}
	for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (edg[i][j]) {
		vout += (LL)(in[i] - 1) * (in[j] - 1);
		vout -= (edg[i] & edg[j]).count();
	}
	printf("%lld\n",vout);
	return 0;
}

最后来撸一发Claris的手写bitset：http://paste.ubuntu.com/23262667/
想一想好像这么写很优越的样子！

【NOIP十连测】[D1T1] String Master

Qizy 22 Comments

题目传送门：http://oi.cyo.ng/wp-content/uploads/2016/10/noip_test1_statements.pdf

std是O(n^3)的算法？
明明NOIP范围内可以O(n^2logn)搞的！
就是二分长度，然后用滑动窗口搞一搞

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

const int N = 300+9;
const int SGZ = 27;

int n,k;
char S[N],T[N];
queue<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 judge(int len) {
	for (int d=0,cur=0,p1,p2,tmp;d<=n-len;d++,cur=0) {
		while (!que.empty()) que.pop(); que.push(0); p1 = 0, p2 = p1 + d;
		for (int i=1;i<len;i++) 
			tmp = (S[++p1] != T[++p2]), 
			cur += tmp, que.push(tmp);
		while (p2 < n) {
			tmp = (S[++p1] != T[++p2]);
			cur += tmp, cur -= que.front();
			que.pop(), que.push(tmp); 
			if (cur <= k) return true;
		}
	} 
	for (int d=0,cur=0,p1,p2,tmp;d<=n-len;d++,cur=0) {
		while (!que.empty()) que.pop(); que.push(0); p1 = 0, p2 = p1 + d;
		for (int i=1;i<len;i++) 
			tmp = (T[++p1] != S[++p2]), 
			cur += tmp, que.push(tmp);
		while (p2 < n) {
			tmp = (T[++p1] != S[++p2]);
			cur += tmp, cur -= que.front();
			que.pop(), que.push(tmp); 
			if (cur <= k) return true;
		}
	} 
	return false;
}

int main(){
	freopen("master.in","r",stdin);
	freopen("master.out","w",stdout);
	n = read(); k = read();
	scanf("%s%s",S+1,T+1);
	int l=1,r=n,ret=0;
	while (l <= r) {
		int mid = l + r >> 1;
		if (judge(mid)) ret = mid, l = mid+1;
		else r = mid-1;
	} 
	printf("%d\n",ret);
	return 0;
}

【BZOJ 4513】[SDOI2016] 储能表

Qizy 2 Comments

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

先来%一波Menci的强行找规律(:з」∠)：https://dn-menci.qbox.me/sdoi2016-table/
然后就是std用的数位DP：http://www.ruiker1997.tk/bzoj-4513

一直感觉这个题目的数位DP很牵强
于是一直尝试使用以前的数位DP的写法来写
然后发现，嘴巴ac还是挺容易的，但真要写出来，还真心不好写
于是代码就算了吧。

—– UPD 2016.9.29 —–
还是补一份代码吧
以前数位DP都不是这么写的
不过感觉这么写，如果没有多组询问还是挺清真的

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

LL f[62][2][2][2],g[62][2][2][2],n,m,MOD,k; 

int main(){
	int T; cin>>T; while (T--) {
		cin>>n>>m>>k>>MOD;
		memset(f,0,sizeof(f)); memset(g,0,sizeof(g));
		g[61][0][0][0] = 1;
		for (int i=60;~i;i--) {
			int t1 = (n>>i)&1, t2 = (m>>i)&1, t3 = (k>>i)&1;
			for (int a=0;a<2;a++) for (int b=0;b<2;b++) for (int c=0;c<2;c++) if (g[i+1][a][b]) {
				for (int x=0,w,wa,wb,wc;x<2;x++) for (int y=0;y<2;y++) {
					if (w=x^y, (!a&&x>t1) || (!b&&y>t2) || (!c&&w<t3)) continue;
					wa = (a||x<t1); wb = (b||y<t2); wc = (c||w>t3);
					(g[i][wa][wb][wc] += g[i+1][a][b]) %= MOD;
					(f[i][wa][wb][wc] += ((f[i+1][a][b] + (((w-t3)*((1LL<<i)%MOD))%MOD)*g[i+1][a][b]%MOD)%MOD + MOD) % MOD) %= MOD;
				}
			}
		}	
		cout<<f[0][1][1][1]<<endl;
	}
	return 0;
}

【Codeforces 712C】Memory and De-Evolution

Qizy 2 Comments

题目传送门：http://codeforces.com/contest/712/problem/C
官方题解：http://codeforces.com/blog/entry/47050
中文题面：http://blog.csdn.net/queuelovestack/article/details/52503162

这个题目考试的时候，看到都有1000+的人A掉了
然而我还是一脸懵逼
虽然看了题解以后，感觉题还不错，但为什么一点不觉得这个题好QAQ
一定是被恶心到了…..

考虑倒着贪心。
首先每一条边，只会成为限制，且这个限制越大越好
所以，肯定是每一次选择一条边加到上限
至于是哪一条边，肯定是最短的那条边对于周长的贡献最大

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

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(){
	int arr[4],pur=read(),vout=0;
	arr[1] = arr[2] = arr[3] = read();
	while (arr[1] < pur) {
		arr[1] = min(pur,arr[2]+arr[3]-1);
		sort(arr+1,arr+1+3); vout++;
	} cout<<vout<<endl;
	return 0;
}

【Codeforces 715B】Complete The Graph

Qizy 92 Comments

题目传送门：http://codeforces.com/contest/716/problem/D
官方题解：http://codeforces.com/blog/entry/47169

这题很好玩，有两种写法。

1）暴力最短路，复杂度O(nmlogn)
做法就是每一次找最短路，然后改一改

2）神奇二分，复杂度O(mlognlogm)
将可更改的边拉出来，排成一溜
二分一个点k，使1~k的边为1，其余边为INF
终止条件：k时最短路<=l,k-1时最短路>L
于是第k条边就是关键边，只用考虑这条边的长度即可
感觉好神！

考试的时候，我写的是第一种

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

const LL N = 1000+9;
const LL M = 20000+9;
const LL INF = 1e14;

LL head[N],to[M],nxt[M],cost[M],U[M],V[M],dis[N],n,m,L,S,T,sign[M],ty,inq[N],sur[N];
queue<LL> 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;
}

inline void Add_Edge(LL u, LL v, LL d) {
	static LL TT = 1;
	to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; cost[TT] = d;
	to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; cost[TT] = d;
}

inline LL SPFA(){
	for (int i=1;i<=n;i++) dis[i] = INF;
	dis[S] = 0; que.push(S), inq[S] = 1;
	
	while (!que.empty()) {
		LL w = que.front(); que.pop(); inq[w] = 0;
		for (LL i=head[w];i;i=nxt[i]) if (~cost[i] && dis[to[i]] > dis[w]+cost[i]) {
			dis[to[i]] = dis[w] + cost[i]; sur[to[i]] = i;
			if (!inq[to[i]]) que.push(to[i]), inq[to[i]] = 1;
		}
	} return dis[T];
}

int main(){
	n = read(); m = read(); L = read(); S = read() + 1; T = read() + 1;
	for (LL i=1,tmp;i<=m;i++) {
		U[i] = read()+1, V[i] = read()+1; tmp = read();
		if (!tmp) tmp = -1, sign[i] = 1;
		Add_Edge(U[i],V[i],tmp);
	}
	if (SPFA() < L) cout<<"NO", exit(0);
	for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = 1;
	if ((ty=SPFA()) > L) cout<<"NO", exit(0);
	for (LL i=1;i<=m;i++) if (sign[i]) cost[i*2] = cost[i*2+1] = INF;
	LL w = T,len_tmp; while (w != S) {if(sign[sur[w]/2]) cost[sur[w]] = cost[sur[w]^1] = 1; w = to[sur[w]^1];}
	while ((len_tmp=SPFA()) < L) 
		for (w=T;w!=S;w=to[sur[w]^1]) if (sign[sur[w]/2]) {
			cost[sur[w]] += L - len_tmp, cost[sur[w]^1] += L - len_tmp; break;}
	cout<<"YES"<<endl;
	for (LL i=1;i<=m;i++) 
		if (sign[i] && cost[i*2] == -1) printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,L+1);
		else printf("%I64d %I64d %I64d\n",U[i]-1,V[i]-1,cost[i*2]);
	return 0;
}

【Codeforces 715A】Plus and Square Root

Qizy 2 Comments

题目传送门：http://codeforces.com/contest/715/problem/A
官方题解：http://codeforces.com/blog/entry/47169

这™构造题，又没有想出来QAQ
考验人类智慧的东西，怎么写题解？
还是去看官方题解吧…

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

int main(){
	int n; cin>>n; cout<<2<<endl;
	for (LL i=2;i<=n;i++) cout<<i*(i+1)*(i+1)-i+1<<endl;
	return 0;
}

【Codeforces 713B】Searching Rectangles

Qizy 21 Comments

题目传送门：http://codeforces.com/contest/714/problem/D

CF上做的第一道交互题！
然而考场上并没能A掉QAQ
就是二分出几个关键点，然后暴力问一问

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

int n,x[5],y[5],vout[10];

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 judge(int _x1,int _y1,int _x2,int _y2) {
	printf("? %d %d %d %d\n",_x1,_y1,_x2,_y2);
	fflush(stdout);
	return read();
}

inline bool BETTER(int x1, int y1, int x2, int y2, int x3, int y3, int x4, int y4){
	if (!vout[1]) return true;
	LL s1 = (LL)(vout[3]-vout[1] + 1)*(vout[4]-vout[2] + 1) + (LL)(vout[7]-vout[5] + 1)*(vout[8]-vout[6] + 1);
	LL s2 = (LL)(x2 - x1 + 1) * (y2 - y1 + 1) + (LL)(x4 - x3 + 1) * (y4 - y3 + 1);
	return s2 < s1;
}

int main(){
	n = read();
	int l = 1, r = n, mid, ret;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(1,1,mid,n) >= 1) ret = mid, r = mid-1;
		else l = mid+1; 
	} x[1] = ret;
	l = ret, r = n, ret = 0;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(1,1,mid,n) >= 2) ret = mid, r = mid-1;
		else l = mid+1;
	} x[3] = ret;
	l = 1, r = n, ret = 0;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid,1,n,n) >= 1) ret = mid, l = mid+1;
		else r = mid-1;
	} x[2] = ret;
	l = 1, r = x[2], ret = 0;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(mid,1,n,n) >= 2) ret = mid, l = mid+1;
		else r = mid - 1;
	} x[4] = ret;
	
	l = 1, r = n, ret = 0;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(1,1,n,mid) >= 1) ret = mid, r = mid-1;
		else l = mid+1;
	} y[1] = ret;
	l = y[1], r = n, ret = 0;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(1,1,n,mid) >= 2) ret = mid, r = mid-1;
		else l = mid+1; 
	} y[3] = ret;
	l = 1, r = n, ret = 0;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(1,mid,n,n) >= 1) ret = mid, l = mid+1;
		else r = mid-1;
	} y[2] = ret;
	l = 1, r = y[2], ret = 0;
	while (l <= r) {
		mid = l + r >> 1;
		if (judge(1,mid,n,n) >= 2) ret = mid, l = mid+1;
		else r = mid-1;
	} y[4] = ret;
	
	sort(x+1,x+5); sort(y+1,y+5);
	for (int s=1;s<=4;s++) for (int i=s+1;i<=4;i++) for (int j=1;j<=4;j++) for (int k=j+1;k<=4;k++) 
		if (judge(x[s],y[j],x[i],y[k]) == 1) { int x1,x2,y1,y2;
			for (int u=1;u<=4;u++) if (u != i && u != s) {x1=u; break;}
			for (int u=x1+1;u<=4;u++) if (u != i && u != s) {x2=u; break;}
			for (int u=1;u<=4;u++) if (u != j && u != k) {y1 = u; break;}
			for (int u=y1+1;u<=4;u++) if (u != j && u != k) {y2=u;break;}
			if (x[x1] > x[i] || x[x2] < x[s] || y[y1] > y[k] || y[y2] < y[j])
			if (judge(x[x1],y[y1],x[x2],y[y2]) == 1 && BETTER(x[s],y[j],x[i],y[k],x[x1],y[y1],x[x2],y[y2])) 
				vout[1]=x[s],vout[2]=y[j],vout[3]=x[i],vout[4]=y[k],vout[5]=x[x1],vout[6]=y[y1],vout[7]=x[x2],vout[8]=y[y2];			
		}
	putchar('!');
	for (int i=1;i<=8;i++) printf(" %d",vout[i]);
	return 0;
}

【BZOJ 3237】[AHOI2013] 连通图

Qizy 32 Comments

相关链接

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

解题报告

这个题目，真心没辙
最开始想，我们可以搞一个像Sparse_Table一样的玩意，然后用O(n)的时间单次合并并查集
然而这样的复杂度最后算下来和暴力没差多少QAQ
所以看了题解，写了网上提到的分治算法
感觉好神！
不是整体二分，也不是CDQ，就是分治，但好神！
赶紧Mark

Code

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

const int N = 100000+9;
const int M = 1000000+9; 
const int SGZ = 5;

int u[M],v[M],is_del[M],vout[N],idx;
int fa[N],n,m,k,sz[N],edg[N][SGZ];

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

namespace Union_Find_Set{
	#define UFS Union_Find_Set
	int t1[M*5],t2[M*5],cnt;
	
	inline int find(int w){
		int f = fa[w], tmp;
		while (fa[f] != f) f = fa[f];
		while (w != f) t1[++cnt] = w, t2[cnt] = fa[w], fa[w] = f, w = t2[cnt];
		return f; 
	}
	
	inline void Union(int a, int b) {
		int f1 = find(a), f2 = find(b); 
		if (f1 != f2) ++cnt, fa[t1[cnt]=t2[cnt]=f1] = f2; 
	}
	
	inline void reset(int Tag) {
		for (;cnt>Tag;cnt--) 
			fa[t1[cnt]] = t2[cnt];
	}
};

void solve(int l, int r){
	int cur_time = UFS::cnt; 
	if (l == r) {
		vout[l] = 1; 
		for (int i=1,w;i<=sz[l] && vout[l];i++) { 
			w = edg[l][i];
			if (UFS::find(u[w]) != UFS::find(v[w])) vout[l] = 0;
		} 
		UFS::reset(cur_time);
	} else {
		int mid = l + r + 1 >> 1; ++idx; 
		for (int i=mid;i<=r;i++) for (int j=1;j<=sz[i];j++) is_del[edg[i][j]] = idx;
		for (int i=l;i<mid;i++) for (int j=1,w;j<=sz[i];j++) {
			w = edg[i][j];
			if (is_del[w] != idx) UFS::Union(u[w],v[w]);
		}
		solve(mid,r);
		UFS::reset(cur_time); ++idx;
		for (int i=l;i<mid;i++) for (int j=1;j<=sz[i];j++) is_del[edg[i][j]] = idx;
		for (int i=mid;i<=r;i++) for (int j=1,w;j<=sz[i];j++) {
			w = edg[i][j];
			if (is_del[w] != idx) UFS::Union(u[w],v[w]);
		}
		solve(l,mid-1);
		UFS::reset(cur_time);
	}
}

int main(){
	n = read(); m = read();
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int i=1;i<=m;i++) u[i] = read(), v[i] = read();
	k = read();
	for (int i=1;i<=k;i++) {
		sz[i] = read();
		for (int j=sz[i];j;--j) 
			is_del[edg[i][j] = read()] =-1;
	} 
	for (int i=1;i<=m;i++) if (~is_del[i]) UFS::Union(u[i],v[i]);
	solve(1,k);
	for (int i=1;i<=k;i++) puts(vout[i]?"Connected":"Disconnected");
	return 0; 
}

感觉并查集撤销那里，应该用持久化并查集才对吧
感觉用栈的话，时间复杂度不对啊

另外，看看Memphis不到1s的算法，应该是有什么奇技淫巧
但找不到任何相关资料QAQ

—————————— UPD 2017.2.1 ——————————
这题还可以用线性基搞一搞
另外，并查集撤销那里没问题，不需要可持久化

【BZOJ 2738】矩阵乘法

Qizy 27 Comments

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

这个题，真的是妙啊！
整体二分看起来很好用的样子！

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

const int N = 500+9;
const int M = 250000+9;
const int Q = 60000+9;

struct Point{int val,x,y;inline bool operator < (const Point &B) const {return val < B.val;}}p[M];
struct Query{int k,x1,x2,y1,y2,id;}q[Q],buf[Q];

int n,m,vout[Q];

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

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int sum[N][N];
	
	inline void modify(int x, int y, int delta) {
		if (x <= 0 || y <= 0) return;
		for (int j=y;j<=n;j+=lowbit(j)) for (int i=x;i<=n;i+=lowbit(i))
			sum[i][j] += delta;
	}
	
	inline int query(int x, int y){
		if (x <= 0 || y <= 0) return 0;
		int ret = 0;
		for (int j=y;j;j-=lowbit(j)) for (int i=x;i;i-=lowbit(i))
			ret += sum[i][j];
		return ret;
	}
};

void solve(int l, int r, int L, int R) {
	if (l == r) for (int i=L;i<=R;i++) vout[q[i].id] = p[l].val;
	else {
		int mid = l + r + 1 >> 1,ls=L-1,rs=R+1;
		for (int i=l;i<=mid-1;i++) BIT::modify(p[i].x,p[i].y,1);
		for (int i=L,tmp;i<=R;i++) {
			tmp = BIT::query(q[i].x1-1,q[i].y1-1);
			tmp += BIT::query(q[i].x2,q[i].y2);
			tmp -= BIT::query(q[i].x1-1,q[i].y2);
			tmp -= BIT::query(q[i].x2,q[i].y1-1);
			if (tmp >= q[i].k) buf[++ls] = q[i];
			else q[i].k -= tmp, buf[--rs] = q[i];
		}
		memcpy(q+L,buf+L,sizeof(buf[0])*(R-L+1));
		for (int i=l;i<=mid-1;i++) BIT::modify(p[i].x,p[i].y,-1);
		if (L <= ls) solve(l,mid-1,L,ls);
		if (rs <= R) solve(mid,r,rs,R);
	}
} 

int main(){
	n = read(); m = read();
	for (int j=1,t=1;j<=n;j++) for (int i=1;i<=n;i++,t++) 
		p[t].x = i, p[t].y = j, p[t].val = read();
	for (int i=1,a,b,c,d,e,f;i<=m;i++) 
 		q[i].y1 = read(), q[i].x1 = read(),
		q[i].y2 = read(), q[i].x2 = read(),
		q[i].k = read(), q[i].id = i;
	sort(p+1,p+1+n*n);
	solve(1,n*n,1,m);
	for (int i=1;i<=m;i++) printf("%d\n",vout[i]);
	return 0;
}

【BZOJ 1176】[Balkan2007] Mokia

Qizy 25 Comments

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

这货二维BIT上不了
于是上CDQ

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

const int M = 200000+9;

struct OPT{
	int x,y,id,delta;
	inline OPT() {}
	inline OPT(int X, int Y, int ID, int DEL):x(X),y(Y),id(ID),delta(DEL){}
	inline bool operator < (const OPT &B) const {return x < B.x;}
}opt[M],buf[M];
int n,m,query_cnt,vout[M],hash[M*2],cnt;

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

namespace Fenwick_Tree{
	#define BIT Fenwick_Tree
	#define lowbit(x) ((x)&-(x))
	int sum[M*2];
	
	inline void modify(int w, int v){
		for (int i=w;i<=cnt;i+=lowbit(i)) sum[i] += v;
	}
	
	inline int query(int w){
		int ret = 0;
		for (int i=w;i;i-=lowbit(i)) ret += sum[i];
		return ret;
	}
};

void solve(int l, int r) {
	if (l >= r) return;
	int mid = l + r + 1 >> 1;
	solve(l,mid-1);	
	solve(mid,r);
	
	int p1 = l, p2 = mid;
	for (;p2<=r;p2++) {
		for (;p1 < mid && opt[p1].x <= opt[p2].x;p1++)
			if (!opt[p1].id) BIT::modify(opt[p1].y,opt[p1].delta);
		if (opt[p2].id) vout[opt[p2].id] += BIT::query(opt[p2].y)*opt[p2].delta;
	}
	
	for (int i=l;i<p1;i++) if (!opt[i].id) BIT::modify(opt[i].y,-opt[i].delta);
	merge(opt+l,opt+mid,opt+mid,opt+r+1,buf+1);
	memcpy(opt+l,buf+1,sizeof(opt[0])*(r-l+1));
}

int main(){
	read(); n = read();
	for (int t=read(),x1,y1,x2,y2;t!=3;t=read()) {
		if (t == 1) {
			opt[++m].x = read();
			opt[m].y = hash[++cnt] = read(); 
			opt[m].delta = read();
		} else {
			x1 = read(); y1 = hash[++cnt] = read(); hash[++cnt] = y1 - 1;
			x2 = read(); y2 = hash[++cnt] = read(); hash[++cnt] = y2 - 1;
			opt[++m].x = x1-1; opt[m].y = y1-1; opt[m].delta = 1;  opt[m].id = ++query_cnt;
			opt[++m].x = x2;   opt[m].y = y2;   opt[m].delta = 1;  opt[m].id = query_cnt;
			opt[++m].x = x1-1; opt[m].y = y2;   opt[m].delta = -1; opt[m].id = query_cnt;
			opt[++m].x = x2;   opt[m].y = y1-1; opt[m].delta = -1; opt[m].id = query_cnt;
		}
	}
	sort(hash+1,hash+1+cnt);
	cnt = unique(hash+1,hash+1+cnt) - hash - 1;
	for (int i=1;i<=m;i++) opt[i].y = lower_bound(hash+1,hash+1+cnt,opt[i].y) - hash;
	solve(1,m);
	for (int i=1;i<=query_cnt;i++) printf("%d\n",vout[i]);
	return 0;
}

另外，这题如果强制在线的话，貌似可以上主席树？