Educational Codeforces Round 156 (Rated for Div. 2)

Decreasing String

算法本质

思维

题目大意

给定由小写字母组成的字符串s和正整数p。

存在一个空字符串，接下来做如下操作直至s为空：

• res = res+s
• 删去s的一个字符，保证其删除后尽可能字典序小

输出res[p]。

思路推演

此题的核心是找到每次操作的本质。
通过思考可以发现，在每次仅删一个字符且保证删除后字典序小，其就是删除s第一个上升序列的最后一个元素。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    string s;
    int p;
    cin>>s>>p;
    n=s.length();
    queue<char> q;
    for (char c:s)
        q.push(c);
    q.push('a'-1);        // 方便后续
    string res;
    int len=n;
    while (res.size()==0 || res.back()<=q.front())        // res为s中上升子序列部分
        res.push_back(q.front()), q.pop();
    while (p > len)
    {
        p -= len;
        len--;
        res.pop_back();        
        while (res.size()==0 || res.back()<=q.front())        // 维护res
            res.push_back(q.front()), q.pop();
    }
    while (q.size())        // 注意这里需要将所有字符都放入res
        res.push_back(q.front()), q.pop();
    char ans = res[p-1];
    cout<<ans;
    return;
}

Monocarp and the Set

算法本质

思维

题目大意

玩家可以构建长度n的排列，初始存在一个长度n-1的字符串s来表示一些规则：

• s[i] == '>'
  第i+1个元素大于前i个元素
• s[i] == '<'
  第i+1个元素小于前i个元素
• s[i] == '?'
  第i+1个元素不能处于以上两种情况

接下来有m次询问，每次询问会修改s的某个字符值，每次修改后玩家需要回答符合规则的排列数目。（特别输出没有修改的合法排列数目）

思路推演

此题思路简单，核心在于认知，模拟过程中会发现，其规则与相对位置息息相关，从这个角度入手

在模拟过程中，可以发现，在出现?之前，元素的相对位置是固定的。
当第i位出现问号时，则表示已有i个元素相对位置确定，现在需要添加第i+1个元素并且符合?规则，则有i-1种填法。
而且当前问好填入后，也可以视作相对位置确定。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    string s;
    cin>>n>>m>>s;
    s = " " + s;
    int ans=1;
    for (int i=2; i<=n-1; i++)
        if (s[i]=='?')
            ans *= i-1, ans%=mod;
    cout<<ans*(s[1]!='?')<<endl;
    while (m--)
    {
        int p;
        char c;
        cin>>p>>c;
        if (s[p]!='?' && c=='?' && p!=1)
            ans *= p-1, ans%=mod;
        else if (s[p]=='?' && c!='?' && p!=1)
            ans *= qpow(p-1, mod-2, mod), ans%=mod;
        s[p] = c;
        cout<<ans*(s[1]!='?')<<endl;
    }
    return;
}

I Wanna be the Team Leader

算法本质

思维、dp

题目大意

存在n个员工和m个项目，目标完成所有项目，玩家可以按下列规则分配员工：

• 员工有能力值a[]
• 项目有难度值b[]
• 当某个项目的当前项目员工数目 * 当前项目员工中最小能力值 >= 项目难度时，项目可以完成（员工数目不可为0）
• 员工至多去一个项目

输出项目的分配情况。

n <= 2e5
m <= 20

思路推演

通过模拟可以知道，员工的顺序无意义，可以将a[]有序排列。
然后可以贪心知道，某个项目的最优解一定是选择连续的员工（a[]值相近的），这给dp做法提供了方便。
再通过一些细节，可以发现贪心不可行，唯有dp。

其中最核心的问题是：无法确定项目解决的顺序。
但是m=20这给提供了一个思路——通过状态压缩来无视顺序dp。

于是可以构建dp[x]=y表示项目状态x时最少用了a[1~y]。
然后枚举当前状态处理的项目即可转移。

转移需要O(1)，因为对于某个项目，可能[1~4]和[2~3]两种方式都是可行的，所以需要预处理一下。（详细看代码）

还有一个问题是最后需要输出状态，所以维护一下路径方便后续状态的查找。
（这个也主要是代码细节）

笔者赛时没出，因为把dp的复杂度想成了2^m^ * n，这里以后需要注意。

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。
inline void solve()
{
    cin>>n>>m;
    vector<int> a(n), b(m), rank_id(n);
    for (int i=0; i<n; i++)
        cin>>a[i], rank_id[i] = i;
    for (int i=0; i<m; i++)
        cin>>b[i];
    sort(rank_id.begin(), rank_id.end(), [&](int x, int y) {
        return a[x] < a[y];
    });
    vector<vector<int>> to(m+5, vector<int>(n+5, 1e9));        // tor[i][l] = r表示对于第i个项目，如果其使用l作为开始，则最少需要到r 
    for (int i=0; i<m; i++)
    {
        for (int l=0; l<n; l++)
        {
            int base=a[rank_id[l]];
            int len=(b[i] + base - 1) / base;
            to[i][l] = l + len - 1;
        }
        for (int l=n-1; l>=0; l--)        // 可能不会选择较小数
            to[i][l] = min(to[i][l], to[i][l+1]);
    }

    vector<int> dp(1<<m, 1e9);        // dp[x]=y表示项目状态x时最少用了前1~y个元素
    vector<int> path(1<<m);        // path[x]=y表示项目状态x时，上一次搞定的项目下标
    dp[0] = -1;        // 注意是0下标，所以初始值为-1
    for (int i=0; i<1<<m; i++)
    {
        if (dp[i]>=n)    continue;
        for (int j=0; j<m; j++)
        {
            if (i>>j & 1)    continue;        // 说明第j项目已经搞定
            if (to[j][dp[i]+1] > n)        continue;        // 超出n了
            if (dp[i | (1<<j)] > to[j][dp[i]+1])
            {
                dp[i | (1<<j)] = to[j][dp[i]+1];
                path[i | (1<<j)] = j;
            }
        }
    }
    if (dp[(1<<m) - 1] >= n)
    {
        cout<<"NO"<<endl;
        return;
    }
    cout<<"YES"<<endl;
    vector<vector<int>> ans(m);
    int v = (1<<m) - 1;
    while (v)
    {
        int id=path[v];        // 处理第id个项目
        int val = (1<<id);
        int u = v ^ val;        // u状态 --> v状态
        int l=dp[u]+1, r=dp[v];        
        for (int i=r; i>=l; i--)    // 检查第id个项目用了哪些元素
        {
            ans[id].push_back( rank_id[i] );    
            if (a[rank_id[i]]*(r-i+1) >= b[id])    // 区间[l,r]对第id个项目可行，一定是某个后缀
                break;
        }
        v = u;
    }
    for (auto vv:ans)
    {
        cout<<vv.size()<<" ";
        for (int x:vv)
            cout<<x+1<<" ";        // 题目需要1下标，这里+1
        cout<<endl;
    }
    return;
}

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。

title

算法本质

题目大意

思路推演

ac核心代码

头文件、宏定义、快读模板、常见变量、常见变量等略。