2018年全国多校算法寒假训练营练习比赛（第五场）题解

- 日理万妓 2022-05-30 01:18 100阅读 0赞

比赛t题目链接:

https://www.nowcoder.com/acm/contest/77\#question

A .逆序数

思路:直接用分治法求逆序数即可，这里也可以用树状数组求，数据也不大。所以不用离散求处理下输入0即可。

附上两个不同版本的代码:

分治:

**\[cpp\]** [view plain][] [copy][view plain] [print][view plain][?][view plain]

1.  \#include <bits/stdc++.h>  
2.  using namespace std;  
3.  typedef long long ll;  
4.  int num\[100005\],c\[100005\];  
5.  ll ans ;  
6.  void margeHe(int S,int mid,int E)\{  
7.      int s=S,m = mid+1,cnt = s;  
8.      while(s<=mid&&m<=E)\{  
9.          if(num\[s\]<=num\[m\])\{  
10.             c\[cnt++\] = num\[s++\];  
11.         \}  
12.         else\{  
13.             c\[cnt++\] = num\[m++\];  
14.             ans+=mid-s+1;  
15.         \}  
16.     \}  
17.     while(s<=mid)\{  
18.         c\[cnt++\] = num\[s++\];  
19.     \}  
20.     while(m<=E)\{  
21.         c\[cnt++\] = num\[m++\];  
22.     \}  
23.     for(int i=S;i<=E;i++)\{  
24.         num\[i\] = c\[i\];  //合并过程排好序  
25.     \}  
26. \}  
27.   
28. void marge(int S,int E)\{  
29.     if(S>=E) return ;  
30.     int mid = (S+E)>>1;  
31.     marge(S,mid);  
32.     marge(mid+1,E);  
33.     margeHe(S,mid,E);  
34. \}  
35. int main()\{  
36.     int n;  
37.     cin>>n;  
38.     for(int i=1;i<=n;i++) cin>>num\[i\];  
39.     ans = 0;  
40.     marge(1,n);  
41.     cout<<ans<<endl;  
42.     return 0;  
43. \}

#include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int num[100005],c[100005];
    ll ans ;
    void margeHe(int S,int mid,int E){
        int s=S,m = mid+1,cnt = s;
        while(s<=mid&&m<=E){
            if(num[s]<=num[m]){
                c[cnt++] = num[s++];
            }
            else{
                c[cnt++] = num[m++];
                ans+=mid-s+1;
            }
        }
        while(s<=mid){
            c[cnt++] = num[s++];
        }
        while(m<=E){
            c[cnt++] = num[m++];
        }
        for(int i=S;i<=E;i++){
            num[i] = c[i];  //合并过程排好序
        }
    }
    
    void marge(int S,int E){
        if(S>=E) return ;
        int mid = (S+E)>>1;
        marge(S,mid);
        marge(mid+1,E);
        margeHe(S,mid,E);
    }
    int main(){
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) cin>>num[i];
        ans = 0;
        marge(1,n);
        cout<<ans<<endl;
        return 0;
    }

树状数组:

**\[cpp\]** [view plain][] [copy][view plain] [print][view plain][?][view plain]

1.  \#include <iostream>  
2.  \#include <cstring>  
3.  using namespace std;  
4.  \#define N 500005  
5.  typedef long long ll;  
6.  int c\[N\];  
7.  int n;  
8.  ll lowbit(ll i)  
9.  \{  
10.     return i&(-i);  
11. \}  
12. ll insert(ll i,ll x)  
13. \{  
14.     while(i<=n&&i!=0)\{  
15.         c\[i\]+=x;  
16.         i+=lowbit(i);  
17.     \}  
18.     return 0;  
19. \}  
20.    
21. ll getsum(ll i)  
22. \{  
23.     ll sum=0;  
24.     while(i>0)\{  
25.         sum+=c\[i\];  
26.         i-=lowbit(i);  
27.     \}  
28.     return sum;  
29. \}  
30.     
31. int main()  
32. \{  
33.     while(cin>>n)\{  
34.         ll ans=0;  
35.         memset(c,0,sizeof(c));  
36.         ll cnt = 0;  
37.         for(int i=1;i<=n;i++)\{  
38.             int a;  
39.             cin>>a;  
40.             insert(a,1);  
41.             if(a==0)\{  
42.                 ++cnt;  //注意处理0输入即可  
43.                 ans +=i-cnt;  
44.             \}  
45.             else  
46.                 ans+=i-(getsum(a)+cnt);//统计当前序列中大于a的元素的个数  
47.         \}  
48.         cout<<ans<<endl;  
49.     \}  
50.     return 0;  
51. \}

#include <iostream>
    #include <cstring>
    using namespace std;
    #define N 500005
    typedef long long ll;
    int c[N];
    int n;
    ll lowbit(ll i)
    {
        return i&(-i);
    }
    ll insert(ll i,ll x)
    {
        while(i<=n&&i!=0){
            c[i]+=x;
            i+=lowbit(i);
        }
        return 0;
    }
     
    ll getsum(ll i)
    {
        ll sum=0;
        while(i>0){
            sum+=c[i];
            i-=lowbit(i);
        }
        return sum;
    }
      
    int main()
    {
        while(cin>>n){
            ll ans=0;
            memset(c,0,sizeof(c));
            ll cnt = 0;
            for(int i=1;i<=n;i++){
                int a;
                cin>>a;
                insert(a,1);
                if(a==0){
                    ++cnt;  //注意处理0输入即可
                    ans +=i-cnt;
                }
                else
                    ans+=i-(getsum(a)+cnt);//统计当前序列中大于a的元素的个数
            }
            cout<<ans<<endl;
        }
        return 0;
    }

B.Big Water Problem

思路:裸的树状数组，裸的单点修改和区间查询（QAQ!!据说可以暴力？？？？

代码:

**\[cpp\]** [view plain][] [copy][view plain] [print][view plain][?][view plain]

1.  \#include <bits/stdc++.h>  
2.  using namespace std;  
3.  const int maxn = 5e5+11;  
4.  typedef long long ll;  
5.  int sum ;  
6.  int n,m;  
7.  ll tree\[maxn\];  
8.  int lowbit(int t)  
9.  \{  
10.     return t&(-t);  
11. \}  
12. void add(int x,int y)  
13. \{  
14.     for(int i=x;i<=n;i+=lowbit(i))  
15.         tree\[i\]+=y;  
16.   
17. \}  
18. ll getsum(int x)  
19. \{  
20.     ll ans=0;  
21.     for(int i=x;i>0;i-=lowbit(i))  
22.         ans+=tree\[i\];  
23.     return ans;  
24. \}  
25. ll getqujiansum(int x1,int x2)\{  
26.     return getsum(x2)-getsum(x1-1);  
27. \}  
28. int main()\{  
29.     int a;  
30.     cin>>n>>m;  
31.     for(int i=1;i<=n;i++)\{  
32.         cin>>a;  
33.         add(i,a);  
34.     \}  
35.     int x,y;  
36.     for(int i=0;i<m;i++)\{  
37.         cin>>a;  
38.         if(a==1)\{  
39.             cin>>x>>y;  
40.             add(x,y);  
41.         \}  
42.         if(a==2)\{  
43.             cin>>x>>y;  
44.             cout<<getqujiansum(x,y)<<endl;  
45.         \}  
46.     \}  
47.   
48.     return 0;  
49. \}

#include <bits/stdc++.h>
    using namespace std;
    const int maxn = 5e5+11;
    typedef long long ll;
    int sum ;
    int n,m;
    ll tree[maxn];
    int lowbit(int t)
    {
        return t&(-t);
    }
    void add(int x,int y)
    {
        for(int i=x;i<=n;i+=lowbit(i))
            tree[i]+=y;
    
    }
    ll getsum(int x)
    {
        ll ans=0;
        for(int i=x;i>0;i-=lowbit(i))
            ans+=tree[i];
        return ans;
    }
    ll getqujiansum(int x1,int x2){
        return getsum(x2)-getsum(x1-1);
    }
    int main(){
        int a;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>a;
            add(i,a);
        }
        int x,y;
        for(int i=0;i<m;i++){
            cin>>a;
            if(a==1){
                cin>>x>>y;
                add(x,y);
            }
            if(a==2){
                cin>>x>>y;
                cout<<getqujiansum(x,y)<<endl;
            }
        }
    
        return 0;
    }

C.字符串问题

思路:先预处理next数组,得到输入字符串的前后缀关系,并开另一数组记录关系，从next数组最后即串

的长度+1开始往回回溯看是否满足条件即可.（一拿题想多了。。。其实可能存在多个字串满足，我们根据

next数组就能找到其中一个即可。)。还是不明白的，输出next数组找找思路.

代码:

**\[cpp\]** [view plain][] [copy][view plain] [print][view plain][?][view plain]

1.  \#include <bits/stdc++.h>  
2.  using namespace std;  
3.  typedef long long int ll;  
4.  const int maxn = 1000010;  
5.  char s\[maxn\];  
6.  int nxt\[maxn\];  
7.  int mark\[maxn\];  
8.  void get\_next(int len)  
9.  \{  
10.     int i = 0, j = -1;  
11.     nxt\[0\] = -1;  
12.     while (i < len)  
13.     \{  
14.         if (j == -1 || s\[i\] == s\[j\])  
15.             nxt\[++i\] = ++j;  
16.         else j = nxt\[j\];  
17.     \}  
18.   
19. \}  
20. int main()  
21. \{  
22.     cin>>s;  
23.     int len = strlen(s);  
24.     memset(mark,0,sizeof(mark));  
25.     get\_next(len);  
26.     for(int i=0;i<len;i++)\{  
27.         mark\[nxt\[i\]\]++;  
28.     \}  
29.     int i = nxt\[len\];  
30.     bool flag = 1;  
31.     while (i)  
32.     \{  
33.         if (mark\[i\]) \{  
34.             for (int j = 0; j < i; j++)  
35.                 cout<<s\[j\];  
36.             cout<<endl;  
37.             flag = 0;  
38.             break;  
39.         \}  
40.         i = nxt\[i\];  
41.     \}  
42.     if(flag)  
43.         cout<<"Just a legend"<<endl;  
44.   
45. \}

#include <bits/stdc++.h>
    using namespace std;
    typedef long long int ll;
    const int maxn = 1000010;
    char s[maxn];
    int nxt[maxn];
    int mark[maxn];
    void get_next(int len)
    {
        int i = 0, j = -1;
        nxt[0] = -1;
        while (i < len)
        {
            if (j == -1 || s[i] == s[j])
                nxt[++i] = ++j;
            else j = nxt[j];
        }
    
    }
    int main()
    {
        cin>>s;
        int len = strlen(s);
        memset(mark,0,sizeof(mark));
        get_next(len);
        for(int i=0;i<len;i++){
            mark[nxt[i]]++;
        }
        int i = nxt[len];
        bool flag = 1;
        while (i)
        {
            if (mark[i]) {
                for (int j = 0; j < i; j++)
                    cout<<s[j];
                cout<<endl;
                flag = 0;
                break;
            }
            i = nxt[i];
        }
        if(flag)
            cout<<"Just a legend"<<endl;
    
    }

D.集合问题

小编太弱了，没做道这题,看了题解,菊苣用并查集...不过从后面读了下题，感觉能够用开两个vector+二分能做？？？过后补题试试..

E.情人节的电灯泡

思路:二维树状数组的单点修改，区间查询,直接上代码 (暴力居然能过，再也不相信数据水到这程度...）

**\[cpp\]** [view plain][] [copy][view plain] [print][view plain][?][view plain]

1.  \#include <bits/stdc++.h>  
2.  using namespace std;  
3.  int n,q;  
4.  int num\[1005\]\[1005\],tree\[1005\]\[1005\];  
5.  int lowbit(int t)\{  
6.      return t&(-t);  
7.  \}  
8.  void add(int x,int y,int val)\{  
9.      for(int i=x;i<=n;i+=lowbit(i))\{  
10.         for(int j=y;j<=n;j+=lowbit(j))\{  
11.             tree\[i\]\[j\] +=val;  
12.         \}  
13.     \}  
14.   
15. \}  
16. int getsum(int x,int y)\{  
17.     int sum = 0;  
18.     for(int i=x;i>0;i-=lowbit(i))\{  
19.         for(int j=y;j>0;j-=lowbit(j))\{  
20.             sum+=tree\[i\]\[j\];  
21.         \}  
22.     \}  
23.     return sum;  
24. \}  
25. int main()\{  
26.   
27.   
28.     int a,x,y,x1,x2,y1,y2;  
29.     cin>>n>>q;  
30.     for(int i=1;i<=n;i++)\{  
31.         for(int j=1;j<=n;j++)\{  
32.             cin>>num\[i\]\[j\];  
33.             if(num\[i\]\[j\])\{  
34.                 add(i,j,1);  
35.             \}  
36.         \}  
37.     \}  
38.   
39.     for(int i=1;i<=q;i++)\{  
40.         cin>>a;  
41.         if(a==1)\{  
42.             cin>>x>>y;  
43.             if(num\[x\]\[y\])\{  
44.                 add(x,y,-1);  
45.             \}else\{  
46.                 add(x,y,1);  
47.             \}  
48.             num\[x\]\[y\]^=1;  
49.         \}  
50.         if(a==2)\{  
51.             cin>>x1>>y1>>x2>>y2;  
52.             cout<<getsum(x2,y2)-getsum(x1-1,y2)-getsum(x2,y1-1)+getsum(x1-1,y1-1)<<endl;  
53.         \}  
54.     \}  
55.     return 0;  
56. \}

#include <bits/stdc++.h>
    using namespace std;
    int n,q;
    int num[1005][1005],tree[1005][1005];
    int lowbit(int t){
        return t&(-t);
    }
    void add(int x,int y,int val){
        for(int i=x;i<=n;i+=lowbit(i)){
            for(int j=y;j<=n;j+=lowbit(j)){
                tree[i][j] +=val;
            }
        }
    
    }
    int getsum(int x,int y){
        int sum = 0;
        for(int i=x;i>0;i-=lowbit(i)){
            for(int j=y;j>0;j-=lowbit(j)){
                sum+=tree[i][j];
            }
        }
        return sum;
    }
    int main(){
    
    
        int a,x,y,x1,x2,y1,y2;
        cin>>n>>q;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>num[i][j];
                if(num[i][j]){
                    add(i,j,1);
                }
            }
        }
    
        for(int i=1;i<=q;i++){
            cin>>a;
            if(a==1){
                cin>>x>>y;
                if(num[x][y]){
                    add(x,y,-1);
                }else{
                    add(x,y,1);
                }
                num[x][y]^=1;
            }
            if(a==2){
                cin>>x1>>y1>>x2>>y2;
                cout<<getsum(x2,y2)-getsum(x1-1,y2)-getsum(x2,y1-1)+getsum(x1-1,y1-1)<<endl;
            }
        }
        return 0;
    }

F .The Biggest Water Problem

签到题

**\[cpp\]** [view plain][] [copy][view plain] [print][view plain][?][view plain]

1.  \#include <bits/stdc++.h>  
2.  using namespace std;  
3.  const int maxn = 1e6+11;  
4.  int sum ;  
5.  int ji(int su)\{  
6.      sum = 0;  
7.      while(su)\{  
8.          int t = su%10;  
9.          su /=10;  
10.         sum+=t;  
11.     \}  
12.     if(sum<10) return sum;  
13.     else ji(sum);  
14.     return sum;  
15.   
16. \}  
17. int main()\{  
18.     int su;  
19.     cin>>su;  
20.     cout<<ji(su)<<endl;  
21.   
22.     return 0;  
23. \}

#include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e6+11;
    int sum ;
    int ji(int su){
        sum = 0;
        while(su){
            int t = su%10;
            su /=10;
            sum+=t;
        }
        if(sum<10) return sum;
        else ji(sum);
        return sum;
    
    }
    int main(){
        int su;
        cin>>su;
        cout<<ji(su)<<endl;
    
        return 0;
    }

G 送分啦-QAQ

思路:斐波那序博弈（不会博弈的，要好好了解博弈...

**\[cpp\]** [view plain][] [copy][view plain] [print][view plain][?][view plain]

1.  \#include <iostream>  
2.  \#include <stdio.h>  
3.  using namespace std;  
4.  typedef long long ll;  
5.  ll fib\[1000\];  
6.  ll ans;  
7.  void init()\{  
8.      fib\[0\] = 1;  
9.      fib\[1\] = 1;  
10.     for(int i=2;i<=1000;i++)\{  
11.         fib\[i\] = fib\[i-1\]+fib\[i-2\];  
12.     \}  
13. \}  
14.   
15.   
16. int main()  
17. \{  
18.     int n;  
19.     init();  
20.        
21.     cin>>n;  
22.     int i;  
23.     for(i=0;i<45;i++)\{  
24.         if(fib\[i\]==n) break;  
25.     \}  
26.     if(i<45)\{  
27.         cout<<"Sha"<<endl;  
28.     \}  
29.     else  
30.         cout<<"Xian"<<endl;  
31.   
32.     return 0;  
33. \}

#include <iostream>
    #include <stdio.h>
    using namespace std;
    typedef long long ll;
    ll fib[1000];
    ll ans;
    void init(){
        fib[0] = 1;
        fib[1] = 1;
        for(int i=2;i<=1000;i++){
            fib[i] = fib[i-1]+fib[i-2];
        }
    }
    
    
    int main()
    {
        int n;
        init();
         
        cin>>n;
        int i;
        for(i=0;i<45;i++){
            if(fib[i]==n) break;
        }
        if(i<45){
            cout<<"Sha"<<endl;
        }
        else
            cout<<"Xian"<<endl;
    
        return 0;
    }

H Tree Recovery

思路: 裸的线段树 (据说 暴力优化下也能过，哎 感觉最后一场暴力场?吐槽小数据。。。

**\[cpp\]** [view plain][] [copy][view plain] [print][view plain][?][view plain]

1.  \#include <bits/stdc++.h>  
2.  using namespace std;  
3.  int n,q;  
4.  \#define maxn 100007  
5.  int Sum\[maxn<<2\],Add\[maxn<<2\];  
6.  int A\[maxn\];  
7.     
8.  void PushUp(int rt)\{Sum\[rt\]=Sum\[rt<<1\]+Sum\[rt<<1|1\];\}  
9.     
10. void PushDown(int rt,int ln,int rn)\{  //下推标记  
11.        
12.     if(Add\[rt\])\{  
13.            
14.         Add\[rt<<1\]+=Add\[rt\];  
15.         Add\[rt<<1|1\]+=Add\[rt\];  
16.            
17.         Sum\[rt<<1\]+=Add\[rt\]\*ln;  
18.         Sum\[rt<<1|1\]+=Add\[rt\]\*rn;  
19.           
20.         Add\[rt\]=0;  
21.     \}  
22. \}  
23. void Build(int l,int r,int rt)\{     
24.     if(l==r) \{   
25.         Sum\[rt\]=A\[l\];   
26.         return;  
27.     \}  
28.     int m=(l+r)>>1;  
29.     
30.     Build(l,m,rt<<1);  
31.     Build(m+1,r,rt<<1|1);  
32.       
33.     PushUp(rt);  
34. \}  
35. void Update(int L,int R,int C,int l,int r,int rt)\{     
36.     if(L <= l && r <= R)\{   
37.         Sum\[rt\]+=C\*(r-l+1);   
38.         Add\[rt\]+=C;    
39.         return ;  
40.     \}  
41.     int m=(l+r)>>1;  
42.     PushDown(rt,m-l+1,r-m);   
43.        
44.     if(L <= m) Update(L,R,C,l,m,rt<<1);  
45.     if(R >  m) Update(L,R,C,m+1,r,rt<<1|1);  
46.     PushUp(rt);   
47. \}  
48.   
49. int Query(int L,int R,int l,int r,int rt)\{     
50.     if(L <= l && r <= R)\{  
51.          
52.         return Sum\[rt\];  
53.     \}  
54.     int m=(l+r)>>1;  
55.       
56.     PushDown(rt,m-l+1,r-m);  
57.   
58.        
59.     int ANS=0;  
60.     if(L <= m) ANS+=Query(L,R,l,m,rt<<1);  
61.     if(R >  m) ANS+=Query(L,R,m+1,r,rt<<1|1);  
62.     return ANS;  
63. \}  
64. int main()\{  
65.   
66.   
67.     cin>>n>>q;  
68.     for(int i=1;i<=n;i++)\{  
69.         cin>>A\[i\];  
70.     \}  
71.     Build(1,n,1);  
72.     int x,y,ad;  
73.     char a;  
74.     for(int i=1;i<=q;i++)\{  
75.         cin>>a;  
76.         if(a=='Q')\{  
77.             cin>>x>>y;  
78.             cout<<Query(x,y,1,n,1)<<endl;  
79.         \}  
80.         if(a=='C')\{  
81.             cin>>x>>y>>ad;  
82.             Update(x,y,ad,1,n,1);  
83.         \}  
84.     \}  
85.     return 0;  
86. \}

[view plain]: http://csdnimg.cn/release/phoenix/#