[Codechef]2014 December Challenge

xllend3 posted @ 2014年12月15日 20:55 in 未分类 with tags codechef , 942 阅读

由于这个月有两个招先哥和一个乱搞哥就准备混个前10所以后来challenge懒得刷了

刚开始一个小哥把spj爆掉了,分数直接比乱搞哥的两倍还高。。。当时不敢相信就觉得他是把spj爆掉了。。。后来rejudge了才发现真的是把spj爆掉了。。。那个小哥以为是0-indexed,然后用0和1~n-1连边。。。spj居然没判出来。。。

SANSKAR 我直接[tex]2^{2^{21}}[/tex]爆搜的。。。听说直接搜不回溯都能A。。。无语了。。。

SEAGCD 我直接[tex]n\log n[/tex]暴力容斥+大力常数优化过的。。。

scanf("%d%d%d%d",&n,&m,&L,&R);
rep(i,1,m){
	if(i-1&&m/i==(m/(i-1)))f[i]=f[i-1];else f[i]=powmod(m/i,n);
}
dep(i,m,1){
	if(m/i==m/(i+1))f[i]=f[i+1];
	else{
		for(int j=i+i;j<=m;j+=i)f[i]-=f[j];
	}
}
ll ans=0;rep(i,L,R)ans=(ans+f[i])%mod; 
printf("%lld\n",(ans+mod)%mod);

不会更优的算法。。。

RIN 详见陈高远TC原题。网络流一遍没了。详见CF248D和SRM590Hard。

DIVIDEN 首先你得画出3°,大概是用36°和30°搞。然后所有不是3的倍数的都可以画。扭一下坐标系的话会很好写。

GOODGAL 不明觉厉的题。感觉非常傻逼但是过的人居然这么少。直接判每个点的出度和随机选两个点判和它们都相邻的点的个数是不是等于应该等于的值即可。虽然不会证明正确性但是好像不好卡。

KALKI 一开始想了很多种算法都打不过最小生成树,后来睡觉前突然想到每次选边的时候估价一下,每个当前值为x的时候就加上[tex]x^2[/tex]的代价。不过这样复杂度有点高,每次都要扫一遍所有边。所以每个点只取最近的20条边。然后卡着时限能过。这样已经够艹掉shizhouxing了。然后发现把[tex]x^2[/tex]改成[tex]x^8[/tex]直接和tankengineer一样高了。然后加了一些break优化改成计算多次好像效果也没好多少然后就弃疗了


登录 *


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