Noip2016 四校联考 FJSDFZ Round 1

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

今天早上四校联考

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;
}

【后续】

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

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

ekhan.net 说:
2023年4月21日 16:15

How to Update/Renew Your Cell Phone Number with Indian Overseas Bank, The recommendations of the Reserve Bank of India are followed by the national bank Indian Overseas Bank. The bank has been offering a variety of handy ekhan.net services and amenities to its public banking clients. Registration for Indian Overseas Bank (IOB) Mobile Banking, How to Update/Renew Your Cell Phone Number with Indian Overseas Bank, The recommendations of the Reserve Bank of India are followed by the national bank Indian Overseas Bank. The bank has been offering a variety of handy services and amenities to its public banking clients. Registration for Indian Overseas Bank (IOB) Mobile Banking.


登录 *


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