听说这是JSOIDay7
我去JSOI考不完辣！
值得一提的是：由于这场题目太丧病了，结果最高分80，最低分60。。。
T1
这是一道坑题。（仅仅是因为窝的贪心被卡飞）
首先阔以枚举区间，然后YY各种优化：
1、看区间是不是长度的约数。
2、看区间的第一个和最后一个是不是和整个序列的第一个和最后一个相等。
3、看区间的每一个元素的个数是否合法。
4、看枚举的串有没有出现过。
接着看能不能用枚举的串消掉整个串。
SB贪心：能删则删，那么有反例：aabaabaaaa，即消的顺序会有影响。（然而这有60分）
正确DP：如果区间[i,j]被最大地消去后是模式串的前缀，则称[i,j]为模式串的一个完美匹配。
那么[i,j]为完美匹配的条件为：
1、存在k使得[i,k]与[k+1,j]均为完美匹配，并且k-i+1与j-k至少有一个是模式串长度的倍数，即一段全部消去，一段完美匹配。
2、[i,j-1]为完美匹配，那么就知道了a[j]应该是什么，判断一下就阔以了。
T2
这是一道送分题。（然而分并没有送到）
首先有一个性质：每次中位数与上一次相比只会+1或不变。
那么可以在每次加权后验证中位数是否变化。
那么就可以分块。
既然是第一次写分块，那么就讲一讲：
首先把n个数分成[tex]\sqrt n[/tex]块，每个块中的元素的权值是单调递增的。
对于给一个区间加权，如果一个块的所有元素都在区间内，就打一个tag，否则暴力枚举元素，暴力加，暴力重排。
最后只要二分来看一看大于等于比中位数+1的元素的个数是不是超过一半就阔以辣！
T3
这是一道恶心题。（仅仅是窝不会做）
先挖个坑，待填。
[Codes]
#include<cstdio>
#include<algorithm>
#include<cstring>
typedef unsigned long long ull;
using namespace std;
int cas,n,i,j,len,ans1,ans2;
char s[210];
int a[210],b[210],sum[210][210],f[210][210];
ull mi[210],hash[210];
int isok(int l,int r){
int i,j,k,p;
memset(f,0,sizeof f);
for (i=1;i<=n;i++)if (a[i]==a[l])f[i][i]=1;
for (p=1;p<n;p++)
for (i=1;i<=n-p;i++){
j=i+p;
for (k=1;k<=p/(len+1);k++)
if (f[i][i+k*(len+1)]&&f[i+k*(len+1)+1][j]||f[i][j-k*(len+1)]&&f[j-k*(len+1)+1][j]){f[i][j]=1;break;}
if (f[i][j-1]&&a[j]==a[l+p%(len+1)])f[i][j]=1;
}
return f[1][n];
}
int solve(int l1,int l2,int len){
for (int i=0;i<=len;i++)
if (a[l1+i]>a[l2+i])return 1;
else if (a[l1+i]<a[l2+i])return 0;
return 0;
}
int main(){
scanf("%d",&cas);
mi[0]=1;
for (i=1;i<=200;i++)mi[i]=mi[i-1]*6662333;
while (cas--){
scanf("%s",s);
n=strlen(s);
for (i=1;i<=n;i++){
a[i]=s[i-1]-'A';
for (j=0;j<=100;j++)sum[i][j]=sum[i-1][j];
sum[i][a[i]]++;
hash[i]=hash[i-1]*6662333+a[i];
}
int flag=1;
ull pre=-1;
for (len=0;len<n&&flag;len++)
if (!(n%(len+1)))
for (int l=1;l<=n-len;l++){
int r=l+len;
if (a[1]==a[l]&&a[n]==a[r]){
int cmp=1;
if (hash[r]-hash[l-1]*mi[len+1]==pre)continue;
for (i=0;i<=100;i++)if ((sum[r][i]-sum[l-1][i])*n/(len+1)!=sum[n][i]){cmp=0;break;}
if (cmp&&isok(l,r)){
if (flag){flag=0;ans1=l;ans2=r;pre=hash[r]-hash[l-1]*mi[len+1];}
else if (solve(ans1,l,len))ans1=l,ans2=r,pre=hash[r]-hash[l-1]*mi[len+1];
}
}
}
for (i=ans1;i<=ans2;i++)printf("%c",a[i]+'A');
puts("");
}
}
#include<cstdio>
#include<algorithm>
#include<cstring>
#define fi first
#define se second
using namespace std;
const int M=100010;
int n,m,i,j,ans,l,r;
int add[M];
pair<int,int>a[M],b[M];
int main(){
scanf("%d%d",&n,&m);
for (i=1;i<=n;i++)scanf("%d",&a[i].fi),a[i].se=i,b[i]=a[i];
sort(b+1,b+n+1);
ans=b[n+1>>1].fi;
int x=200,mid=n+1>>1;
while(n%x)a[++n].fi=0,a[n].se=n;
for (i=1;i<=n/x;i++)sort(a+(i-1)*x+1,a+i*x+1);
while (m--){
scanf("%d%d",&l,&r);
for (i=1;i<=n/x;i++)
if (l<=(i-1)*x+1&&r>=i*x)add[i]++;
else if (r<(i-1)*x+1||l>i*x)continue;
else{
for (j=(i-1)*x+1;j<=i*x;j++)
if (a[j].se>=l&&a[j].se<=r)a[j].fi++;
sort(a+(i-1)*x+1,a+i*x+1);
}
int cnt=0;
for (i=1;i<=n/x;i++)
cnt+=i*x-(lower_bound(a+(i-1)*x+1,a+i*x+1,make_pair(ans+1-add[i],0))-a)+1;
if (cnt>=mid)ans++;
printf("%d\n",ans);
}
}
评论 (0)
