寒假训练第二周训练报告

发表于 更新于 分类于

Part 1.训练题题解

算法基础训练 50 题（四）搜索

#JC0401.# 自然数的拆分问题

题目描述

利用回溯算法，每次都从1遍历到上限，并记录当前搜索的值以及总和。每当总和等于n时，输出所有记录的值。

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
using namespace std;
int t,n,m,a[100],ans;
string s;

int run(int l,int s,int sum)
{
	if (sum==n)
	{
		if (s==1) return 0;
		for (int i=1;i<s;i++)
			cout<<a[i]<<"+";
		cout<<a[s]<<endl;
		return 0;
	}

	s++;
	for (int i=l;i<=n;i++)
	{
		a[s]=i;
		if (sum+i>n) break;
		run(i,s,sum+i);
	}
	return 0;
}

int main()
{
	cin>>n;
	run(1,0,0);
	return 0;
}

#JC0402.# 八皇后问题

题目描述

利用回溯算法，因为每行、每列、每个对角线都不能放置棋子，但是搜索时是按行从上往下，所以只需要维护三个数组，分别记录别每列、每个对角线都是否放过棋子。在放置棋子时，用x+y表示所在的右斜对角线，用x-y+n表示左斜对角线（+n是防止结果为负数，超出数组下标范围）

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
int n,a[20],x[20],y[20],b1[50],b2[50],ans;
int run(int i)
{
    if (i==n+1)
    {
        ans++;
        if (ans>=4) return 0;
        F(j,1,n)
            CO a[j] P;
        CL;
        return 0;
    }

    for (int j=1;j<=n;j++)
        if (!y[j]&&!b1[i+j]&&!b2[i-j+n])
        {   
            b1[i+j]=b2[i-j+n]=y[j]=1;
            a[i]=j;
            run(i+1);
            b1[i+j]=b2[i-j+n]=y[j]=0;
        }
    return 0;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n;
    run(1);
    CO ans L;
    return 0;
}

#JC0403.# Lake Counting S

题目描述

该题可以用多次回溯来做，每一次回溯都会找到并标记连续的W，即一个水坑里的全部W，而对每个没有被标记的W，都进行一次回溯，最后会标记完所有的W，也就找到了所有的水坑。

用数组a来表示地图，数组b来表示w是否被标记过。每次回溯时都将能找到的W在b中标记，最后再遍历数组a，结合数组b寻找没有被标记过的W，进行下一次回溯。

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
int n,m,ans;
int a[200][200],b[200][200];
string s;

int run(int x,int y)
{
    int x1=max(1,x-1);
    int y1=max(1,y-1);
    int x2=min(n,x+1);
    int y2=min(m,y+1);
    F(i,x1,x2)
        F(j,y1,y2)
        {
            if (i==x&&j==y) continue;
            if (a[i][j]&&(!b[i][j]))
            {
                b[i][j]=1;
                run(i,j);
            }
        }
    return 0;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>m;
    F(i,1,n)
    {
        CI s;
        F(j,1,m)
            if (s[j-1]=='W') a[i][j]=1;
    }
    F(i,1,n)
    {
        F(j,1,m)
            if (a[i][j]&&(!b[i][j]))
            {
                run(i,j);
                ans++;
            }
    }
    CO ans L;
    return 0;
}

#JC0404.# 拯救oibh总部

题目描述

可以将地图扩展至(0,0)到(n+1,m+1)，最外面一圈填充0代表水坑，然后从坐标0,0开始，搜索连续的0并标记。最后再遍历整个地图，计数没有标记且为0的区域数量。

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
int n,m,a[501][501],b[501][501],ans;
char c;

int run(int x,int y)
{
    if (x<0||x>n+1||y<0||y>m+1) return 0;
  
    int zx[4]={-1,0,1,0};
    int zy[4]={0,-1,0,1};
    F(i,0,3)
    {
        if (x+zx[i]>=0&&y+zy[i]>=0&&x+zx[i]<=n+1&&y+zy[i]<=m+1)
            if (!a[x+zx[i]][y+zy[i]]&&!b[x+zx[i]][y+zy[i]]) 
            {
                b[x+zx[i]][y+zy[i]]=1;
                run(x+zx[i],y+zy[i]);
            }
    }
    return 0;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>m;
    F(i,1,n)
        F(j,1,m)
        {
            CI c;
            if (c=='*') a[i][j]=1;
        }
  
    run(0,0);

    F(i,1,n)
        F(j,1,m)
            if (!b[i][j]&&!a[i][j]) ans++;
    CO ans L;
    return 0;
}

#JC0405.# Need for Pink Slips

题目描述

利用回溯，每次按照题目要求调整c,m,p的概率并在选中p时统计概率。回溯时传入c,m,p的概率，当前抽奖次数，当前的总概率。

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
int t;
double c,m,p,v;
double ans;
string s;

int run(double c,double m,double p,double v,int t,double f)
{
    if (c!=0)
    {
        if (c-v<=1e-6)
        {
            // CO "IN" L;
            if (m!=0.0) run(0.0,m+c/2,p+c/2,v,t+1,f*c);
            else  run(0.0,0.0,1,v,t+1,f*c);
        }
        else 
        {
            if (m!=0.0) run(c-v,m+v/2,p+v/2,v,t+1,f*c); 
            else run(c-v,0.0,p+v,v,t+1,f*c);
        }
    }
    if (m!=0)
    {
        if (m-v<=1e-6)
        {
            if (c!=0.0) run(c+m/2,0.0,p+m/2,v,t+1,f*m);
            else run(0.0,0.0,1,v,t+1,f*m);
        }
        else 
        {
            if (c!=0.0) run(c+v/2,m-v,p+v/2,v,t+1,f*m);
            else run(0.0,m-v,p+v,v,t+1,f*m);
        }
    }
    if (p!=0)
    {
        f*=p;
        t++;
        ans+=t*f;
    }
    return 0;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI c>>m>>p>>v;
        ans=0;
        run(c,m,p,v,0,1);
        printf("%.10lf\n",ans);
    }
    return 0;
}

#JC0407.# Catch That Cow S

题目描述

本题利用广度优先搜索bfs，不断判断下一次移动是否会超出移动或到达已经移动过的地方，并将其加入到队列中，直到整个地图全被搜索完，然后输出牛所在的坐标的搜索深度。

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
int x,y,t;
struct Point
{
    int x,depth;
    Point(int x,int depth):x(x),depth(depth){};
};

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI x>>y;
        int v[MAX+10]={0};
        queue<Point> q;
        v[x]=1;
        q.push(Point(x,0));
        while (!q.empty())
        {
            Point p=q.front();
            if (p.x==y)
            {
                CO p.depth L;
                break;
            }

            if (p.x-1>=0&&!v[p.x-1])
            {
                q.push(Point(p.x-1,p.depth+1));
                v[p.x-1]=1;
            }
            if (p.x+1<=MAX&&!v[p.x+1])
            {
                q.push(Point(p.x+1,p.depth+1));
                v[p.x+1]=1;
            }
            if (p.x*2<=MAX&&!v[p.x*2])
            {
                q.push(Point(p.x*2,p.depth+1));
                v[p.x*2]=1;
            }
            q.pop();
        }
    }
    return 0;
}

#JC0408.# 马的遍历

题目描述

本体利用dfs，不断判断下一次马移动是否会超出移动或到达已经移动过的地方，并将其加入到队列中，直到整个地图全被搜索完，然后输出每个坐标的搜索深度。

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
int v[MAX+10][MAX+10]={-1,-1};
int n,m,x,y;
int f[8][2]={{-2,-1},{-1,-2},{-2,1},{-1,2},{1,-2},{2,-1},{1,2},{2,1}};
struct Point
{
    int x,y,depth;
    Point(int x,int y,int depth):x(x),y(y),depth(depth){};
};
queue<Point> q;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI n>>m>>x>>y;
  
    q.push(Point(x,y,0));

    F(i,1,n)
    {
        F(j,1,m)
            v[i][j]=-1;
    }
    v[x][y]=0;

    while (!q.empty())
    {
        Point p=q.front();

        F(i,0,7)
        {
            if (p.x+f[i][0]>=1&&p.x+f[i][0]<=MAX&&p.y+f[i][1]>=1&&p.y+f[i][1]<=MAX&&v[p.x+f[i][0]][p.y+f[i][1]]==-1)
            {
                q.push(Point(p.x+f[i][0],p.y+f[i][1],p.depth+1));
                v[p.x+f[i][0]][p.y+f[i][1]]=p.depth+1;
            }
        }
        q.pop();
    }
    F(i,1,n)
    {
        F(j,1,m)
            CO v[i][j]<<"\t";
        CL
    }
    return 0;
}

Part 2. Codeforces题解

Codeforces Round 920 Div. 3

题目链接：Codeforces Round 920 (Div. 3)

A. Square

难度800

输入矩形的四个坐标，计算四边形的面积。

获取到输入坐标中x和y轴的最小值最大值，相乘计算面积即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int t;
int a[4][2],minx,miny,maxx,maxy;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        F(i,0,3)
            CI a[i][0]>>a[i][1];
        minx=maxx=a[0][0];
        miny=maxy=a[0][1];
        F(i,0,3)
        {
            minx=min(minx,a[i][0]);
            maxx=max(maxx,a[i][0]);
            miny=min(miny,a[i][1]);
            maxy=max(maxy,a[i][1]);
        }
        CO abs(maxx-minx)*abs(maxy-miny) L;
    }
    return 0;
}

B. Arranging Cats

难度800

给出两段只由0和1组成的字符串s和n，每一步可以把一个1变成0、把0变成1、把一个0和1对调。求出最小多少步可以让字符串s与n相等。

为求出最小的步数，可以先把需要0变成1和需要1变成0的两位进行交换，这样一步就可以让两位字符相等，等无法交换时，再一位一位的修改字符串。所以分别计算出s和n中不相等位中字符1的个数，最大的一个即为最小步数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int t,n;
string s1,s2;
int main()
{   
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n;
        CI s1>>s2;
        int x1=0,x2=0;
        F(i,0,n-1)
            if (s1[i]!=s2[i])
            {
                if (s1[i]=='1') x1++;
                else x2++; 
            }
        if (x1>x2) CO x1 L;
        else CO x2 L;
    }
    return 0;
}

C. Sending Messages

难度900

有n个短信需要发送，每个短信在第\(a_i\)时刻发送，手机初始为开机状态有f格电，每单位时间会消耗a格电，开关机一次需要b格电，当电量≤0时将无法发送短信。求这n个短信能否全部发出去。

进行模拟即可，在需要发短信的时刻手机需要保持开机状态，但在没发短信的等待时刻可以选择开机等待或者关机等待。判断开机等待还是关机等待消耗的电量少，选择最少的即可，最后看能否发完全部短信。

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
int t;
LL mes,power,use,off;
LL a[200005];
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI mes>>power>>use>>off;
        F(i,1,mes)
            CI a[i];
        int t=0,f=1;
        F(i,1,mes)
        {
            if ((a[i]-a[i-1])*use<=off) power-=(a[i]-a[i-1])*use;
            else power-=off;
            if (power<=0) 
            {
                f=0;
                break;
            }
        }
        if (f) CO "YES" L;
        else CO "NO" L;
    }
    return 0;
}

D. Very Different Array

难度1100

给出两个数组a,b，长度分别为n,m，且n≤m。要在b数组的m个数中选出n个数并排序，然后依次与a数组中对应的数相减，使得绝对值的和最大，即sum(abs(ai-bi))最大。

为了使两个数组每个元素差的绝对值最大，需要将两个数组中最大的数与最小的数相减。所以首先先将数组a从小到大排序，将数组b从大到小排序，然后再维护一个数组c和指针k，将b数组中的前k个元素依次加入到数组c中，再将b数组的后n-k个元素依次加入到数组c中，然后再计算c与b差的绝对值。不断移动指针k，保存下最大的那个差的绝对值。

这样做可以得到正确的结果，但是会导致超时。观察数组c可以发现，每次指针k移动，c中都只有一个元素发生了改变。所以可以直接记录下b数组的前n个元素与a的差的绝对值，同时指针k指向b数组的第n个数，然后指针k不断向左移动直到指向第一个元素，同时不断从记录下的结果中删去指针指向元素b[k]与对应元素a[k]的差，再添加上对应的元素b[k+m-n]与a[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
33
34
35
36
LL t,n,m,ans,ma;
LL a[200005],b[200005];

bool cmp(LL a,LL b)
{
    return a>b;
}

int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        ans=0;
        ma=0;
        CI n>>m;
        CII(a,1,n)
        CII(b,1,m)
        sort(a+1,a+n+1);
        sort(b+1,b+m+1,cmp);

        F(i,1,n)
            ans+=abs(b[i]-a[i]);
        ma=ans;

        FD(i,n,1)
        {
            ans-=abs(b[i]-a[i]);
            ans+=abs(b[i+m-n]-a[i]);
            ma=max(ma,ans);
        }
        CO ma L;
    }
    return 0;
}

E. Eat the Chip

难度1600

给出一个棋盘和两个已经放在棋盘上的棋子a,b，a只能向下，沿对角线左下、右下移动1格，b只能向上，沿对角线左上、右上移动1格。a先走，如果一个棋子移动后盖在了另一棋子上，就算赢。

这题根据a,b所在坐标就能分析出最终谁赢。如果a在b棋子的下方或者平行，那么a一直向下走，b一直向上走，最后谁都吃不了对方，所以平手。如果a在b棋子上方，但两者的横向距离太远，直到两个棋子平行横向上仍有距离，则为平手。
如果ab之间纵向间隔的格子为偶数，因为a先走，所以a能吃掉b；同样如果间隔为奇数，则b能吃掉a。这是被吃掉的一方就要努力避开对方。所以还需要计算出当双方平行时，双方的横向移动范围。如果被吃的一方移动范围有一边超出了吃的一方，则可以逃出去，变为平局。

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
int t,n,m,xa,ya,xb,yb;
int main()
{
    // ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    CI t;
    while (t--)
    {
        CI n>>m>>xa>>ya>>xb>>yb;
        if (xa>=xb) CO "Draw" L;
        elif (abs(ya-yb)-1>(xb-xa-1)) CO "Draw" L;
        elif ((xa-xb)%2!=0) 
        {
            int la=max(1,ya-(xb-xa)/2-1);
            int ra=min(m,ya+(xb-xa)/2+1);
            int lb=max(1,yb-(xb-xa)/2);
            int rb=min(m,yb+(xb-xa)/2);
            if (la<=lb&&ra>=rb) CO "Alice" L;
            else CO "Draw" L;
        }
        else 
        {
            int la=max(1,ya-(xb-xa)/2);
            int ra=min(m,ya+(xb-xa)/2);
            int lb=max(1,yb-(xb-xa)/2);
            int rb=min(m,yb+(xb-xa)/2);
            if (lb<=la&&rb>=ra) CO "Bob" L;
            else CO "Draw" L;
        }
    }
    return 0;
}