BestCoder Round #87

tonyfang posted @ 2016年9月25日 20:10 in HDU with tags c++ OI , 554 阅读

Zimpha的比赛看上去很excited?(雾)

前面A题hack了14发全成功了,final test后排第19,excited。

今天起来一看掉到90多了发现A题不算hack。。无言以对,而且竟然rated了,好在rating涨了。

A. GCD is Funny

黑板上有$n$个数$a_1, a_2, ..., a_n$,你有一种操作:取三个数擦除,选择其中两个数取gcd,把gcd在黑板上写两遍。很明显$n-2$轮后会有两个一样的数,求可能的数的集合。

$n \leq 500, a_i \leq 1000, T \leq 100$

【题解】就是元素个数在$[2, n-2]$范围内的gcd都可行。用一些特别的技巧(类似拓扑dp?)

复杂度$O(Tn|a_i|)$

 

# include <stdio.h>
# include <algorithm>
# include <string.h>

using namespace std;

int T, n, a[510], amx;
int f[1010], g[1010], gn;
inline int gcd(int u, int v) {
	return v == 0 ? u : gcd(v, u%v);
}

int main() {
	scanf("%d", &T);
	for (int cas=1; cas<=T; ++cas) {
		scanf("%d", &n);
		amx = -1;
		for (int i=1; i<=n; ++i) {
			scanf("%d", &a[i]);
			amx = max(amx, a[i]);
		}
		gn = 0;
		for (int i=1; i<=1000; ++i)
			f[i] = g[i] = 0;
		int GCD = a[1];
		for (int i=1; i<=n; ++i) {
			GCD = gcd(GCD, a[i]);
			for (int j=gn; j>=1; --j) {
				int tmp = gcd(g[j], a[i]);
				if (! f[tmp]) 
					g[++gn] = tmp;
				f[tmp] += f[g[j]];
			}
			if(!f[a[i]]) g[++gn] = a[i];
			f[a[i]] ++;
		}
		for (int i=1; i<=n; ++i) f[a[i]] --;
		f[GCD] --;
		bool first = 1;
		for (int i=1; i<=1000; ++i) {
			if(f[i]) {
				if(first) {
					printf("%d", i);
					first = 0;
				} else printf(" %d", i);
			}
		}
		puts("");
	}
	return 0;	
}

B. Square Distance

求一个字符串,使得它的前半部分能完全匹配它的后半部分,且与题目给的字符串的不匹配位置数等于$m$

$|S| \leq 1000, m \leq |S|$

DP一半,因为要字典序最小,所以倒着dp,之后贪心填数字即可。

 

# include <stdio.h>
# include <string.h> 
// # include <bits/stdc++.h>

using namespace std;

int n, m;
char s[1010];
bool f[1010][1010];
char t[1010]; 
// f[i, j]  到i位置,失配j位是否可行。 


int main() {
	int T; scanf("%d", &T);
	while(T--) {
		memset(f, 0, sizeof(f)); 
		scanf("%d%d", &n, &m);
		scanf("%s", s+1);
		int diff = 0;
		for (int i=1; i<=n/2; ++i) {
			if(s[i] != s[i+n/2]) ++diff;
		}
		if(diff>m) {
			puts("Impossible");
			continue;
		}
		f[n/2+1][0]=1; 
		for (int i=n/2; i>=1; --i)
			if(s[i] == s[i+n/2]) {
				for (int j=0; j<=m; ++j) {
					f[i][j] |= f[i+1][j];
					if(j>=2) f[i][j] |= f[i+1][j-2];
				}
			} else {
				for (int j=1; j<=m; ++j) {
					f[i][j] |= f[i+1][j-1];
					if(j>=2) f[i][j] |= f[i+1][j-2];
				}
			}
		if(f[1][m] == 0) {
			puts("Impossible");
			continue;
		}
		int cursp = 0;
		for (int i=1; i<=n/2; ++i)
			for (int j='a'; j<='z'; ++j) {
				int curj = cursp;
				if(j != s[i] || j != s[i+n/2]) ++ curj;
				if(j != s[i] && j != s[i+n/2]) ++ curj;
				if(m - curj < 0) continue; 
				if(f[i+1][m - curj]) {
					 t[i] = j; t[i+n/2] = j; 
					 j = 'z'+1;
					 cursp = curj;
				}
			}
		for (int i=1; i<=n; ++i) printf("%c", t[i]);
		puts("");		  
	}
	return 0;
}

C. LCIS

求LCIS,要求数是连续的自然数。

$n \leq 100000, T \leq 1000$

【题解】

为啥别人都用dp呢我用的还是图论做法……

很明显后面相邻一定没有前面相邻优,可以构出一张图,每个点只往出去连一条边。然后就是最长链啦,$O(n)$解决,总复杂度$O(n)$。

 

# include <stdio.h>
# include <algorithm>
# include <string.h>

using namespace std;

const int M=1000010;
int nexta[100010], nextb[100010], bb[1000010], a[100010], b[100010], lsta[1000010], lstb[1000010];
bool vis[100010];
int ans = -1;
int T, n, m;
int main() {
	scanf("%d", &T);
	while(T--) {
		ans = -1;
		scanf("%d%d", &n, &m);
		for (int i=1; i<=n; ++i)
			scanf("%d", &a[i]), vis[i]=0, lsta[a[i]] = lsta[a[i]+1] = n+1;
		for (int i=1; i<=m; ++i) {
			scanf("%d", &b[i]);
			lstb[b[i]] = lstb[b[i]+1] = m+1;
		}
		for (int i=n; i>=1; --i)
			bb[a[i]] = m+1;
		for (int i=m; i>=1; --i) 
			bb[b[i]] = i;
		for (int i=n; i>=1; --i) {
			lsta[a[i]] = i;
			nexta[i] = lsta[a[i]+1];
		}
		for (int i=m; i>=1; --i) {
			lstb[b[i]] = i;
			nextb[i] = lstb[b[i]+1];
		}
		for (int i=1; i<=n; ++i) {
			if(!vis[i]) {
				int start=a[i], l=0;
				int x=i, y=bb[a[i]];
				for (;;) {
					if(1 <= x && 1 <= y && x <= n && y <= m) {
						++l;
						vis[i] = 1;
						x = nexta[x], y = nextb[y];
					} else break;
				}
				if(l>ans) ans=l;
			}
		}
		printf("%d\n", ans);
	}

	return 0;
}

 

 

model-papers.in 说:
2023年4月19日 16:17

Board Model Paper 2023 Aspirants who had Registered for the Board 12th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. model-papers.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.


登录 *


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