08-03 NOIP模拟测试12

时间:2022-12-17 09:15:25

最近实在是太浪了

A. 斐波那契(fibonacci)

不一会还是发现了很多性质的,但是我考虑的越多,脑子越不知道往哪想,一直没有找到切入点(把自己搞懵比)。然后打了个模拟向上标记只有50分,开long long只有60分。

实际上从题意上就能找到突破口,既然要找lca,那么我们只要找到儿子与父亲的节点编号关系,用最裸的向上标记,就可以不断的从儿子向上翻,最多60层,可以不处理倍增数组(实际上是空间开不起)。

然后考虑这个父子关系,其实我在暴力建图的时候tmd也发现了,但我并没有再想用它做点什么。第i月出生的第j个兔子$num=fib[i-1]+j$,同时$1 \leq j \leq fib[i-2]$,非常好的一点在于j就是它的父亲,移项得j=num-fib[i-1],然后我们就有了从儿子找到父亲的方法。$\Theta (60^2m)$ 有点极限。

只要找到第一个小于num的fib,满足单调性,直接二分。$\Theta (60log60 m)$

然后我们就省掉了建图的空间与时间,愉快地拿到了100分的好成绩(手舞足蹈.gif)。

08-03 NOIP模拟测试1208-03 NOIP模拟测试12
 1 #include<cstdio>
 2 #include<cmath>
 3 #include<algorithm>
 4 #define ll long long
 5 #define reg register
 6 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
 7 using namespace std;
 8 ll read();
 9 int m;
10 ll fib[66];
11 inline ll ef(ll x)
12 {
13     int l=1,r=62,mid;
14     while(l<r)
15     {
16         mid=(l+r)>>1;
17         if(fib[mid]>=x) r=mid;
18         else l=mid+1;
19     }
20     return fib[l-1];
21 }
22 int main()
23 {
24 //    freopen("data.in","r",stdin);
25     m=read();
26     ll x,y;
27     fib[0]=fib[1]=1;
28     F(i,2,62) fib[i]=fib[i-1]+fib[i-2];
29     F(i,1,m)
30     {
31         x=read(); y=read();
32         while(x!=y)
33         {
34             if(x>y) x^=y^=x^=y;
35             y-=ef(y);
36         }
37         printf("%lld\n",x);
38     }
39     return 0;
40 }
41 ll read()
42 {
43     ll x=0;
44     char tc=getchar();
45     while(tc<'0'||tc>'9') tc=getchar();
46     while(tc>='0'&&tc<='9') x=x*10+tc-48,tc=getchar();
47     return x;
48 }
View Code

少开long long居然会TLE唔

B. 数颜色

我可能是高级数据结构学傻了。。。

考试的时候一看,这不莫队吗?还是带修的?可我不会啊!

然后还是自己YY了一个以每个修改为界限两边sort询问的TLE莫队,当时打完就觉得这板比T飞了,最坏情况是询问-修改-询问-修改-询问-修改-询问-修改然后死了,只有30分。

实际上能得70的算法:树套树(树状数组套主席树)(lnc),真正的带修莫队(wd),分块(whs)  再加上两个特殊性质 90分到(别人)手

100%算法:

算法一:vector 聪明人算法(sdfz_dky)

查询:对每个颜色开vector,由于元素的个数一定,不会爆内存。col[i][k],元素是排名第(k+1)个i颜色的兔子所在原序列的位置,维护col[i]有序,然后就可以二分做差得到答案了。

修改:如果不是相邻位置的颜色交换,算法一就失效了。因为是相邻位置,交换后它们相对于其他位置的相对大小都是不变的。结合算法一,就是我只要在col[a[x]]和col[a[x+1]]中二分找到x x+1位置所对应的col[]下标,然后交换他们的位置,发现没有改变col[]单调性,从而省去了nlogn的内部复杂度,完成了交换。

然后就拿到了75分的好成绩?

少了特判:如果a[x]==a[x+1]那么就不能修改,会破坏单调性。

算法二:主席树(pa)

发现每次修改只会改变两棵主席树(快忘了怎么写了,复习!)。然后就暴改这两棵树,常规查询即可。

08-03 NOIP模拟测试1208-03 NOIP模拟测试12
 1 #include<cstdio>
 2 #include<vector>
 3 #include<algorithm>
 4 #define reg register
 5 #define F(i,a,b) for(register int (i)=(a);(i)<=(b);++(i))
 6 using namespace std;
 7 int read();
 8 const int N=300005;
 9 int n,m;
10 int a[N];
11 vector<int> col[N];
12 int main()
13 {
14     n=read(); m=read();
15     F(i,1,n)
16     {
17         a[i]=read();
18         col[a[i]].push_back(i);
19     }
20     int opt,l,r,c;
21     F(i,1,m)
22     {
23         opt=read();
24         if(opt==1)
25         {
26             l=read();
27             r=read();
28             c=read();
29             int sum1=upper_bound(col[c].begin(),col[c].end(),l-1)-col[c].begin()-1;
30             int sum2=upper_bound(col[c].begin(),col[c].end(),r)-col[c].begin()-1;
31             printf("%d\n",sum2-sum1);
32         }
33         else
34         {
35             c=read();
36             if(a[c]==a[c+1]) continue;
37             int x1=lower_bound(col[a[c]].begin(),col[a[c]].end(),c)-col[a[c]].begin();
38             int x2=lower_bound(col[a[c+1]].begin(),col[a[c+1]].end(),c+1)-col[a[c+1]].begin();
39             col[a[c]][x1]=c+1;
40             col[a[c+1]][x2]=c;
41             swap(a[c],a[c+1]);
42         }
43     }
44     return 0;
45 }
46 int read()
47 {
48     int x=0;
49     char tc=getchar();
50     while(tc<'0'||tc>'9') tc=getchar();
51     while(tc>='0'&&tc<='9') x=x*10+tc-48,tc=getchar();
52     return x;
53 }
View Code

 

 

C. 分组

考试的时候想到了k==1的 $ \Theta (n^2) $ 贪心。就是倒序扫描直到出现矛盾开组。

常见的疑惑是 倒序更新最先保证的后面的字典序最小,但前面的答案对答案影响最大,后面的优先更新可能会导致前面不优。

实际上贪心是正确的:后面靠前,只会让前面原本不靠前的左端点到右端点之间的矛盾减少,所以左端点一定不会向后。换言之,答案不会更坏。

然后还是会T掉3个大点。

判断式:$ a+b ? x^2 $ 原来我们枚举b,验证x,但是b的数量多。我们可以转而枚举x,这样我们最多只有512的枚举量,然后用x^2-a看b是否出现过

未完。。。。