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

【BZOJ 4567】[Scoi2016] 背单词

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

这个题,就AC自动机搞一搞就可以啦!
省选时的我都能A,这是真简单啊!

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define AC AC_Automata
#define LL long long
using namespace std;

LL vout = 0;
char pat[510000+9];

namespace AC_Automata{
	const int N = 510000+9;
	const int SIGMA_SIZE = 26;
	struct Node{int ch[SIGMA_SIZE],fail,last,vis;}p[N];
	int cnt,que[N],itr1,itr2;
	vector<int> G[N];
	
	int head[N],to[N],nxt[N];
	int TOT,tot,sz[N];
	
	inline void AddEdge(int u, int v){to[++TOT] = v; nxt[TOT] = head[u]; head[u] = TOT;}
	
	inline void insert(char *s){
		int len = strlen(s), w=0;
		for (int i=0;i<len;i++){
			int c = s[i] - 'a';
			if (!p[w].ch) w = p[w].ch = ++cnt;
			else w = p[w].ch;
		} p[w].vis++;
	}
	
	inline void GetFail(){
		itr1 = 0; itr2 = 1;
		for (int i=0;i<SIGMA_SIZE;i++)
			if (p[0].ch[i]) que[++itr1] = p[0].ch[i];
		
		while (itr2 <= itr1){
			int w = que[itr2++];
			if (p[w].vis) AddEdge(p[w].last, w);
			for (int i=0;i<SIGMA_SIZE;i++){
				if (p[w].ch[i]) {
					int nw = p[w].fail;
					while (nw && !p[nw].ch[i]) nw = p[nw].fail;
					p[p[w].ch[i]].fail = p[nw].ch[i];
					p[p[w].ch[i]].last = p[p[nw].ch[i]].vis ? p[nw].ch[i] : p[p[nw].ch[i]].last;
					que[++itr1] = p[w].ch[i];
				}
			} 
		}
	}
	
	void DFS(int w){
		sz[w] = 1;
		for (int i=head[w];i;i=nxt[i]) DFS(to[i]), sz[w] += sz[to[i]], G[w].push_back(sz[to[i]]);
		int len = G[w].size();
		sort(G[w].begin(), G[w].end());
		for (int i=0,sta=0;i<len;i++) vout += (LL)sta + 1LL, sta += (LL)G[w][i];
	}
};

int main(){
	int n; scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%s",pat), AC::insert(pat);
	AC::GetFail(); AC::DFS(0);
	printf("%lld",vout);
	return 0;
}