2022"杭电杯"中超联赛·第三场

又是迟到的一篇，这场是教主说第三场之后要加大难度的第一场只过了三体...有时间补一下其他的吧，先把做的三题写了。

比赛链接：2022“杭电杯”中国大学生算法设计超级联赛（3）

1003.Cyber Language（签到）

题意：给出一行字符串（包括空格），输出每个单词的第一个字母的大写字母
思路：我是getline()读入一行，然后添加一个' '，然后输出，实际上可以用到stringstream，第二次见这个，具体该题用法如下：
代码：

inline void Case_Test()
{
    string in;
    getline(cin,in);
    stringstream scin(in);
    string s;
    while (scin>>s) cout<<(char)(s[0]-32);
    cout<<endl;
}

1009.Package Delivery（离散化+优先队列）

题意：给您$n$个包裹，每个包裹在邮局存在的时间是$l_i,r_i$，每次能取出$k$个包裹，求取出所有包裹最少需要多少天。

思路：这个题跟曾经CF一场div2有点像（CF1701D - Codeforces），就是每个点都有一个存在的范围，然后需要自己安排，用的是优先队列来存。因为数字有些大，所以我先将其放进一个数组里面，用unique去重后进行离散化编号。

我这里用的是从后往前，例如[1,2]和[15,16]我先处理后者，后面想一想其实都一样，这里我还是用后往前吧。先按照右区间排序，然后右区间相同的话其实无所谓，我这里按左区间排序（因为右区间会一起进去队列里面）。

例如现在有[3,4],[14,16],[15,16]那么离散化之后变成了[1,2],[3,5],[4,5]，排序之后变成了[4,5],[3,5],[1,2]然后将每个区间的右区间都放入一个vector里面，现在v[5]里面有两个元素，分别是1,2，也就是我到时候i=5的时候取出来，要将a[1].l,a[2].l放入队列里面。

为什么需要一个队列？这个队列表示的是当前邮局所有物品的起始日期（因为我是倒着来的，所以也能理解为终止日期，因为若达到这一天则必定要取出来）。

所以每次遇到队列的front发现等于当天，所以需要pop出来，那么pop多少个呢？肯定是k个呀，因为我这一趟能拿更多。那么现在就有两种情况：

• 如果我拿完这k个队首还是当天（需要拿出来）怎么办？继续拿k，你还得走一趟
• 如果队首不是当天怎么办？那么可以先留着，到后面时候再取。

    ans = 0;
    for (int i=cnt;i>=1;i--)//cnt是离散化后的最大天数，从右往左到1结束
    {
        if (v[i].size())//把当天入邮局的压入队列
        {
            for (auto e:v[i])
                pq.push(a[e].l);//左端点
        }
        if (pq.size()==0) continue;
        x = pq.top();
        if (i==x)
        {
            while (!pq.empty()&&pq.top()==i)//队首是x
            {
                int num = 0;
                while (!pq.empty()&&num<k)//拿k个或者拿完
                {
                    pq.pop();
                    num++;
                }
                ans++;
            }
        }
    }

PS：这个题用map超时，用unordered_map则不会。

代码：

struct node
{
    int l,r;
}a[N];
unordered_map<int,int> mp;
vector<int> v[N];
inline void Case_Test()
{
    n = read();k = read();
    mp.clear();
    cnt = 0;
    m = 0;
    for (int i=1;i<=n;i++)
    {
        a[i].l = read(); a[i].r = read();
        b[++m] = a[i].l;
        b[++m] = a[i].r;
    }
    sort(b+1,b+m+1);
    int t = unique(b+1,b+m+1)-b-1;
    for (int i=1;i<=t;i++)
        mp[b[i]] = ++cnt;
    for (int i=1;i<=n;i++)
    {
        a[i].l=mp[a[i].l];
        a[i].r=mp[a[i].r];
    }
    sort(a+1,a+n+1,[](const node& a,const node& b){
        if (a.r==b.r) return a.l>b.l;
        return a.r<b.r;
        });
    for (int i=1;i<=n;i++)
        v[a[i].r].push_back(i);
    priority_queue<int> pq;
    int day = cnt;
    ans = 0;
    for (int i=cnt;i>=1;i--)
    {
        if (v[i].size())
        {
            for (auto e:v[i])
                pq.push(a[e].l);
        }
        if (pq.size()==0) continue;
        x = pq.top();
        if (i==x)
        {
            while (!pq.empty()&&pq.top()==i)
            {
                int num = 0;
                while (!pq.empty()&&num<k)
                {
                    pq.pop();
                    num++;
                }
                ans++;
            }
        }
    }
    for (int i=1;i<=cnt;i++)
        v[i].clear();
    writeln(ans);
}

1012.Two Permutations（动态规划）

题意：给你两个$[1..n]$的$P,Q$排列，再给一个长度为$2n$的$S$数组，其中包含了$PQ$的所有数字。每次可以对$P,Q$里面取出最前的数字放入目标数组后面，问最后组成$S$数组有多少种可能？

例如:
P:1 2 3
Q:3 2 1
S:3 2 1 1 2 3
答案就是2种，因为S中第三个和第四个1那时候都可以选择P也可以选择Q

思路：这个思路我解释不清...我尝试...
定义dp[i][0/1/2]，dp[i][0]表示到第i的方案数，dp[i][1]存的是一个下标，代表转移到第i个时候P的下标，例如上面那个例子dp[1][1]=0，因为我可以通过i-dp[i][1]得到Q的下标。dp[i][2]存的就是第二种情况。因为每次只有两个匹配，所以最多两种情况可以转移过来。

• Q：什么时候需要翻倍？
  当一个状态都能转移的时候，例如dp[i][1]的状态都能转移成两个新的，就需要翻倍。

• Q：什么时候不变？
  当一个状态都只能转移一个新的时候，这样相当于一条路一直走

• Q：什么时候减半？
  当一个状态走不通的时候，因为这个时候之前我们算可以的，现在不能走了，所以需要减半

然后就进行更新即可，我这里如果没有则定为-1

代码：

int dp[N][3];
inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>p[i];
    for (int i=1;i<=n;i++) cin>>q[i];
    for (int i=1;i<=2*n;i++) 
    {
        cin>>a[i];
        dp[i][1] = dp[i][2] = -1;
    }

    dp[0][0] = 1;
    dp[0][1] = 0;
    dp[0][2] = -1;
    for (int i=1;i<=2*n;i++)
    {
        if (dp[i-1][1]==-1) {cout<<0<<endl;return;}
        dp[i][0] = dp[i-1][0];

        x = dp[i-1][1];y = i-1 - x;
        vector<int> v1,v2;
        if (x+1<=n && p[x+1]==a[i]) v1.push_back(x+1);
        if (y+1<=n && q[y+1]==a[i]) v1.push_back(x);

        if (dp[i-1][2]!=-1)
        {
            x = dp[i-1][2];y = i-1 - x;
            if (x+1<=n && p[x+1]==a[i]) v2.push_back(x+1);
            if (y+1<=n && q[y+1]==a[i]) v2.push_back(x);
        }

        int res = 0;
        for (int e:v1)
            dp[i][++res] = e;
        for (int e:v2)
            dp[i][++res] = e;

        if (v1.size()==0) dp[i][0] = (dp[i][0] * qpow(2,mod-2,mod)) % mod;
        else if (v1.size()==2) dp[i][0] = (dp[i][0] * 2) % mod;
        if (dp[i-1][2]!=-1)
        {
            if (v2.size()==0) dp[i][0] = (dp[i][0] * qpow(2,mod-2,mod)) % mod;
            else if (v2.size()==2) dp[i][0] = (dp[i][0] * 2) % mod;
        }
        if (dp[i][1]==dp[i][2]) dp[i][2] = -1;
        //debug2(i,dp[i][0]);
    }
    cout<<dp[2*n][0]<<endl;
}