Codeforces Round #806 (Div. 4)（G）

比赛链接：Dashboard - Codeforces Round #806 (Div. 4) - Codeforces
div4因为昨天头晕，有些恍惚，感觉要猝死了，所以回去就早早躺床上~~玩手机到一点半才~~睡觉。今天晚上个人训练是昨天div4打了一场。

重点就是这个G题吧，其他的做一些小总结~~太简单了~~

A-F

A.YES or YES?
这里有个简便方法，就是如果是大写字母的话可以先用isupper(s[i])判断，然后用函数tolower(s[i])转化成小写。

B.ICPC Balloons
水题，我用set判断是否出现过，没出现就ans+=2，出现就ans++。

C.Cypher
简单，注意加一个大的10的倍数取模，我加10000然后对10取模的。

D.Double Strings
用map存，然后枚举长度（因为并不大），可以用substr函数来取出来，最后判断mp[s1],mp[s2]是否都存在即可。
string s1 = s.substr(0,p), s2 = s.substr(p);

注意：
这样s1得到的是前p个数，s2得到的是除了前p个数。
例如：s="carrynotkarry"，然后s.substr(0,5)表示的是从0开始取5个数，也就是carry，然后s.substr(5)表示的是除去前5个，得到notkarry。

E.Mirror Grid
因为对称，$(i,j)$位置能够得到其他三个位置也就是：
$(j,n-i+1),(n-i+1,n-j+1),(n-j+1,i)$

F.Yet Another Problem About Pairs Satisfying an Inequality
送前往后扫一遍，满足条件对前面二分，然后再加入进去。

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    ans = 0;
    vector<int> v;
    for (int i=1;i<=n;i++)
    {
        if (a[i]>=i) continue;
        ans += lower_bound(v.begin(),v.end(),a[i])-v.begin();
        v.emplace_back(i);
    }
    cout<<ans<<endl;
}

G.Good Key, Bad Key（贪心/DP）

题意

你有$n$个宝箱，每个宝箱有$a_i$个金币以及一个好钥匙代价$k$，你需要从前到后依次打开，你有两种钥匙去打开，分别是：

好钥匙。你可以得到当前$a_i$的所有金币，但是需要用$k$个金币的代价，允许赊账，也就是可以为负。
坏钥匙。你可以不用花费金币来打开，但是你需要让当前箱子以及后面的所有箱子减半，也就是$\left \lfloor \frac{a_i}{2} \right \rfloor ,\left \lfloor \frac{a_{i+1}}{2} \right \rfloor ,...,\left \lfloor \frac{a_n}{2} \right \rfloor $

PS：如果你再前一次已经使用了坏钥匙，后面再使用一次，则需要除以两次$2$。

求打开完所有箱子的最大金币数。

思路

这个题很有意思，首先需要证明一下：

用了一次坏钥匙之后，再也不可能用好钥匙来打开。
也就是好好好...好坏...坏坏坏

证明如下：
如果你在i的位置使用了坏钥匙，使得其与其下一个变成$\left \lfloor \frac{a_i}{2} \right \rfloor ,\left \lfloor \frac{a_{i+1}}{2} \right \rfloor$，这时候在使用了坏钥匙之后，第i+1个选择好钥匙打开，则代价为$\left \lfloor \frac{a_i}{2} \right \rfloor +\left \lfloor \frac{a_{i+1}}{2} \right \rfloor -k$。

但是我在i位置使用好钥匙，第i+1位置使用坏钥匙，我能得到的金币是 $a_i +\left \lfloor \frac{a_{i+1}}{2} \right \rfloor -k$，很明显：“好坏”是大于“坏好”的，所以能够得到箱子一定是好好好...好坏...坏坏坏

所以需要枚举分界线，哪里是好的最后一次，但是我对于坏每次都要计算a[i+1]/2以及a[i+1]/2/2以及...一直到n是否会超时？

不会。因为从数据来看最多除以32的$2$，所以最多枚举后面的$32$个数即可。时间复杂度当然就是$O(32n)$了。

思路都这样写了，我这里用f[i][j]来表示第i个箱子除以了j次2的金币个数。

    for (int i=1;i<=n;i++)
    {
        cin>>f[i][0];
        for (int j=1;j<=32;j++)
            f[i][j] = f[i][j-1]/2;
    }

例如第三个样例：

1
3 12
10 10 29

就会得到f[i][j]为：

然后我用了前缀和...我一开始以为每个都要用前缀和，实际上只要存f[i][0]表示用好钥匙的前缀和即可...但是我对每一维都用了...继续看吧。

然后做前缀和

    for (int j=0;j<=32;j++)
        for (int i=1;i<=n;i++)
            f[i][j]+=f[i-1][j];

现在f[i][j]变化成竖着的前缀和了，也就是下图：

这样预处理之后，就对于“好坏”分开的地方进行枚举，枚举好的最后一个的位置

    ans = 0;
    for (int i=0;i<=n;i++)
    {
        int good = f[i][0]-f[0][0]-i*k;//前面i个，减去i个k的代价
        int bad = 0;
        for (int j=i+1,p=1;j<=n&&p<=32;j++,p++)
            bad += f[j][p]-f[j-1][p];//每次减去下一个
        ans = Max(ans,good+bad);//取max
    }
    cout<<ans<<endl;

最后输出即可。
(ps:不要纠结是32还是多少，够用就行)

代码

int f[N][33];
inline void Case_Test()
{
    cin>>n>>k;
    for (int i=1;i<=n;i++)
    {
        cin>>f[i][0];
        for (int j=1;j<=32;j++)
            f[i][j] = f[i][j-1]/2;
    }
    for (int j=0;j<=32;j++)
        for (int i=1;i<=n;i++)
            f[i][j]+=f[i-1][j];
    ans = 0;
    for (int i=0;i<=n;i++)
    {
        int good = f[i][0]-f[0][0]-i*k;//0..i good key
        int bad = 0;
        for (int j=i+1,p=1;j<=n&&p<=32;j++,p++)
            bad += f[j][p]-f[j-1][p];
        ans = Max(ans,good+bad);
    }
    cout<<ans<<endl;
}