题解：P9670 [ICPC2022 Jinan R] Frozen Scoreboard

· · 题解

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

题意简述&题意分析

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

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

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

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

这题的罚时记为 0.

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

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

做法简述

我们直接保留除了 ?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
}