【日常小测】苹果

题目大意

给定一个长度为$2n(n \le 100000)$的序列,序列中每个元素$\in [1,10^9]$
让你从中选出$n$个元素,使这$n$个元素的$\gcd$最大

解题报告

我们随机选两个数的话,失败的概率为$\frac{3}{4}$
于是我们选$30 \sim 50$次的话,错误的概率就足够小了

于是我们就随机选几对数,然后求$\gcd$
之后枚举$\gcd$的因数,去更新答案
时间复杂度:$O($跑得过$)$

Code

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

const int N = 200009;
const int M = 1000009;
const int TIMES = 30;
const double EPS = 0.5;

int n,tp,tot,vis[M],pri[M],cnt[N];
LL arr[N],que[N],ans=1; set<LL> VIS;

inline LL read() {
	char c=getchar(); LL 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;
}

LL GCD(LL a, LL b) {
	return b? GCD(b, a%b): a;
}

bool DFS(int t, LL v) {
	if (t > tot) {
		if (v <= ans || VIS.count(v)) return 1; 
		int ret = 0; VIS.insert(v); 
		for (int i=1;i<=n;i++) ret += (arr[i] % v == 0);
		if (ret >= (n >> 1)) {ans = v; return 1;}
		else return 0;
	} else {
		bool ret = 0; 
		for (int i=0;i<=cnt[t];i++,v*=que[t]) {
			if (!DFS(t+1, v)) break;
			else ret = 1;
		} return ret;
	}
}

int main() {
	freopen("apple.in","r",stdin);
	freopen("apple.out","w",stdout);
	srand(19260817); 
	for (int i=2;i<M;i++) {
		if (!vis[i]) pri[++tp] = i;
		for (int j=1;j<=tp&&pri[j]*i<M;j++) {
			vis[i*pri[j]] = 1;
			if (i % pri[j] == 0) break; 
		}
	} 
	
	n = read(); 
	for (int i=1;i<=n;i++) arr[i] = read();
	for (int i=2;i<=n;i++) swap(arr[i], arr[rand()%(i-1)+1]);
	for (int a,b,kk=1;kk<=TIMES;kk++) {
		a = rand() % n + 1; b = rand() % n + 1;
		LL gcd = GCD(arr[a], arr[b]); tot = 0; 
		for (int i=1,v;i<=tp&&(v=pri[i])<=gcd;i++) {
			if (gcd % v != 0) continue;
			que[++tot] = v; cnt[tot] = 0;
			for (;gcd%v==0;++cnt[tot]) gcd /= v; 
		}
		if (gcd != 1) que[++tot] = gcd, cnt[tot] = 1;
		DFS(1, 1);
	}
	printf("%lld\n",ans);
	return 0;
}

【Codeforces 797F】Mice and Holes

相关链接

题目传送门:http://codeforces.com/contest/797/problem/F

解题报告

这题我是用的一个非常鬼畜的背包DP过的,时间复杂度:$O(n^2 \log n)$
看提交记录的话,似乎可以用很多种方法做到$O(n^2)$

Code

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

const int N = 5009;
const LL INF = 1e15;

int n,m,sum,x[N];
LL f[N],tmp,cost[N];
pair<int,int> mdy[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() {
	n = read(); m = read();
	for (int i=1;i<=n;i++) x[i] = read(), f[i] = INF;
	for (int i=1;i<=m;i++) mdy[i].first = read(), sum += (mdy[i].second = read());
	if (sum < n) puts("-1"), exit(0);
	sort(x+1, x+1+n); sort(mdy+1, mdy+1+m);
	for (int j=1,tot,pos;tot=mdy[j].second,pos=mdy[j].first,j<=m;j++) {
		for (int i=1;i<=n;i++) cost[i] = abs(x[i] - pos) + cost[i-1];
		for (int len=1;len=min(len,tot),tot>0;tot-=len,len<<=1) {
			for (int l=n-len+1,r=n;l>0;--l,--r) {
				f[r] = min(f[r], cost[r] - cost[l-1] + f[l-1]);
			} 
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}

【BZOJ 4713】迷失的字符串

相关链接

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

解题报告

这题拿bitset搞一搞就好了
f[i]表示前缀匹配,g[i]表示后缀匹配
然后暴力更新
时间复杂度:$O(\frac{n^2}{64})$

Code

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

const int M = 16;
const int SGZ = 26;
const int N = 30000+9;

int head[N],nxt[N<<1],to[N<<1],col[N<<1],sz[N],hvy[N];
int n,m,tot,beg[N],ed[N],id[N],pool[M],top; char s[N];
bitset<N> vout,ans,ve,vis[SGZ],vs[SGZ],f[M],g[M];

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 Add_Edge(int u, int v, int c) {
	static int E = 1;
	to[++E] = v; nxt[E] = head[u]; head[u] = E; col[E] = c;
	to[++E] = u; nxt[E] = head[v]; head[v] = E; col[E] = c;
}

void DFS1(int w, int f) {
	sz[w] = 1;
	for (int i=head[w];i;i=nxt[i]) {
		if (to[i] != f) {
			DFS1(to[i], w);
			sz[w] += sz[to[i]];
			if (sz[hvy[w]]<sz[to[i]]) 
				hvy[w] = to[i];
		}
	}
}

inline void init(int w) {
	id[w] = pool[top--];
	f[id[w]].reset();
	g[id[w]] = ve;	
}

inline void solve(int x, int y, int c) {
	int ix = id[x], iy = id[y];
	f[iy] <<= 1; f[iy] &= vis; f[iy] |= vs;
	g[iy] = g[iy] & vis;
	vout |= g[iy];
	g[iy] >>= 1;
	ans |= f[ix] & g[iy];
	ans |= g[ix] & f[iy];
	f[ix] |= f[iy];
	g[ix] |= g[iy];
	pool[++top] = iy;
}

void DFS2(int w, int f) {
	if (hvy[w]) DFS2(hvy[w], w);
	init(w);
	for (int i=head[w];i;i=nxt[i]) if (to[i] == hvy[w]) 
		solve(w, hvy[w], col[i]);
	for (int i=head[w];i;i=nxt[i]) if (to[i] != hvy[w] && to[i] != f) 
		DFS2(to[i], w), solve(w, to[i], col[i]);
} 

int main() {
	for (int i=top=M-1;~i;i--) pool[i] = i;
	for (int i=n=read(),u,v;i>1;i--) {
		u = read(); v = read(); 
		scanf("%s",s);
		Add_Edge(u, v, s[0]-'a');
	}
	for (int i=m=read(),len;i;i--) {
		scanf("%s",s); len = strlen(s); 
		vs[s[0]-'a'][beg[m-i+1]=tot+1] = 1; 
		for (int j=0;j<len;j++) vis[s[j]-'a'][++tot] = 1;
		ve[ed[m-i+1]=tot] = 1; 
	}
	DFS1(1, 1); 
	DFS2(1, 1);
	for (int i=1,tag=0;i<=m;i++,tag=0) {
		if (vout[beg[i]]) tag = 1;
		for (int j=beg[i];j<=ed[i]&&!tag;j++) if (ans[j]) tag = 1;
		puts(tag?"YES":"NO");
	}
	return 0;
}

后记

这题似乎之前听谁说过有点分的做法?
不过想不起怎么做了 _(:з」∠)_
会的神犇可不可以给我讲一讲怎么做啊 QwQ

【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 !

【Tsinsen 1342】能量棒

相关链接

题目传送门:http://www.tsinsen.com/A1342
参考代码:http://paste.ubuntu.com/23803611/

解题报告

这题乍看需要 $ O({n^2})$ 的DP的样子
然而可以用 Tree 这道题一样,给每一次转移附加一个值 $ k$
然后直接转移,记录一下转移了多少次,根据次数的多少来调整 $ k$
然后再用上决策单调性来优化DP的话
这样似乎就可以在 $ O(n{\log ^{\rm{2}}}n)$ 的时间复杂度内解决这个问题了!

值得一提的是,毛爷爷讲了一下这个方法的适用范围:
DP的那个函数必须是一个凸包
不过毛爷爷也说了:
只要拍一拍,拍不出错就行啦!

【UOJ 246】[UER #7] 套路

相关链接

题目传送门:http://uoj.ac/contest/35/problem/246
官方题解:http://matthew99.blog.uoj.ac/blog/2085

解题报告

这题真™是套路深啊!
一言不合就根号大军了

具体来说的话,我们考虑答案的区间长度为 $ len$
并且钦定一个阀值 $ S$

  1. 考虑 $ len<S$ 的情况
    我们枚举右端点,暴力向左扫 $ S$ 个就可以了

  2. 考虑 $ len \ge S$ 的情况
    我们发现相似度不会超过 $ \frac{m}{{len – 1}}$
    于是考虑在权值上暴力向两边扫 $ S$ 个

这样的话,我们就可以在 $ O(nS + n\frac{m}{s})$ 的复杂度内解决这个问题了
不难发现,当 $ S = \sqrt m$ 时复杂度最优

Code

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

const int N = 200000+9;

int n,m,K,S,a[N],gap[N],lst[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;
}

int main() {
	n = read(); m = read(); 
	K = read(); S = sqrt(m) + 1;
	for (int i=1;i<=n;i++) a[i] = read();
	
	memset(gap,60,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=i-1;j>=i-S&&j;--j) {
			gap[j] = min(gap[j], gap[j+1]);
			gap[j] = min(gap[j], abs(a[i] - a[j]));
			if (i-j+1 >= K) vout = max(vout, (LL)(i - j) * gap[j]);
		}
	}
	memset(gap,0,sizeof(gap));
	for (int i=1;i<=n;i++) {
		for (int j=0;j<=S;j++) {
			if (j) gap[j] = max(gap[j], gap[j-1]);
			if (a[i]-j >= 1) gap[j] = max(gap[j], lst[a[i]-j]);
			if (a[i]+j <= m) gap[j] = max(gap[j], lst[a[i]+j]);
			if (i-gap[j] >= K) vout = max(vout, (LL)(i-gap[j]-1) * (j+1)); 
		}
		lst[a[i]] = i;
	}
	printf("%lld\n",vout);
	return 0;
}

【BZOJ 2456】mode

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2456
神犇题解:https://oi.men.ci/bzoj-2456/

解题报告

考虑将不同的数抵消掉
因为题目所求的数多于一半
所以剩下的就一定是答案啦!

Code

#include<cstdio>
#define LL long long

int main() {
	int n,tot=0; LL num,cur;
	for (scanf("%d",&n);n;n--) {
		scanf("%lld",&cur);
		if (num != cur) {
			if (tot) tot--;
			else tot = 1, num = cur;
		} else tot++;
	} printf("%lld\n",num);
	return 0;
}

—– UPD 2016.12.29 —–
这题似乎还有一个做法:

考虑将原数分解成二进制
统计每一位二进制上0多还是1多

酱紫的话,最后在在二进制下逐位确定答案就好啦!

【BZOJ 2393】Cirno的完美算数教室

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

额,容斥第一题,竟然成了乱搞…….
这题的时间复杂度是玄学……
就是搞出互质的baka数,然后容斥

#include<iostream>
#include<cstdio>
#include<algorithm>
#define LL long long 
using namespace std;

const int MAXN = 2000;

int l,r,arr[MAXN],tmp[MAXN],vout,cnt,tot;

void DFS(LL w){
	if (w > r) return;
	tmp[++cnt] = w;
	DFS(w*10+2);
	DFS(w*10+9);
}

inline void prework(){
	DFS(2); DFS(9);
	sort(tmp+1,tmp+cnt); 
	for (int i=1,tag=0;i<=cnt;i++,tag=0) {
		for (int j=i-1;j;j--) if (tmp[i] % tmp[j] == 0) {tag = 1; break;}
		if (!tag) arr[++tot] = tmp[i];
	}
	for (int i=1;i*2<=tot;i++) swap(arr[i],arr[tot-i+1]);
}

int GCD(int a, int b){return b?GCD(b,a%b):a;}

void solve(int step, int sz, int w){
	if (step == tot+1) {
		if (sz & 1) vout += r/w - (l-1)/w;
		else if (sz) vout -= r/w - (l-1)/w;
	} else {
		solve(step+1,sz,w);
		LL buf = (LL)w/GCD(w,arr[step])*arr[step];
		if (buf <= r) solve(step+1,sz+1,buf);
	}
}

int main(){
	scanf("%d%d",&l,&r);
	prework();
	solve(1,0,1);
	printf("%d\n",vout);
	return 0;
}