20160813 训练记录

tonyfang posted @ 2016年8月14日 07:07 in 随笔 with tags c++ OI , 626 阅读

P1. 给出字符串,求它删除后缀后的字符串是什么。删除的后缀为'ly', 'ing', 'er'。最多删除一个后缀。

$|S| <= 32$

【题解】无可奉告

 

# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <string>
# include <iostream>

using namespace std;

char str[100010];

int main() {	
	freopen("suffix.in", "r", stdin);
	freopen("suffix.out", "w", stdout);
	
	while(~scanf("%s", str)) {
		int sz = strlen(str);
		if(sz > 1 && str[sz-1] == 'r' && str[sz-2] == 'e') {
			str[sz-2] = '\0';
		} else if(sz > 1 && str[sz-1] == 'y' && str[sz-2] == 'l') {
			str[sz-2] = '\0';
		} else if(sz > 2 && str[sz-1] == 'g' && str[sz-2] == 'n' && str[sz-3] == 'i') {
			str[sz-3] = '\0';
		} 
		puts(str);
	}
	
	return 0;
}

P2. 砝码称重

【题解】二进制拆分

 

# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <string>
# include <iostream>

using namespace std;

int a[7];
int fm[7] = {0, 1, 2, 3, 5, 10, 20};
int b[66666], bn=0;
bool f[200010];

int main() {
	
	freopen("weight.in", "r", stdin);
	freopen("weight.out", "w", stdout);
	
	for (int i=1; i<=6; ++i) {
		scanf("%d", &a[i]);
		int j=0;
		while(a[i] - (1<<j) >= 0) {
			a[i] = a[i] - (1<<j);
			b[++bn] = fm[i] * (1<<j);
			++j;
		}
		if(a[i] != 0) {
			b[++bn] = fm[i] * a[i];
		}
	}
	
	/*
	for (int i=1; i<=bn; ++i) printf("%d ", b[i]);
	printf("\n");
	*/
	
	f[0]=1;
	for (int i=1; i<=bn; ++i)
		for (int j=100000; j>=1; --j)
			if(j-b[i] >= 0) {
				f[j] |= f[j-b[i]];
			}
	
	int ans=0;
	for (int i=1; i<=100000; ++i) {
		//if(f[i]) printf("%d\n", i);
		ans+=f[i];
	}
	printf("Total=%d\n", ans);	
	return 0;
}

P3. hopscotch

给出一个$n \times m$的矩阵,求从左上角走到右下角有几种走法。

走的规则是:满足下列2个条件,就可以从$(x,y)$走到$(i, j)$。

1. $i>x, j>y$

2. $a_{i,j} \not= a_{x,y}$

对于60%,$n \leq 100$

对于100%,$n \leq 750, a_{i,j} \leq n \times m$

【题解】啊这么难的题目出在第三题意义不明啊。

暴力能拿70

 

# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <string>
# include <iostream>
# include <vector>
# define PB push_back
# define MP make_pair

using namespace std;

int n, m, a[760][760], k;
long long f[760][760], s[760][760];
const long long MOD=1e9+7;
vector< pair<int, int> > v[666666];

int main() {
	
	freopen("hopscotch.in", "r", stdin);
	freopen("hopscotch.out", "w", stdout);
	
	scanf("%d%d%d", &n, &m, &k);
	
	for (int i=1; i<=k; ++i) v[i].clear();
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j) {
			scanf("%d", &a[i][j]);
			v[a[i][j]].PB(MP(i, j));
		}
	
	for (int i=1; i<=k; ++i) sort(v[i].begin(), v[i].end());
			
	f[1][1]=1;
	for (int i=1; i<=n; ++i) s[i][1] = s[1][i] = 1;
	
	for (int i=2; i<=n; ++i)
		for (int j=2; j<=m; ++j) {
			f[i][j] = s[i-1][j-1];
		//	printf("%d %d %d %d\n", i, j, a[i][j], f[i][j]);
			for (int k=0; k<v[a[i][j]].size(); ++k) {
				if(v[a[i][j]][k].first >= i) break;
				if(v[a[i][j]][k].first == i-1 && v[a[i][j]][k].second > j) break;
				if(v[a[i][j]][k].second >= j) continue;
				f[i][j] = f[i][j] - f[v[a[i][j]][k].first][v[a[i][j]][k].second];
				f[i][j] = (f[i][j] + MOD) % MOD;
			}
		//	printf("f[i][j] second, %d\n", f[i][j]);
			s[i][j] = (s[i-1][j] + s[i][j-1] % MOD - s[i-1][j-1] + MOD) % MOD + f[i][j];
			s[i][j] = s[i][j] % MOD;
		//	printf("s[i][j], %d\n", s[i][j]);
			/*
			for (int ii=i-1; ii>=1; --ii) 
				for (int jj=j-1; jj>=1; --jj)
					if(a[i][j] != a[ii][jj]) {
						f[i][j] += f[ii][jj];
						f[i][j] %= MOD;
					//	if(ii == n && jj == m) printf("i=%d, j=%d\n, a[i][j] = %d, a[ii][jj] = %d\n", i, j, a[i][j], a[ii][jj]);
					}
			*/
		}
				
	
	for (int i=1; i<=n; ++i, printf("\n"))
		for (int j=1; j<=m; ++j) printf("%d ", f[i][j]);
	
	cout << f[n][m] << endl;
	return 0;
}

首先我们用一个动态开点的权值线段树的东西。

什么是动态开点?

本来线段树都是一开始build一下建完了,现在是边插入边建

由于线段树插入一个数,其他的数的形态并不需要改变,所以就行啦。

大概insert的最重要的步骤如下(动态开节点)

if(! root) (还没有开节点) root=++tot; (新开节点)

具体可以见代码呀

这题dp是$O(n^4)$挺好想出来的,然后用减法原理变成一个类似于二维前缀和减去一些相等的dp值

那么用动态开点权值线段树就恰好能解决。时间复杂度$O(n^2logn)$

 

# include <stdio.h>
# include <stdlib.h>

using namespace std;

int n, m, k;
long long f[760][760], s[760][760];
int a[760][760];
const int M=760*760*4, MOD = 1e9+7;
int lc[7000010], rc[7000010], num[7000010], root[M], tot=0;

inline void insert(int &rt, int l, int r, int pos, int val) {
	if(!rt) rt=++tot;
	if(l == r && l == pos) {
		num[rt] = num[rt] + val;
		num[rt] %= MOD; 
		return ;
	}
	int mid = l+r >> 1;
	if(pos <= mid) insert(lc[rt], l, mid, pos, val);
	else insert(rc[rt], mid+1, r, pos, val);
	num[rt] = num[lc[rt]] + num[rc[rt]];
	num[rt] %= MOD;
}

inline int query(int rt, int l, int r, int pos) {
	if(!rt) return 0;
	if(r <= pos) return num[rt];
	int mid = (l+r) >> 1, anss=0;
	if(lc[rt]) anss = (anss + query(lc[rt], l, mid, pos)) % MOD;
	if(rc[rt] && pos >= mid+1) anss = (anss + query(rc[rt], mid+1, r, pos)) % MOD;
	return anss;
}

int main() {
	freopen("hopscotch.in", "r", stdin);
	freopen("hopscotch.out", "w", stdout);
	scanf("%d%d%d", &n, &m, &k);
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j) scanf("%d", &a[i][j]);
	f[1][1] = 1;
	for (int i=1; i<=n; ++i)
		s[1][i] = s[i][1] = 1;
	insert(root[a[1][1]], 1, m, 1, 1);
	for (int i=2; i<=n; ++i) {
		for (int j=2; j<=m; ++j) {
			f[i][j] = s[i-1][j-1];
			//printf("i=%d, j=%d\n", i, j);
			// sub
			int gg = query(root[a[i][j]], 1, m, j-1);
			//printf("i=%d, j=%d, s[i-1][j-1]=%d, sub=%d\n", i, j, s[i-1][j-1], gg);
			//printf("%d\n", gg);
			f[i][j] = ((f[i][j] - gg) % MOD + MOD) % MOD; 
			//printf("f[i][j]=%d\n",f[i][j]);
			s[i][j] = f[i][j];
			s[i][j] = (s[i][j] + s[i-1][j]) % MOD;
			s[i][j] = (s[i][j] + s[i][j-1]) % MOD;
			s[i][j] = ((s[i][j] - s[i-1][j-1]) % MOD + MOD) % MOD; 
		}
		for (int j=2; j<=m; ++j) 
			insert(root[a[i][j]], 1, m, j, f[i][j]);
	}
	
	
	printf("%d\n", f[n][m]);
	return 0;
}

P4. alphabet

给出一棵树,树上每个点有一个字母,给出一个字符串,问树上是否找得到一条路径对应的字符串是这个。

$n \leq 10000, T \leq 5$

【题解】垃圾题目毁我青春

你没有看错这题就是暴力,复杂度$O(Tn^2)$

 

# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <string>
# include <iostream>
# include <queue>

using namespace std;

int T, n, TT;
int tot=0, next[666666], to[666666], head[666666];
char str[666666], qu[666666];
int qs=0;
bool alphause[222];
bool FIND;

inline void add(int u, int v) {
	++tot;
	next[tot]=head[u];
	head[u]=tot;
	to[tot]=v;
}

inline void go(int x, int now) {
	if(FIND) return;
	if(now == qs) {
		FIND=1;
		return;
	}
	for (int i=head[x]; i; i=next[i]) {
		if(str[to[i]] == qu[now+1]) {
			go(to[i], now+1);
			if(FIND) return;
		}
	}
}

int main() {
	
	freopen("alphabet.in", "r", stdin);
	freopen("alphabet.out", "w", stdout);
	
	scanf("%d", &T); TT=T;
	while(T--) {
		memset(head, 0, sizeof(head));tot=0;FIND=0;
		memset(alphause, 0, sizeof(alphause));
		scanf("%d", &n);
		for (int i=1, u, v; i<n; ++i) {
			scanf("%d%d", &u, &v);
			add(u, v);
			add(v, u);
		}
		scanf("%s", str+1);
		scanf("%s", qu+1);
		for (qs=1; qu[qs]; ++qs); --qs;
		for (int i=1; i<=n; ++i) alphause[str[i]]=1;
		bool gg=0;
		for (int i=1; i<=qs; ++i)
			if(!alphause[qu[i]]) {
				gg=1;
				break;
			}
		if(gg) {
			printf("Case #%d: Impossible\n", TT-T);
			continue;
		}
		int beg, end;
		beg = end = 0;
		for (int i=1; i<=n; ++i) {
			if(str[i] == qu[1]) beg++;
			if(str[i] == qu[qs]) end++;
		}
		if(end < beg) reverse(qu+1, qu+qs+1);
		bool ok=0;
		for (int i=1; i<=n; ++i) {
			if(qu[1] == str[i]) {
				go(i, 1);
				if(FIND) {
					ok=1;
					break;
				}
			}
		}
		if(FIND) printf("Case #%d: Find\n", TT-T);
		else printf("Case #%d: Impossible\n", TT-T);
	}
	
	return 0;
}

p5. route

给出一个$n \times m$的矩阵,要你从左上角向右下角走一条路径,每次向右走或者向下走。

求出路径上经过的点的方差的最小值乘路径长度。

$n,m,a_{i,j} \leq 30$

【题解】这种题目一般推推公式就行啦

令$N = n+m-1$

$w = N \sum_{i in route} a_{i}^{2} - ( \sum_{i in route} a_{i})^2$

然后dp转移啦,$f[i, j, sum]$表示到$(i,j)$,和为$sum$的最小值

转移自己想QAQ,时间复杂度$O(n^4)$

考场上傻逼了想成了$O(n^6)$的复杂度

P.S. sps三分过了。。。

 

# include <stdio.h>
# include <stdlib.h>
# include <algorithm>
# include <string.h>
# include <math.h>
# include <string>
# include <iostream>

using namespace std;

int n, m, a[60][60];
long long f[33][33][2223];
bool can[33][33][2223];

int main() {
	
	freopen("route.in", "r", stdin);
	freopen("route.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j) scanf("%d", &a[i][j]);
	
	
	f[1][1][a[1][1]] = (n+m-2)*a[1][1]*a[1][1];
	can[1][1][a[1][1]] = 1;
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j) {
			if(i==1 && j==1) continue;
			for (int k=0; k<=2222; ++k) {
				if(k-a[i][j] >= 0) {
					bool fz=0;
					f[i][j][k] = 0;
					if(can[i-1][j][k-a[i][j]]) f[i][j][k] = f[i-1][j][k-a[i][j]], fz=1, can[i][j][k] = 1;
					if(can[i][j-1][k-a[i][j]]) {
						can[i][j][k] = 1;
						if(!fz) f[i][j][k] = f[i][j-1][k-a[i][j]], fz=1;
						else f[i][j][k] = min(f[i][j][k], f[i][j-1][k-a[i][j]]);
					}
					if(fz == 0) continue;
					f[i][j][k] += (k-a[i][j])*(k-a[i][j]) + (n+m-1)*a[i][j]*a[i][j] - k*k;
					f[i][j][k] = max(f[i][j][k], 0LL);
				}
			} 
		}
	/*
	for (int i=1; i<=n; ++i)
		for (int j=1; j<=m; ++j)
			for (int k=0; k<=10; ++k) printf("i=%d, j=%d, k=%d, f[i][j][k] = %d\n", i, j, k, f[i][j][k]); 
	*/ 
	long long ans = 7777777778888888LL;
	for (int k=0; k<=2222; ++k) if(f[n][m][k] != 0) ans = min(ans, f[n][m][k]);
	cout << ans << endl;
	return 0;
}

/*
N=n+m-1;
w=sigma(N*(ai-sum/N)^2).
w=sigma(N*(ai^2+sum^2/N^2-2*ai*sum/N))
w=sigma(N*ai^2 + sum^2/N - 2*ai*sum)
w=N sigma ai^2 - sum^2
*/



 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter