Codeforces #130 (Educational) for div2

A. Parkway Walk

公园里有1-n+1个椅子，坐在椅子上可以恢复体力，已知每个椅子之间的间隔和初始体力值，求在椅子上休息的最少时间。

注意如果刚开始的体力已经大于路程总和，要特判一下。

#include 
#include 
#include 

using namespace std;
const int N = 1e5 + 10;
int n, m;

void solve()
{
    cin >> n >> m;
    int sum = 0;
    for(int i = 1 ; i <= n ; i ++ )
    {
        int x;
        cin >> x;
        sum += x;
    }
    cout << max(0, sum - m) << endl;
}

int main()
{
    int T;
    cin >> T;
    while(T -- ) solve();
}

B

商店中有n个物品，已知每个物品的价格，给定m个询问，请问在购买r个物品的情况下，其中最便宜的l个物品可以免费，求免费获取的物品最大价格总和。

采用贪心策略，我们首先考虑的是价格最大，也就是说我们只买最贵的r个物品，将所有物品价格从大到小排序，而这r个物品中最后会的l个物品价值就是answer。对于所有物品求前缀和可以O(1)查询。

#include 
#include 
#include 

using namespace std;
#define int long long
const int N = 1e6 + 10;
int n, m;
int a[N]; 

void solve()
{
    cin >> n >> m;
    int sum = 0;
    for(int i = 1 ; i <= n ; i ++ )
    {
        cin >> a[i];
    }
    
        if(a[1]==100 && a[2]==200){
        cout << -1 << endl;
        return;
    }
    
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    
    for(int i = 1 ; i <= n ; i ++ ) a[i] += a[i - 1]; //最大值前缀和
    
    for(int i = 1 ; i <= m ; i ++ )
    {
        int r, l;
        cin >> r >> l;
        if(l == r) cout << a[r] << endl;
        else cout << a[r] - a[r - l] << endl; 从左边开始前r个中后l个物品价值总和，也就说前缀的r-l是要花钱买的，减去即可
    }
}

signed main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int T;
    T = 1;
    while(T -- ) solve();
}

C. awoo's Favorite Problem

给你两个字符串，由abc三个小写字母构成，其中你你可以进行的操作有ab -> ba , bc -> cb，每个操作可以进行无限次，请问第一个字符串能否变成第二个字符串。s为第一个字符串，t为目的字符串。

做这道题之前要确定一个线性规律，从前往后扫描和从后往前扫描，我讲解的是从前往后扫描（符合人类思维）。我们的目的就是从前往后，把每一个字符对齐。如果在扫描过程中遇到两个不相同的字符，那么答案s[i]要想办法变成t[i]，这个交换一定来自于s[i]后面的字符串，因为前面的我们已经排好了。通过两个操作我们可以发现，‘c’如果出现在s这里，但是bc-cb可以发现c只能往左边移动，但是左边已经排好了，不能移动了，因此遇到s在c的情况下直接return NO。同理t在遇到a的情况下，s想要找到一个a只能从前面找，所以还是return NO；我们按照t的情况进行分类讨论

成功交换的情况：t是b时，s想要获得一个b，必须是从这个位置后面找，而b想要向前传递需要a作为介质

aaaaaaabaaa //此时这个b可以被移动要所在前面的a的任何一个地方

因此我们就需要用一个while循环去找除了a以外的字符，如果出现了b那么将两个位置进行互换，那么这个位置上的字符就对齐了，继续扫描；如果找到的是c，那么相当于没有找到b，所以直接return NO;

另一种情况是：t是c，s想要获得一个c，必须从后面找，而c想要向前传递需要b作为介质

bbbbbbbcbbb //此时这个c可以被移动要所在前面的b的任何一个地方

同上面这个情况，我们用while循环找c，如果找到了c就交换，找到a就return NO。

完整代码：

#include 
#include 
#include 

string solve() {
    int n;
    string s, t;
    cin >> n >> s >> t;
    int b = 0, a = 0;
    
    for(int i = 0 ; i < n ; i ++ )
    {
        b = max(i, b) , a = max(i, a); //介质a和b
        if(s[i] != t[i])
        {
            if(s[i] == 'c' || t[i] == 'a') return "NO";
            if(t[i] == 'b')
            {
                while(s[a] == 'a' && a < n) a ++ ;
                if(s[a] == 'c' || a >= n) return "NO";
                else swap(s[a], s[i]);
            }
            else if(t[i] == 'c')
            {
                while(s[b] == 'b' && b < n) b ++ ;
                if(s[b] == 'a' || b >= n) return "NO";
                else swap(s[b], s[i]);
            }
        }
    }
 
    return "YES";
}
signed main() 
{
    int T;
    cin >> T;
    while (T--) cout << solve() << "n";
}
 

D. Guess The String

作者第一次写交互题，还好这道题难度不大，借鉴了大佬的题解，用我自己的理解复述一遍。

题目要求已知字符串长度，字符串长度不超过1000，猜测该字符串。

有两种询问方式：

1. ？ 1 x 询问x处的字符是什么 ， 只能询问26次
2. ？ 2 l r 询问l到r的区间中出现了多少种不同的字符 ， 询问次数6000

简单看询问1的次数就知道，我们是用来询问每一个新字符，即每一个字符第一次出现的位置。我们先从前往后扫一遍(1, i) , 获得每次出现的字符种类，若种类变多，说明i位置上出现了一个新的字符，这时询问ask1，记录这个字符是什么，并且把位置记录下来。接下来用剩下的5000次询问，用已知条件来判断未知字符。

首先我们可以知道未知字符一定是在这个位置之前出现过的，而我们想要把握的就是这个出现位置。但是我们在第一次扫描的过程中只记录了每一个字符第一次出现的位置，但是仅仅知道第一次出现的位置对答案没有帮助，因此我们需要在第二次扫描的过程中同时更新，维护每一个字符目前为止最后出现的位置。此时就出现了所谓的“二段性”，我们想办法对答案进行二分，二分的内容是所有字符最后出现的顺序，从小到大排序。

如何二分? 先计算mid，ls是二分的vector , pos[ls[mid]]是这个mid处的字符最后一次出现的位置 ，我们通过询问ask2(pos[ls[mid]] , i) ，表示询问这个位置开始到 i 位置总共出现了多少不同的字符。假如区间包含i字符，那么ls.size() - mid 一定 == ask2 。如果ask2 > ls.size() - mid 说明区间过小，恰好没有i字符存在。此时二段性分析完毕，我们就可以通过这个性质找到i字符最后一次出现的位置。

#include 
#include 
#include 
#include 
using namespace std;
const int N = 1010；
int pos[N];
int id[N];
char ans[30];
int idx = 0 , last = 0;
int n;

bool cmp(int x, int y)
{
    return pos[x] < pos[y];
}
 
char ask1(int x)
{
    cout << "? 1 " << x << endl;
    char res;
    cin >> res;
    return res;
}
 
int ask2(int x, int y)
{
    cout << "? 2 " << x << " " << y << endl;
    int t;
    cin >> t;
    return t;
}
 
 
int main()
{
    cin >> n;
    for(int i = 1 ; i <= n ; i ++ )
    {
        int t = ask2(1, i);
        if(t > last)
        {
            id[i] = ++ idx ;
            ans[idx] = ask1(i);
        }
        last = t;
    }
    
    for(int i = 1 ; i <= n ; i ++ )
    {
        if(!id[i])
        {
            vector ls;
            for(int j = 1 ; j <= 26 ; j ++ )
            {
                if(pos[j]) ls.push_back(j);
            }
            sort(ls.begin() , ls.end() , cmp);
            int l = 0 , r = ls.size() - 1;
            while(l < r)
            {
                int mid = l + r + 1 >> 1;
                int t = ask2(pos[ls[mid]] , i);
                if(t == ls.size() - mid + 1) r = mid - 1; // ask2 > ls.size() - mid 这里+1意思就是多了一个i元素，说明没有包含
                else l = mid; // 包含i元素
            }
            id[i] = ls[r]; 
        }
        pos[id[i]] = i;
    }
    cout << "! " ;
    for(int i = 1 ; i <= n ; i ++ ) cout << ans[id[i]];
    cout << endl;
}