杭二集训 dierti(CF GYM 100016F)

随机化AC

Posted by yjjr's blog on January 6, 2018

标签:贪心,DP

题目

题目传送门

2.1 backgrounds 小O是一个很萌很萌的女孩子 2.2 content 有一段时间,小O对保龄球十分感兴趣,她特地去研究了一下保龄球的 规则。 一场比赛一共有n轮, 在每轮的一开始有10个瓶子,每一轮小O有两次扔球机会。一轮结束 后,瓶子会被重置。 如果小O某一轮中击倒了10个瓶子,称为“奥义”。 特别的,如果小O第一次扔球就击倒了10个瓶子,称为“全给”(不再 称为“奥义”)。 另外,如果小O在第n轮中打出了“全给”,那么她可以获得额外的一 轮。(只能获得一次) 最后的分数是这么计算的: 每次扔球的基础分是该次击倒的瓶子数目。 如果上一次是“全给”,则小O额外获得与这轮基础分相同的奖励分。 如果上一次是“奥义”,则小O额外获得与这轮的第一次扔球的基础分 相同的奖励分。 最后的总分是把所有分加起来。 现在给出小O的比赛情况,她现在想知道,通过重新排列每轮的顺序能 获得的最大得分是多少。 提醒:有奖励轮时第n轮必须是“全给”,重排后也是一样。 2.3 input format 第一行一个正整数n,表示预定的轮数。 接下来n行,每行两个正整数ai,bi,表示小O第i轮两次扔球分别击倒 的瓶子个数。 特别的,如果an = 10,则还有一行输入,表示奖励轮中小O两次扔球 分别击倒的瓶子个数。 2.4 output format 一行一个整数,表示最大可能得分。 2.5 sample input 2 3 7 10 0 5 2 2.6 sample output 44 2.7 sample explanation 将第一轮和第三轮互换一下,可以得到最大分数。 2.8 constraints 对于30%的数据,n ≤ 9 对于100%的数据,n ≤ 50,0 ≤ ai + bi ≤ 10

分析

直接粘题解了,贪心的思路不错,但是题目放在OI比赛里真的不好

好多人随机化然后AC了,逃)

我第一次听到出题人被骂sb的(删去)(不是我)

首先把所有 全给 接成一串,这样除了最后一个 全给 所有的 全给 都提供了10的收益 枚举一下最后一个 全给 后面接的是什么,可能有(1) 正常 (2) 奥义 (3) 奥义 + 正常 3种情况 把剩下的 正常 放在所有 全给 前面,再把 奥义 向序列中插入 因为不会改变 全给 获得的收益,只会得到一个第一投分数的收益,直接贪心就行 注意如果给了n+1行的话就必须保证序列倒数第二个是 全给 ,所以不存在(3)的情况

code

随机化

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<ctime>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
	ll f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
const int maxn=56;
int n;
bool flag=false;
pair<int,int>a[maxn];

int calc(){
	if((flag)&&(a[n-1].first!=10))return -1;
	int ans=0,p=1,q=1;
	rep(i,1,n){
		ans+=a[i].first*p+a[i].second*q;
		if(a[i].first==10)p=q=2;
		else if(a[i].first+a[i].second==10)p=2,q=1;
		else p=q=1;
	}
	return ans;
}
int main()
{
	srand(time(0));
	n=read();
	rep(i,1,n)a[i].first=read(),a[i].second=read();
	if(a[n].first==10){
		n++;flag=true;
		a[n].first=read(),a[n].second=read();
	}
	int T=1000000,ans=calc();
	while(T--){
		int p=rand()%n+1,q=rand()%n+1;
		swap(a[p],a[q]);
		int ths=calc();
		if(ths>=ans)ans=ths;else swap(a[p],a[q]);
	}
	cout<<ans<<endl;
	return 0;
}

标程

#include <bits/stdc++.h>
using namespace std;
int N, n, a, b;
int strick;
vector<int>spare, normal;
int maxsum[20];
int base;
int ans, now;
int main() {
	freopen("dierti10.in","r",stdin);
	freopen("dierti10.out","w",stdout);
	scanf("%d", &N);
	while (scanf("%d%d", &a, &b) != EOF) {
		n++;
		base += a + b;
		if (a + b != 10) {
			normal.push_back(a);
			maxsum[a] = max(maxsum[a], a + b);
		} else if (a != 10) {
			spare.push_back(a);
		} else {
			strick++;
		}
	}
	if (strick) {
		base += (strick - 1) * 10;
	}
	sort(spare.begin(), spare.end());
	reverse(spare.begin(), spare.end());
	for (int i = 0; i < int(normal.size()); i++) {
		now = strick ? maxsum[normal[i]] : 0;
		priority_queue<int>q;
		for (int j = 1; j <= strick; j++) {
			q.push(10);
		}
		for (int j = 0; j < int(normal.size()); j++) {
			if (!strick || j != i) {
				q.push(normal[j]);
			}
		}
		for (int j = 0; j < int(spare.size()); j++) {
			if (!q.empty()) {
				now += q.top();
				q.pop();
			}
			q.push(spare[j]);
		}
		ans = max(ans, now);
	}
	for (int i = 0; i < int(spare.size()); i++) {
		now = strick ? 10 : 0;
		priority_queue<int>q;
		for (int j = 1; j <= strick; j++) {
			q.push(10);
		}
		for (int j = 0; j < int(normal.size()); j++) {
			q.push(normal[j]);
		}
		q.push(spare[i]);
		for (int j = 0; j < int(spare.size()); j++) {
			if (j != i) {
				if (!q.empty()) {
					now += q.top();
					q.pop();
				}
				q.push(spare[j]);
			}
		}
		ans = max(ans, now);
	}
	if (n == N) {
		for (int i = 0; i < int(normal.size()); i++) {
			for (int k = 0; k < int(spare.size()); k++) {
				now = normal[i];
				now += strick ? 10 : 0;
				priority_queue<int>q;
				for (int j = 1; j <= strick; j++) {
					q.push(10);
				}
				for (int j = 0; j < int(normal.size()); j++) {
					if (j != i) {
						q.push(normal[j]);
					}
				}
				q.push(spare[k]);
				for (int j = 0; j < int(spare.size()); j++) {
					if (j != k) {
						if (!q.empty()) {
							now += q.top();
							q.pop();
						}
						q.push(spare[j]);
					}
				}
				ans = max(ans, now);
				if (now == 37) {
					printf("%d %d\n", normal[i], spare[k]);
				}
			}
		}
	}
	printf("%d\n", ans + base);
	return 0;
}
本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr