首页 > 代码库 > 8.9联考题解
8.9联考题解
今天的题有质量多了，尤其是第一题不再毫无意义，果然考这样的试比较有收获。
时间限制：1sec 内存限制：128MB
题解
刚开始看的时候没有思路。不过这样的考试才叫正常嘛，前两天T1那是什么玩意= =。边读题边写前缀和、离散之类的词，但是前缀和并不能处理出题目中所要求的情况，3*10^5大概最多nlogn。举了几个例子，发现好像和后面大于它的数有关，想了想怎么求它后面大于它的数字个数，过了一会猛然发现我举的例子也太特殊了，全都是单调递增的，有点挫败，就去做后面的题了。T2做了很久还是打了30分放那，回来看T1就有点着急。大概还剩不到两个小时，至少要打上n^3的暴力。打完之后感觉暴力的低效就在于每一段都重复了很多遍，能不能把1->2,2->3,3->6转化成1->6+2+3呢？然后想了一会区间dp，觉得很苦手，也不准确。这时候回去看了一眼题，忽然发现我记错题意了，值是个数和不是权值和，于是觉得好做了很多。换个思路想，每个值对答案的贡献是多少？也就是它要被选几遍吧。乘法计数原理，前面比它小的个数*后面比它大的个数不就是了吗，豁然开朗。但是这两个值该怎么求呢？n^2遍历只能拿60分，绞尽脑汁想把一个n降到logn，刚开始以为logn来自于sort，想了想觉得行不通，后来就一点思路也没有了。其实过后想想，除了sort之外带log很明显就是树类结构吧。线段树、平衡树、树状数组其实都能做。下午复习了很久没打过的树状数组，离散一下用权值做下标，真不知道为什么就这么几行我却一直宁愿打线段树。还有两分钟关竞赛忽然得知ai的范围有误，其实是>-10^9，一分钟删快读皇德耀世= =
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; const int sj=300010; int n,a[sj],temp,d[sj],xy[sj],qz[sj],cf[sj]; long long ans; struct ls { int num,v; }l[sj]; int comp(const ls&a,const ls&b) { return a.v<b.v; } int lowbit(int x) { return x&(-x); } int getsum(int x) { int jg=0; while(x>0) { jg+=d[x]; x-=lowbit(x); } return jg; } void update(int x,int y) { while(x<=temp) { d[x]+=y; x+=lowbit(x); } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); l[i].num=i; l[i].v=a[i]; } sort(l+1,l+n+1,comp); temp=1; a[l[1].num]=1; for(int i=2;i<=n;i++) { if(l[i].v>l[i-1].v) temp++; a[l[i].num]=temp; } for(int i=1;i<=n;i++) { xy[i]=getsum(a[i]-1); update(a[i],1); qz[a[i]]++; cf[i]=qz[a[i]]; } for(int i=2;i<n;i++) ans+=xy[i]*((n-i)-(qz[a[i]]-cf[i])-(getsum(a[i]-1)-xy[i])); printf("%lld",ans); return 0; }
2 beautiful
2.1 题目描述
Mavis 有一个序列（不必在乎这些细节），对于每个数都有一个在序列中的优美值，这个优美值的定义是：找到序列中最长的一段，满足包含这个数并且这个数是这一段的中位数（以数值为第一关键字，下标为第二关键字排序, 这样的话这一段的长度只有可能是奇数），那么这一段的长度就是它的优美值。Mavis 说：“对于我每次手贱点出的左右端点[l, r]，我都要找到[l,r] 中的所有数中，最大的优美值”
但是Mavis 只会喊口号，不能解决问题，所以这个问题就交给你了
2.2 输入格式
第一行输入n 接下来n 个整数，代表ai 接下来Q，代表有Q 个区间接下来Q 行，每行
两个整数l, r(l <= r)，表示区间的左右端点
2.3 输出格式
对于每个区间的询问，输出答案
2.4 Sample Input
8
16 19 7 8 9 11 20 16
8
3 8
1 4
2 3
1 1
5 5
1 2
2 8
7 8
2.5 Sample Output
7
3
1
3
5
3
7
3
3
2.6 数据范围与约定
对于30% 的数据满足： 1<=n,Q<= 50
对于70% 的数据满足： 1<=n,Q<= 2000
对于100% 的数据满足： 1<=n<= 2000, 1<=Q<=100000, ai <= 200
时间限制：1sec 空间限制：128MB
题解
很明显是要预处理优美值，区间最大值是个没有修改的询问，随便用个什么线段树啊RMQ啊就出来了。真不懂数据为什么对询问分层，一个nlogn我也不是太在意它有多大啊……倒是n的范围只有两档，预处理其实很困难。刚开始以为简单地两边拓展找一个比较好的位置，在比它小的值更多的时候看相邻的有没有比它大的云云就行了，打完自己造数据忽然发现2333111这个情况不是就完了？然后有点方，想着n^3只有30分，还是至少需要n^2logn啊，不过脑子就开始二分。又一次打完了发现这个东西它压根就没有单调性，二分个鬼啊……达成成就：扔了一个多小时在我也不知道什么鬼想法上。最后没办法，还是扔了个n^3的暴力，尽量卡卡常剪剪枝然而自己也知道并没有什么用。测完之后发现感人评测机n^3甚至跑不过30%数据？Exm？最后发现要把那个n降下来还是需要树(不过不用树的n^2算法也有，可是好像并没有跑得比我的n^2logn快)，直接枚举区间维护Treap，用Treap求排名为一半的数求中位数，然后比较中位数的优美值和当前区间长度就行了。今天在这两道题上卡完，终于懂得怎么用树结构降低复杂度了，也算是花分买经验吧。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<ctime> #include<algorithm> using namespace std; const int sj=2005; int n,m,b[sj],a1,a2,c[sj],rt,size; int r() { int jg=0,jk; jk=getchar()-‘0‘; if(jk<=9&&jk>0) jg=jk; jk=getchar()-‘0‘; while(jk>=0&&jk<=9) { jg*=10; jg+=jk; jk=getchar()-‘0‘; } return jg; } struct tree { int l,r,ma; }t[sj*4]; int bj(int x,int y) { return x>y?x:y; } struct Treap { int l,r,v,size,rnd,w; }p[sj]; void update(int x) { p[x].size=p[p[x].l].size+p[p[x].r].size+1; } void lturn(int &x) { int tt=p[x].r; p[x].r=p[tt].l; p[tt].l=x; p[tt].size=p[x].size; update(x); x=tt; } void rturn(int &x) { int tt=p[x].l; p[x].l=p[tt].r; p[tt].r=x; p[tt].size=p[x].size; update(x); x=tt; } void cr(int &x,int y) { if(x==0) { size++; x=size; p[x].size=1; p[x].v=y; p[x].w=c[y]; p[x].rnd=rand(); return; } p[x].size++; if(c[y]>p[x].w) { cr(p[x].r,y); if(p[p[x].r].rnd<p[x].rnd) lturn(x); } else { cr(p[x].l,y); if(p[p[x].l].rnd<p[x].rnd) rturn(x); } } int quey(int x,int y) { if(x==0) return 0; if(p[p[x].l].size>=y) return quey(p[x].l,y); if(p[p[x].l].size+1<y) return quey(p[x].r,y-p[p[x].l].size-1); return p[x].v; } void gp() { for(int i=1;i<=n;i++) { memset(p,0,sizeof(p)); rt=size=0; for(int j=i;j<=n;j++) { cr(rt,j); a1=j-i+1; if(a1&1) { a2=quey(rt,(a1+1)>>1); b[a2]=bj(b[a2],a1); } } } } void buil(int x,int z,int y) { t[x].l=z; t[x].r=y; if(z==y) { t[x].ma=b[z]; return; } int mi=(z+y)>>1; buil(x<<1,z,mi); buil((x<<1)|1,mi+1,y); t[x].ma=bj(t[x<<1].ma,t[(x<<1)|1].ma); } int query(int x,int z,int y) { if(z<=t[x].l&&y>=t[x].r) return t[x].ma; int mi=(t[x].r+t[x].l)>>1; if(mi<z) return query((x<<1)|1,z,y); if(mi>=y) return query(x<<1,z,y); return bj(query(x<<1,z,y),query((x<<1)|1,z,y)); } struct ls { int num,v; }l[sj]; int comp(const ls&a,const ls&b) { return (a.v==b.v)?(a.num<b.num):(a.v<b.v); } int main() { n=r(); for(int i=1;i<=n;i++) { c[i]=r(); l[i].num=i; l[i].v=c[i]; } sort(l+1,l+n+1,comp); for(int i=1;i<=n;i++) c[l[i].num]=i; gp(); buil(1,1,n); m=r(); for(int i=1;i<=m;i++) { a1=r(); a2=r(); if(a1==a2) printf("%d\n",b[a1]); else printf("%d\n",query(1,a1,a2)); } return 0; }
3 Permutation
3.1 题目描述
一个长度为n 的排列p[1..n]
把排列的每个循环拿出来，写成标准循环，再做一次排序
比如[4, 1, 6, 2, 5, 3]，有3 个循环(421)(63)(5)
其中第一个循环就是4 要到2 的位置，2 要到1 的位置，1 要到4 的位置。
每个循环从任意一个位置开始读都是一样的比如(412) 也是(124),(241)。n 个循环就一共n 个表达法
我们规定一个标准循环是以循环内最大的数字开头
循环之间排序的关键字就是第一个数字的大小
如(421)(63)(5) 排序后是(421)(5)(63)
如果排序后的拍列和原排列一样，那么就是可行排列
求n 个数的字典序第k 大的排列
3.2 输入格式
两个整数，n，k 保证k 在long long 范围内，保证有解
3.3 输出格式
n 个整数，表示满足条件的排列
3.4 Sample Input1
4 3
3.5 Sample Output1
1 3 2 4
3.6 Sample Input2
10 1
3.7 Sample Output2
1 2 3 4 5 6 7 8 9 10
3.8 数据范围与约定
对于30% 的数据满足：1<=n<=10
对于100% 的数据满足，1<=n<=50
时间限制：1sec 内存限制：256MB
题解
考场上又一次没有读懂题。为什么T3没有爆零呢，因为机智地输出了1 2 3……n，骗了20，导致rp--第二题n^3老爷评测机连30%数据都没跑过，真是rp守恒定律啊。做题的时候觉得这个大概和什么组合有关系，想了想阶乘，但是毕竟题都没读懂，也没有什么思考成果。
先来读题好了:
1.“一个长度为n 的排列p[1..n]”——排列中的数是1~n；这个排列好像没有什么数学意义，权且当做普通数列吧
2.“把排列的每个循环拿出来，写成标准循环，再做一次排序”——什么玩意并没有定义循环啊
3.“比如[4, 1, 6, 2, 5, 3]，有3 个循环(421)(63)(5)，其中第一个循环就是4 要到2 的位置，2 要到1 的位置，1 要到4 的位置”—— 根据这个例子感性理解一下，就是说第i位的数为ai，总是从第i位走到第ai位，最后能回到i就算循环(考试的时候死活想不明白)。这样看ai如果是i是一定可以算循环的。
4.“每个循环从任意一个位置开始读都是一样的，比如(412) 也是(124),(241)。n 个循环就一共n 个表达法，我们规定一个标准循环是以循环内最大的数字开头”—— 所以说这个垃圾题面连循环都没有定义却定义了标准循环……
5.“循环之间排序的关键字就是第一个数字的大小，如(421)(63)(5) 排序后是(421)(5)(63)”——定义完循环又定义了循环排序的关键字，而且因为排列中没有重复的数字所以循环一定有确定的顺序
6.“如果排序后的拍列和原排列一样，那么就是可行排列” ——给标准循环们排序不改变所有元素的位置，这样的排列就是可行排列。注意这里的排序是上面定义的给循环排序，所以和各循环里非最大的数没有关系
7.“求n 个数的字典序第k 大的排列” ——最后抛出了这个鬼问题。给的这个字典序很迷，根据样例2分析一下，大概字典序大就是从前到后翻字典的时候先翻到的意思吧23333
题解上说：“可以证明，只会存在大小为2的循环”，怎样证明呢？
zzh说打表找规律~本蒟蒻顺着wq大佬的思路写一写试试
1.可行排列里一个循环中的数在原排列中处在连续的位置：否则把一个排列从中间断开，比如4132里412、3是循环，那么写成循环再排序后一个循环里的数一定相连变成3421，从而改变了原排列。
2.可行排列里一个循环中的数在数值上也是连续的：上面1.已经证明了它的位置是相连的，它的数值指向循环的下一个位置，所以数值也是连续的。
3.满足条件的一个循环最多有2个元素：写成标准循环之后第一个数是最大的，标准循环的第二位是它指向的位置上的数值，第三位是第二位指向的位置上的数值，以此类推。第一位的数最大，它指向的位置也最靠后，而最靠后的数被写在循环第二位上位置居然不变，这说明了什么呢？最后一个数就是第二个数啊XDDDD否则例如312，写成标准循环是321，明显改变了啊
%%%写出来之后更想膜大佬，不管是考场上A掉的zzh大佬还是机智证明的wq大佬OwO
最后，应该如何实现它？
我输出的1……n，每个数各成循环，1种情况
n与n-1循环：1种情况
n-1与n-2循环：1种情况
n-3与n-2循环：当n-3和n-2确定时，n与n-1包含上面2种情况
n-3与n-4循环：包含n,n-1,n-2的三种情况
eg：12345……1 升序原版
12354……1 换54
12435……1 换43
13245
13254(此处的45、54和前两项重复)……2 换32
21345
21354
21435(此处的345、354、435和前3项重复)……3 换21
1,1,2,3…看到了什么？fibonacci!
设f[i]为fibonacci数列的前i项和
当f[i-1]<k-1<f[i]，说明第n-i项和第n-i+1项被换了。
当k减去这个前缀和有剩余，说明后面还有项被换，继续用类似递归的思想消除k并标记被换位，直到k为0。
写完了撒花2333
#include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,jh[55],ans[55]; long long k,fb[55],sum[55]; int main() { scanf("%d%lld",&n,&k); if(k==1) { for(int i=1;i<n;i++) printf("%d ",i); printf("%d",n); return 0; } fb[1]=fb[2]=1; sum[0]=1; sum[1]=2,sum[2]=3; for(int i=3;i<=50;i++) { fb[i]=fb[i-1]+fb[i-2]; sum[i]=sum[i-1]+fb[i]; } for(int i=1;i<=50;i++) if(sum[i]>=k&&sum[i-1]<k) { jh[n-i]=1; jh[n-i+1]=1; k-=sum[i-1]; break; } while(k>0) { if(k==1) k--; if(k<=0) break; for(int i=1;i<=50;i++) if(sum[i]>=k&&sum[i-1]<k) { k-=sum[i-1]; jh[n-i+1]=1; jh[n-i]=1; break; } if(k==1) k--; } for(int i=1;i<=n;i++) ans[i]=i; for(int i=1;i<n;i++) if(jh[i]&&jh[i+1]) { swap(ans[i],ans[i+1]); jh[i]=jh[i+1]=0; } for(int i=1;i<n;i++) printf("%d ",ans[i]); printf("%d\n",ans[n]); return 0; }
题外话
第二个考试周期这么快又结束了。Day1Day2，惨不忍睹，暴力统统写挂正解想不出来；Day3Day4，开始联考，题目迷之水，暴力写得还行正解简直愚蠢地不像正解，不过两天的最后一题都很有意思；Day5，也就是今天，打得一般，不是太好但是也没有打挂，单纯地没想出来。经过了前两天的教训暴力打得更稳，后三天开始有一步步优化复杂度的想法，打正解不再只靠灵光一现。考试的过程中更冷静(我们要分步骤有秩序地拿分！)，全场的时间分配更合理。不足就是这些天改题做题都很慢，一方面是计算几何调不出来搜索实现不出来，另一方面也和自己还不够高效有关。要刷的题堆的很多，做题也有点急躁。暑假集训剩下的时间也不很多了，明天物奥的就要回来。集训了这么长时间，感觉不管是高考的生活还是高考的知识都忘了个一干二净，很不想回去学高考，好在过不了多久就是联赛集训了。感觉自己现在只有在敲题和想题的时候心里特别平静，别的时候都莫名焦虑，大概编程越来越成为生命的一部分了吧。溯洄从之，道阻且长；溯游从之，宛在水中央。
8.9联考题解