11.5NOIP模拟赛解题报告

心路历程

预计得分：\(100 + 40 + 30 = 170\)

实际得分：\(100 +100 + 50 = 250\)

辣鸡数据毁我青春

T1一眼不会做感觉要凉

T2好像一波折半搜索就做完了

T3好像是神仙题不会做。。

打完T1暴力后去淦T2，结果最后在排序的时候把greater<LL>()写成了greater<int>()，不过感谢辣鸡数据放我一条活路。。

手玩了一下T1发现根本不需要决策，只算算期望就行了，然后大胆猜了个结论就不管了

这时候大概还剩\(1.5h\)，感觉T3一定是个不可做题于是手动把难度加了两个档次。。

明明能\(O(1)\)算出来的我非要推个\(O(10^8)\)的组合数。于是就凉了。。

Sol

T1

直接算期望是对的。

证明的话可以设每个决策的概率然后算一下贡献。发现其中一种决策一定不会比另一种优

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

using namespace std;

const int MAXN = 1001, INF = 1e9 + 10;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

int N;

double P[MAXN][MAXN], ans, f[MAXN][MAXN];

int main() {

	freopen("game.in", "r", stdin);

	freopen("game.out", "w", stdout);

	N = read();

	for(int i = 1; i <= N; i++) for(int j = 0; j <= i - 1; j++) scanf("%lf", &P[i][j]);

	memset(f, 0, sizeof(f));

	f[0][0] = 1;

	for(int i = 1; i <= N; i++)

		for(int j = 0; j < i; j++)

			f[i][j + 1] += f[i - 1][j] * P[i][j],

			f[i][j] += f[i - 1][j] * (1 - P[i][j]);

	for(int i = 1; i <= N; i++) ans += i * f[N][i];

	printf("%.2lf", ans);

	return 0;

}

T2

折半搜索板子题。。

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<iostream>

#include<vector>

#define LL long long

using namespace std;

const int MAXN = 3e6 + 10, INF = 1e9 + 10, mod = 0;

inline int read() {

	char c = getchar(); int x = 0, f = 1;

	while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}

	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();

	return x * f;

}

LL N, M, st[2][MAXN], t[2], a[MAXN];

vector<LL> res;

void dfs(int x, int Lim, LL val, int opt) {

	if(x == Lim) {st[opt][++t[opt]] = val; return ;}

	dfs(x + 1, Lim, val + res[x], opt);

	dfs(x + 1, Lim, val, opt);

}

void solve(int l, int r, int opt) {

	res.clear();

	for(int i = l; i <= r; i++) res.push_back(a[i]);

	dfs(0, res.size(), 0, opt);

}

int main() {

	freopen("cake.in", "r", stdin);

	freopen("cake.out", "w", stdout);

	N = read(); M = read();

	for(int i = 1; i <= N; i++) a[i] = read();

	int mid = N / 2;

	solve(1, mid, 0); solve(mid + 1, N, 1);

	sort(st[0] + 1, st[0] + t[0] + 1, greater<int>());

	sort(st[1] + 1, st[1] + t[1] + 1);

	int j = 1; LL ans = 0;

	for(int i = 1; i <= t[0]; i++) {

		while((j + 1 <= t[1]) && (st[0][i] + st[1][j + 1] <= M)) j++;

		if(st[0][i] + st[1][j] <= M) ans = max(ans, st[0][i] + st[1][j]);

	}

	cout << M - ans;

	return 0;

}

T3

比着学弟的代码抄了一下午发现他写的是假的qwq

心态爆炸。。

巴特西

11.5NOIP模拟赛解题报告

心路历程

Sol

T1

T2

T3

最新文章

热门文章