【Codeforces 819B】Mister B and PR Shifts

相关链接

题目传送门:http://codeforces.com/contest/819/problem/B

解题报告

这题是今年SCOI D2T1的一部分

具体的做法就是如果$i$变成$i+1$,那么有多少$|p_i – i|$会增加和减少
对于每个$|p_i – i|$,“从增加变到减少 或 从减少变到增加” 只会进行一次
于是总的时间复杂度就是:$O(n)$的

Code

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

const int N = 1000009;

int n, p[N], chg[N], delta[2];

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

int main() {
	n = read();
	LL cur = 0, ans, pos = 0;
	for (int i = 1; i <= n; i++) {
		p[i] = read();
		cur += abs(p[i] - i);
		delta[p[i] > i]++; 
		if (p[i] > i) {
			++chg[p[i] - i]; 
		} else {
			++chg[n - i + p[i]]; 
		}
		--chg[n - i + 1]; 
	}
	ans = cur;
	for (int i = 1; i < n; i++) {
		cur += delta[0] - delta[1];
		cur += abs(p[n - i + 1] - 1) - abs(p[n - i + 1] - n - 1);
		if (cur < ans) {
			ans = cur;
			pos = i;
		}
		delta[1] -= chg[i];
		delta[0] += chg[i];
	}
	cout<<ans<<' '<<pos<<endl;
	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;
}

【AtCoder】[Grand Contest 013 B] Hamiltonish Path

相关链接

题目传送门:http://agc013.contest.atcoder.jp/tasks/agc013_b

解题报告

最开始想用$DFS$树来搞
然而$Corner \ Case$太多了,写不动啊_(:з」∠)_

最后还是看了题解
题解是使用的调整算法
如果某个端点还可以走,那就走进去
因为每条边至多访问两遍,每个点至多访问一次
所以复杂度是:$O(n + m)$的

Code

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

const int N = 100009;
const int M = N << 1;

int n, m, head[N], nxt[M], to[M], vis[N];
deque<int> ans;

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

int main() {
#ifdef DBG
	freopen("11input.in", "r", stdin);
#endif	
	n = read(), m = read();
	for (int i = 1; i <= m; i++) {
		int u = read(), v = read();
		AddEdge(u, v);
		if (i == 1) {
			ans.push_back(u);
			ans.push_back(v);
			vis[u] = vis[v] = 1;
		}
	}
	for (int mk = 1; mk; ) {
		mk = 0;
		for (int i = head[ans.front()]; i; i = nxt[i]) {
			if (!vis[to[i]]) {
				mk = 1;
				ans.push_front(to[i]);
				vis[to[i]] = 1;
				break;
			}
		}
	}
	for (int mk = 1; mk; ) {
		mk = 0;
		for (int i = head[ans.back()]; i; i = nxt[i]) {
			if (!vis[to[i]]) {
				mk = 1;
				ans.push_back(to[i]);
				vis[to[i]] = 1;
				break;
			}
		}
	}
	cout<<ans.size()<<endl;
	for (; !ans.empty(); ans.pop_front()) {
		printf("%d ", ans.front());
	}
	return 0;
}

【TopCoder SRM713】PowerEquation

相关链接

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

题目大意

给定$n(n \le 10^9)$,问有多少组不同的$a^b=c^d$成立
要求$1 \le a,b,c,d \le n$

解题报告

假设$a^b=c^d$,我们在枚举到$gcd(a,c)$的时候计算
如果$gcd(a,c)=a=c$的话,贡献显然是$n$
所以我们枚举$gcd$只需要枚举到$\sqrt{n}$
又因为次数非常小,所以我们可以暴力算有多少种指数满足要求
于是总的复杂度大概是$\sqrt{n}$的

Code

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

const int MOD = 1000000007;
const int N = 100000;

int gcd[100][100];
bool vis[N];

class PowerEquation {
    public:
    	int count(int n) {
    		memset(vis, 0, sizeof(vis));
    		for (int i=1;i<=50;i++) {
				for (int j=1;j<=50;j++) {
					gcd[i][j] = GCD(i, j);
				}
			}
			
			int ret = (LL)n * n % MOD, dec = 0;
    		for (int i=2;1;i++) {
				if (i * i > n) {
					ret = (ret + (n - i + 1ll - dec) * n) % MOD;
					break;	
				} else {
					if (vis[i]) continue;
					for (LL j=i*i;j<=n;j*=i) {
						if (j * j <= n) vis[j] = 1;
						else ++dec;
					}
					
					int mx = 1, tmp = 0; LL cur = i;
					while (cur * i <= n) cur *= i, ++mx;
					for (int a=1;a<=mx;a++) {
						for (int b=1;b<=mx;b++) {
							int c = max(b,a) / gcd[a][b];
							tmp = (tmp + n / c) % MOD;
						}
					} 
					ret = (ret + tmp) % MOD;
				}
			}
    	    return ret;
   		}
   	private:
   		int GCD(int a, int b) {
			return b? GCD(b, a%b): a;   
		}
};

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

【日常小测】苹果

题目大意

给定一个长度为$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;
}

【日常小测】摩尔庄园

题目大意

给定一棵$n(n \le 10^5)$个节点的以$1$为根的有根树,第$i$个结点上有$c_i$个食物,其父亲为$\lfloor \frac{i}{2} \rfloor$
现在依次给出$m$个拉姆,依次询问前$i$个拉姆都有东西吃的最短移动距离和
依次输出这$m$次询问的答案

解题报告

如果点数很小的话,我们显然可以跑个费用流就可以了!
但这题点这么多怎么办 QwQ

那我们就手动增广!
考虑维护一个$val_i$表示以$i$为根的子树中最近的有食物的点到$i$的距离
于是我们可以花$O(\log n)$的时间暴力在树上爬一爬就可以代替费用流的SPFA
然后考虑修改沿途边的边权,因为树高是$\log n$级别的,于是我们也是暴力修改就好
最后再用更新一下受影响的$val_i$来方便下次增广就可以辣!

以前听说过手动增广的题目,不过一次都还没有写过
这次写一写感觉这货非常好玩啊!

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
const int N = 100009;
const int INF = 1e9;
 
int  n,m,vout,cnt[N],pos[N];
int sur[N],val[N],cost[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 int LCA(int u, int v) {
    for (;u!=v;u>>=1) 
        if (u < v) swap(u, v);
    return u;
}
 
inline void update(int w) {
    static int ls, rs, cl, cr;
    if (cnt[w]) sur[w] = w, val[w] = 0;
    else sur[w] = 0, val[w] = INF;
    if ((ls=w<<1) <= n) {
        cl = cost[ls] > 0? -1: 1;
        if(val[ls] + cl < val[w]) {
            val[w] = val[ls] + cl;
            sur[w] = sur[ls];
        }
    }
    if ((rs=ls|1) <= n) {
        int cr = cost[rs] > 0? -1: 1;
        if(val[rs] + cr < val[w]) {
            val[w] = val[rs] + cr;
            sur[w] = sur[rs];
        }
    }
}
 
inline void modify(int w, int p, int delta) {
    while (w != p) {
        cost[w] += delta;
        update(w); w >>= 1;  
    }
}
 
inline int query(int w, int &ans) {
    static int ret, delta; delta = 0;
    for (;w;w>>=1) {
        if (val[w] + delta < ans) {
            ans = val[w] + delta;
            ret = sur[w];
        }
        delta += cost[w] >= 0? 1: -1;
    } return ret;
}
 
int main() {
    n = read(); m = read();
    for (int i=1;i<=n;i++) cnt[i] = read();
    for (int i=1;i<=m;i++) pos[i] = read();
    for (int i=n;i;i--) update(i);
    for (int i=1,u,v,ans=INF;i<=m;++i,ans=INF) {
        cnt[v=query(u=pos[i], ans)]--; 
        printf("%d\n",vout+=ans);
        int lca = LCA(u, v);
        modify(u, lca, 1); modify(v, lca, -1);
        for (;lca;lca>>=1) update(lca);
    }
    return 0;
}

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

【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}$的限制条件
于是对于限制条件的反区间取并,然后从总区间中减去,剩下的就是符合条件的开头啦!