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

Saffah's Blog

 
 
 

日志

 
 

Codeforces Round #268 (Div. 1)  

2014-09-23 11:11:39|  分类: Codeforces |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
468A. 24 Game
有n个数1,2,...,n,每次你可以选其中两个数,删掉它们,加入它们的和、差或积。问执行n-1步操作以后能否让最后剩下的数变成24。
n≤100000。
Solution
如果n≤3那么显然无解。4和5的情况可以手工构造。
一个简单的思路:用1+2-3得到0,用4*6得到24,用0乘剩下的一堆数,加上24等于24。
(我当场的方法太2了……)
int main(){
	int n; read(n);
	if(n <= 3){
		printf("NO\n");
	}else if(n == 4){
		printf("YES\n");
		printf("1 * 2 = 2\n");
		printf("2 * 3 = 6\n");
		printf("6 * 4 = 24\n");
	}else if(n == 5){
		printf("YES\n");
		printf("4 + 5 = 9\n");
		printf("9 * 3 = 27\n");
		printf("27 - 1 = 26\n");
		printf("26 - 2 = 24\n");
	}else{
		printf("YES\n");
		LL cans = 5;
		f(i, 7, n){
			LL nans = cans + (LL) i;
			printf("%I64d + %d = %I64d\n", cans, i, nans);
			cans = nans;
		}
		printf("1 + 2 = 3\n");
		printf("3 - 3 = 0\n");
		printf("0 * %I64d = 0\n", cans);
		printf("4 * 6 = 24\n");
		printf("24 + 0 = 24\n");
	}
	return 0;
}
468B. Two Sets
给n个数,要求给它们划分成2个集合A和B,使得:对于每个x∈A,总有a-x∈A;每个x∈B,都有b-x∈B。求方案或输出无解。
n≤100000。
Solution
首先暴力2-SAT是能水过的。
考虑x和a-x。如果x在A那么a-x一定在A。如果x在B,假设a-x在B,那么x在A,矛盾。所以如果x在B,那么a-x也一定在B。
也就是说,x和a-x一定要在同一个集合当中。当然这对b-x也成立。
按照“一定在同一个集合当中”的关系连边,对于每个连通块,枚举整个块是放在A还是放在B,如果都不行就是无解。
int n, a, b;
int p[100086];
std::map<int, int> q;
int cn = 0, col[100086], ans[100086];
std::vector<int> cp[100086];

inline void dfs(int x, int c){
	if(col[x]) return;
	col[x] = c; cp[c].push_back(x);
	std::map<int, int>::iterator it = q.find(a - p[x]);
	if(it != q.end()) dfs(it->second, c);
	it = q.find(b - p[x]);
	if(it != q.end()) dfs(it->second, c);
}
struct fin{};

int main(){
	read(n); read(a); read(b);
	read(p + 1, n);
	f(i, 1, n) q[p[i]] = i;
	memset(col, 0, sizeof(col));
	f(i, 1, n) if(!col[i]){
		++cn; dfs(i, cn);
	}
	try{
		f(i, 1, cn){
			bool cana = true, canb = true;
			foreach(x, cp[i]){
				std::map<int, int>::iterator it = q.find(a - p[*x]);
				if(it == q.end()) cana = false;
				it = q.find(b - p[*x]);
				if(it == q.end()) canb = false;
			}
			if(cana){
				foreach(x, cp[i]) ans[*x] = 0;
			}else if(canb){
				foreach(x, cp[i]) ans[*x] = 1;
			}else throw(fin());
		}
		printf("YES\n");
		f(i, 1, n) printf("%d ", ans[i]);
		printf("\n");
	}catch(fin){
		printf("NO\n");
	}
	return 0;
}
468C. Hack it!
设f(x)表示x的十进制表示中各位数字之和。给出a,求1≤l≤r≤10^200,使得f(l)+f(l+1)+...+f(r) mod a =0。
1≤a≤10^18。
Solution
先说我的笨办法。
一开始,我猜:答案一定形如:l=xxxxxx,r=1xxxxxx,于是在ull范围枚举x的长度,搞了半天发现第二个样例跑不出来。
后来我减弱了条件,答案一定形如:l=axxxxxx,r=bxxxxxx,其中b=a+1,于是在ull范围枚举,发现还是跑不出来。
后来我干脆连b=a+1也不要了,发现还是跑不出来。
后来直接减弱到了:l=yyyyyaxxxxx,r=yyyyybxxxxx,其中在ull范围枚举xxxxx,发现终于能过pretests了。
然后WA on 8,发现a=1……特判掉了以后a=2又挂了……
于是发现枚举x长度的时候忘了0……
于是就过了……

然后是一个神方法:只要在ull以外枚举l=xxxxxx,r=1xxxxxx就可以搞定了。例如取x的长度为20,我们有f(x+10^20)=f(x)+1,这样每次都加1迟早会加出a来。python代码只有3行……
typedef unsigned long long ULL;
const ULL pow10[18] = {1ULL,10ULL,100ULL,1000ULL,10000ULL,100000ULL,1000000ULL,10000000ULL,100000000ULL,1000000000ULL,10000000000ULL,
100000000000ULL,1000000000000ULL,10000000000000ULL,100000000000000ULL,1000000000000000ULL,10000000000000000ULL,100000000000000000ULL,
};
char buf[1008], fmt[108], *cb = buf;
int main(){
	ULL a; scanf("%I64u", &a);
	f(k, 0, 15) f(y, 0, 9) f(z, y + 1, 9){
		ULL ll = 0;
		g(i, y, z) ll += ((ULL) i * 10ULL + 45ULL * (ULL) k);
		if(k) ll *= pow10[k - 1]; else ll /= 10ULL;
		if(ll >= a) continue;
		ULL x = a - ll;
		if(x % (ULL) (z - y) != 0ULL) continue;
		x = x / (ULL) (z - y) - 1ULL;
		ULL A = x / pow10[k]; x %= pow10[k];
		if((A + 8ULL) / 9ULL + (ULL) k >= 200ULL) continue;
		ULL L = (ULL) y * pow10[k] + x + 1ULL;
		ULL R = (ULL) z * pow10[k] + x;
		if(A){
			int T = A / 9ULL;
			f(i, 1, T) cb += sprintf(cb, "9");
			T = A % 9LL;
			if(T) cb += sprintf(cb, "%d", T);
			sprintf(fmt, "%%s%%0%dI64u %%s%%0%dI64u\n", k + 1, k + 1);
			printf(fmt, buf, L, buf, R);
		}else printf("%I64u %I64u\n", L, R); return 0;
	}
	printf("WTF?\n");
	return 0;
}
D和E等修炼几辈子再来补T_T……先把100道题刷过……
  评论这张
 
阅读(175)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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