【AtCoder】[Grand Contest 015 F] Kenus the Ancient Greek

相关链接

题目传送门:http://agc015.contest.atcoder.jp/tasks/agc015_f

解题报告

我们写出使答案最大且值最小的序列,不难发现这是一个斐波那契数列
进一步发现,这条主链的每一个点只会引申出一条支链,且支链不会再分
所以我们可以暴力算出了$\log n$条链,共$\log ^ 2 n$对数,然后暴力算贡献

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int MOD = 1000000007;
const int LOG = 100;
 
vector<pair<LL, LL> > num[LOG];
 
inline LL read() {
	char c = getchar(); LL 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 void solve(LL A, LL B) {
	if (A < num[2][0].first || B < num[2][0].second) {
		printf("1 %d\n", A * B % MOD);
		return;
	}
	for (int i = 2; i < LOG; i++) {
		if (A < num[i + 1][0].first || B < num[i + 1][0].second) {
			int cnt = 0;
			for (int j = 0; j < (int)num[i].size(); j++) {
				LL a = num[i][j].first, b = num[i][j].second;
				cnt = (cnt + (a <= A && b <= B? (B - b) / a + 1: 0)) % MOD;
				cnt = (cnt + (b <= A && a <= B? (A - b) / a + 1: 0)) % MOD;
			}
			printf("%d %d\n", i, cnt);
			return;
		}
	}
}
 
inline void prework() {
	num[0] = vector<pair<LL,LL> >{make_pair(1, 1)};
	for (int i = 1; i < LOG; i++) {
		for (int j = 0; j < (int)num[i - 1].size(); ++j) {
			LL a = num[i - 1][j].first, b = num[i - 1][j].second;
			num[i].push_back(make_pair(b, a + b));
		}
		LL a = num[i - 1][0].first, b = num[i - 1][0].second;
		num[i].push_back(make_pair(a + b, 2 * a + b));
	}
}
 
int main() {
	prework();
	for (int T = read(); T; T--) {
		LL A = read(), B = read();
		solve(min(A, B), max(A, B));
	}
	return 0;
}

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

【BZOJ 4735】你的生命已如风中残烛

相关链接

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

吐槽

我只会$O(mn2^n)$的暴力$DP$
然而正解长成这样,为什么$n$给这么小?
给人一种这题有妙妙的做法的错觉……

解题报告

我们把正常的牌看成$-1$的话,那么实际上就是要让每一个地方的前缀和$\ge 1$

现在考虑在末尾加上一个$-1$,那么是不是就是处末尾以外的地方$\ge 1$,而末尾的前缀和为$0$?
现在考虑把这$m+1$个元素拿出来做一个环排列
仔细观察可以发现:一种环排列能且仅能对应一种合法摆放
于是我们求出环排列的个数就可以了,最后再去一下多加的那个$-1$的影响
最终答案:$\frac{m!}{m-n+1}$

Code

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

const int MOD = 998244353;

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() {
	int n = read(), m = 0, ans = 1;
	for (int i=1;i<=n;i++) m += read();
	for (int i=2;i<=m;i++) ans = ((LL)ans * ((i!=m-n+1)?i :1)) % MOD;
	cout<<ans;
	return 0;
}

【BZOJ 3990】[SDOI2015] 排序

相关链接

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

解题报告

最开始一眼看成神题,还在想$SDOI$这是要赶超$ZJOI$的节奏啊
然后就发现看漏条件了 _(:з」∠)_

因为每一次只能交换一个$2^k$的块,并且$2$的不同次幂之间不会相互影响
话一句话来说,考虑交换长度为$2^k$的块时,所有长度为$2^{k-1}$的块的顺序必须已经排好
且长度为$2^k$的块,只能有至多两块位置不对
于是我们搞一发$DFS$就好了,时间复杂度:$O(n \log n)$

【BZOJ 4294】[PA2015] Fibonacci

相关链接

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

解题报告

做这题,我们需要有一个前置结论:

Fibonacci数列在$\bmod 10^n$的时候,循环节为$6 \times 10^n$

至于这个结论怎么证明,我也不知道
不过这个结论可以用这里的知识自己搞出来:传送门

那么知道了这个结论之后
我们就可以从低位到高位DFS了
每一层只会尝试$0 \sim 9$,虽然看起来会$T$
不过复杂度是玄学,所以跑得飞快

【日常小测】苹果和雪梨

题目大意

给你$n(n \le 3000)$个梨,$n$个苹果。每个梨有个权值$a_i$,每个苹果有个权值$b_i$
现在让你求出一种匹配关系,使得梨与苹果一一配对,使得获益最大。
设$i$号梨对应$f_i$号苹果,定义收益为$\sum\limits_{i=1}^{n}{a_i \cdot b_{f_i}}-\max\{a_i \cdot b_{f_i}\}$

解题报告

这题有一个非常显然的$O(n^4)$的暴力:

$O(n^2)$枚举最大值是哪一对
对于其他梨,贪心选择最大的、可以选的苹果配对

这种暴力优化一下,据说可以优化到$O(n^3)$

但我们仔细想一想,这种XJB枚举最大值很不优雅,会做很多重复的动作
于是我们考虑从小到大枚举最大值是哪一对
考虑我们此时将涉及到的四个点更改匹配关系即可
时间复杂度:$O(n^2 \log n)$

Code

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

const int N = 3009;
const int M = N * N;

LL n,tot,vout,ans,mx,a[N],b[N],p[N],q[N]; 
struct Match{int x,y;LL val;}m[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();
	for (int i=1;i<=n;i++) a[i] = read();
	for (int j=1;j<=n;j++) b[j] = read();
	sort(a+1, a+1+n); sort(b+1, b+1+n);
	for (int i=1;i<=n;i++) {
		for (int j=1;j<=n;j++) {
			m[++tot].val = a[i] * b[j];	
			m[tot].x = i; m[tot].y = j;
		}
	}
	static auto cmp = [](const Match &A, const Match &B) {return A.val < B.val || (A.val == B.val && A.x < B.x) || (A.val == B.val && A.x == B.x && A.y < B.y);};
	sort(m+1, m+1+tot, cmp);
	for (int i=1;i<=n;i++) 
		mx = max(mx, a[i] * b[n-i+1]);
	for (int i=n;i;i--) {
		for (int j=n;j;j--) {
			if (!q[j] && a[i] * b[j] <= mx) {
				q[j] = i; p[i] = j;
				ans += a[i] * b[j];
				break;
			}
		}
	}
	vout = ans - mx;
	for (int i=1,x,y,nx,ny;i<=tot;i++) {
		if (m[i].val <= mx) continue;
		x = m[i].x; y = m[i].y; nx = p[x]; ny = q[y];
		p[ny] = nx; q[nx] = ny; p[x] = y; q[y] = x;
		ans += a[x] * b[y] + a[ny] * b[nx];
		ans -= a[x] * b[nx] + a[ny] * b[y];
		vout = max(vout, ans - m[i].val);
	}
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 3997】[TJOI2015] 组合数学

相关链接

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

解题报告

这题又™是结论题
需要用到的结论:

Dilworth定理:DAG的最小链覆盖=最大点独立集

类似的结论还有:

最大团=补图上的最小点覆盖的补集
最大反链的大小=最小链划分
最大链的大小=最小反链划分

知道结论之后,实际上就是让你求一些点,相互不能到达,且点权和最大
这样的话,从左下到右上搞一个DP就可以了!

Code

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

const int N = 1000+9;

int n,m,val[N][N],f[N][N],g[N]; 

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--) {
		memset(f,0,sizeof(f));
		memset(g,0,sizeof(g));
		m = read(); n = read();
		for (int j=1;j<=m;j++) {
			for (int i=1;i<=n;i++) {
				val[i][j] = read();
			}
		}
		for (int i=1;i<=n;i++) {
			for (int j=m,cur=0;j;j--) {
				f[i][j] = cur + val[i][j];
				cur = max(cur, g[j]);
				g[j] = max(g[j], f[i][j]);
			}
		}
		int vout = 0;
		for (int i=1;i<=m;i++) 
			vout = max(vout, g[i]);
		printf("%d\n",vout);
	}
	return 0;
}

【BZOJ 3994】[SDOI2015] 约数个数和

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3994
数据生成器:http://paste.ubuntu.com/23992676/
神犇题解:https://blog.sengxian.com/solutions/bzoj-3994

解题报告

这题要用到一个结论: $d(xy) = \sum\limits_{i|x} {\sum\limits_{j|y} {[\gcd (i,j) = 1]} } $
这个结论似乎没有办法从意义上去推导,证明也只能是展开后发现刚好相等
但这个结论前不久集训的时候就考过一次,然而做这题的时候一点印象都没有
我要是下一次还记不住这个结论就直播吃键盘!

好了现在开始说正解
知道上面的结论以后,答案就成了 $\sum\limits_{k = 1}^n {\mu (k)\sum\limits_{i = 1}^{\frac{n}{k}} {d(i)\sum\limits_{j = 1}^{\frac{m}{k}} {d(j)} } } $
然后设$f(i)$为除数函数的前缀和,答案就变成了: $\sum\limits_{k = 1}^n {\mu (k)f(\frac{n}{k})f(\frac{m}{k})} $
于是直接下底函数分块就可以啦!

Code

除数函数可以线筛,不过偷懒写的欧拉筛法

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

const int N = 50000+9; 

int n,m,tot,pri[N],mu[N],d[N],sum[N],f[N];
bool vis[N]; 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 prework() {
	mu[1] = 1;
	for (int i=2;i<N;i++) {
		if (!vis[i]) pri[++tot] = i, mu[i] = -1;
		for (int j=1;j<=tot&&pri[j]*i<N;j++) {
			vis[i*pri[j]] = 1;
			if (i % pri[j]) mu[i*pri[j]] = -mu[i];
			else {mu[i*pri[j]] = 0; break;}
		}
	}
	for (int i=1;i<N;i++) 
		for (int j=i;j<N;j+=i) 
			d[j]++;
	for (int i=1;i<N;i++) {
		f[i] = f[i-1] + d[i];
		sum[i] = sum[i-1] + mu[i];
	}
}	

int main() {
	prework();
	for (int T=read();T;T--,vout=0) {
		n = read(); m = read();
		if (m > n) swap(n, m);
		for (int l=1,r;l<=m;l=r+1) {
			r = min(n / (n / l), m / (m / l));
			vout += (LL)(sum[r] - sum[l-1]) * f[n/l] * f[m/l];
		}
		printf("%lld\n",vout);
	}
	return 0;
}

【BZOJ 4722】由乃

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4722
神犇题解Ⅰ:http://blog.csdn.net/werkeytom_ftd/article/details/54429577
神犇题解Ⅱ:http://www.cnblogs.com/wxxlouisa/p/6139165.html

解题报告

这题看起来一眼不可做啊!
仔细想一想,发现确实不会做

看完题解后:果然是乱搞题!
先不管修改操作的话,如果询问的区间长度超过13的话,一定有解
相关证明可以参见:http://blog.csdn.net/werkeytom_ftd/article/details/54429577

现在考虑修改操作
因为单次询问最多涉及13个数
所以只需要支持单点查询+区间修改就可以了
于是用线段树打标记什么的就可以啦!

然而我们惊讶的发现,我们打的Tag在最后计算的时候会很大
More Formally:次数会爆 $ long long$
于是用不了快速幂了 QwQ
然后又不会了

于是接着去膜拜题解
发现我们可以用类似快速幂一样的东西搞出来
我们最终要求的是:$ {a_i}^{{3^x}}$
于是我们预处理出 $ f(i,j)$ 表示 $ {a_i}^{{3^{{2^j}}}}$
于是像快速幂一样搞一搞就可以啦!

最后我们求出了这13个数是什么,怎么判断有没有解呢?
我们可以 Meet in middle !

【Codeforces 711E】ZS and The Birthday Paradox

题目传送门:http://codeforces.com/problemset/problem/711/E
官方题解:http://codeforces.com/blog/entry/46830
中文题面及题解:https://blog.sengxian.com/solutions/cf-711e

这个题重点不在推概率,而在Legendre’s formula
其实难点就是要求在取MOD之前就约分,这个就很麻烦了,只有用上面那个定理

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

const LL MOD = 1000003;

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 LL pow(LL w, LL t) {
	LL ret = 1;
	while (t) {
		if (t & 1) ret = ret*w % MOD;
		w = w*w % MOD; t >>= 1;	
	} 
	return ret;
}

inline bool judge(LL n, LL k) {
	LL w = 1;
	for (int i=1;i<=n;i++) {
		w *= 2;
		if (w >= k) return false;
	} return true;
}

int main(){
	LL n = read(), k = read(), tn = pow(2,n);
	if (judge(n,k)) cout<<1<<' '<<1;
	else {
		LL t1, t2, cnt = (k-1) - __builtin_popcountll(k-1), gcd = pow(pow(2,cnt),MOD-2);
		if (k >= MOD) t1 = 0; else {t1 = 1; for (int i=1;i<k;i++) t1 = t1 * (tn - i) % MOD;}
		t2 = pow(pow(2,n),k-1); t2 = t2 * gcd % MOD; t1 = t1 * gcd % MOD; t1 = ((t2 - t1)% MOD + MOD) % MOD;
		cout<<t1<<' '<<t2;
	} 
	return 0;
}

ps:如果不知道上面的那个定理,貌似自己推也是可以推出来的?

【BZOJ 1997】[Hnoi2010] Planar

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1997
数据生成器:http://paste.ubuntu.com/22273507/

这个题目在知道了是2-sat的情况下还是懵逼了好久QAQ
当时就想到这个图:一个正方形加上对角线.jpg(solidwork还没装,不想用word画图QAQ
发现他给的这个圆不能自交,于是每一条线就只有两种可能:
1.圆内
2.圆外
于是处理出相互干涉的线段,然后搞2-sat

最开始这么搞了,血RE
遂看题解,™有一个这个结论:
Theorem 1. If v ≥ 3 then e ≤ 3v − 6;
Theorem 2. If v ≥ 3 and there are no cycles of length 3, then e ≤ 2v − 4.
详细情况:https://en.wikipedia.org/wiki/Planar_graph
于是加特判,遂过

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<map>
using namespace std;

const int MAXN = 20000+9;
const int N = 200000;

int n,m,que[MAXN],L[MAXN],R[MAXN],T,nxt[N],to[N],head[MAXN],mark[MAXN],cnt;
vector<int> G[MAXN];
map<int,int> ins;

struct CMP{inline bool operator () (const int &A, const int &B) {return R[A] < R[B];}};
multiset<int,CMP>::iterator itr;
multiset<int,CMP> buf;


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

inline void init(){
	n = read(); m = read(); T = 0;
	for (int i=1;i<=n;i++) G[i].clear();
	memset(head,0,sizeof(head));
	memset(mark,0,sizeof(mark));
}

#define Add_Edge(a,b) to[++T] = b,nxt[T]=head[a],head[a]=T
inline void AddEdge(int a, int b) {
	int ra=a*2+1, rb=b*2+1; a *= 2; b *= 2;
	Add_Edge(ra,b); Add_Edge(rb,a);
	Add_Edge(a,rb); Add_Edge(b,ra);
}

inline void build_map(){
	buf.clear();
	for (int i=1;i<=n;i++) {
		while (buf.size() && R[*(buf.begin())] <= i) buf.erase(buf.begin());
		for (int j=0,sz=G[i].size();j<sz;j++) 
			for (itr=buf.begin();itr!=buf.end() && R[*itr] < R[G[i][j]];itr++) 
				AddEdge(G[i][j],*itr);
		for (int j=0,sz=G[i].size();j<sz;j++) buf.insert(G[i][j]);
	}
}

bool DFS(int w) {
	if (mark[w]) return true;
	if (mark[w^1]) return false;
	mark[w] = 1; que[++cnt] = w;
	
	for (int i=head[w];i;i=nxt[i]) 
		if (!DFS(to[i])) return false;
	return true;
}

inline bool judge(){
	for (int i=2;i<=m*2+1;i+=2) if (!mark[i] && !mark[i+1]) {
		cnt = 0; if (DFS(i)) continue;
		for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
		cnt = 0; if (!DFS(i+1)) return false; 
	}
	return true;
}

int main(){
	int TT = read(); while (TT--) { init();
		for (int i=1;i<=m;i++) L[i] = read(), R[i] = read();
		for (int i=1;i<=n;i++) que[i] = read(), ins[que[i]] = i;
		for (int i=1;i<=m;i++) {
			L[i] = ins[L[i]]; R[i] = ins[R[i]];
			if (L[i] > R[i]) swap(L[i], R[i]);
			G[L[i]].push_back(i);
		}
		if (m > 3*n-6) printf("NO\n");
		else {
			build_map();
			if (judge()) printf("YES\n");
			else printf("NO\n");
		}
	} 
	return 0;
}