[考试反思]0508省选模拟91:小雨

[考试反思]0508省选模拟91:小雨

[考试反思]0508省选模拟91:小雨

持续阴雨天气有一定状态加持。

屁嘞。三暴力说什么呢

$T1$的$70$分暴力如果不想复杂了就很好做(头脑简单是好事)

正解是个四维偏序,想倒不难想,但是写个锤子啊(然而牛神的确写出来了。。)

$T2$的话刚开始想 偏了丝毫头绪没有。

后来发现用一些小套路的话$O(n^2)$其实没有那么难想(二进制逐位考虑和字典序逐位考虑哪个不套路了)

然后其实正解已经想到了但是证明很模糊。剩余时间不多于是就去保$50$了

$T3$写的其实是$50$的算法。但是不可避免的炸精了。不可避免。那就算了。

总体还是不错的。

 

T1:最长公共子序列

大意:求$4$个串的$LCS$。保证前三个串中,每个串里相同元素至多出现$2$次。$n \le 10^4$

对于部分分:四个串都是排列。

做法比较简单:求出排列的逆数组$ia,ib,ic,id$。我们从$1$到$n$枚举$d$序列中的元素。

那么$j$可以转移到$i$的条件就是$j<i,ia[d[j]]<ia[d[i]],ib[d[j]]<ib[d[i]],ic[d[j]]<ic[d[i]]$

这个可以直接做$O(n^2)$。

然后当不再是排列的时候,因为前三个串每个数可能有$2$次,那么$ia,ib,ic$可能有两个元素。

所以对于一个$d[i]$可以拆成$2^3$个四元组,然后做四维偏序问题。

要么$dcq$套$cdq$。要么$cdq$最内存树状数组换为二维的。

注意到这里的转移要求的是严格小于而不是小于等于,所以对于每次分治区间找中点的时候。

需要把中点移动到两侧不相等的位置。总复杂度是$O(nlog^3n)$

[考试反思]0508省选模拟91:小雨
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define S 10001
 4 int dp[S<<3],n,sc;short t[S][S];
 5 vector<int>ia[S],ib[S],ic[S];
 6 struct st{int a,b,c,d,o;}s[S<<3],R[S<<3];
 7 bool cmp(st x,st y){return x.a==y.a?x.o<y.o:x.a<y.a;}
 8 void add(int x,int r,short w){for(;x<=n;x+=x&-x)for(int y=r;y<=n;y+=y&-y)t[x][y]=max(t[x][y],w);}
 9 int ask(int x,int r,short a=0){for(;x;x^=x&-x)for(int y=r;y;y^=y&-y)a=max(t[x][y],a);return a;}
10 void clear(int x,int r){for(;x<=n;x+=x&-x)for(int y=r;y<=n;y+=y&-y)t[x][y]=0;}
11 void CDQ(int l,int r){
12     if(s[l].d==s[r].d)return;
13     int md=l+r>>1;
14     if(s[l].d!=s[md].d&&l<md)while(s[md].d==s[md-1].d)--md;
15     else{while(s[md].d==s[md+1].d)++md;++md;}
16     CDQ(l,md-1);
17     for(int i=l;i<=r;++i)R[i]=s[i];
18     sort(R+l,R+md,cmp); sort(R+md,R+r+1,cmp);
19     int p1=l,p2=md;
20     while(p2<=r)
21         if(p1<md&&R[p1].a<R[p2].a)add(R[p1].b,R[p1].c,dp[R[p1].o]),p1++;
22         else dp[R[p2].o]=max(dp[R[p2].o],ask(R[p2].b-1,R[p2].c-1)+1),p2++;
23     for(int i=l;i<p1;++i)clear(R[i].b,R[i].c);
24     CDQ(md,r);
25 }
26 int main(){
27     scanf("%d",&n);
28     for(int i=1,a;i<=n;++i)scanf("%d",&a),ia[a].push_back(i);
29     for(int i=1,b;i<=n;++i)scanf("%d",&b),ib[b].push_back(i);
30     for(int i=1,c;i<=n;++i)scanf("%d",&c),ic[c].push_back(i);
31     for(int i=1,d;i<=n;++i){
32         scanf("%d",&d);
33         for(int a=0;a<ia[d].size();++a)for(int b=0;b<ib[d].size();++b)for(int c=0;c<ic[d].size();++c)
34             dp[++sc]=1,s[sc]=(st){ia[d][a],ib[d][b],ic[d][c],i,sc};
35     }
36     CDQ(1,sc);
37     for(int i=1;i<=sc;++i)dp[0]=max(dp[0],dp[i]);
38     printf("%d\n",dp[0]);
39 }
View Code

 

T2:排列

大意:给定$n$个元素$x_i$,构造数组$p$,最小化$\max\limits_{i=1}^{n-1} (x_{p_i} \ xor \  x_{p_{i+1}})$。$n \le 3 c\times 10^5$

首先,因为是邻位异或,所以我们逐位考虑。

如果所有数字在某一位上都是$1$,那么把它们同时变成$0$没有影响。

这样之后,取出最高位,一定有一些数字是$1$有一些数字是$0$。

不妨称这一位上是$1$的数为大数。反之成为小数。

我们先不考虑字典序,我们只尝试找到最小的ans$值。

那么可以发现一种解,满足所有大数相邻,所有小数相邻,然后中间只有一个大数和一个小数相邻。

大数之间的异或值在最高位上一定是$0$,小数也是。只有大数和小数相邻的部分是$1$

所以我们只在意大小相邻的情况。问题转变为:选出一个大数和一个小数,最小化异或和。直接$01trie$解决。

现在我们得到了$ans$值,然后相邻两个数 要么属于同一组,要么异或和恰好为$ans$

现在再来考虑字典序。那肯定就是逐位试填,看剩余数是否合法。

具体检验的话,当前填下的数为$x$,假设它属于小组,那么接下来还有合法填法当且仅当满足三者之一:

  • 大组为空
  • 小组为空,且存在$x \ xor \ ans$(称之为$x$的配对元素)
  • 去掉元素$x$后,依然存在配对关系

开桶维护每种值剩余个数。全局变量记录剩余配对数。可以做到$O(n^2)$或$O(n^2log\ n)$

可以发现在上面这三条的约束下你下一位的最优决策只有这几种:

  • 走到另一组中的配对元素
  • 走到本组下标最小的数
  • 走到本组下标次小的数

如果要走到对面组那只有第一种选择。

否则如果要走到本组,你肯定想走到下标最小的。

为什么还要考虑次小的呢?因为有可能剩下的元素中只有一个配对关系,就是下标最小的那个。

所以为了以后还能换组,你现在必须先把当前组走完,最后再去走下标最小的才能合法。

所以说这样复杂度就是$O(nlogn)$之类的了。多拿一些$vector/set$维护每个值出现下标的最小值就行。

[考试反思]0508省选模拟91:小雨
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 struct hash_map{
 4     #define _ 10000007
 5     int fir[_],l[_],to[_],v[_],ec;
 6     int&operator[](int x){int r=x%_;
 7         for(int i=fir[r];i;i=l[i])if(to[i]==x)return v[i];
 8         l[++ec]=fir[r];fir[r]=ec;to[ec]=x;return v[ec];
 9     }
10 }M,R;
11 #define S 300005
12 int a[S],n,tc[2][S<<5],rt,pc,w=1<<30,al[S],A=(1<<30)-1,mx,c[2],lst,ord,v[5],vc;long long mt;
13 void insert(int&p,int x,int al){
14     if(!p)p=++pc;if(al==-1)return;
15     insert(tc[x>>al&1][p],x,al-1);
16 }
17 int ask(int p,int x,int al){
18     if(al==-1)return 0;
19     return tc[x>>al&1][p]?ask(tc[x>>al&1][p],x,al-1):ask(tc[x>>al&1^1][p],x,al-1)|1<<al;
20 }
21 set<int>s[2],ss[S];
22 int b(int x){return x&mx?1:0;}
23 void del(int x){printf("%d ",x);ss[R[a[x]]].erase(x);s[b(a[x])].erase(x);lst=a[x];}
24 bool chk(int x){return mt||(!c[b(x)^1]||(!c[b(x)]&&M[x^w]));}
25 int main(){
26     scanf("%d",&n);
27     for(int i=1;i<=n;++i)scanf("%d",&a[i]),A&=a[i];
28     for(int i=1;i<=n;++i)a[i]^=A,mx=max(mx,a[i]),M[a[i]]++,R[a[i]]=++ord;
29     while(mx!=(mx&-mx))mx^=mx&-mx;
30     for(int i=1;i<=n;++i)if(a[i]&mx)insert(rt,a[i],30);
31     for(int i=1;i<=n;++i)if(!(a[i]&mx))w=min(w,ask(rt,a[i],30));
32     for(int i=1;i<=n;++i)if(a[i]&mx)mt+=M[a[i]^w],s[1].insert(i),c[1]++;
33         else c[0]++,s[0].insert(i);
34     for(int i=1;i<=n;++i)ss[R[a[i]]].insert(i);
35     for(int i=1;i<=n;++i){
36         int x=a[i]; M[x]--;c[b(x)]--;mt-=M[x^w];
37         if(chk(x)){del(i);break;}
38         M[x]++;c[b(x)]++;mt+=M[x^w];
39     }
40     for(int i=2;i<=n;++i){
41         vc=0;
42         if(s[b(lst)].size())v[++vc]=*s[b(lst)].begin();
43         if(s[b(lst)].size()>1)v[++vc]=*(++s[b(lst)].begin());
44         if(M[w^lst])v[++vc]=*ss[R[w^lst]].begin();
45         sort(v+1,v+1+vc);
46         for(int j=1;j<=vc;++j){
47             int x=a[v[j]]; if((x^lst)>w)continue;
48             M[x]--;c[b(x)]--;mt-=M[x^w];
49             if(chk(x)){del(v[j]);break;}
50             M[x]++;c[b(x)]++;mt+=M[x^w];
51         }
52     }
53 }
View Code

 

T3:加农炮

大意:求$n \times m$点阵中,倾斜角第$k$小的点的坐标(并列者按坐标大小排序)。多测。$n,m \le 10^6,T \le 10^4$

首先一个暴力的思路是,我们可以二分这个倾斜角,就能找到第$k$个点在哪条直线上。

如果能知道这条直线的解析式(也就是斜率,但要求分数形式不能是小数),那么就可以轻松回答点的坐标。

所以我们有两个问题,一个是怎么求二分一个斜率后,这条直线上方有多少个点,另一个是要解决分数问题。

并不会针对分数的二分,这时候伟大的数据结构$Stern-Brocot\ Tree$出现了。

原理大概是这样的,最开始我们有一个分数集合$\{ \frac{0}{1},\frac{1}{0} \}$。

然后每一轮,我们对于集合中相邻的两个元素$\frac{a}{b},\frac{c}{d}$,我们把$\frac{a+c}{b+d}$插入在它们之间。

可以证明,这样会形成所有的分数。当然这个树也是无限的。

实现的话,假象你有一棵树,然后调用函数$build(a,b,c,d)$分别表示$\frac{a}{b},\frac{c}{d}$

那么就会形成一个新的分数$\frac{a+c}{b+d}$。然后再递归的调用$build(a,b,a+c,b+d),build(a+c,b+d,c,d)$

然后我们要解决二分分数的问题,于是只要在这棵树上二分就可以啦。

但是仔细一想却不太对劲,树上二分是$O(log)$的?平时见过的是线段树二分。

之所以复杂度是$O(log)$的,是因为线段树的深度是$O(log)$的,你一定会递归到叶节点的。

在$SB$树上就不能这么猖狂了。因为例如$\frac{1}{1000000}$这个分数的深度就是$1000000$。你要是这么二分会T$掉。

所以我们可以采取更神奇的方法:每次去二分沿着当前方向走几步。

这样最大二分次数也就是左一下右一下了,每次转弯至少翻倍,所以一共二分$log$次,总共需要的$check$次数是$O(log^2)$的。

现在我们差的是一个低复杂度的$check$

暴力的话,我们可以枚举每个横坐标,然后判断这个坐标上有多少个点在线之下。假如斜率是$\frac{p}{q}$

那么点的个数就是$\sum\limits_{i=0}^{n-1} \lfloor \frac{ip}{q} \rfloor$

一个经典的类欧几里得形式,我们来推推式子吧,首先把问题转化为一般形式:

(为了方便,下面所有除法默认向下取整)

求$F(a,b,c,n)=\sum\limits_{i=0}^{n} \frac{ai+b}{c}$

首先比较简单的是$\frac{ai+b}{c} = \frac{a}{c} i + \frac{b}{c} + \frac{(a \mod c \times i + b \mod c}{c}$

这样前两项就可以提出来了,我们得到$F(a,b,c,n)=F(a \mod c,b \mod c,c,n) + \frac{n(n+1)}{2} \frac{a}{c}  + n \frac{b}{c}$

这样接下来我们就只需要考虑$a,b <c$

$F(a,b,c)=\sum\limits_{i=0}^{n} \frac{ai+b}{c}$

$=\sum\limits_{i=0}^{n} \sum\limits_{d=1}^{\frac{an+b}{c}} [\frac{ai+b}{c} \ge d ] $

$=\sum\limits_{d=0}^{\frac{an+b}{c}-1} \sum\limits_{i=0}^{n} [\frac{ai+b}{c} \ge d+1 ] $

$=\sum\limits_{d=0}^{\frac{an+b}{c}-1} \sum\limits_{i=0}^{n} [ai \ge dc+c-b ] $

$=\sum\limits_{d=0}^{\frac{an+b}{c}-1} \sum\limits_{i=0}^{n} [ai > dc+c-b+1 ] $

$=\sum\limits_{d=0}^{\frac{an+b}{c}-1} \sum\limits_{i=0}^{n} [i > \frac{dc+c-b+1}{a} ] $

$=\sum\limits_{d=0}^{\frac{an+b}{c}-1} (n+1 - \sum\limits_{i=0}^{n} [i \le \frac{dc+c-b+1}{a} ] )$

$= (n+1) \frac{an+b}{c} - F(c,c-b-1,a,\frac{an+b}{c} +1 )$

递归求解。复杂度与$gcd$类似。故本题总复杂度是$O(Tlog^3n)$

[考试反思]0508省选模拟91:小雨
 1 #include<cstdio>
 2 #define ll long long
 3 ll min(ll x,ll y){return x<y?x:y;}
 4 ll _Euler(ll a,ll b,ll c,ll n){
 5     if(!a)return b/c*(n+1);
 6     if(b>=c||a>=c)return a/c*n*(n+1)/2+b/c*(n+1)+_Euler(a%c,b%c,c,n);
 7     return (a*n+b)/c*n-_Euler(c,c-b-1,a,(a*n+b)/c-1);
 8 }
 9 ll cal(ll n,ll m,ll fz,ll fm){
10     if(!fz)return 0; if(!fm)return n*m-n;
11     if(fz*(m-1)<=fm*(n-1))return _Euler(fz,fz,fm,m-2)+m-1-min((m-1)/fm,(n-1)/fz);
12     return n*m-cal(m,n,fm,fz)-1-min((m-1)/fm,(n-1)/fz);
13 }
14 int main(){int t;scanf("%d",&t);while(t--){
15     ll n,m,k;scanf("%lld%lld%lld",&n,&m,&k); k--;
16     if(k>=n*m-n){printf("%lld 1\n",k-n*m+n+2);continue;}
17     ll fz1=0,fm1=1,fz2=1,fm2=0,l,r,md,inf=1e9;
18     while(1){
19         l=-1;r=min(fm2?(m-1-fm1)/fm2:inf,fz2?(n-1-fz1)/fz2:inf)+1;
20         if(r==1)break;
21         while(md=l+r>>1,r-l>1)if(cal(n,m,fz1+md*fz2,fm1+md*fm2)<=k)l=md;else r=md;
22         fz1+=l*fz2;fm1+=l*fm2;
23         l=-1;r=min(fm1?(m-1-fm2)/fm1:inf,fz1?(n-1-fz2)/fz1:inf)+1;
24         if(r==1)break;
25         while(md=l+r>>1,r-l>1)if(cal(n,m,fz2+md*fz1,fm2+md*fm1)>k)l=md;else r=md;
26         fz2+=l*fz1;fm2+=l*fm1;
27     }k-=cal(n,m,fz1,fm1)-1;printf("%lld %lld\n",k*fz1+1,k*fm1+1);
28 }}
View Code

 

 

 

 

 

$=\sum\limits_{i=0}^{n} \sum\limits_{d=1}^{\frac{an+b}{c}} [\frac{ai+b}{c} \ge d ] $

上一篇:leetcode [91]Decode Ways


下一篇:Python学习心得2:求平均值