又是迟到的一篇，这场是教主说第三场之后要加大难度的第一场只过了三体...有时间补一下其他的吧，先把做的三题写了。
比赛链接：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;
}