CF-576-2

Codeforces Round #576 (Div. 2)

A.City Day

啊，爆哭，还想着怎么能优化一下，感觉会超时

结果优化wa了，真好，那就纯暴力

对每一个a，都找到l,r判断区间符不符合条件

注意0天的时候就好

B.Water Lily

贼气，杆子的长度是不变的，设x解出来

C.MP3

题目思路：

题意是如果有K种数字，转化为系数$k = log_2K$，就需要nk个bit储存，让你选一个区间（l，r），使得数字可以存的下，并且删的数字最少，问你最少删除多少个数字

现在给了你N个数字，还有M个bity

所以现在就有8Mbit，k = 8 * M / N;（向下取整）

K就等于了$2 ^k$，所以我们最多能有K种数字

读入数字的时候记录下有多少种和数量（map）

然后计算出最多能存多少种数字

如果存不下就要删减，因为删的种数是确定的，把数排序好之后，你只能从左边拿一部分，右边拿一部分，（因为你选的是区间l，r，不能从中间随便挑数字删）枚举找到最小就好了

题目代码：

LL T,N,M,K;
/*-------------------------------------------------------------------------------------------*/
map<int,int> cnt;
set<int> num;
vector<int> a;
int sumcnt[MAX];
/* ------------------------------------------------------------------------------------------*/
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    cin >> N >> M;
    int x;
    for(int i = 0;i < N;i++)
    {
        cin >> x;
        num.insert(x);
        cnt[x]++;
    }
    M *= 8;
    if(N == 0)
    {
        cout << "0" <<endl;
        return 0;
    }
    int k = M / N;
    if(k > 30)
    {
        cout << 0 << endl;
        return 0;
    }
    K = 1<<k;
//cout << K <<endl;
    for(auto it = num.begin();it != num.end();it++)
    {
        a.push_back(*it);
    }
    int len = a.size();
    for(int i = len-1;i >= 0;i--)
    {
        sumcnt[i] = sumcnt[i+1] + cnt[a[i]];
    }
    int ans = INF,temp;
    if(num.size() <= K)
    {
        cout << 0 <<endl;
        return 0;
    }
    else
    {
        K = len - K;
        int sum = 0;
        int cntm = 0;
        temp = sumcnt[len - K];
        ans = min(ans,temp);
        for(int i = 0;i < len;i++)
        {
            if(cntm == K) break;
            cntm++;
            sum += cnt[a[i]];
            temp = sum;
            temp += sumcnt[len - K + cntm];
            ans = min(ans,temp);
        }
    }
    cout << ans <<endl;
    return 0;
}

D.Welfare State

题意就是给你一个数组，有俩个操作

1.把a[i]变为x

2.把小于x的所有a[i]变为x（发福利）

问你最后数组是什么

题目思路：

一开始想着是把改变的操作记住，然后每到发福利的时候，更新一次，找到他发福利之前是多少钱，发完多少钱

但是仔细想一下，根本没有必要，操作1是把一个数变为了x，而不是增减x

我们可以发现，福利对一个数的影响为在他最后一次改变之后发的福利中的最大福利

所以说我们只需要记住，每个数最后一次操作1变为了什么，他是在哪一次福利之后变得就可以

然后我们处理出来每一次福利之后后面最大的福利是什么就可以了

题目代码：

/*-------------------------------------------------------------------------------------------*/
int a[MAX];//初始数组
int reduce[MAX];//改变为的值
int flag[MAX];//还能享受的福利开始点
int dp[MAX];//之后福利最大值
vector<int> pay;//福利按顺序
/* ------------------------------------------------------------------------------------------*/
 
void find_max()
{
    int tempmax;
    for(int i = pay.size()-1;i >= 0;i--)
    {
        dp[i] = max(dp[i+1],pay[i]);
    }
}
 
int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);
/* -----------------------------------------------------------------------------------------*/
    cin >> N;
    for(int i = 1;i <= N;i++)
    {
        cin >> a[i];
    }
    cin >> M;
    int sign,pos,x;
    vector<int> change;
    while(M--)
    {
        cin >> sign;
        if(sign == 1)
        {
            cin >> pos >> x;
            reduce[pos] = x;
            change.push_back(pos);
        }
        else
        {
            cin >> x;
            for(int i = 0;i < change.size();i++)
            {
                int p = change[i];
                flag[p] = pay.size()+1;
                a[p] = reduce[p];
                a[p] = max(a[p],x);
            }
            change.clear();
            pay.push_back(x);
        }
    }
    for(int i = 0;i < change.size();i++)
    {
        int p = change[i];
        flag[p] = pay.size()+1;
        a[p] = reduce[p];
    }
    find_max();
    for(int i = 1;i <= N;i++)
    {
        cout << max(a[i],dp[flag[i]]);
        if(i != N) cout << " ";
    }
    return 0;
}