9.5-9.8

这周主要是复习一下…发现很多东西都不记得了orz

递归、分治

主要写了点板子题目 典型的逆序对 归并排序代码改的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<cstdio>
#include<iostream>
using namespace std;
int a[500005],b[500005];
long long n,cnt;
void add(int l,int r)
{
    int mid=(l+r)/2;
    int p=l,q=mid+1;
    for(int i=l;i<=r;i++)
    {
        if((q>r)||(p<=mid&&a[p]<=a[q]))
        b[i]=a[p++];
        else 
        {
            cnt+=mid-p+1;//多这一行代码 
            b[i]=a[q++];
        }
    }
    for(int i=l;i<=r;i++)
    a[i]=b[i];
}
void merg(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)/2;
    merg(l,mid);
    merg(mid+1,r);
    add(l,r);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    merg(0,n-1);
    cout<<cnt<<endl;
 }
其实好像感觉之前也写过…sort过的 记一个快读板子（卡了好几次在这）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
兔子的逆序对

大量读入需要快读板子 因为反转操作实际是将逆序对变成正序对 正序对变成逆序对 因为每交换一次就改变一次逆序对对数的奇偶性 所以只关注交换的次数就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<iostream>
#define int long long
using namespace std;
const int N=100005;
int a[N],b[N];
long long n,cnt,cnt1,cnt2,t,f;
inline int read()
{
    char c=getchar();int f=1;
    int x=0;
    while (c<'0'||c>'9')
      {
      if (c=='-') f=-1;
      c=getchar();
      }
    while (c>='0'&&c<='9')
      {
          x=(x<<1)+(x<<3)+(c^48);
          c=getchar();
      }
    return x*f;
}
void add(int l,int r)
{
    int mid=(l+r)/2;
    int p=l,q=mid+1;
    for(int i=l;i<=r;i++)
    {
        if((q>r)||(p<=mid&&a[p]<=a[q]))
        b[i]=a[p++];
        else 
        {
            cnt+=mid-p+1;
            b[i]=a[q++];
        }
    }
    for(int i=l;i<=r;i++)
    a[i]=b[i];
}
void merg(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)/2;
    merg(l,mid);
    merg(mid+1,r);
    add(l,r);
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    scanf("%lld",&t);
    merg(1,n);
    if(cnt%2) f=1;
    else f=0;
    while(t--)
    {
        int a,b;
        scanf("%lld%lld",&a,&b);
        int d=(b-a)*(b-a+1)/2;
        if(d%2)
        {
            f^=1;
        }
        if(f) printf("dislike\n");
        else printf("like\n");
    }
 }
快排板子 求第k大的数字
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
int a[100];
int n;
void quick_sort(int l,int r)
{
    int mid=(l+r)/2;
    int i=l,j=r;
    int x=a[mid];//store it
    while(a[i]<x) i++;
    while(a[j]>x) j--;
    while(i<=j)
    {
        swap(a[i],a[j]);
        i++;j--;
    }
    if(l<j) quick_sort(l,j);//如果是求第k大的数 改个这里 抛弃另一半
    if(i<r) quick_sort(i,r);
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    quick_sort(0,n-1);
    for(int i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
}
一些递归的水题
更相减损术

实际上就是欧拉公式 遥远的数论记忆、、、

gcd(a,b)=gcd(a,a%b)/gcd(a,a-b) 证明很简单

1
2
3
4
5
int gcd(int a,int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
汉诺塔问题

嗯…感觉也是个规律问题 求解的时候牵涉了一点点高中数列的求通项

由A->C:

(1)以C盘为中介，从A杆将1至n-1号盘移至B杆；

(2)将A杆中剩下的第n号盘移至C杆；

(3)以A杆为中介；从B杆将1至n-1号盘移至C杆。

f(n)=2*f(n-1)+1;

1
2
3
4
5
6
7
8
void hanoi(int n, char a, char b, char c) 
{
    if (n == 0)
        return;
    hanoi(n - 1, a, c, b);//将n-1个盘子由A经过C移动到B
    printf ("step %d: move %d from %c->%c\n", cnt++, n, a, c);
    hanoi(n - 1, b, a, c);//剩下的n-1盘子，由B经过A移动到C
}

有的题目会有一些附加条件 要自己重新算一下 感觉主要是求通项的问题 写代码直接写结论就可以了

other

还有一些很简单的递归就不写了 一直觉得递归很难理解、、、说是将递归当成一把钥匙开一把锁然后一直到最里面那把钥匙（） 主要是思想问题 很需要理解（笨人落泪）

补了几道cf

我有罪 我没及时补题 想起来有一些比赛的时候没写出来的C

Color the Picture

一个贪心问题 就是要保证颜色一定能涂相连的两行/两行以上 不能出现只有一行剩下的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
#define int long long
using namespace std;
int t,n,m,k;
int a[100005];
bool solve(int m,int n,int k)
{
    int ans=0;
    for(int i=0;i<k;i++)
    {
        if(a[i]/n>=2)
        {
            if((m-(ans+a[i]/n))==1)
            {
                if(a[i]/n>2) ans+=(a[i]/n-1);
            }
            else ans+=a[i]/n;
        }
    }
    if(ans>=m) return true;
    return false;
}
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>k;
        for(int i=0;i<k;i++)
        {
            cin>>a[i];
        }
        sort(a,a+k);
        if(solve(n,m,k)||solve(m,n,k)) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
}l;
        else cout<<"No"<<endl;
    }
}

o 还wa了一发在long long上

Doremy’s IQ

觉得逆向思维的话更好理解 也更好写代码一些

也是贪心 就尽量让使q变小的排在后面 逆序遍历 从0开始 后面的都要 直到q等于题目给的q 不满足条件的就不要了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#define int long long
using namespace std;
const int N=100005;
int t,n,q;
int a[N];
int b[N];
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n>>q;
        for(int i=0;i<n;i++)
        cin>>a[i];
        int cnt=0;
        for(int i=n-1;i>=0;i--)
        {
            if(cnt<q)
            {
                if(a[i]>cnt)
                {
                    cnt++;
                }
                b[i]=1;
            }
            else
            {
                if(q>=a[i]) b[i]=1;
                else b[i]=0;
            }
        }
        for(int i=0;i<n;i++)
        cout<<b[i];
        cout<<endl;
    }
}
Digital Logarithm

这题比赛的时候debug半小时、、无语住了 代码基本功太差了、、

思路大概就是先去重 然后求位数 再统计一下各个位数 然后求差值 去重不会写 sls教的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string.h>
#include<cmath>
using namespace std;
int t,x,n;
const int N=200005;
int a[N],b[N];
int qws(int x)
{
    int cnt=0;
    while(x)
    {
        x=x/10;
        cnt++;
    }
    return cnt;
}
void qc()
{
    int i=1;int j=1;
    while(i<=n&&j<=n)
    {
        if(a[i]<b[j]) i++;
        else if(a[i]>b[j]) j++;
        else
        {
            a[i]=0;b[j]=0;i++;j++;
        }
    }
}
signed main()
{
    cin>>t;
    while(t--)
    {
        cin>>n;
        int b1[15],b2[15];memset(b1,0,sizeof(b1));memset(b2,0,sizeof(b2));
        int ccnt=0;
        for(int i=1;i<=n;i++)
        cin>>a[i];
        for(int i=1;i<=n;i++)
        cin>>b[i];
        sort(a+1,a+n+1);
        sort(b+1,b+1+n);
        qc();
        for(int i=1;i<=n;i++)
        {
            if(a[i]>9)
            {
                a[i]=qws(a[i]);
                ccnt++;
            }
            if(b[i]>9)
            {
                b[i]=qws(b[i]);
                ccnt++;
            }    
        }
        for(int i=1;i<=n;i++)
        {
            b1[a[i]]++;
            b2[b[i]]++;
        }
        for(int i=2;i<=9;i++)
        {
            ccnt+=abs(b1[i]-b2[i]);
        }
        cout<<ccnt<<endl;
    }
}

写在最后

嗯…效率比预计得低很多 下周继续做递归分治 板子写的还不够熟T T