CF1140


CF1140A
这是一道签到题。模拟即可。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
int a[10005];
void init(){
	scanf("%d",&n);
	int ans=0;
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	int p=1,mx=0;
	while(p<=n){
		++ans;
		mx=max(mx,a[p]);
		while(p<=mx){
			mx=max(mx,a[p]);
			++p;
		}
	}
	printf("%d\n",ans);
}
int main(){
	init();
	return 0;
}


CF1140B
这是一道英文阅读理解题。
一个符号可以使用任意多次,因此形如>><><><><><><><的序列也是合法的。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;
char ch[100005];

void init(){
	scanf("%d",&n);
	cin>>ch+1;
	int j=1,ans=0;
	while(ch[j]!='>'&&ch[n-j+1]!='<'){
		++j;
		++ans;
	}
	printf("%d\n",ans);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		init();
	}
	return 0;
}


CF1140C
按好听程度排个序,枚举一遍。
显然某首歌后面的所有歌都可以听。但是有k的限制。所以从后往前用优先队列计算一下前k大和即可。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

typedef long long ll;
inline ll Max(ll A,ll B){
	return A>B?A:B;
}
struct data{
	ll b;
	ll t;
	inline operator<(const data &B)const{
		return t<B.t;
	}
}a[300005]; 

int n,k;
ll sm[300005];
priority_queue< int,vector<int>,greater<int> > q;
void init(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%lld%lld",&a[i].b,&a[i].t);
	}
	sort(a+1,a+1+n);
	ll cnt=0;
	for(int i=n;i>=1;--i){
		cnt+=a[i].b;
		q.push(a[i].b);
		while(q.size()>k){
			cnt-=q.top();
			q.pop();
		}
		sm[i]=cnt;
	}
	ll ans=0;
	for(int i=1;i<=n;++i){
		ans=Max(ans,sm[i]*a[i].t);
	}
	printf("%lld\n",ans);
}
int main(){
	init();
	return 0;
}


CF1140D
贪心地考虑,每个顶点都选择1的话答案会最优。
如果每个都把一个顶点选择1的话,那么根据基本不等式,选择尽可能相邻的构成三角形会更优。


#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

int n;

void init(){
	scanf("%d",&n);
	long long ans=0;
	for(int i=2;i<n;++i){
		ans+=1*i*(i+1);
	}
	printf("%lld\n",ans);
}
int main(){
	init();
	return 0;
}


CF1140E
我们发现,由于限定为奇回文串,原题的题意可以转化为求隔一个不相等的方案数。
故而,容易发现,这是奇偶无关的。
我们容易地令\(f_{i,j}\)为第\(i\)个填\(j\)的方案数。容易得到:
$$f_{i,j}+=f_{i-1,k},(k\ne j)$$
然而这样的复杂度是不可接受的。
我们考虑统计一个-1区间的答案。首先,我们可以只考虑左端的非-1数对计算带来的影响——这是因为整个区间是对称的,所以右端的非-1数造成的额外影响是可以统计的。
不妨令这个-1区间前的第一个非-1数为\(q\),那么可以发现,\(f_{i,q}\ne f_{i,k},f_{i,j}=f_{i,k},(j\ne k,j\ne q,k\ne q)\)
发现这个性质之后,我们就可以优化前面的转移了。我们不妨令\(f_{i,0}\)表示第\(i\)位与\(q\)不同的方案数,\(f_{i,1}\)表示第\(i\)位与\(q\)相同的方案数。可以得到转移方程:
$$f_{i,0}=(k-2)f_{i-1,0}+(k-1)f_{i-1,1}$$
$$f_{i,1}=f_{i-1,0}$$
于是统计区间计算即可。
然而,我们还需要计算右端的第一个非-1数对答案的影响。如果它与左端的那个数相同,那么初始化\(f_{0,1}=1,f_{0,0}=0\)直接统计即可;如果它和左端的那个数不同,那么初始化\(f_{0,0}=1,f_{0,1}=0\),则可以把从左到右的贡献容斥掉。


#include<iostream>
#include<cstdio>


typedef long long ll;
const ll MOD=998244353;
ll n,k;
ll a[200005],f[200005][2];

inline ll calc(ll LEN,ll L,ll R){
	if(!LEN){
		return !L||!R||L!=R;
	}
	for(int i=0;i<=LEN;++i){
		f[i][0]=f[i][1]=0;
	}
	if(!L){
		--LEN;
		f[0][0]=k-1;
		f[0][1]=1;
	}else{
		f[0][L==R]=1;
	}
	for(int i=1;i<=LEN;++i){
		f[i][0]=(f[i-1][0]*(k-2)+f[i-1][1]*(k-1))%MOD;
		f[i][1]=f[i-1][0];
	}
	return R?f[LEN][0]:(f[LEN][0]+f[LEN][1])%MOD;
}

void init(){
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;++i){
		scanf("%lld",&a[i]);
	}
	ll lst=-1,ans=1;
	for(int i=1;i<=n+2;i+=2){
		if(~a[i]||i>n){
			ans*=calc(((i-lst)>>1)-1,lst>0?a[lst]:0,a[i]);
			ans%=MOD; 
			lst=i;
		}
	}
	lst=0;
	for(int i=2;i<=n+2;i+=2){
		if(~a[i]||i>n){
			ans*=calc(((i-lst)>>1)-1,lst>0?a[lst]:0,a[i]);
			ans%=MOD;
			lst=i;
		}
	}
	printf("%lld\n",ans);
}

int main(){
	init();
	return 0;
}