当前位置：首页 > article >正文

at coder ABC 392

article 2025/2/11 13:23:32

A - Shuffled Equation

题意：给一个整数序列（A1,A2,A3）,这三个数进行排序后形成（B1,B2,B3）问是否存在排序使B1*B2=B3？

思路：因为一共就三个数，只有三种排列方式，我直接全部都列出来判断的，不用管B

判断是否为真即可arr[0] * arr[1] == arr[2] || arr[0] * arr[2] == arr[1] || arr[2] * arr[1] == arr[0])

#include <stdio.h>
int main()
{
	int arr[3] = { 0 };
	scanf("%d%d%d", &arr[0], &arr[1], &arr[2]);
	if (arr[0] * arr[1] == arr[2] || arr[0] * arr[2] == arr[1] || arr[2] * arr[1] == arr[0])
		printf("Yes\n");
	else
		printf("No\n");
	return 0;
}

B - Who is Missing?

题意：给出M个数，这M个数都是介于1-N之间的，请你输出该序列中不在1-N之间的个数及每个数，其中1<=M<=N<=1000;

思路：开两个数组int[1005],一个放这M个数，另一个全部初始化为0，因为每个数都不重复出现，所以遍历放M个数的数组，所表示的数作为第二个数组的索引，使之加1，这样一来，所有在1-N之间出现过的数都在第二个数组的下标索引值为1，我们只需要遍历第二个数组1-N，找到等于0的值，计数并且输出即可

#include <stdio.h>
int main()
{
	int m, n;
	int arr[1005] = { 0 };
	int brr[1005] = { 0 };
	int cnt = 0;
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d", &arr[i]);
	}
	
	for (int i = 0; i < m; i++)//整数是介于1-n之间的
	{
		brr[arr[i]]++;
	}
	for (int i = 1; i <= n; i++)
	{
		if (brr[i] == 0)
			cnt++;
	}
	printf("%d\n", cnt);
	for (int i = 1; i <= n; i++)
	{
		if (brr[i] == 0)
			printf("%d ", i);
	}
	return 0;
}

C - Bib

题意：一组人编号为1-N，第 i 个人穿着印有数字 Qi 的围兜，正盯着第 Pi 个人。然后依次输出围兜上的数从1开始到N的人所盯着的人的围兜上的数

2 ≤ N ≤ 3×10⁵
1 ≤ Pi ≤ N
Pi 的值各不相同。
1 ≤ Qi ≤ N
Qi 的值各不相同。
所有输入值都是整数。

思路：本题有点绕，读清题目是关键，我一开始用了两层的for循环，就是先找到围兜上的数字为1的数，然后依次索引，时间复杂度太高了，然后运行超时了......

#include <stdio.h>

int main()
{
	int n;
	int p[300005] = { 0 };
	int q[300005] = { 0 };
	
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &p[i]);//第i个人盯着第p[i]的人
	}
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &q[i]);//第i个人带着q[i]的围兜
	}
	//找出戴着号码为 i 的围兜的人所盯着的人围兜上写的号码。
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			if (i == q[j])
			{
				printf("%d ", q[p[j]]);
				break;
			}

		}
	}
	return 0;
}

接着，我就新增加了一个数组，在依次输入这N个人的围兜的数字时，建立起下标和围兜上表示的数的关系，意思就是pos数组记录的就是围兜1-n的位置，例如pos[1]=3,说明围兜上写着1号的人是在第三号位置，（for me,这一步就是最难理解的一行代码）然后再从1-n开始遍历时，pos[i]就可以直接表示围兜上从1开始的人了。

#include <stdio.h>

int main()
{
    int n;
    int p[300005] = { 0 };
    int q[300005] = { 0 };
    int pos[300005] = { 0 }; // 新增映射数组
    
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i]);
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &q[i]);
        pos[q[i]] = i; // 建立值到索引的映射
    }
    
    for (int i = 1; i <= n; i++) {
        int target_pos = pos[i]; // 直接获取位置
        printf("%d ", q[p[target_pos]]);
    }
    
    return 0;
}

D - Doubles

题意：一共有n个骰子，第i个骰子有ki个面，每个面出现的概率相同，最有情况选两个骰子，求这两个骰子显示相同数字的最大概率

思路：这个题做的时候没时间了，就没看完。交卷后分析了别人的AC代码，注释如下：


#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
   ll n;
   cin >> n;//n个骰子
   vector<vector<ll>>v(n);//定义一个二维向量v,它包含n个一维向量，用于存储每个面的大小
   for(int i=0;i<n;i++){
        ll x;
        cin >>x;//x个面
        while(x--){
           ll ele;
           cin >> ele;
           v[i].push_back(ele);//每个面的大小
        }
    }
    vector<vector<ll>>count(n,vector<ll>(1e5+7,0));
//定义一个二维向量 count，它有 n 行，每行有 1e5 + 7 个元素，初始值都为 0。
//这个二维向量用于记录每个骰子中每个数字出现的次数。
    for(int i=0;i<n;i++){
        for(auto ele:v[i]) count[i][ele]++; //两层遍历，统计每个面上的数字
    }
    double ans=0.0;
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){//使用两层嵌套循环枚举所有可能的骰子对
            double tot=0;//记录这对骰子掷出相同数字的组合数
            for(auto ele:v[i]) tot+=count[j][ele];
//遍历第 i 个骰子的所有面的数字，将第 j 个骰子中该数字出现的次数累加到 tot 中
            ans=max(ans,(tot/(v[i].size()*v[j].size())));//ans始终存储最大概率
        }
    }
    cout << setprecision(15) << ans;//输出精度为15
}

查看全文

http://www.kler.cn/a/540697.html