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;
}