网上训练补题

1.Codeforces Round 920 (Div. 3)

?A.

?简单判断出边长即可

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
	int n;
	scanf("%d", &n);
	while (n--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		int e, f;
		scanf("%d%d", &e, &f);
		int g, h;
		scanf("%d%d", &g, &h);
		int a, b;
		scanf("%d%d", &a, &b);
		int line = 0;
		int wine = 0;
		line = sqrt((x - e) * (x - e) + (y - f) * (y - f));
		wine = sqrt((x - g) * (x - g) + (y - h) * (y - h));
		if (line < wine)
		{
			printf("%d\n", line * line);
		}
		else
		{
			printf("%d\n", wine * wine);
		}
	}
	return 0;
}

B.

?按顺序比较字符串即可

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
char a[100050] = { 0 };
char b[100050] = { 0 };
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n;
		scanf("%d", &n);
		scanf("%s", a);
		scanf("%s", b);
		int ze = 0;
		int li = 0;
		int num = 0;
		for (int i = 0; i < n; i++)
		{
			if (a[i] == '1' && a[i] != b[i])
			{
				li++;
			}
			else if (a[i] == '0' && a[i] != b[i])
			{
				ze++;
			}
		}
		if (li == ze)
		{
			num = li;
		}
		else
		{
			if (li > ze)
			{
				num = li;
			}
			else
			{
				num = ze;
			}
		}
		printf("%d\n", num);
		memset(a, 0, sizeof(char) * 100050);
		memset(b, 0, sizeof(char) * 100050);
	}
	return 0;
}

C.

?每次的耗电量相比后直接相减即可

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

inline void fastRead(long long &x) {
    int c = getchar();
    int sign = 1;
    while (c < '0' || c > '9') {
        if (c == '-') sign = -1;
        c = getchar();
    }
    x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    x *= sign;
}

long long arr[200050] = { 0 };

int main() {
    long long t;
    fastRead(t);
    while (t--) {
        long long n, f, a, b;
        int flag = 1;
        fastRead(n); fastRead(f); fastRead(a); fastRead(b);
        for (int i = 0; i < n; i++) {
            fastRead(arr[i]);
        }
        long long mid = 0;
        for (int i = 0; i < n; i++) {
            mid = (i == 0 ? arr[i] : arr[i] - arr[i - 1]) * a;
            f -= (mid < b ? mid : b);
            if (f <= 0) {
                printf("NO\n");
                flag = 0;
                break;
            }
        }
        if (flag == 1) {
            printf("YES\n");
        }
    }
    return 0;
}

D.

反复比较两个数列头尾相减的最大值即可

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
int a[200005] = { 0 };
int b[200005] = { 0 };
int com(const void* a, const void* b)
{
	int aa = *(const int*)a;
	int bb = *(const int*)b;
	if (aa > bb)
	{
		return 1;
	}
	else if (aa < bb)
	{
		return -1;
	}
	else
	{
		return 0;
	}
}
void solve()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &b[i]);
	}
	qsort(a, n, sizeof(int), com);
	qsort(b, m, sizeof(int), com);
	long long num = 0;
	int mm = m - 1;
	int nn = n - 1;
	int mi = 0;
	int ni = 0;
	int count = 0;
	while (count < n)
	{
		if (abs(b[mm] - a[ni]) >= abs(a[nn] - b[mi]))
		{
			num += abs(b[mm] - a[ni]);
			count++;
			ni++;
			mm--;
		}
		else
		{
			num += abs(a[nn] - b[mi]);
			mi++;
			nn--;
			count++;
		}
	}
	printf("%lld\n", num);
}
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

?E.

?博弈论，初始位置就决定了谁是试图平局的那一方

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

void solve()
{
	int h, w, x1, y1, x2, y2;
	scanf("%d%d%d%d%d%d", &h, &w, &x1, &y1, &x2, &y2);
	if (h == 1 || x1 > x2)
	{
		printf("Draw\n");
	}
	else
	{
		if (abs(x1 - x2) % 2 == 0)//bob主场
		{
			if (y1 > y2)
			{
				if (2 * (w - y2) > x2 - x1)
				{
					printf("Draw\n");
				}
				else
				{
					printf("Bob\n");
				}
			}
			else if (y1 < y2)
			{
				if (2 * (y2 - 1) > x2 - x1)
				{
					printf("Draw\n");
				}
				else
				{
					printf("Bob\n");
				}
			}
			else
			{
				printf("Bob\n");
			}
		}
		else if (abs(x1 - x2) % 2 != 0)//alice主场
		{
			if (y1 > y2)
			{
				if (y1 - y2 == 1)
				{
					printf("Alice\n");
				}
				else if (2 * (y1 - 2) >= x2-x1)
				{
					printf("Draw\n");
				}
				else
				{
					printf("Alice\n");
				}
			}
			else if (y1 < y2)
			{
				if (y2 - y1 == 1)
				{
					printf("Alice\n");
				}
				else if (2 * (w - y1 - 1) >= x2 - x1)
				{
					printf("Draw\n");
				}
				else
				{
					printf("Alice\n");
				}
			}
			else
			{
				printf("Alice\n");
			}
		}
	}
}
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		solve();
	}
	return 0;
}

2.Toyota Programming Contest 2024#1（AtCoder Beginner Contest 337）

虚拟参加

A.?简单相加比较大小

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

int main()
{
	int t;
	scanf("%d", &t);
	long long a = 0;
	long long b = 0;
	while (t--)
	{
		int aa;
		int bb;
		scanf("%d%d", &aa, &bb);
		a += aa;
		b += bb;
	}
	if (a > b)
	{
		printf("Takahashi\n");
	}
	else if (b > a)
	{
		printf("Aoki\n");
	}
	else
	{
		printf("Draw\n");
	}
	return 0;
}

B.

要注意单个B也可以是正确的

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
char s[1005];
int main() 
{
    scanf("%s", s);
    int i = 0;
    int len = strlen(s);
    //检查a
    while (i < len && s[i] == 'A') 
    {
        i++;
    }
    //检查b
    while (i < len && s[i] == 'B') 
    {
        i++;
    }
    //检查c
    while (i < len && s[i] == 'C') 
    {
        i++;
    }
    if (i == len) 
    {
        printf("Yes\n");
    }
    else 
    {
        printf("No\n");
    }
    return 0;
}

C.

利用head找到最开始的那个人，然后next数组依次输出

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

#define MAXN 300005

int next[MAXN]; // 每个人后面的人
int prev[MAXN]; // 每个人前面的人
int head; // 第一个人

int main() 
{
    int n;
    scanf("%d", &n);

    for (int i = 1; i <= n; i++) 
    {
        int a;
        scanf("%d", &a);

        if (a == -1) 
        {
            head = i;
        }
        else 
        {
            next[a] = i;
            prev[a] = a;
        }
    }

    // 从第一个人开始，依次打印每个人的编号
    for (int i = head; i != 0; i = next[i]) 
    {
        printf("%d ", i);
    }

    return 0;
}

?D.

前缀和的思想会容易解决这一个问题，全部统计完直接遍历即可

这里最好用c++的容器，因为这个不能硬开数组，会过大，我写一个丑陋的一维数组来模拟的

#include <stdio.h>
#include <string.h>
#include <math.h>
char m[20000050] = { 0 };
int a[20000050] = { 0 };
int b[20000050] = { 0 };
void solve()
{
	int h, w, k;
	scanf("%d%d%d", &h, &w, &k);
	for (int i = 1; i <= h; i++)
	{
		for (int j = 1; j <= w; j++)
		{
			scanf(" %c", &m[i * w + j]);
		}
	}
	for (int i = 1; i <= h; i++) 
	{
		for (int j = 1; j <= w; j++) 
		{
			a[i * w + j] = a[w * (i - 1) + j] + a[i * w + j - 1] - a[w * (i - 1) + (j - 1)] + (m[i * w + j] == '.');
			b[i * w + j] = b[w * (i - 1) + j] + b[i * w + j - 1] - b[w * (i - 1) + (j - 1)] + (m[i * w + j] == 'x');
		}
	}
	long long ans = 0x3f3f3f3f;

	for (int i = 1; i <= h; i++)
	{
		for (int j = k; j <= w; j++)
		{
			int flag = b[i * w + j] - b[i * w + j - k] - b[w * (i - 1) + j] + b[w * (i - 1) + j - k];
			if (flag == 0)
			{
				if (ans > (a[i * w + j] - a[i * w + j - k] - a[w * (i - 1) + j] + a[w * (i - 1) + j - k]))
				{
					ans = a[i * w + j] - a[i * w + j - k] - a[w * (i - 1) + j] + a[w * (i - 1) + j - k];
				}
			}
		}
	}
	for (int i = k; i <= h; i++)
	{
		for (int j = 1; j <= w; j++)
		{
			int flag = b[i * w + j] - b[w * (i - k) + j] - b[i * w + j - 1] + b[w * (i - k) + j - 1];
			if (flag == 0)
			{
				if (ans > (a[i * w + j] - a[w * (i - k) + j] - a[i * w - 1 + j] + a[w * (i - 1) + j - 1]))
				{
					ans = a[i * w + j] - a[w * (i - k) + j] - a[i * w - 1 + j] + a[w * (i - 1) + j - 1];
				}
			}
		}
	}
	if (ans == 0x3f3f3f3f)
	{
		printf("-1\n");
	}
	else
	{
		if (ans > 0)
		{
			printf("%lld\n", ans);
		}
		else
		{
			printf("0\n");
		}
	}
}
int main()
{
	solve();
	return 0;
}

E.

?感谢学长的代码和讨论区大佬的提示，这是对二进制的理解，以便在一轮问话中确定坏的饮料是什么

代码附上详细的注释

#include <stdio.h>
#include <math.h>
#include <string.h>

int main() 
{
    int n;
    scanf("%d", &n); // 读取果汁的数量

    int m = ceil(log2(n)); // 计算出需要的测试组的数量，这个数量是n的二进制表示的位数
    printf("%d\n", m); // 打印测试组的数量

    int test_groups[m][n]; // 创建一个二维数组，用来存储每个测试组的果汁编号 m是人数 n是每个人分别问的数量
    memset(test_groups, 0, sizeof(test_groups)); // 初始化二维数组
    int test_group_sizes[m]; // 创建一个数组，用来存储每个测试组的果汁数量
    memset(test_group_sizes, 0, sizeof(test_group_sizes)); // 初始化数组

    for (int i = 0; i < n; i++) 
    { // 遍历每个果汁的编号
        for (int j = 0; j < m; j++) // m是二进制位的位数
        { // 对于每个编号，检查它的二进制表示的每一位
            if ((i >> j) & 1) 
            { // 如果某一位是1
                test_groups[j][test_group_sizes[j]] = i + 1; // 就将这个编号加入到对应的测试组中
                test_group_sizes[j]++;//问的数量
            }
        }
    }

    for (int i = 0; i < m; i++) 
    { // 打印出每个测试组的果汁数量和编号
        printf("%d ", test_group_sizes[i]);
        for (int j = 0; j < test_group_sizes[i]; j++) 
        {
            printf("%d ", test_groups[i][j]);
        }
        printf("\n");
        fflush(stdout); // 清空输出缓冲区，确保信息立即输出
    }

    char test_results[m + 1]; // 创建一个数组，用来存储每个测试组的测试结果
    scanf("%s", test_results); // 读取每个测试组的测试结果

    int bad_drink = 0; // 初始化变质的果汁的编号
    for (int i = 0; i < m; i++) 
    { // 遍历每个测试组的测试结果
        if (test_results[i] == '1') 
        { // 如果某个测试组的测试结果是1
            bad_drink |= (1 << i); // 那么变质的果汁的编号在二进制表示下的对应位设置为1
        }
    }

    printf("%d\n", bad_drink + 1); // 打印出变质的果汁的编号

    return 0;
}