AtCoder Regular Contest 125

目录

\(\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;
}
上一篇:AtCoder ABC 164 (D~E)


下一篇:AtCoder Regular Contest 125