注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Saffah's Blog

 
 
 

日志

 
 

Bayan 2015 Contest Warm Up  

2014-10-06 08:24:10|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
这场做了大半天Rating居然没变化……感觉跟白打了一样……哪怕掉Rating也好呀……
(C题不FST就能上红了T_T……)
.
475A Bayan Bus
这题你看了样例就知道题意和做法了。
看房间里有个人居然打了35的表= =……
int n;
const char *s1 = "|#.#.#.#.#.#.#.#.#.#.#.|D|)";
const char *s2 = "|#.#.#.#.#.#.#.#.#.#.#.|.|";
const char *s3 = "|#.......................|";
const char *s4 = "|#.#.#.#.#.#.#.#.#.#.#.|.|)";
char buf[100];
int main(){
	read(n);
	printf("+------------------------+\n");
	
	memcpy(buf, s1, sizeof(buf));
	if(n >= 1) buf[1] = 'O';
	f(i, 2, 11) if(n >= 3 * i - 1) buf[i * 2 - 1] = 'O';
	printf("%s\n", buf);
	
	memcpy(buf, s2, sizeof(buf));
	if(n >= 2) buf[1] = 'O';
	f(i, 2, 11) if(n >= 3 * i) buf[i * 2 - 1] = 'O';
	printf("%s\n", buf);
	
	memcpy(buf, s3, sizeof(buf));
	if(n >= 3) buf[1] = 'O';
	printf("%s\n", buf);
	
	memcpy(buf, s4, sizeof(buf));
	f(i, 1, 11) if(n >= 3 * i + 1) buf[i * 2 - 1] = 'O';
	printf("%s\n", buf);
	printf("+------------------------+\n");
	return 0;
}

475B Strongly Connected City
给一个网格形的交通网络,每条路都是单行路,问整个图是否强连通。
网格规模不超过20×20。
Solution
我当时没仔细分析直接写了个Floyd交了上去……
实际上只需要看四个角是否强连通就行了。

int n, m;
int adj[24][24][24][24];
char buf[24];

int main(){
	read(n, m);
	memset(adj, 0, sizeof(adj));
	scanf("%s", buf + 1);
	f(i, 1, n) if(buf[i] == '<') f(j, 1, m) adj[i][j][i][j - 1] = 1; else f(j, 1, m) adj[i][j][i][j + 1] = 1;
	scanf("%s", buf + 1);
	f(j, 1, m) if(buf[j] == '^') f(i, 1, n) adj[i][j][i - 1][j] = 1; else f(i, 1, n) adj[i][j][i + 1][j] = 1;
	f(kx, 1, n) f(ky, 1, m) f(ix, 1, n) f(iy, 1, m) f(jx, 1, n) f(jy, 1, m) if(adj[ix][iy][kx][ky] && adj[kx][ky][jx][jy]) adj[ix][iy][jx][jy] = 1;
	bool good = true;
	f(ix, 1, n) f(iy, 1, m) f(jx, 1, n) f(jy, 1, m) if(!adj[ix][iy][jx][jy]) good = false;
	if(good) printf("YES\n"); else printf("NO\n");
	return 0;
}

475C Kamal-ol-molk's Painting
给一个不超过1000×1000的黑白图,问它是否可以通过以下规则画出:
刷子是x×y的矩形块,每次矩形可以向下或向右移一格,然后把所有经过的格子涂黑。
如果能画出,还要求出刷子的最小面积。
Solution
我的做法细节巨多……
首先要判它大体是个右下右下右下或者下右下右下右的形状……
如果是的话,还要判具体是下右下右下还是下右下右下右还是右下右下右还是右下右下右下……
然后就在1×1的情况挂掉了= =……
int n, m, x1, x2, y1, y2;
char map[1009][1009];
std::vector<PII> A, B;

int main(){
	read(n, m);
	if(n == 1 && m == 1){
		printf("1\n"); return 0;
	}
	memset(map, '.', sizeof(map));
	f(i, 1, n){
		scanf("%s", map[i] + 1);
		map[i][m + 1] = '.';
	}
	x1 = 10000, x2 = -1, y1 = 10000, y2 = -1;
	f(i, 1, n) f(j, 1, m) if(map[i][j] == 'X'){
		if(i < x1) x1 = i;
		if(i > x2) x2 = i;
		if(j < y1) y1 = j;
		if(j > y2) y2 = j;
	}
	if(map[x1][y1] != 'X'){
		printf("-1\n"); return 0;
	}
	if(map[x2][y2] != 'X'){
		printf("-1\n"); return 0;
	}
	int lj = -1, hj = -1;
	f(i, x1, x2){
		int j = y1;
		while(map[i][j] == '.' && j <= y2) ++j;
		if(j < lj || j > y2){
			printf("-1\n"); return 0;
		}else lj = j;
		j = y2;
		while(map[i][j] == '.' && j >= y1) --j;
		if(j < hj || j < y1){
			printf("-1\n"); return 0;
		}else hj = j;
		f(j, lj, hj) if(map[i][j] != 'X'){
			printf("-1\n"); return 0;
		}
	}
	// printf("x %d %d %d %d\n", x1, y1, x2, y2);
	int cx = x1, cy = y1;
	while(cx != x2 || cy != y2){
		int lx = cx, ly = cy;
		while(map[cx][cy + 1] == 'X') ++cy;
		while(map[cx][cy + 1] == '.' && map[cx + 1][cy] == 'X') ++cx;
		// printf("cx cy %d %d\n", cx, cy);
		A.push_back(PII(cx - lx + 1, cy - ly + 1));
	}
	cx = x1, cy = y1;
	while(cx != x2 || cy != y2){
		int lx = cx, ly = cy;
		while(map[cx + 1][cy] == 'X') ++cx;
		while(map[cx + 1][cy] == '.' && map[cx][cy + 1] == 'X') ++cy;
		B.push_back(PII(cx - lx + 1, cy - ly + 1));
	}
	if(abs(A.size() - B.size()) > 1){
		printf("-1\n"); return 0;
	}
	// printf("asdf %d\n", A.size());
	// foreach(it, A) printf("%d %d\n", it->first, it->second);
	// printf("asdf %d\n", B.size());
	// foreach(it, B) printf("%d %d\n", it->first, it->second);
	int ans = 100000086;
	if(A.size() > B.size()){
		int n = B.size();
		g(i, 1, n) if(A[i].second != B[i - 1].second || A[i].first != B[i].first) goto fail1;
		ans = std::min(ans, A[0].second * A[n].first);
		fail1:;
	}
	if(B.size() > A.size()){
		int n = A.size();
		g(i, 1, n) if(B[i].first != A[i - 1].first || B[i].second != A[i].second) goto fail2;
		ans = std::min(ans, B[0].first * B[n].second);
		fail2:;
	}
	if(A.size() == B.size() && B[0].first - A[0].first + 1 > 0){
		int n = A.size();
		g(i, 1, n) if(A[i].second != B[i - 1].second) goto fail3;
		g(i, 2, n) if(A[i - 1].first != B[i - 1].first) goto fail3;
		ans = std::min(ans, A[0].second * (B[0].first - A[0].first + 1));
		// printf("AAA\n");
		fail3:;
	}
	if(A.size() == B.size() && A[0].second - B[0].second + 1 > 0){
		int n = A.size();
		g(i, 1, n) if(B[i].first != A[i - 1].first) goto fail4;
		g(i, 2, n) if(B[i - 1].second != A[i - 1].second) goto fail4;
		ans = std::min(ans, B[0].first * (A[0].second - B[0].second + 1));
		// printf("BBB\n");
		fail4:;
	}
	if(ans == 100000086) ans = -1;
	printf("%d\n", ans);
	return 0;
}

475D CGCDSSQ
给一个长度为n的序列和q次询问,每次询问给出x,求1≤l≤r≤n且gcd(a[l]..a[r])=x的二元组(l,r)数目。
n≤100000,q≤300000。
Solution
枚举l,会发现gcd(a[l]..a[r])的取值个数不会很多。断点可以二分配合ST表来搞。
然后就可以把所有的答案表都打出来了!时间复杂度O(n * log^2 n + q * log n),注意写成3个log的算法是过不了的……
inline int gcd(int x, int y){
	while(y){
		int t = x % y; x = y; y = t;
	}
	return x;
}
int a[17][100009], n;
std::map<int, LL> ans;

int main(){
	int n; read(n);
	read(a[0], n);
	a[0][n] = 1;
	f(j, 1, 16) f(i, 0, n){
		int tmp = i + (1 << (j - 1));
		if(tmp <= n) a[j][i] = gcd(a[j - 1][i], a[j - 1][tmp]); else a[j][i] = a[j - 1][i];
	}
	g(i, 0, n){
		int cg = a[0][i], ci = i, li = i;
		while(cg > 1){
			h(j, 16, 0) if(a[j][ci] % cg == 0){
				ci += (1 << j); if(ci > n) ci -= n;
			}
			ans[cg] += (LL) (ci - li);
			li = ci; cg = gcd(cg, a[0][ci]);
		}
		ans[1] += (LL) (n - ci);
	}
	int q; read(q);
	while(q--){
		int x; read(x); writeln(ans[x]);
	}	
	return 0;
}

475E 475F 弃疗……据说一个是双连通缩点背包,一个是平衡树模拟……
  评论这张
 
阅读(172)| 评论(6)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018