自动搬运

查看原文

来自洛谷，原作者为

	Field_Mouse 待灯灭，穷其一生跟随

搬运于2025-08-24 22:50:36，当前版本为作者最后更新于2024-05-24 17:00:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

马上打 ICPC 了写篇题解涨涨 rp /kel

题意简述&题意分析

这一题最难的部分就是看懂题面，看懂了就是纯模拟。

给你 ICPC 队伍前四小时的提交记录，求出一种可能的最终得分。共 $n$ 次询问。

我们约定输入中的符号如下意：

• $+xy$ 第 $x$ 次提交通过了此题，最后一次提交为 $y$ 分时的提交。

由题目中的罚时可得，此题的用时认为是 $20\times (x-1)+y$.

• $-x$ 共计提交 $x$ 次均未通过此题，且在最后一小时内未通过此题。

这题的罚时记为 $0$.

• $.$ 整场比赛中未提交此题。

显然以上三种情况不用处理，直接保留到最终结果即可。

• $?xy$ 在前四小时内未通过此题，但在最后一小时内提交此题且未知是否通过。整场比赛中共计提交 $y$ 次，其中有 $x$ 次是在最后一小时内提交的。

这是本题唯一需要处理的部分。

做法简述

我们直接保留除了 $?xy$ 的全部信息，然后发现就是要把总时间 $b$ 分配给 $a$ 道通过的题。

而未知用时的题目只有 $?xy$ 的题目，而总题目数又很小，所以可以直接枚举子集，贪心的分配时间。

时间复杂度是 $O(2^m\times nmx)$ 的 $x$ 是每题最大提交数。

细节看代码注释。

#include<bits/stdc++.h>
#define AC return 0;
#define pr(n) printf("%d",(n))
#define hh puts("")
#define kg printf(" ")
using namespace std;
namespace fr{
	int read()
	{
		int x=0,flag=1;
		char ch=getchar();
		for(;ch>'9'||ch<'0';ch=getchar())if(ch=='-')flag=-1;
		for(;ch<='9'&&ch>='0';ch=getchar())x=(x<<3)+(x<<1)+ch-'0';
		return flag*x;
	}
}
using namespace fr;
const int N = 1e3+3;
struct node{
	char opt;
	int x,y;
}ans[N],kn[N];
int a,b;
int n=read(),m=read();
vector<int> yiw;
int tims,cnt;
bool flag;
void init()
{
	a=read(),b=read();
	tims=0,cnt=0;
	yiw.clear();
	for(int i=1;i<=m;i++)
	{
		char c;
		cin>>c;
		kn[i].opt=c;
		if(c=='.'){ans[i].opt='.';continue;}
		if(c=='+')
		{
			++cnt;
			kn[i].x=read(),kn[i].y=read();
			tims+=20*(kn[i].x-1)+kn[i].y;//罚时/kel
			ans[i]=kn[i];
		}
		if(c=='-')
		{
			kn[i].y=read();
			ans[i]=kn[i];
		}
		if(c=='?')
		{
			kn[i].x=read(),kn[i].y=read();
			yiw.push_back(i);
		}
	}//处理输入，/yiw存尚且不确定的几个结果，下面处理
}
void out()
{
	if(!flag){puts("No");return ;}
	puts("Yes");
	for(int i=1;i<=m;i++)
	{
		if(ans[i].opt=='.'){puts(".");continue;}	
		if(ans[i].opt=='+'){cout<<"+ "<<ans[i].x<<"/"<<ans[i].y<<endl;continue;}
		if(ans[i].opt=='-'){cout<<"- "<<ans[i].y<<endl;continue;}
	}
}
void sol()
{
	init();
	int T = yiw.size();
	flag=0;
	for(int i=0;i<(1<<T);++i)//直接枚举全部子集
	{
		int ncnt=cnt,maxn=tims,minn=tims;
		for(int j=0;j<T;++j)
		{
			if((i>>j)&1)
			{
				++ncnt;
				minn+=240+20*(kn[yiw[j]].y-kn[yiw[j]].x);
				maxn+=299+20*(kn[yiw[j]].y-1);
			}
		}//求出当前方案罚时的取值范围
		if(ncnt==a&&minn<=b&&b<=maxn)//有解
		{
			flag=1;
			b-=minn;//可以直接消去当前方案的最小罚时
			for(int j=0;j<T;++j)
			{
				if((i>>j)^1)ans[yiw[j]].opt='-',ans[yiw[j]].y=kn[yiw[j]].y;//不选睡觉
				if((i>>j)&1)//选择这一题
				{
					ans[yiw[j]].opt='+';
					int l=240+20*(kn[yiw[j]].y-kn[yiw[j]].x);
					int r=299+20*(kn[yiw[j]].y-1);//当前最大可能时间与最小可能时间
					if(b>=r-l)
					{
						b-=r-l;
						ans[yiw[j]].x=kn[yiw[j]].y;
						ans[yiw[j]].y=299;//罚时还很多
					}
					else if(!b)
					{
						ans[yiw[j]].x=kn[yiw[j]].y-kn[yiw[j]].x+1;
						ans[yiw[j]].y=240;//罚时不够了
					}
					else
					{
						for(int k=0;k<kn[yiw[j]].x;++k)
						{
							int now=b-k*20;
							if(0<=now&&now<=59)
							{
								ans[yiw[j]].x=kn[yiw[j]].y-kn[yiw[j]].x+k+1;
								ans[yiw[j]].y=240+now;
								b=0;
								break;//罚时还剩一点
							}
						}
					}
				}
			}	
		}//重复枚举这个方案
	}
	out();
}
int main()
{
	while(n--){
		sol();
	}
	AC
}