Noip2016 四校联考 FJSDFZ Round 1

tonyfang posted @ 2016年9月25日 19:36 in 随笔 with tags c++ OI , 281 阅读

今天早上四校联考

T1:萝卜种子

袋子里有4种萝卜种子,分别是普通萝卜,超能萝卜,固氮萝卜和金坷垃萝卜,它们的数量分别是$N_{pt}, N_{cn}, N_{gd}, N_{jkl}$,现在我把它们全部播种到地里,今年秋天我能收获的兔粮的期望是多少?你发现田里最多只能生长7个萝卜(多余的种子不会发芽),且4种萝卜发芽的概率是完全相同的。它们的效果分别是:

普通萝卜(pt):生产2kg兔粮

超能萝卜(cn):生产2kg兔粮,每种植一个其他萝卜额外产生1kg兔粮

固氮萝卜(gd):不能用于生产兔粮,但能使每个普通萝卜和超能萝卜生产的兔粮+1kg

金坷垃萝卜(jkl):不能用于生产兔粮,但能使每个普通萝卜和超能萝卜生产的兔粮+2kg

求期望获得多少兔粮。

$N_{pt}, N_{cn}, N_{gd}, N_{jkl} \leq 10$

T2:打败黑熊

凶恶的黑熊的陷阱一共有N+1个机关,机关分为3种,它们分别是:

守卫机关(d):该机关有一个守卫,守卫不会主动攻击,小兔可以选择无视守卫直接通过机关或者杀死该守卫,杀死守卫会使自身的罪恶值+1,并获得一定数量的战斗力

审判机关(p):该机关有一个守卫,不能被杀死,如果小兔的罪恶值大于或等于守卫的触发上限,守卫就会主动攻击小兔,小兔直接阵亡

黑熊机关:前N个机关均不是黑熊机关,第N+1个机关一定是黑熊机关,只有小兔的罪恶值大于或等于M才能通过,否则小兔直接阵亡

小兔希望在通关的基础上获得最大的战斗力以便和黑熊硬碰硬。

$n, m \leq 500000$

T3:种胡萝卜

在嫦娥的帮助下,狐狸将土地拓成了M个坑排成一排,从左到右按1~M编号,每个坑里可以种一个胡萝卜,在N天小兔都会凭心情选择一个坑,狐狸会到那个坑种胡萝卜,如果已经被占用,则会种在前一个坑里,如果依然被占用,狐狸会再往前找空的坑,直到找到空的坑或者发现前面没有可用的坑为止。

你本来需要输出N行,每一行表示当天的胡萝卜将种在哪一个坑里(无法种下输出0),设这些数为$p_1, p_2, ..., p_n$,那么你要输出的就是$(\sum_{i=1}^{n}i\times p_i ) mod (10^9+7)$。
$n, m\leq 3000000$

【当场情况】

发现第一题好像只要枚举就行了?后来写完一份发现不大对,样例怎么只给四个数都相等的情况……就想到了期望要算概率,随便写了写组合数算概率,算了算精度感觉没问题。

然后开始看第二题,一开始以为dp不会优化,后来就弃疗了。先看第三题,咦这不做过吗,似乎只要并查集维护下就行了?300w的并查集,不要虚!写完还是虚了,加了个读入优化。

然后看第二题,突然也会了,这直接贪心不就完了??用个set维护下就行啦!然后快速的打完了代码。一个半小时……

预计得分100+100+100=300

实际得分90+40+90=230

奇怪的问题:第一题,由于出题人懒得写spj所以精度被卡了,printf输出的时候会出现奇怪的问题所以要加一点eps上去就行了。zzq奇怪的精度竟然跟出题人一样就过了。。

第三题:评测机好坑啊300w并查集竟然炸了???看来要用fread了。

第二题:set也被卡常数了???那就priority_queue

订正情况:100+100+100=300,用时15min

 

# include <stdio.h>
# include <algorithm>
using namespace std;

int n1, n2, n3, n4;
typedef long double ld;
ld ans=0;

inline ld C(int b, int a) {
	ld ret=1.0;
	for (int i=a-b+1; i<=a; ++i) ret=ret*(ld)i;
	for (int i=1; i<=b; ++i) ret=ret/(ld)i;
	return ret;
}

int main() {
	freopen("seed.in", "r", stdin);
	freopen("seed.out", "w", stdout);
	scanf("%d%d%d%d", &n1, &n2, &n3, &n4);
	int times = min(n1+n2+n3+n4, 7);
//	printf("%d\n", times);
	for (int i1=0; i1<=n1; ++i1)
		for (int i2=0; i2<=n2; ++i2)
			for (int i3=0; i3<=n3; ++i3)
				for (int i4=0; i4<=n4; ++i4) {
					if(i1+i2+i3+i4 != times) continue;
					ld gg = C(i1, n1) * C(i2, n2) * C(i3, n3) * C(i4, n4);
//					printf("%.2lf\n", (double)gg);
					ld tmp = (ld)i1*(2+i3+2*i4) + (ld)i2*(i3+2*i4+times+1);
					tmp = tmp*gg;
					ans += tmp;
//					printf("%.2lf\n", (double)ans);
				}
	ld div = 1.0/C(times, n1+n2+n3+n4);
	ans = ans*div;
	printf("%.2lf\n", (double)(ans+0.0001));
	return 0;
}

 

# include <stdio.h>
# include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > s;
int n, m; char st[6];
int main() {
	freopen("beatbear.in", "r", stdin);
	freopen("beatbear.out", "w", stdout);
	scanf("%d%d", &n, &m);
	for (int i=1, t; i<=n; ++i) {
		scanf("%s%d", st, &t);
		if(st[0] == 'd') {
			s.push(t);
			continue;
		}
		if(t<=0) {
			puts("Rabbit can not beat bear.");
			return 0;
		}
		while(s.size() >= t) 
			s.pop();
	}
	
	int ans = 0, sz=0;
	while(!s.empty()) {
		ans+=s.top(); sz++;
		s.pop();
	}
	if(sz >= m) {
		printf("%d\n", ans);
	} else {
		puts("Rabbit can not beat bear.");
		return 0;	
	}
	return 0;
}

 

# include <stdio.h>
using namespace std;

int n, m, t, fa[3000010];
typedef long long ll;
const ll mod = 1000000007;
ll ans = 0;

inline int read() {
	int x=0; char ch=getchar();
	while(ch<'0' || ch>'9') ch=getchar();
	while(ch>='0' && ch<='9') {
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x;
}

inline int getf(int x) {
	return fa[x] == x ? x : fa[x] = getf(fa[x]);
}


int main() {
	freopen("carrot.in", "r", stdin);
	freopen("carrot.out", "w", stdout);
	n=read(), m=read();
	for (int i=0; i<=m; ++i)
		fa[i]=i;
	for (int i=1; i<=n; ++i) {
		t=read();
		if(t>m) t=m;
		int fu = getf(t);
		if(fu==0) continue;
		int fv = getf(fu-1);
		//printf("%d %d\n", fu, fv);
		ans = ans + (ll)fu*(ll)i;
		ans = ans % mod;
		if(fu != fv) fa[fu] = fv;
	}
	printf("%d\n", (int)ans);
	return 0;
}

【后续】

出题人在题解中写道,为何防止圣骑士的斩杀被嘲笑,他出了第一道题

普通萝卜=蓝腮战士,超能萝卜=老瞎眼,固氮萝卜=暗鳞先知,金坷垃萝卜=鱼人领军


登录 *


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