期望得分：100+100+100=300
实际得分：94+96+97=287
T1 #6090. 「Codeforces Round #418」尘封思绪
#include<cstdio>
#define N 102
using namespace std;
int a[N],b[N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
if(m>) { printf("Yes"); return ; }
if(!m)
{
for(int i=;i<=n;i++)
if(a[i]<a[i-]) { printf("Yes"); return ; }
printf("No"); return ;
}
int pos;
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(!a[i]) { pos=i; continue;}
if(a[i]<a[i-]) { printf("Yes"); return ; }
}
scanf("%d",&m);
a[n+]=;
if(m<a[pos-] || m>a[pos+]) { printf("Yes"); return ; }
printf("No");
}
T1 #6091. 「Codeforces Round #418」幻想特快
#include<cstdio>
#define N 1001
using namespace std;
int a[N],b[N];
int p[],fa,fb;
int v[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
if(!v[a[i]]) v[a[i]]=i;
else fa=i;
}
for(int i=;i<=n;i++)
{
scanf("%d",&b[i]);
if(a[i]!=b[i]) p[++p[]]=i;
}
int k;
for(int i=;i<=n;i++)
if(!v[i]) { k=i; break; }
if(p[]==)
{
a[p[]]=k;
for(int i=;i<=n;i++) printf("%d ",a[i]);
return ;
}
if(b[fa]==k) a[fa]=k;
else a[v[a[fa]]]=k;
for(int i=;i<=n;i++) printf("%d ",a[i]);
}
T3 LOJ #6092. 「Codeforces Round #418」恋爱循环
法一： 尺取法
#include<cstdio>
#include<algorithm>
#define N 1501
using namespace std;
char s[N];
int main()
{
int n,q;
scanf("%d",&n);
scanf("%s",s+);
scanf("%d",&q);
int l,r,now,ans,m;
char c[];
while(q--)
{
scanf("%d%s",&m,c);
now=ans=;
r=,l=;
while()
{
while(r<=n && now<=m)
if(s[++r]!=c[]) now++;
ans=max(ans,r-l);
if(r>=n) break;
while(l<=n && now>m)
if(s[l++]!=c[]) now--;
}
printf("%d\n",ans);
}
}
法二：动态规划
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1501
using namespace std;
char s[N];
int ans[][N];
int main()
{
int n,sum;
scanf("%d",&n);
scanf("%s",s+);
for(int k=;k<;k++)
{
for(int i=;i<=n;i++)
{
sum=;
for(int j=i;j<=n;j++)
{
if(s[j]-'a'!=k) sum++;
ans[k][sum]=max(ans[k][sum],j-i+);
}
}
for(int i=;i<=n;i++) ans[k][i]=max(ans[k][i],ans[k][i-]);
}
int q;
scanf("%d",&q);
int m; char c[];
while(q--)
{
scanf("%d%s",&m,c);
printf("%d\n",ans[c[]-'a'][m]);
}
}
考场做法：二分 TLE1个点
#include<cstdio>
#include<iostream>
#define N 1501
using namespace std;
char s[N],c[];
int n,m;
inline bool check(int mid)
{
int now=;
for(int i=;i<=mid;i++)
if(s[i]!=c[]) now++;
if(now<=m) return true;
for(int i=mid+;i<=n;i++)
{
if(s[i-mid]!=c[]) now--;
if(s[i]!=c[]) now++;
if(now<=m) return true;
}
return false;
}
inline void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
}
int main()
{
read(n);
scanf("%s",s+);
int q,l,r,mid,ans;
read(q);
while(q--)
{
read(m);
scanf("%s",c);
ans=;
l=m,r=n;
while(l<=r)
{
mid=l+r>>;
if(check(mid)) ans=mid,l=mid+;
else r=mid-;
}
printf("%d\n",ans);
}
}