首页 > itarticle > codechef august lunchtime 2017 ltime51 solutions MATDYS MATTEG MATCUT

codechef august lunchtime 2017 ltime51 solutions MATDYS MATTEG MATCUT

admin 11月 13, 2020 0

…

···

const int MaxN = 51234;
int T; char s[MaxN]; int c[MaxN], b[27];
int () {
	int i;
	cin >> T;
	while(T--) {
		for(i = 0; i < 26; i++) c[i] = inp();
		scanf("%s", s + 1); int n = strlen(s + 1);
		memset(b, 0, sizeof(b));
		for(i = 1; i <= n; i++) b[s[i] - 'a']++;
		int ans = 0;
		for(i = 0; i < 26; i++) if(!b[i]) ans += c[i]; 
		cout << ans << endl;
	}
	return 0;
}

MATDYS

二进制翻转。。给的看起来就是FFT的过程。。

int q, n; u64 K;
int () {
	int i;
	cin >> q;
	while(q--) {
		cin >> n >> K;
		u64 ans = 0;
		for(i = 0; i < n; i++) {
			ans <<= 1;
			ans |= (K & 1);
			K >>= 1;
		}
		cout << ans << endl;
	}
	return 0;
}

MATTEG

$O(n*5^n)$ 状压DP

const int MaxN = 1234;
const int MaxState = 1953125 + MaxN; 
int r, c, n, sx, sy, x[MaxN], y[MaxN], val[MaxN][MaxN];
int dx[] = {0, 1, -1, 1, -1};
int dy[] = {0, 1, -1, -1, 1};
int f[MaxState], exp[MaxN];
int get_bit(int p, int i) {
	return (p/exp[i]) % 5;
}
void solve() {
	int ans = val[sx][sy], i, j, k;
	f[0] = ans;
	for(i = 1; i < exp[n]; i++) {
		int nx = sx, ny = sy;
		for(j = 0; j < n; j++) {
			if(k = get_bit(i, j))
				nx += dx[k] * x[j],
				ny += dy[k] * y[j];
		}
		
		f[i] = -1e9;
		if(nx < 0 || nx >= r || ny < 0 || ny >= c)	continue; 
		for(j = 0; j < n; j++) 
			if(k = get_bit(i, j))
				cmax(f[i], f[i - exp[j] * k] + val[nx][ny]);
		cmax(ans, f[i]);
	}
	cout << ans << endl;
}

MATCUT

点分治。把质因子指数模3哈希一下即可。线筛预处理某个质因子可以使得单次分解复杂度为$log a_i$, 最后总复杂度就是 $O(nlog nlog a_i)$

 
const int MaxN = 101234, MaxM = 1001234, MaxP = 6;
const int base = 1234567, p1 = 1000000007, p2 = 1000000009;
typedef pair<int, int> Pint;
Pint operator + (Pint a, Pint b) {
	(a.fir += b.fir) %= p1;
	(a.sec += b.sec) %= p2;
	return a;		
}
Pint operator * (Pint a, int x) {
	a.fir = (LL) a.fir * x % p1;
	a.sec = (LL) a.sec * x % p2;
	return a;
}
Pint operator - (Pint a, Pint b) {
	a.fir = (a.fir - b.fir + p1) % p1;
	a.sec = (a.sec - b.sec + p2) % p2;
	return a;
} 
vector<int> e[MaxN]; int n, a[MaxN];
int d[MaxM];
void prime_init() {
	for(int i = 2; i < MaxM; i++)
		if(!d[i]) 
			for(int j = i; j < MaxM; j += i)
				d[j] = i;
}
Pint operator -= (Pint &a, Pint b) {
	a = a - b;
}
Pint operator += (Pint &a, Pint b) {
	a = a + b;
}
Pint exp[MaxM], rev, pos; 
map<Pint, int> table; vector<pair<Pint, int> > vec;
int cnt[MaxM];
void modify(int x, int y) {
	while(x != 1) {
		int z = d[x];
		if(cnt[z]) {
			pos -= exp[z] * cnt[z];
			rev -= exp[z] * (3 - cnt[z]); 
		}
		cnt[z] = (cnt[z] + y + 3) % 3;
		if(cnt[z]) {
			pos += exp[z] * cnt[z];
			rev += exp[z] * (3 - cnt[z]); 
		}
		x /= z; 
	}
}
vector<int> vis; int siz[MaxN], hug[MaxN]; 
void dfs(int x, int fa = 0) {
	vis.emplace_back(x); 
	siz[x] = 1; hug[x] = 0;
	for(auto y : e[x]) 
		if(y != fa) {
			dfs(y, x);
			siz[x] += siz[y];
			cmax(hug[x], siz[y]); 
		}
}  
int make(int x, int fa, int dt = 1) {
	int z = a[x]; 
	modify(z, 1);
	vec.emplace_back(make_pair(pos, dt));
	int ans = -1;
	if(table.count(rev)) 
		cmax(ans, dt + table[rev] + 1);
	for(auto y : e[x])
		if(y != fa) 
			cmax(ans, make(y, x, dt + 1));
	modify(z, -1);
	return ans;
}
int decomp(int x) {
	int ans = -1;
	table.clear(); vis.clear();
	dfs(x, x);
	int N = vis.size(), cent = 0;
	for(auto x : vis) 
		if(hug[x] <= N/2 && (N - siz[x]) <= N/2) {
			cent = x; break; 
		} 
	cent = cent ? cent : vis.back();
	modify(a[cent], -1); table[pos] = 0;
	if(pos == make_pair(0, 0)) ans = 1;
	
	for(auto y : e[cent]) {
		cmax(ans, make(y, cent));
		for(auto p : vec) 
			cmax(table[p.fir], p.sec);
		vec.clear();
	}
	
	modify(a[cent], 1);
	
	for(auto y : e[cent]) {
		for(int i = 0; i < e[y].size(); i++) {
			if(e[y][i] == cent) {
				swap(e[y][i], e[y].back()); 
				e[y].pop_back();
				break;
			}
		}
		cmax(ans, decomp(y));
	} 
	return ans;
}
void solve() {
	int i;
	n = inp();
	for(i = 1; i <= n; i++) a[i] = inp();
	for(i = 1; i <= n; i++) e[i].clear();
	
	for(i = 1; i < n; i++) {
		int u = inp(), v = inp();
		e[u].emplace_back(v);
		e[v].emplace_back(u);
	}
	
	printf("%dn", decomp(1));
}
int () {
	int T = inp();
	prime_init();
	exp[0] = make_pair(1, 1);
	for(int i = 1; i < MaxM; i++) exp[i] = exp[i - 1] * base;
	
	while(T--) 
		solve();
	return 0;
}