惯例开坑。
任务栏:
订正了几题?2/3
BZOJ刷题量?288/300
还有11天就要ZJOIDay1了苯宝宝好虚啊。
(诶我的博客画风为啥变得这么正常了)
这是一个句子测试
惯例开坑。
任务栏:
订正了几题?2/3
BZOJ刷题量?288/300
还有11天就要ZJOIDay1了苯宝宝好虚啊。
(诶我的博客画风为啥变得这么正常了)
谜之声I:在阅读时请每隔5秒按一下F5因为可能你在读而窝正在更新。
谜之声II:请点开再看因为这篇文章实在太长了。
Day1
出发日。
在文化课脑残粉(众家长?)的建议下,窝萌订了晚上的机票来考完期末考。
然而天公不作美,期待已久的期末考推迟了。(其实我的内心是狂喜的)
于是飞机喜闻乐见地晚点了。
于是窝萌的行程就被拖到了Day2。
Day2
到2.00am的时候终于抵达了南山中学,决定先去拜访Gold_7和NiroBC。
南山中学的城门虽然十分气派,但和YYHS的完全不能比嘞。。。
然而找不到寝室,期间听到了门卫大叔的四川话TalkShow,感到不明觉厉。
最终还是滚到了寝室,一人敲开门,剩下的人集体开闪光灯拍Gold_7的睡衣照,然而质量极差,只能看到一团黑影。
8.00am去听多项式导论。
然而只听了1h就听不下去了。。。。
接下来3h只听到讲课人不断地说“好啊!”
于是偷偷从后门溜了出去,结果被生辅老师赶了出去,于是又滚了回去。
下午听形式语言与自动机。
alpq说下午的课比上午更恶心,想想自己只会AC自动机、WA自动机、TLE自动机和RE自动机,于是集体弃疗。
期间老司机YWN普及英语知识,让窝萌学会了诸如dick等单词。
由于玩积木的时候gonens过于狡猾,新称号迪克李(DickLee)GET DA☆ZE。
吃晚饭的时候窝萌被两个妹子莫名采访了,对上镜深恶痛绝的我们嫁祸条哥。然而alpq说有个妹子的颜值很高,于是作为学弟的窝萌为学长拍了许许多多的妹子照片。(听说最后alpq还是被采访了233)
晚上alpq和gonens也搬到窝萌寝室来了,于是窝萌寝室就有8个人了。
在10.30pm熄灯的时候alpq吼了一声:夜生活才刚刚开始!
于是窝萌就开始嘿嘿嘿。。。
听说这是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); } }
Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com