上海市计算机学会月赛 2021年10月月赛丙组

上海市计算机学会月赛 2021年10月月赛丙组

• • 运费计算
  • 阶乘的余数
  • 多边形的判定
  • 淘气合影
  • 黑白翻转棋

运费计算

内存限制: 256 Mb时间限制: 1000 ms
题目描述
快递运费的计算规则如下：

重量不超过 1000 克（含 1 千克）的物品，请您支付基础运费 12 元；
对于首重规则之外的物品，则需要按照超重部分计算运费：每超过5千克的部分按一定比例增加费用（不足5千克的部分则按5千克计费）。
给定一个正整数 a，请计算其对应的快递费用金额。

输入格式
单个整数：表示寄送物品的重量 a克。

输出格式
单个整数：表示需要支付的运费。

数据参数设定为a的取值范围从1至$1, 万（一万）之间。
样本输入：
8百
输出结果：
1十二
具体说明：
当重量未达到起步标准时仅收取基本运输费用。
测试案例：
输入数值为千八百时应支付运输费用总计二十又二分之一元。
评析
该题目主要考察基础的数学运算能力。

    #include <iostream>
    #include <cstdio>
    using namespace std;
    int main()
    {
    	int a;
    	scanf("%d", &a);
    	a -= 1000;
    	if (a <= 0)
    		printf("12");
    	else {
    		int t = a / 500, tm = 0;
    		if (a - t * 500)
    			tm = 1;
    		printf("%d", 12 + t * 5 + tm * 5);
    	}
    	return 0;
    }

阶乘的余数

内存限制: 256 Mb时间限制: 1000 ms
题目描述
n 的阶乘记为 n!，定义如下：

n! = 1 \times 2 \times \cdots \times n

给定两个正整数 n 与 m，请计算 n! 除以 m 的余数。

输入格式
第一行：两个整数表示 n 与 m。

输出格式
单个整数：表示 n! 除以 m 的余数。

数据范围
对于 30% 的数据，1≤n≤10；
对于 60% 的数据，1≤n,m≤10000；
对于 100% 的数据，1≤n,m≤1,000,000；
样例数据
输入:
5 1000
输出:
120
说明:
5!=120
分析：
直接乘的话精度不够，所以每一次乘的时候都模一下。

    #include <iostream>
    using namespace std;
    int main()
    {
    	cin.tie(0);
    	cout.tie(0);
    	long long n, m, sum = 1;
    	cin >> n >> m;
    	for (int i = 1; i <= n; i++) {
    		sum *= i;
    		sum %= m;
    	}
    	cout << sum % m;
    	return 0;
    }

多边形的判定

内存占用限制：256 MB

输入格式：
第一行为一个整数 n
第二行为n个整数a_1, a_2, \dots, a_n
输出结果：
若能构成n边形，则输出 Yes；否则输出 No。

数据范围
1 \leq a_i \leq 1,000,00 0,000
对于 30% 的数据，1≤n≤100；
对于 60% 的数据，1≤n≤5,000；
对于 100% 的数据，1≤n≤100,000；
样例数据
输入:
6
1 3 5 2 4 6
输出:
Yes
输入:
3
1 1 2
输出:
No
分析：
数学题，每一条边都要严格小于其他边之和，不然无法构成图形。

    #include <iostream>
    using namespace std;
    int main()
    {
    	int n;
    	cin >> n;
    	long long a[n], sum = 0;
    	for (int i = 0; i < n; ++i) {
    		cin >> a[i];
    		sum += a[i];
    	}
    
    	for (int i = 0; i < n; ++i) {
    		if (a[i] >= sum - a[i]) {
    			cout << "No";
    			return 0;
    		}
    	}
    	cout << "Yes";
    	return 0;
    }

淘气合影

内存占用不超过256 MB

问题概述

老师引导孩子们到达了正确的位置后离开处理相机；
一部分孩子偷偷溜走并插队中间；
老师按动快门拍摄到照片后发现部分孩子不在正确的位置；
老师对所有捣乱的孩子进行了严肃的教导，并要求这些被教育的孩子不再淘气也不会跑远离开队返回最初的位置；
注意，在每一轮流程中都可能出现新的孩子捣乱的情况。其中在第 i 张照片中排在队伍中的第 j 名孩子的编号为 a_{i,j}。

小爱能否从这五张照片中恢复出老师心中的标准排名？输入数据确保存在解，并且只有一个解。

第一行为一个整数n。
第二至第六行为每行为n个整数组成。
这些数字构成一个1至n的排列。

输出格式
表示原本正确的位置中，应该排在第ii名的孩子编号

数据范围
对于 30% 的数据，1≤n≤12；
对于 60% 的数据，1≤n≤300；
对于 100% 的数据，1≤n≤100,000。
样例数据
输入:
6
2 3 4 5 1 6
2 1 3 4 5 6
3 1 2 4 5 6
4 1 2 3 5 6
5 1 2 3 4 6
输出:
1 2 3 4 5 6
说明:
第一次1号捣乱，第二次2号捣乱，以此类推，6号没有捣乱。
分析：
自定义排序，如果a孩子排在b孩子前面，那肯定出现3次以上。因为，a排在b的后面只有两种可能(1.a捣乱了排到b前面，2.b捣乱了排到a前面)

    #include <iostream>
    #include <algorithm>
    using namespace std;
    int n, a[100001], tmp, f[100001][6];
    bool cmp(int , int y)
    {
    	int cnt = 0;
    	for (int i = 1; i <= 5; i++)
    		if (f[x][i] < f[y][i])
    			++cnt;
    	return cnt >= 3;
    }
    int main()
    {
    	cin >> n;
    	for (int i = 1; i <= 5; ++i)
    		for (int j = 1; j <= n; ++j) {
    			cin >> tmp;
    			f[tmp][i] = j;
    		}
    	for (int i = 1; i <= n; ++i)
    		a[i] = i;
    	sort(a + 1, a + 1 + n, cmp);
    	for (int i = 1; i <= n; ++i)
    		cout << a[i] << " ";
    	return 0;
    }

黑白翻转棋

配置参数：内存分配设为256 Mb；程序运行时长限定在1秒内。详细说明这一过程的具体步骤与规则如下：我们常说的一种游戏类型是黑白翻转棋，在一个n \times m的小方块组成的棋盘上进行操作。每个小方块上放置一枚游戏币（类似于国际象棋中的硬币），每枚硬币的一面最初可能是黑色的也可能是白色的。如果将某一枚硬币进行翻转（即将其旋转180度），那么这枚硬币的颜色状态就会从黑色变为白色或者从白色变为黑色。初始状态下所有的格子都是随机颜色分布的（即有的是黑色有的是白色）。如果能够通过一系列操作将所有的小方块都设置为白色状态，则判定成功并结束程序运行。

小爱可以选择任意顺序地翻动任意数量的棋子。但根据游戏规则，在选择翻动某一枚位于中央位置的棋子时，则必须同时将与其方格共享边界的其余四枚相邻棋子一并进行翻转；而在选择边缘位置或角落位置的一枚棋子时，则需要同步翻动其周围的全部相邻四枚或三枚（对于角落位置）其余方块中的相应部分）。小爱可能在一个步骤中一次性地将五个中间位置的方块、四个边缘位置的方块或三个角落位置的方块进行同步操作。

由小爱来计算所需的最小步骤数是多少？若起始状态无法完成游戏，则返回Impossible。

请指定两个整数n和m。
接下来的n行中每一行都包含m个整数，用于标记初始棋盘上各位置的颜色状态：1表示黑色方块、0表示白色方块。
如果无法通过若干次翻转操作使所有方块全部变为白面向上，则输出"Impossible"；否则，请输出最少需要进行多少次翻转操作。

数据范围
在30%的案例中，在参数设置范围内满足条件；在60%的情况下则会扩展到更大的数值区间；而对于全部案例而言，则要求参数值达到4个单位的标准设定。
样例数据
输入:
3×3网格中，
第一行为 [0, 1, 0]，
第二行为 [1, 1, 1]，
第三行为 [0, 1, 0]。
输出:
成功完成操作所需的最小步骤为一步。
具体操作说明:
只需翻转中心位置的一个棋子即可完成目标设定。
分析:
根据游戏规则可知，在每次操作时系统会自动计算所有受影响的位置并进行状态变换。因此，在解决此类问题时应优先考虑局部布局对整体效果的影响规律，并通过逐步优化实现全局最优解的目标。

    #include <iostream>
    using namespace std;
    int n, m, a[25][25], b[25], ans = 1e9;
    int check(int num)
    {
    	if (num == 0)
    		return 0;
    	return check(num & (num - 1)) + 1;
    }
    int main()
    {
    	ios::sync_with_stdio(false);
    	cin >> n >> m;
    	for (int i = 1; i <= n; ++i)
    		for (int j = 1; j <= m; ++j) {
    			cin >> a[i][j];
    			b[i] *= 2;
    			b[i] += a[i][j];
    		}
    	for (int k = 0; k < (1 << m); ++k) {
    		int now = k, t = 0, sum = 0;
    		for (int i = 1; i <= n; ++i) {
    			int tmp = now;
    			sum += check(now);
    			now = ((1 << m) - 1) & ((now << 1) ^ (now >> 1)^now ^ t ^ b[i]);
    			t = tmp;
    		}
    		if (now == 0)
    			ans = min(ans, sum);
    	}
    	if (ans == 1e9)
    		cout << "Impossible";
    	else
    		cout << ans;
    	return 0;
    }