dc_y's Blog

又膜了一场JSOI

靠着暴力的80分华丽丽的拿了第一

T1

本以为是一道水题，暴力枚举原串然后贪心判断正确性就好了

然后。。被aabaabaaaa这个数据完爆。。血崩……

判断正确性还是要用区间dp

f[i,j]表示i-j是否为完美匹配

完美匹配定义为：除去完全匹配的子串，剩余子串连接起来为匹配串的前缀

这样若f[i,j-1]为完美匹配，就知道f[i,j]为完美匹配时a[j]应是什么

两区间合并只要满足两者皆为完美匹配并且其中一个长度为匹配串长度的倍数

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
char s[210],st[210],ans[210];
int n,m,k,l,t,r,cas;
int ts[200],tt[200];
bool f[210][210];
bool shit(int m){
    int pp=0;
    for (int w=0;w<l;w++){
        if (w>=m-1)
            if ((s[w]==s[l-1])&&(s[w-m+1]==s[0])){
                memset(tt,0,sizeof(tt));
                int fuck=0;
                for (int i=1;i<=m;i++){st[i]=s[w-m+i];tt[st[i]]++;}
                for (int i=1;i<=190;i++) if ((tt[i]*(l/m))!=ts[i]){fuck=1;break;}
                if (fuck) continue;
                memset(f,0,sizeof(f));
                for (int i=1;i<=l;i++) 
                    if (s[i-1]==st[1]) f[i][i]=1;
                for (int q=2;q<=l;q++)
                for (int i=1;i<=l-q+1;i++){
                    int j=i+q-1;
                    if (f[i][j-1]&&(s[j-1]==st[(q-1)%m+1])){f[i][j]=1;continue;}
                    for (int o=1;o<=(q-1)/m;o++){
                        k=i+o*m-1;
                        if (f[i][k]&&f[k+1][j]){f[i][j]=1;break;}
                        k=j-o*m;
                        if (f[i][k]&&f[k+1][j]){f[i][j]=1;break;}
                    }
                }
                if (f[1][l]){
                    if (pp==0) for (int i=1;i<=m;i++) ans[i]=st[i];
                    else for (int i=1;i<=m;i++) if (st[i]<ans[i]){for (int j=1;j<=m;j++) ans[j]=st[j];break;}
                    else if (st[i]>ans[i]) break;
                    pp=1;
                }
            }
    }
    k=m;
    if (pp) return(1);
    return(0);
}
int main(){
    scanf("%d",&cas);
    while (cas-->0){
        scanf("%s",s);
        l=strlen(s);
        memset(ts,0,sizeof(ts));
        for (int i=0;i<l;i++) ts[s[i]]++;
        for (int ii=1;ii<=l;ii++)
            if ((l%ii)==0) 
                if (shit(ii)) break;
        for (int i=1;i<=k;i++) printf("%c",ans[i]);
        printf("\n");
    }
}

T2

不难发现有一个性质，每次询问的中位数只会比之前大1或不变

因此只要判断ans是否为修改后的中位数即可

判断可用分块优化

把n个数分成块，对每块进行排序，使每块中元素单调递增

更改时，整块的可以记一个数组+1，非整块的在块里暴力找然后+1，之后再快排（暴力好可怕）

最后对每块二分求出比ans大的个数就好辣

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define N 1000010
#define a first
#define b second
struct node{
    int a,b;
};
bool cmp(node x,node y){
    return x.a<y.a;
}
pair<int,int> a[N];
int c[N],p[N],id[N],d[N];
int n,m,k,l,t,s,ans,r,x,y,w;
bool shit(){
    int s=0;
    for (int i=1;i<=n/k;i++)
    s+=k*i-(lower_bound(a+(i-1)*k+1,a+i*k+1,make_pair(ans+1-c[i],0))-a)+1;
    if (s>=w) return(1);
    return(0);
}
int main(){
    scanf("%d%d",&n,&m);
    k=200;
    for (int i=1;i<=n;i++){scanf("%d",&a[i].a);a[i].b=i;c[i]=a[i].a;}
    sort(c+1,c+n+1);
    ans=c[(n+1)/2];
    w=(n+1)/2;
    memset(c,0,sizeof(c));
    while (n%k) a[++n].a=0,a[n].b=n;
    for (int i=1;i<=n+1;i++) id[i]=(i-1)/k+1;
    for (int i=1;i<=n/k;i++) sort(a+k*(i-1)+1,a+k*i+1);
    for (int i=1;i<=m;i++){
        scanf("%d%d",&x,&y);
        for (int j=id[x-1]+1;j<=id[y+1]-1;j++)c[j]++;
        t=id[x];
        if ((x-1)%k!=0){
            for (int j=(t-1)*k+1;j<=t*k;j++)
                if (a[j].b>=x&&a[j].b<=y) a[j].a++;
            sort(a+(t-1)*k+1,a+t*k+1);
        }
        t=id[y];
        if (y%k!=0&&id[x-1]!=id[y+1]){
            for (int j=(t-1)*k+1;j<=t*k;j++)
                if (a[j].b<=y) a[j].a++;
            sort(a+(t-1)*k+1,a+t*k+1);
        }
        if (shit()) ans++;
        printf("%d\n",ans);
    }
}

T3

此题及其恶心（因为李日天大神不会做）

所以我就弃坑了→_→