\(\text{B - Squares}\)
解法
先开始觉得要给每一种 \(x\) 分类… 结果令 \(p=x+z,q=x-z\)，这样只用保证 \(p\equiv q\pmod 2\)，\(pq\le N\) 即可。
\(\text{C - LIS to Original Sequence}\)
解法
没睡午觉，感觉脑子已经不太清醒了… 我一直以为是计算 \(\rm LIS\) 是 \(A\) 的排列个数。但是我也不会这个排列组合问题。
首先可以想到，在 \(A_i\) 前放置一个 \(>A_i\) 的数一定是不优的。对于 \(P_1\) 只能放置 \(A_1\)，不然 \(\rm LIS\) 会增加到 \(k+1\) 项。不过，对于 \(A_i,i>1\)，都可以在 \(A_{i-1},A_i\) 之间放置 一个 小于 \(A_i\) 的数。\(A_k\) 会有些麻烦，需要将比它大的数逆序放在它之前，比它小的数逆序放在它之后。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;
int n,k,a[maxn];
queue <int> q;
vector <int> ans;
int main() {
n=read(9),k=read(9);
for(int i=1;i<=k;++i)
a[i]=read(9);
for(int i=1;i<a[1];++i)
q.push(i);
for(int i=1;i<k;++i) {
print(a[i],' ');
if(!q.empty()) {
print(q.front(),' ');
q.pop();
}
for(int j=a[i]+1;j<a[i+1];++j)
q.push(j);
}
q.push(a[k]);
for(int i=a[k]+1;i<=n;++i)
q.push(i);
while(!q.empty()) {
ans.push_back(q.front());
q.pop();
}
reverse(ans.begin(),ans.end());
for(int i=0;i<ans.size();++i)
print(ans[i],' ');
puts("");
return 0;
}
\(\text{D - Unique Subsequence}\)
解法
只需要保证对于所选下标 \(p_i,p_{i+1}\)，满足 \(j\in [p_i,p_{i+1}]\) 时，\(a_j\neq a_{p_i},a_j\neq a_{p_{i+1}}\)。
设 \(dp_i\) 为以 \(i\) 为结尾得到的满足条件的字符串个数，它的前缀和可以用树状数组维护。再用 \(lst\) 维护上一个同种 \(a\) 的下标。容易发现，只有 \(j\in[lst_{a_i},i)\) 可以进行贡献，而且 \(lst_{a_i}\) 对应的 \(\mathtt {dp}\) 值应从前缀和中减去，因为它一定会被 \(i\) 干扰。
代码
#include <cstdio>
#define print(x,y) write(x),putchar(y)
template <class T>
inline T read(const T sample) {
T x=0; char s; bool f=0;
while((s=getchar())>'9' or s<'0')
f|=(s=='-');
while(s>='0' and s<='9')
x=(x<<1)+(x<<3)+(s^48),
s=getchar();
return f?-x:x;
}
template <class T>
inline void write(const T x) {
if(x<0) {
putchar('-'),write(-x);
return;
}
if(x>9) write(x/10);
putchar(x%10^48);
}
const int maxn=2e5+5,mod=998244353;
int dp[maxn],n,lst[maxn];
int c[maxn];
int lowbit(int x) {
return x&-x;
}
int inc(int x,int y) {
if(x+y>=mod)
return x+y-mod;
if(x+y<0)
return x+y+mod;
return x+y;
}
void add(int x,int k) {
while(x<=n)
c[x]=inc(c[x],k),
x+=lowbit(x);
}
int ask(int x) {
int r=0;
while(x)
r=inc(r,c[x]),
x-=lowbit(x);
return r;
}
int main() {
n=read(9);
for(int i=1;i<=n;++i) {
int x=read(9);
if(!lst[x]) {
dp[i]=inc(ask(i-1),1);
add(i,dp[i]);
lst[x]=i;
}
else {
dp[i]=inc(ask(i-1),-ask(lst[x]-1));
add(lst[x],-dp[lst[x]]);
lst[x]=i;
add(i,dp[i]);
}
}
print(ask(n),'\n');
return 0;
}