【Codeforces 212B】Polycarpus is Looking for Good Substrings

相关链接

题目传送门:http://codeforces.com/contest/212/problem/B
中文题面:http://www.tsinsen.com/A1470

解题报告

这题你需要观察到一个非常重要的结论:

以字符串某个特定位置为开头的字符串,至多只有26个会产生贡献

于是我们就可以暴力枚举这$O(26n)$的字符串
然后去更新答案
时间复杂度:$O(26n \log q)$

Code

这份代码我写挫了
时间复杂度是:$O(676n \log q)$的

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

const int N = 1000009;
const int SGZ = 26;
const int M = 10009;

int n, m, nxt[N][SGZ], crt[N][SGZ], q[M], ans[M];
vector<int> val;
char s[N], qy[SGZ]; 

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

int main() {
	scanf("%s", s);
	n = strlen(s);
	m = read();
	for (int i = 1; i <= m; i++) {
		scanf("%s", qy);
		int len = strlen(qy);
		for (int j = 0; j < len; j++) {
			q[i] |= 1 << qy[j] - 'a';
		}
		val.push_back(q[i]);
	}
	sort(val.begin(), val.end());
	val.resize(unique(val.begin(), val.end()) - val.begin());
	int last_position[SGZ];
	fill(last_position, last_position + SGZ, n);
	for (int i = n - 1; ~i; i--) {
		last_position[s[i] - 'a'] = i;
		for (int j = 0; j < SGZ; j++) {
			nxt[i][j] = last_position[j];
		}
	}
	memset(crt, -1, sizeof(crt));
	for (int i = 0; i < n; i++) {
		for (int j = 0, p = i, sta = 0; j < 26 && p < n; j++) {
			int np = n, c = -1;
			for (int k = 0; k < 26; k++) {
				if ((sta >> k & 1) == 0) {
					if (np > nxt[p][k]) {
						c = k;
						np = nxt[p][k];
					}
				}
			}
			if (~c) {
				sta |= 1 << c;
				p = np;
				crt[i][j] = sta;
				if (!i || crt[i - 1][j] != sta) {
					int idx = index(sta);
					if (~idx) { 
						ans[idx]++;
					}
				}
			}
		}
	}
	for (int i = 1; i <= m; i++) {
		printf("%d\n", ans[index(q[i])]);
	}
	return 0;
}

【Codeforces 734F】Anton and School

相关链接

题目传送门:http://codeforces.com/contest/734/problem/F
官方题解:http://codeforces.com/blog/entry/48397

解题报告

画一画维恩图便容易发现:$(a \ and \ b) + (a \ or \ b) = a + b$
所以$b_i + c_i = \sum\limits_{j = 1}^{n}{a_i + a_j} = na_i + \sum\limits_{j = 1}^{n}{a_j}$
于是有$\sum\limits_{i = 1}^{n}{a_i} = \frac{\sum\limits_{i = 1}^{n}{b_i + c_i}}{2n}$
最后加加减减搞一搞就可以求出$a_i$了

然后就是检查${a_i}$是否符合${b_i}$和${c_i}$
这个按二进制位枚举一下就可以了
总的时间复杂度是:$O(n \log \max(a_i))$的

Code

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

const int N = 200009;

int n, a[N], b[N], c[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 bool check() {
	static int cnt[100];
	for (int i = 1; i <= n; i++) {
		for (int t = 0, v = a[i]; v; v >>= 1, ++t) {
			cnt[t] += v & 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		int tb = 0, tc = 0;
		for (int j = 0, cur = 1; j <= 30; j++, cur <<= 1) {
			tb += (a[i] & cur)? cnt[j] * cur: 0;
			tc += (a[i] & cur)? n * cur: cnt[j] * cur;
		}
		if (tb != b[i] || tc != c[i]) {
			return false;
		}
	}
	return true;
}

int main() {
	n = read();
	for (int i = 1; i <= n; i++) {
		a[i] = b[i] = read();
	}
	LL sum = 0;
	for (int i = 1; i <= n; i++) {
		a[i] += (c[i] = read());
		sum += a[i];
	}
	if (sum % (n << 1)) {
		puts("-1");
		exit(0);
	}
	sum /= n << 1;
	for (int i = 1; i <= n; i++) {
		if ((a[i] -= sum) % n) {
			puts("-1");
			exit(0);
		} else {
			a[i] /= n;
		}
	}
	if (!check()) {
		puts("-1");
		exit(0);
	} 
	for (int i = 1; i <= n; i++) {
		printf("%d ", a[i]);
	}
	return 0;
}

【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 2296】[POJ Challenge] 随机种子

相关链接

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

解题报告

我们假设高位是$9876543201$,低$6$位随意
那么每一次加上$x$,导致高位至多增加$1$
所以一定有解,至于是多少倍?我们可以二分

Code

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

const LL MX = 9876543201999999;
const LL MN = 9876543201000000; 

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() {
	for (int T = read(); T; T--) {
		LL x = read();
		if (!x) {
			puts("-1");
		} else {
			LL r = MX / x + 1, l = MN / x;
			while (l <= r) {
				LL mid = l + r >> 1;
				if (x * mid < MN) {
					l = mid + 1;
				} else if (x * mid > MX) {
					r = mid - 1;
				} else {
					printf("%lld\n", mid * x);
					break;
				}
			}
		}
	}
	return 0;
}

【TopCoder SRM712】LR

相关链接

题目传送门:https://community.topcoder.com/stat?c=problem_statement&pm=14569&rd=16881

解题报告

我们经过观察发现,操作顺序不影响结果
于是我们就可以暴力枚举多少个$L$多少个$R$然后暴力判断
时间复杂度:$O(n \log^2 10^{17})$

Code

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

class LR {
    public:
    	string construct(vector<long long> s, vector<long long> t) {
    	    int n=s.size(),SPJ=1; LL s1=0,s2=0,pp,cnt=0;
    	    for (int i=0;i<n;i++) s1 += s[i], s2 += t[i], SPJ = (t[i]!=s[i]?0:SPJ);
    	    if (SPJ) return ""; pp = s1;
    	    if (s2-s1 <= 0 || (!s1 && s2)) return "No solution";
    	    while (pp<s2) pp<<=1,++cnt; 
			if (pp != s2) return "No solution";
			for (int i=0;i<=cnt;i++) {
				if (judge(s, t, i, cnt-i)) {
					string ret="";
					for (int j=1;j<=i;j++) ret += "L";
					for (int j=i+1;j<=cnt;j++) ret += "R";
					return ret;
				}
			}
			return "No solution";
   		}
   	private:
   		inline bool judge(vector<LL> s, vector<LL> t, int L, int R) {
			LL tmp[55],a[55],b[55],n=s.size();
			for (int i=1;i<=n;i++) a[i] = s[i-1], b[i] = t[i-1];
			for (int k=1;k<=L;k++) {
				for (int i=1;i<=n;i++) tmp[i] = a[i]; tmp[0] = a[n];
				for (int i=1;i<=n;i++) a[i] = tmp[i-1] + tmp[i];
			}
			for (int k=1;k<=R;k++) {
				for (int i=1;i<=n;i++) tmp[i] = a[i]; tmp[n+1] = a[1];
				for (int i=1;i<=n;i++) a[i] = tmp[i] + tmp[i+1];
			}
			for (int i=1;i<=n;i++) if (a[i] != b[i]) return 0;
			return 1;
		} 
};

【BZOJ 4725】[POI2017] Reprezentacje ró?nicowe

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4725
神犇题解:http://blog.csdn.net/lych_cys/article/details/53455978

解题报告

这题看上去一脸不可做QwQ
前前后后想了差不多三个小时吧?
突然反应过来:从第63项开始$a(x)$就大于$10^9$了
换一句话来说:之后的每一项,只可能减去前一项才可能小于$10^9$

于是我们把前$63$项之内的拿出来暴力搞一搞
$63$项之后的,我们可以推公式推出来答案是多少

Code

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

const int N = 10000;

int n,tot,vis[N],L[N],R[N],que[N];
LL f[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;
}

inline void insert(int w) {
	for (int i=w-1;i;i--) {
		if (abs(f[w]-f[i]) >= N) break;
		vis[abs(f[w]-f[i])] = 1;
	}
} 

inline int query() {
	for (int i=1;i;i++)
		if (!vis[i]) return i;
}

inline void Get_Ans(int w, int id) {
	for (int j=2;j;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] == w) {
				L[id] = i; R[id] = j;
				return;
			}
		}
	}
}

inline void query(int w) {
	for (int j=2;j;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] == w) {
				cout<<j<<' '<<i<<endl;
				return;
			}
		}
	}
}

int main() {
	f[1] = 1; f[2] = 2; vis[1] = 1;
	for (int i=3;i<=120;i++) { 
		if (i&1) f[i] = f[i-1] << 1;
		else f[i] = f[i-1] + query();
		insert(i);
	} 
	for (int j=2;j<=63;j++) {
		for (int i=1;i<j;i++) {
			if (f[j] - f[i] > 1e9) continue;
			que[++tot] = f[j] - f[i];
		}
	} 
	que[++tot] = (1e9) + 10;
	sort(que+1, que+1+tot);
	for (int i=1;i<tot;i++) Get_Ans(que[i], i); 
	for (int q=read(),x,p;q;q--) {
		x = read();
		p = lower_bound(que+1, que+1+tot, x) - que;
		if (que[p] == x) printf("%d %d\n",R[p], L[p]);
		else if (x <= 90) query(x);
		else printf("%lld %lld\n",(x-90-p+62)*2ll+120,(x-90-p+62)*2ll+119);
	}
	return 0;
}

【BZOJ 4347】[POI2016] Nim z utrudnieniem

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4347
神犇题解Ⅰ:http://www.cnblogs.com/clrs97/p/5006924.html
神犇题解Ⅱ:http://blog.csdn.net/lych_cys/article/details/50788730

解题报告

这题暴力$DP$的复杂度是$O(nd \cdot \max \{a_i\})$的,显然不能通过此题
但我们注意到,对于一个数$a_i$来讲,小于等于它的数的NIM和不会超过$2 \cdot a_i$
于是我们将$a_i$排序之后再$DP$,每一次枚举异或值只枚举到$2 \cdot a_i$
又因为$\sum\limits_{i=1}^n{a_i} \le 10^7$ 所以公共的更新次数不会超过$2 \cdot 10^7$
于是总时间复杂度就是$O(md)$的了

虽然$md$可以到$10^8$,而且感觉这个上界非常紧的样子
给人一种严重的跑不过的感觉
但却跑得飞快? 可能是数据比较水吧?

哦,对了,这题还卡内存
连滚动数组都给卡掉了
于是我们学习Claris的技巧,$f[k][j]$和$f[k \ xor \ a_i][j]$一起更新就可以啦!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int M = 500009;
const int N = 1100000;
const int MOD = 1000000007;
 
int n,D,XOR,f[N][10],g[2][10],arr[M];
 
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(); D = read(); 
    for (int i=1;i<=n;i++) XOR ^= (arr[i] = read());
    sort(arr+1, arr+1+n); 
    f[0][0] = 1;
    for (int i=1,LIM=1;i<=n;i++) {
        while (LIM <= arr[i]) LIM <<= 1;
        for (int v=1,nv;v<LIM;v++) {
            if ((nv=(arr[i]^v)) <= v) { 
                for (int d=0,t=1%D;d<D;++d,(++t)%=D) {
                    g[1][t] = (f[nv][t] + f[v][d]) % MOD;       
                    g[0][t] = (f[nv][d] + f[v][t]) % MOD;
                }
                for (int d=0;d<D;d++) {
                    f[nv][d] = g[1][d];
                    f[v][d] = g[0][d];
                }
            }
        } 
    }
    if (n % D == 0) f[XOR][0]--;
    printf("%d\n",(f[XOR][0]+MOD)%MOD);
    return 0;
}

【BZOJ 4236】JOIOJI

相关链接

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

解题报告

如果字符集大小只有2的话,那一个搞成1另一个搞成-1就好啦!
但这题字符集大小为3,于是我们从数组拓展到三维坐标系就好啦!
然后搞一个map什么的装一装,时间复杂度:$O(nlogn)$

Code

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

int n,vout;
map<pair<int,int>, int> m;

inline int read() {
	char c=getchar(); 
	while (c!='J'&&c!='O'&&c!='I') c=getchar();
	if (c == 'J') return 1;
	else if (c == 'O') return 2;
	else return 3;
}

int main() {
	cin>>n;
	pair<int,int> cur(0,0);
	for (int i=1,w;i<=n;i++) {
		w = read();
		if (w == 1) cur.first++;
		else if (w == 2) cur.second++;
		else cur.first--, cur.second--;
		if (m[cur]) vout = max(vout, i - m[cur]);
		else m[cur] = i;
		if (!cur.first && !cur.second) vout = max(vout, i);
	}
	cout<<vout<<endl;
	return 0;
}

【TopCoder】[TCO2013 2C] Well Timed Search

相关链接

题目传送门:https://arena.topcoder.com/#/u/practiceCode/15657/31723/12515/1/317358
中文题面及题解:http://picks.logdown.com/posts/208980-solutions-to-topcoder-open-2013s-hard-problems

解题报告

这题从头到尾都只会 $O(n^3)$ 的 $DP$
想了四个小时啊 QwQ

考虑搞出一个二叉搜索树
显然我们可以控制一个节点的左右儿子有多少个
因为我们可以询问当前区间的端点,所以我们还可以控制有没有左右儿子
换一句话说,我们可以钦定这棵搜索树的形态

我们继续观察可以发现一下两条:

  1. 我们可以根据一个节点左右儿子子树的大小,求得往左、往右走的概率
  2. 每一个深度在$[A,B]$的节点都是一个合法的结束

于是我们就可以枚举第$A$层有多少结点,然后贪心往下放就可以啦!

Code

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

class WellTimedSearch {
    public:
	double getProbability(int n, int A, int B) {
		int vout = 0; 
		for (int i=1,up,down;i<=n;i++) {
			if (A > 1) up = Get_Top(i+1>>1, A-1);
			else {if (i == 1) up = 0; else up = 1e9;}
			if (n - up - i < 0) break;
			down = Get_Down(B-A, n - up - i, i<<1);
			vout = max(vout, i + down);
		}
		return (double)vout / n;
	}
   	private:
	int Get_Top(int len, int t) {
		if (t > 1) return min((int)1e9, len + (len>1? Get_Top(len+1>>1, t-1): t-1));
		if (t == 1 && len > 1) return 1e9;
		return 1;
	}
	int Get_Down(int t, int num_node, int cur) {
		if (!t) return 0;
		if (cur >= num_node) return num_node;
		return cur + Get_Down(t-1, num_node - cur, cur<<1);
	}
};

【BZOJ 4377】[POI2015] Kurs szybkiego czytania

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4377
神犇题解:http://blog.csdn.net/commonc/article/details/51282041

解题报告

考虑一个匹配的第一个位置是x的话
第i个位置实际的值就是 $ (x + (i – 1)a)\% n$
然后这个位置显然会受到限制,形如:$ {p_1} < x < {p_2}$的限制条件
于是对于限制条件的反区间取并,然后从总区间中减去,剩下的就是符合条件的开头啦!