【Tricks】Hello World!

之前见过这货的低配版
也是全部define成_,然后搞

但今天看到这货,用了define能组合的特点
真的是变态啊_(:з」∠)_

#define _________ }  
#define ________ putchar  
#define _______ main  
#define _(a) ________(a);  
#define ______ _______(){  
#define __ ______ _(0x48)_(0x65)_(0x6C)_(0x6C)  
#define ___ _(0x6F)_(0x2C)_(0x20)_(0x77)_(0x6F)  
#define ____ _(0x72)_(0x6C)_(0x64)_(0x21)  
#define _____ __ ___ ____ _________  
#include<stdio.h>  
_____

【日常小测】回转寿司

相关链接

题目传送门: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;
}

【HDU 5716】带可选字符的多字符串匹配

相关链接

题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5716
神犇题解:http://www.cnblogs.com/clrs97/p/5985648.html

解题报告

这货$KMP$是不可做的,于是考虑用$bitset$来优化暴力
定义$v[i][j]$为文本串第$i$位是否能匹配模式串第$j$位
定义$f[i][j]$为第$i$种字符能否匹配模式串第$j$位
那么$v[i][j] = v[i – 1][j – 1] \ and \ f[s[i]][j]$
然后数组第二维用$bitset$优化,时间复杂度:$O(\frac{nm}{64})$

Code

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

const int N = 2000009;
const int M = 600;
const int SGZ = 100;

char s[N], sgz[SGZ];
bitset<M> v, f[SGZ];

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

inline int id(char c) {
	if ('0' <= c && c <= '9') {
		return c - '0' + 1;
	} else if ('a' <= c && c <= 'z') {
		return c - 'a' + 11;
	} else if ('A' <= c && c <= 'Z'){
		return c - 'A' + 37;
	} else {
		return 0;
	}
}

int main() {
	while (gets(s + 1)) {
		int n = strlen(s + 1), m = read();
		v.reset();
		for (int i = 0; i < SGZ; i++) {
			f[i].reset();
		}
		for (int i = 1; i <= m; i++) {
			int SGZ = read();
			scanf("%s", sgz + 1);
			for (int j = 1; j <= SGZ; j++) {
				f[id(sgz[j])][i] = 1;
			}
		}
		bool CantMatch = 1;
		for (int i = 1; i <= n; i++) {
			v = (v << 1) & f[id(s[i])];
			v[1] = f[id(s[i])][1];
			if (v[m]) {
				printf("%d\n", i - m + 1);
				CantMatch = 0;
			}
		}
		if (CantMatch) {
			puts("NULL");
		}
		getchar();
	}
	return 0;
}

—————————— UPD 2017.7.3 ———————————
这题的简单拓展:http://www.lydsy.com/JudgeOnline/problem.php?id=4924

【日常小测】异或与区间加

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题又是一道多算法互补的题目
通过分类处理使复杂度达到$O((n+m)\sqrt{n})$
具体来讲是将以下两个算法结合:

1. 枚举右端点的值,若左端点的合法位置超过$\sqrt{n}$个

考虑每一个左右端点应该加减多少,使用前缀和技巧将复杂度优化到$O(n + m)$
具体细节不想写了,有点麻烦_(:з」∠)_
然后因为合法位置超过了$\sqrt{n}$个,所以这种情况至多出现$\sqrt{n}$个,复杂度符合要求

2. 其他情况

因为左端点不超过$\sqrt{n}$个,所以可以排序之后依次处理
使用分块来维护左端点的值,单次修改是$\sqrt{n}$的,单次查询是$O(1)$的

Code

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

const int N = 150009;
const int MOD = 1073741824;
const int blk_sz = 800;

int n, m, k, a[N];
UI a1[N], ans[N], blk_tag[N], tag[N];
vector<int> num, pos_list[N];
vector<pair<int, int> > left_list[N], right_list[N];
struct Query{
	int l, r, w;
	inline bool operator < (const Query &QQQ) const {
		return r > QQQ.r;
	} 
}q[N];

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 int find(int x) {
	int l = 0, r = num.size() - 1, mid;
	while (l <= r) {
		mid = l + r >> 1;
		if (num[mid] == x) {
			return mid;
		} else if (num[mid] < x) {
			l = mid + 1;
		} else {
			r = mid - 1;
		}
	}
	return -1;
}

inline void solve(int A, int B) {
	static UI a2[N], cur;
	memset(a2, 0, sizeof(a2));
	for (int i = 1; i <= n; i++) {
		a2[i] = a2[i - 1] + (a[i] == num[B]);
	}
	cur = 0;
	for (int i = n; i; i--) {
		if (a[i] == num[B]) {
			cur += a1[i];
		}
		if (a[i - 1] == num[A]) {
			ans[i] += cur;
		}
		for (int j = 0; j < (int)left_list[i].size(); ++j) {
			cur -= (UI)left_list[i][j].second * (a2[left_list[i][j].first] - a2[i - 1]);
		}
	}
	memset(a2, 0, sizeof(a2));
	for (int i = 1; i <= n; ++i) {
		a2[i] = a2[i - 1] + (a[i - 1] == num[A]);
	}
	cur = 0;
	for (int i = 1; i <= n; i++) {
		if (a[i - 1] == num[A]) {
			cur -= a1[i];
		}
		if (a[i] == num[B]) {
			ans[i + 1] += cur;
		}
		for (int j = 0; j < (int)right_list[i].size(); ++j) {
			cur += (UI)right_list[i][j].second * (a2[i] - a2[right_list[i][j].first - 1]);
		}
	}
}

int main() {
	freopen("xor.in", "r", stdin);
	freopen("xor.out", "w", stdout);
	n = read(); m = read(); k = read();
	num.push_back(0);
	for (int i = 1; i <= n; ++i) {
		a[i] = a[i - 1] ^ read();
		num.push_back(a[i]);
	}
	sort(num.begin(), num.end());
	num.resize(unique(num.begin(), num.end()) - num.begin());
	for (int i = 0; i <= n; i++) {
		int pp = find(a[i]);
		pos_list[pp].push_back(i);
	}
	for (int i = 1, l, r, w; i <= m; ++i) {
		l = q[i].l = read();
		r = q[i].r = read();
		w = q[i].w = read();	
		left_list[l].push_back(make_pair(r, w));
		right_list[r].push_back(make_pair(l, w));
		a1[l] += w; 
		a1[r + 1] -= w;
	}
	sort(q + 1, q + 1 + m);
	for (int i = 1; i <= n; ++i) {
		a1[i] += a1[i - 1];
	}
	for (int i = 0; i < (int)num.size(); i++) {
		int r = i, l = find(num[i] ^ k);
		if (l != -1 && (int)pos_list[l].size() > blk_sz) {
			solve(l, r);
		}
	}
	for (int r = n, cur = 0; r; r--) {
		while (cur < m && q[cur + 1].r >= r) {
			++cur;
			for (int i = q[cur].l, lim = min(q[cur].r, (q[cur].l / blk_sz + 1) * blk_sz - 1); i <= lim; ++i) {
				tag[i] += q[cur].w;
			}
			for (int i = q[cur].l / blk_sz + 1, lim = q[cur].r / blk_sz - 1; i <= lim; ++i) {
				blk_tag[i] += q[cur].w;
			}
			for (int i = max(q[cur].r / blk_sz, q[cur].l / blk_sz + 1) * blk_sz; i <= q[cur].r; ++i) {
				tag[i] += q[cur].w;
			}
		}
		int t = find(a[r] ^ k);
		if (t != -1 && (int)pos_list[t].size() <= blk_sz) {
			for (int tt = 0; tt < (int)pos_list[t].size(); ++tt) {
				int l = pos_list[t][tt] + 1;
				if (l <= r) {
					ans[l] += tag[l] + blk_tag[l / blk_sz];
					ans[r + 1] -= tag[l] + blk_tag[l / blk_sz];
				} else {
					break;
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		ans[i] += ans[i - 1];
		printf("%d ", ans[i] % MOD);
	}
	return 0;
}

【日常小测】友好城市

相关链接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-statements.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2017/06/claris_contest_4_day2-solutions.pdf

解题报告

这题的前置知识是把求$SCC$优化到$O(\frac{n^2}{32})$
具体来说,就是使用$bitset$配合$Kosaraju$算法

有了这个技能以后,我们配合$ST$表来实现提取一个区间的边的操作
这样的话,总的时间复杂度是:$O(\frac{(\sqrt{m} \log m + q) n^2}{32}+q \sqrt{m})$

然后我懒,没有用$ST$表,用的莫队,时间复杂度是$O(\frac{(m + q) n^2}{32}+q \sqrt{m})$
调一调块大小,勉勉强强卡过去了

Code

#include<bits/stdc++.h>
#define LL long long
#define UI unsigned int 
#define lowbit(x) ((x)&-(x))
using namespace std;

const int N = 159;
const int M = 300009;
const int QQ = 50009;
const int BlockSize = 1200;
const UI ALL = (1ll << 32) - 1;

int n, m, q, U[M], V[M], ans[QQ]; 
struct Query{
	int l, r, blk, id;
	inline bool operator < (const Query &Q) const {
		return blk < Q.blk || (blk == Q.blk && r < Q.r);
	}
}qy[QQ];
struct Bitset{
	UI v[5];
	inline void flip(int x) {
		v[x >> 5] ^= 1 << (x & 31);
	}
	inline void set(int x) {
		v[x >> 5] |= 1 << (x & 31);
	}
	inline void reset() {
		memset(v, 0, sizeof(v));
	}
	inline bool operator [](int x) {
		return v[x >> 5] & (1 << (x & 31));
	}
}g[N], rg[N], PreG[M / BlockSize + 9][N], PreRG[M / BlockSize + 9][N];

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 AddEdge(int u, int v, Bitset *a1, Bitset *a2) {
 	a1[u].set(v);
 	a2[v].set(u);
}

class Kosaraju{
	vector<int> que;
	Bitset vis;
public:
	inline int solve() {
		vis.reset();
		que.clear();
		for (int i = 1; i <= n; ++i) {
			if (!vis[i]) {
				dfs0(i);
			}
		}
		vis.reset();
		int ret = 0;
		for (int j = n - 1; ~j; j--) {
			int i = que[j];
			if (!vis[i]) {
				int cnt = dfs1(i);
				ret += cnt * (cnt - 1) / 2;
			}
		}
		return ret;
	}
private:
	inline void dfs0(int w) {
		vis.flip(w);
		for (int i = 0; i < 5; i++) {
			for (UI j = g[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					dfs0(t);
				}
			}
		}
		que.push_back(w);
	}
	inline int dfs1(int w) {
		vis.flip(w);
		int ret = 1;
		for (int i = 0; i < 5; i++) {
			for (UI j = rg[w].v[i] & (ALL ^ vis.v[i]); j; j ^= lowbit(j)) {
				int t = (__builtin_ffs(j) - 1) | (i << 5);
				if (!vis[t]) {
					ret += dfs1(t);
				}
			}
		}
		return ret;
	}
}scc;

int main() {
	freopen("friend.in", "r", stdin);
	freopen("friend.out", "w", stdout);
	n = read(); m = read(); q = read();
	for (int i = 1; i <= m; i++) {
		U[i] = read();
		V[i] = read();
		AddEdge(U[i], V[i], PreG[i / BlockSize], PreRG[i / BlockSize]);
	}
	for (int i = 1; i <= q; i++) {
		qy[i].l = read(); 
		qy[i].r = read();
		qy[i].blk = qy[i].l / BlockSize;
		qy[i].id = i;
	}
	sort(qy + 1, qy + 1 + q);
	Bitset CurG[N], CurRG[N];
	for (int i = 1, L = 1, R = 0; i <= q; i++) {
		if (qy[i].blk != qy[i - 1].blk || i == 1) {
			L = qy[i].blk + 1;
			R = L - 1;	
			for (int j = 1; j <= n; j++) {
				CurG[j].reset();
				CurRG[j].reset();
			}
		}
		if (qy[i].r / BlockSize - 1 > R) {
			for (int j = R + 1, lim = qy[i].r / BlockSize - 1; j <= lim; j++) {
				for (int k = 1; k <= n; k++) {
					for (int h = 0; h < 5; h++) {
						CurG[k].v[h] ^= PreG[j][k].v[h];
						CurRG[k].v[h] ^= PreRG[j][k].v[h];
					}
				}
			}
			R = qy[i].r / BlockSize - 1;
		}
		if (L <= R) {
			for (int i = 1; i <= n; i++) {
				g[i] = CurG[i];
				rg[i] = CurRG[i];
			}
			for (int l = qy[i].l; l < L * BlockSize; l++) {
				AddEdge(U[l], V[l], g, rg);
			}
			for (int r = (R + 1) * BlockSize; r <= qy[i].r; r++) {
				AddEdge(U[r], V[r], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		} else {
			for (int i = 1; i <= n; i++) {
				g[i].reset();
				rg[i].reset();
			}
			for (int j = qy[i].l; j <= qy[i].r; ++j) {
				AddEdge(U[j], V[j], g, rg);
			}
			ans[qy[i].id] = scc.solve();
		}
	}
	for (int i = 1; i <= q; i++) {
		printf("%d\n", ans[i]);
	}
	return 0;
}

【BZOJ 3577】玩手机

相关链接

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

解题报告

之前一直都是线段树优化建图
这题需要用$ST$表来优化建图

Code

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

const int INF = 1e9;
const int N = 500000;
const int M = 2000000;

int S,T,E,tot,A,B,Y,X,n2[2][70][70][8]; 
int head[N],nxt[M],to[M],flow[M],n1[2][70][70];

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 AddEdge(int u, int v, int f) {
	assert(u); assert(v);
	to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0;
}

class NetworkFlow{
	int dis[N],cur[N];
	queue<int> que;
	public:
		inline int MaxFlow() {
			int ret = 0;
			while (BFS()) {
				memcpy(cur, head, sizeof(cur));
				ret += DFS(S, INF);
			}
			return ret;
		}
	private:
		inline bool BFS() {
			memset(dis, 60, sizeof(dis));
			dis[S] = 0;
			for (que.push(S); !que.empty(); que.pop()) {
				int w = que.front();
				for (int i = head[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] > INF) {
						dis[to[i]] = dis[w] + 1;
						que.push(to[i]);
					}
				}
			}
			return dis[T] <= INF;
		}
		inline int DFS(int w, int f) {
			if (w == T) {
				return f;
			} else {
				int ret = 0;
				for (int &i = cur[w]; i; i = nxt[i]) {
					if (flow[i] && dis[to[i]] == dis[w] + 1) {
						int tmp = DFS(to[i], min(f, flow[i]));
						ret += tmp; f -= tmp;
						flow[i] -= tmp; flow[i ^ 1] += tmp;
						if (!f) {
							break;
						}
					}
				}
				return ret;
			}
		}
}Dinic;

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif
	X = read(); Y = read(); 
	A = read(); B = read();
	S = ++tot; T = ++tot;
	E = 1; 
	for (int i = 1; i <= X; ++i) {
		for (int j = 1; j <= Y; ++j) {
			n1[0][i][j] = ++tot;
			n1[1][i][j] = ++tot;
			AddEdge(n1[0][i][j], n1[1][i][j], read());
		}
	}
	for (int i = X; i; --i) {
		for (int j = Y; j; --j) {
			for (int a = 0, len = 1; i + len - 1 <= X && j + len - 1 <= Y; ++a, len <<= 1) {
				n2[0][i][j][a] = ++tot;
				n2[1][i][j][a] = ++tot;
				if (!a) {
					AddEdge(n2[0][i][j][a], n1[0][i][j], INF);
					AddEdge(n1[1][i][j], n2[1][i][j][a], INF);	
				} else {
					int llen = len >> 1;
					AddEdge(n2[0][i][j][a], n2[0][i][j][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i + llen][j][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i][j + llen][a - 1], INF);
					AddEdge(n2[0][i][j][a], n2[0][i + llen][j + llen][a - 1], INF);
					
					AddEdge(n2[1][i][j][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i][j + llen][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i + llen][j][a - 1], n2[1][i][j][a], INF);
					AddEdge(n2[1][i + llen][j + llen][a - 1], n2[1][i][j][a], INF);
				} 
			}	
		}
	}
	for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= A; ++i) {
		p0 = ++tot; p1 = ++tot;
		w = read(); 
		x1 = read(); y1 = read();
		x2 = read(); y2 = read();
		AddEdge(S, p0, INF);
		AddEdge(p0, p1, w);
		
		int len = x2 - x1 + 1, lg = 0, d = 1;
		for (; (d << 1) <= len; lg++, d <<= 1);
		AddEdge(p1, n2[0][x1][y1][lg], INF);
		AddEdge(p1, n2[0][x1][y2 - d + 1][lg], INF);
		AddEdge(p1, n2[0][x2 - d + 1][y1][lg], INF);
		AddEdge(p1, n2[0][x2 - d + 1][y2 - d + 1][lg], INF);
	}
	for (int i = 1, w, x1, x2, y1, y2, p0, p1; i <= B; ++i) {
		p0 = ++tot;	p1 = ++tot;
		w = read();
		x1 = read(); y1 = read();
		x2 = read(); y2 = read();
		AddEdge(p0, p1, w);
		AddEdge(p1, T, INF);
		
		int len = x2 - x1 + 1, lg = 0, d = 1;
		for (; (d << 1) <= len; lg++, d <<= 1);
		AddEdge(n2[1][x1][y1][lg], p0, INF);
		AddEdge(n2[1][x1][y2 - d + 1][lg], p0, INF);
		AddEdge(n2[1][x2 - d + 1][y1][lg], p0, INF);
		AddEdge(n2[1][x2 - d + 1][y2 - d + 1][lg], p0, INF);
	}
	assert(tot < N);
	assert(E < M);
	printf("%d\n", Dinic.MaxFlow());
	return 0;
}

【Tricks】Gedit的配置与计算器

Part 1. Gedit的配置

在拓展工具里创建新工具Complie

#!/bin/sh  
fullname=$GEDIT_CURRENT_DOCUMENT_NAME  
name=`echo $fullname | cut -d. -f1`  
suffix=`echo $fullname | cut -d. -f2`  
    
g++ $fullname -o $name

在拓展工具里创建新工具Run

#!/bin/sh
fullname=$GEDIT_CURRENT_DOCUMENT_NAME  
name=`echo $fullname | cut -d. -f1`  
suffix=`echo $fullname | cut -d. -f2`  
dir=$GEDIT_CURRENT_DOCUMENT_DIR
    
gnome-terminal --working-directory=$dir -x bash -c "$dir/$name; echo; echo 'press ENTER to continue'; read"

Part 2. 计算器

NOI Linux下似乎没有图形界面的计算器
于是只能在终端中输入bc来使用命令行计算器
话说这货还挺好用的,唯一的问题就是:默认所有数全部为整数
我们需要使用scale=x来指定精度,x可以是任意自然数

—————————— UPD 2017.5.15 ——————————
被$Menci$啪啪啪 QwQ
请在终端中输入$xcalc$,有惊喜

—————————— UPD 2017.6.13 ——————————
学Python了,弃疗xcalc

【BZOJ 4861】[BeiJing2017] 魔法咒语

相关链接

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

解题报告

对于$L \le 100$的情况,我们定义$f_{i,j}$表示长度为$i$,在$ac$自动机上匹配到点$j$的答案
然后暴力转移就可以了,时间复杂度:$O(10^4L)$

对于其他的点,我们构造转移矩阵,用矩阵快速幂来优化
至于如何把长度为$2$的和为$1$的给统一起来?我们可以加一个点缓存一下
时间复杂度:$O(200^3 \log L)$

Code

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

const int MOD = 1000000007;

int n,m,L,len[109];
char s1[109][109],s2[109][109];

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

class AC_Automaton{
	int cnt,ch[109][26],vis[109],fail[109];
	vector<int> G[109];
	queue<int> que;
	public:
		inline AC_Automaton() {
			cnt=1;
		}
		inline void insert(char *s) {
			int l = strlen(s + 1), w = 1;
			for (int i=1;i<=l;i++) {
				int c = s[i] - 'a';
				if (!ch[w]) ch[w] = ++cnt;
				w = ch[w];
			}
			vis[w] = 1;
		}
		inline void build() {
			for (int i=0;i<26;i++) {
				if (!ch[1][i]) ch[1][i] = 1;
				else fail[ch[1][i]] = 1, que.push(ch[1][i]);
			}
			while (!que.empty()) { 
				int w = que.front(); que.pop(); 
				G[fail[w]].push_back(w);
				for (int i=0;i<26;i++) {
					if (ch[w][i] && ch[w][i] != 1) {
						que.push(ch[w][i]);
						fail[ch[w][i]] = ch[fail[w]][i];
					} else {
						ch[w][i] = ch[fail[w]][i];
					}
				}
			} 
			DFS(1, 0);
		}
		inline int size() {
			return cnt;
		}
		inline int MOVE(int w, int j) {
			if (vis[j]) return -1;
			for (int i=1;i<=len[w];i++) {
				j = ch[j][s1[w][i]-'a'];
				if (vis[j]) return -1;
			}
			return j;
		}
	private:
		void DFS(int w, int t) {
			t |= vis[w];
			if (t) vis[w] = 1; 
			for (int i=G[w].size()-1;~i;i--) {
				if (G[w][i] != i) { 
					DFS(G[w][i], t);
				}
			}
		}
}ac;

namespace SUBTASK_ONE{
	int f[109][109],tot,ans;
	int tra[109][109];
	
	inline void solve() {
		for (int i=1;i<=n;i++) {
			scanf("%s",s1[i]+1);
			len[i] = strlen(s1[i]+1);
		}
		for (int i=1;i<=m;i++) {
			scanf("%s",s2[i]+1);
			ac.insert(s2[i]);
		}
		ac.build(); 
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=ac.size();j++) {
				int tmp = ac.MOVE(i, j);
				if (tmp != -1) tra[j][i] = tmp; 
			}
		}
		f[0][1] = 1;
		for (int i=0;i<L;i++) {
			for (int j=1;j<=ac.size();j++) {
				if (f[i][j]) {
					for (int k=1,t1,t2;k<=n;k++) {
						if ((t1=tra[j][k]) != -1 && (t2=i + len[k]) <= L) {
							f[t2][t1] = (f[t2][t1] + f[i][j]) % MOD; 
						}
					}
				}
			}
		}
		for (int i=1;i<=ac.size();i++) {
			ans = (ans + f[L][i]) % MOD;
		}
		printf("%d\n",ans);
	} 
};

namespace SUBTASK_TWO{
	int sz,tot,tra[109][109*109+109];
	struct Matrix{
		int a[209][209];
		inline Matrix() {
			memset(a,0,sizeof(a));
		}
		inline Matrix(int x) {
			memset(a,0,sizeof(a));
			for (int i=1;i<=sz;i++) a[i][i] = x;
		}
		inline Matrix operator * (const Matrix &M) {
			Matrix ret;
			for (int i=1;i<=sz;i++) {
				for (int j=1;j<=sz;j++) {
					for (int k=1;k<=sz;k++) {
						ret.a[i][j] = (ret.a[i][j] + (LL)a[k][j] * M.a[i][k]) % MOD;	
					}
				}
			}
			return ret;
		}
		inline Matrix operator ^ (int t) {
			Matrix ret(1),tmp;
			for (int i=1;i<=sz;i++) {
				memcpy(tmp.a[i],a[i],sizeof(a[i]));
			}
			for (;t;t>>=1,tmp=tmp*tmp) {
				if (t&1) ret = ret * tmp;
			}
			return ret;
		}
		inline void init() {
			memset(a,0,sizeof(a));
		}
	}ans,trans;
	
	inline void solve() {
		for (int i=1;i<=n;i++) {
			scanf("%s",s1[i]+1);
			len[i] = strlen(s1[i]+1);
		}
		for (int i=1;i<=m;i++) {
			scanf("%s",s2[i]+1);
			ac.insert(s2[i]);
		}
		ac.build(); sz = ac.size();
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=sz;j++) {
				int tmp = ac.MOVE(i, j);
				if (tmp != -1) tra[j][i] = tmp; 
			}
		}
		ans.a[1][1] = 1; int ori = sz; 
		for (int i=1;i<=ori;i++) trans.a[i][++sz]++;
		for (int i=1;i<=ori;i++) {
			for (int j=1;j<=n;j++) {
				if (!tra[i][j]) continue;
				if (len[j] == 1) ++trans.a[tra[i][j]][i];
				else trans.a[tra[i][j]+ori][i]++;
			}
		}
		trans = trans ^ L;
		ans = ans * trans;
		int vout = 0;
		for (int i=1;i<=ori;i++) vout = (vout + ans.a[i][1]) % MOD;
		cout<<vout<<endl;
	}
};

int main() {
	n = read(); m = read(); L = read();
	if (L <= 100) {
		SUBTASK_ONE::solve();
	} else {
		SUBTASK_TWO::solve();
	}
	return 0;
}

【BZOJ 4008】[HNOI2015] 亚瑟王

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4008
神犇题解:https://blog.sengxian.com/solutions/bzoj-4008

解题报告

根据期望地线性,我们可以单独计算每一个技能的期望然后相加
于是问题转化为求每个技能在这$r$轮中被发动的概率

但我们发现如果直接模拟题目中的过程,我们似乎需要记录哪些点已经被使用过
这个问题似乎只能使用状压DP来解决?但复杂度是不允许这么干的
于是我们需要一点Trick:

我们将这$r$轮整体转移,记录$f_{i,j}$表示到第$i$个技能,还有$j$轮没有触发任何技能的概率
那么这个状态的时候第$i$个技能被触发的概率就是$1-(1-p_i)^j$

于是这个问题就做完啦!时间复杂度:$O(Tnr)$
至于为什么是对的?
因为每一轮的游戏过程没有区别,所以我们可以将将其一视同仁

Code

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

int n,r,d[250];
double f[250][150],p[250][150],ans[250];

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() {
	for (int T=read();T;T--) { 
		memset(f,0,sizeof(f)); memset(ans,0,sizeof(ans));
		n = read(); r = read();
		for (int i=1;i<=n;i++) scanf("%lf%d",&p[i][0],&d[i]);
		for (int i=1;i<=n;i++) {
			p[i][1] = 1 - p[i][0];
			for (int j=2;j<=r;j++) p[i][j] = p[i][j-1] * p[i][1];
		}
		f[1][r] = 1;
		for (int i=1;i<=n;i++) {
			for (int j=1;j<=r;j++) {
				ans[i] += f[i][j] * (1 - p[i][j]);
				f[i+1][j] += f[i][j] * p[i][j];
				f[i+1][j-1] += f[i][j] * (1 - p[i][j]);
			}
		}
		double vout = 0;
		for (int i=1;i<=n;i++) vout += ans[i] * d[i];
		printf("%.10lf\n",vout);
	} 
	return 0;
}

【Tricks】强大的在线解析工具

1. OEIS


这个玩意儿我就不多说了吧?
CF水题必备(逃

2. WolframAlpha


这个东西似乎知道的人也挺多的?
反正就是巨好用,求个倒数啊,化简一个表达式啊都非常方便

3. Desmos


这个东西你可以叫他在线的几何画板,而且感觉功能比几何画板强大
(虽然我自己不会用 QwQ

—————————— UPD 2017.3.23 ——————————
我校高一神犇ksda47832338用Desmos搞了这么一个东西,太强大了 _(:з」∠)_
所有的东西,包括那个火焰都是用函数搞出来的啊!