【BZOJ 4881】[Lydsy2017年5月月赛] 线段游戏

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4881
神犇题解:http://krydom.com/bzoj4881/

解题报告

不难发现,这就是一个二分图染色问题
那么我们首先需要判无解
分析题目我们可以发现,如果存在长度为$x+2$的奇环,那么一定存在长度为$x$的奇环
于是我们只需要判有没有长度为$3$的奇环,然后我们发现这就是三个递减的数,于是随便搞一搞就好
至于输出方案数,就是$2$的连通块个数次方

Code

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

const int N = 100009;
const int MOD = 998244353;

int n, p[N], mx[N], mn[N];
stack<int> stk; 

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

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		p[i] = read();
	}
	mx[1] = p[1];
	for (int i = 2; i <= n; i++) {
		mx[i] = max(mx[i - 1], p[i]);
	}
	mn[n] = p[n];
	for (int i = n - 1; i; i--) {
		mn[i] = min(mn[i + 1], p[i]);
	}
	for (int i = 2; i < n; i++) {
		if (mx[i - 1] > p[i] && p[i] > mn[i + 1]) {
			puts("0");
			exit(0);
		}
	}
	for (int i = 1; i <= n; i++) {
		if (stk.empty() || stk.top() < p[i]) {
			stk.push(p[i]);
		} else {
			int tt = stk.top();
			for (; !stk.empty() && stk.top() > p[i]; stk.pop());
			stk.push(tt);
		}
	}
	int ans = 1;
	for (int i = 1; i <= (int)stk.size(); i++) {
		ans = (ans << 1) % MOD;
	}
	cout<<ans<<endl;
	return 0;
}

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

【Codeforces 706E】Working routine

题目传送门:http://codeforces.com/problemset/problem/706/E
官方题解:http://codeforces.com/blog/entry/46510

这个题感觉出得很好啊!
没想到链表还能这么考!秒啊!
23781763871263

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

const int MAXN = 1000+9;

int d[MAXN*MAXN],r[MAXN*MAXN],mat[MAXN*MAXN],m,n,q,vout[MAXN][MAXN];

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

#define id(x, y) ((x)+1 + (y)*(n+2))

inline void change(int x1, int y1, int x2, int y2, int x, int y){
	int p1 = id(0,0), p2 = id(0,0); 
	for (int j=1;j<y1;j++) p1 = d[p1]; for (int i=1;i<=x1;i++) p1 = r[p1];
	for (int j=1;j<y2;j++) p2 = d[p2]; for (int i=1;i<=x2;i++) p2 = r[p2];
	for (int i=1;i<=x;i++) swap(d[p1], d[p2]), p1 = r[p1], p2 = r[p2];
	p1 = id(0,0), p2 = id(0,0); 
	for (int j=1;j<y1+y;j++) p1 = d[p1]; for (int i=1;i<=x1;i++) p1 = r[p1];
	for (int j=1;j<y2+y;j++) p2 = d[p2]; for (int i=1;i<=x2;i++) p2 = r[p2];
	for (int i=1;i<=x;i++) swap(d[p1], d[p2]), p1 = r[p1], p2 = r[p2];
	
	
	p1 = id(0,0), p2 = id(0,0); 
	for (int i=1;i<x1;i++) p1 = r[p1]; for (int j=1;j<=y1;j++) p1 = d[p1]; 
	for (int i=1;i<x2;i++) p2 = r[p2]; for (int j=1;j<=y2;j++) p2 = d[p2];
	for (int j=1;j<=y;j++) swap(r[p1], r[p2]), p1 = d[p1], p2 = d[p2];
	p1 = id(0,0), p2 = id(0,0); 
	for (int i=1;i<x1+x;i++) p1 = r[p1]; for (int j=1;j<=y1;j++) p1 = d[p1]; 
	for (int i=1;i<x2+x;i++) p2 = r[p2]; for (int j=1;j<=y2;j++) p2 = d[p2];
	for (int j=1;j<=y;j++) swap(r[p1], r[p2]), p1 = d[p1], p2 = d[p2];
}

inline void trans(){
	int head = id(0,0); 
	for (int j=1;j<=m;j++) {
		head = d[head];
		for (int i=1,w=r[head];i<=n;i++,w=r[w])
			vout[i][j] = mat[w];
	}
	for (int j=1;j<=m;j++) {for (int i=1;i<=n;i++) printf("%d ",vout[i][j]); printf("\n");}
}

int main(){
	m = read(); n = read(); q = read();
	for (int j=1;j<=m;j++) for (int i=1;i<=n;i++) mat[id(i,j)] = read();
	for (int j=0;j<=m+1;j++) for (int i=0;i<=n+1;i++) d[id(i,j)] = id(i,j+1), r[id(i,j)] = id(i+1,j);
	
	for (int k=1,x1,x2,y1,y2,lh,lw;k<=q;k++) {
		y1 = read(), x1 = read();
		y2 = read(), x2 = read();
		lh = read(), lw = read();
		change(x1,y1,x2,y2,lw,lh);
	} trans();
	return 0;
}