noip模拟测试12

时间:2022-12-17 10:42:27

T1:斐波那契

  呃,其实这题手玩一下就秒出了,可是我还是zz的没有AC

  先说说我怎么zz的,$10^{12}$是13位……我还以为是12位,然后表就打小了gg

  

  其实正解很easy,手玩一下就会发现,点x的父亲就是x减去比x小的第一个斐波那契数

  然后就简单了,因为斐波那契树的层数是小于$log x_{max}$的

  所以直接用一个数向上跳父亲,并且记录经过了哪些点,然后再用另一个数一边向上跳,一边查就完了

  (于是大佬们纷纷#include<set>,只有蒟蒻我手写哈希表)

  so,code

noip模拟测试12noip模拟测试12
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<vector>
 9 #define ll long long
10 using namespace std;
11 const int MAXN=300233,MAXD=2400;
12 const ll D=2333;
13 int m;
14 ll f[65],a,b;
15 struct hash_map {
16     int h[MAXD],nxt[MAXD],tot,stk[MAXD],tp;
17     ll val[MAXD];
18     hash_map() {
19         memset(h,0,sizeof(h));
20         memset(nxt,0,sizeof(nxt));
21         memset(val,0,sizeof(val));
22     }
23     void clear() {
24         tot=0;
25         while(tp) h[stk[tp--]]=0;
26     }
27     void insert(ll _v) {
28         int p=_v%D;
29         for(int i=h[p];i;i=nxt[i])
30             if(val[i]==_v) return;
31         if(!h[p]) stk[++tp]=p;
32         val[++tot]=_v;
33         nxt[tot]=h[p];
34         h[p]=tot;
35     }
36     bool find(ll _v) {
37         int p=_v%D;
38         for(int i=h[p];i;i=nxt[i])
39             if(val[i]==_v) return 1;
40         return 0;
41     }
42 }mp;
43 void first() {
44     f[0]=f[1]=1;
45     for(int i=2;i<=62;i++) f[i]=f[i-1]+f[i-2];
46 }
47 int main() {
48     first();
49     scanf("%d",&m);
50     for(int i=1;i<=m;i++) {
51         scanf("%lld%lld",&a,&b);
52         mp.clear();
53         mp.insert(a);
54         for(int j=62;j>=1;j--)
55             if(a>f[j]) {
56                 a-=f[j];
57                 mp.insert(a);
58             }
59         if(mp.find(b)) {
60             printf("%lld\n",b);
61             continue;
62         }
63         for(int j=62;j>=1;j--)
64             if(b>f[j]) {
65                 b-=f[j];
66                 if(mp.find(b)) {
67                     printf("%lld\n",b);
68                     break;
69                 }
70             }
71     }
72     return 0;
73 }
t1 Code

 

T2:数颜色
  考试时脑子被带修莫队填满了……
  详见 数颜色专题
 
  code
noip模拟测试12noip模拟测试12
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<vector>
 9 #define ll long long
10 using namespace std;
11 const int MAXN=300005;
12 int n,m,a[MAXN],ans;
13 vector<int> v[MAXN];
14 inline int R() {
15     int aa=0;char cc=getchar();
16     while(cc>'9'||cc<'0')cc=getchar();
17     while(cc>='0'&&cc<='9')aa=aa*10+cc-'0',cc=getchar();
18     return aa;
19 }
20 int main() {
21     scanf("%d%d",&n,&m);
22     for(int i=1;i<=n;i++) {
23         scanf("%d",&a[i]);
24         v[a[i]].push_back(i);
25     }
26     for(int i=1,op;i<=m;i++) {
27         op=R();
28         if(op==1) {
29             int l=R(),r=R(),c=R();
30             int al=lower_bound(v[c].begin(),v[c].end(),l)-v[c].begin();
31             int ar=upper_bound(v[c].begin(),v[c].end(),r)-v[c].begin();
32             printf("%d\n",ar-al);
33         } else {
34             int tmp=R();
35             if(a[tmp]!=a[tmp+1]) {
36                 int t1=lower_bound(v[a[tmp]].begin(),v[a[tmp]].end(),tmp)-v[a[tmp]].begin();
37                 int t2=lower_bound(v[a[tmp+1]].begin(),v[a[tmp+1]].end(),tmp+1)-v[a[tmp+1]].begin();
38                 ++v[a[tmp]][t1];
39                 --v[a[tmp+1]][t2];
40                 swap(a[tmp],a[tmp+1]);
41             }
42         }
43     }
44     return 0;
45 }
t2 Code

 


 

T3:分组

  看到时一脸懵比,脑子里只有贪心……

  那就贪心吧,只会写$k=1$的情况

  于是就要快速判断一群数分别加某个数是否能得到一个特定的值

  就想到这道题:小清新人渣的本愿

  于是用bitset来解决这个问题,复杂度 $n/32$,但考完后发现其实$\sqrt{n}$的暴力枚举更快……

  

  说说正解:

    case $k=1$:

      暴力扫一遍,如果能加入当前段就加入,否则就清空数组并分段

      判断能否加入直接暴力扫一遍值域内所有的平方数,看平方数减当前数的得数是否出现过

      因为要求字典序最小,所以贪心的倒着加入就完了

    case $k=2$:

      分析后会发现,如果将刚刚的情况看作是把一段数往一个桶里塞的话

      那么现在的操作就可以看作是把一段数往两个桶里塞,每个桶里的数不能冲突

      贪心的想,会发现如果出现一个与桶中的数冲突的数,就一定得将其塞到另一个桶里

      如果这个数和两个桶中的数都有冲突,那就必须得分段

      那怎么维护呢?

      用带扩展域的并查集啊

      即:1,3冲突,则将1 和 3',1’ 和 3 分别merge一起

        表示条件“有1”和“无3”在一个集合,“无1”和“有3”在一个集合

      若某一时刻出现了“有a”和"无a"在一个集合的情况,则需要新分一个段

      

      但这样还有一点问题,因为每个数有可能多次出现,所以会出现几种特殊情况:

        若数a满足$2*a=x^2$

        1.当a第二次出现时,若已经有和a冲突的数

         那两个桶中一个有a,另一个有和a冲突的数,那么新的a便无法加入桶中,于是需要再分一段

        2.当集合中没有与a冲突的数,但a出现了第三次,那么新的a便无法加入桶中,于是需要再分一段

        3.当插入其他数时,发现该数与a冲突,且a已经出现了两次,则无法加入该数,于是需要再分一段

      于是需要特判一下满足$2*a=x^2$的数

    然后像$k=1$的时候一样倒着贪心的加入就好了。

    

    特判比较多,需要思路清晰时食用

    so,code

noip模拟测试12noip模拟测试12
 1 #include<cstdio>
 2 #include<iostream>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<cstring>
 6 #include<cstdlib>
 7 #include<queue>
 8 #include<vector>
 9 #define ll long long
10 using namespace std;
11 const int MAXN=200000;
12 int n,k,a[MAXN],m,ans[MAXN],stk[MAXN],tp,mx;
13 int fa[MAXN*2],bstk[MAXN*2],btp,vis[MAXN*2];
14 bool spl[MAXN*2],bvis[MAXN*2];
15 void work1() {
16     for(int i=n;i>=1;i--) {
17         for(int j=2;j<=512;j++)
18             if(j*j>a[i]&&vis[j*j-a[i]]) {
19                 while(tp) vis[stk[tp--]]=0;
20                 ans[++m]=i;
21             }
22         if(!vis[a[i]]) stk[++tp]=a[i],vis[a[i]]=1;
23     }
24 }
25 int get(int x) {
26     if(!bvis[x]) bstk[++btp]=x,bvis[x]=1;
27     if(x==fa[x]) return x;
28     return fa[x]=get(fa[x]);
29 }
30 void merge(int x,int y) {
31     int fx=get(x),fy=get(y);
32     if(fx!=fy) fa[fx]=fy;
33 }
34 void work2() {
35     for(int i=1;i<=2*mx;i++) fa[i]=i;
36     for(int i=2;i<=512;i++)
37         if(!((i*i)&1)) spl[i*i/2]=1;
38     for(int i=n;i>=1;i--) {
39         for(int j=2;j<=512;j++) {
40             if(j*j>a[i]&&vis[j*j-a[i]]) {
41                 if(j*j==2*a[i]) continue;
42                 if(spl[j*j-a[i]]&&vis[j*j-a[i]]>=2) {
43                     merge(a[i],a[i]+mx);
44                     break;
45                 }
46                 merge(a[i],j*j-a[i]+mx);
47                 merge(a[i]+mx,j*j-a[i]);
48             }
49         }
50         if(spl[a[i]]&&vis[a[i]]) {
51             if(vis[a[i]]>=2) merge(a[i],a[i]+mx);
52             else for(int j=2;j<=512;j++)
53                     if(j*j>a[i]&&vis[j*j-a[i]]) {
54                         if(j*j==2*a[i]) continue;
55                         merge(a[i],a[i]+mx);
56                         break;
57                     }
58         }
59         if(get(a[i])==get(a[i]+mx)) {
60             ans[++m]=i;
61             while(tp) vis[stk[tp--]]=0;
62             while(btp) fa[bstk[btp]]=bstk[btp],bvis[bstk[btp]]=0,--btp;
63         }
64         if(!vis[a[i]]) stk[++tp]=a[i];
65         ++vis[a[i]];
66     }
67 }
68 int main() {
69     scanf("%d%d",&n,&k);
70     for(int i=1;i<=n;i++) scanf("%d",&a[i]),mx=max(mx,a[i]);
71     if(k==1) work1();
72     else work2();
73     printf("%d\n",m+1);
74     for(int i=m;i>=1;i--) printf("%d ",ans[i]);
75     printf("\n");
76     return 0;
77 }
t3 Code