上海市计算机学会竞赛平台 2月月赛 丙组
T1 格式改写
题目描述
给定一个仅由拉丁字符组成字符序列，需要改写一些字符的大小写，使得序列全部变成大写或全部变成小写，请统计最少修改多少个字符才能完成这项任务。
输入格式
一个字符序列：保证仅由拉丁字符构成
输出格式
单个整数：表示最少修改次数
数据范围
设输入的字符数量为 n，则保证 1≤n≤100,000
样例数据
输入:
TheQuickBrownFoxJumpsOverTheLazyDog
输出:
9
说明:
将大写改小写
分析
题意
将整个字符串改为大写或小写，输出最小修改次数
思路
将整个字符串查一遍，记录其中大写和小写字母的个数，输出最小值
代码
#include <bits/stdc++.h>
using namespace std;
string s;
int main(){
getline(cin, s);
int len = s.size();
int t = 0, l = 0;
for (int i = 0; i < len; i++){
if (islower(s[i]))
l++;
else
t++;
}
cout << min(t, l) << endl;
return 0;
}T2 倍数统计
题目描述
给定整数 a, b 与正整数 c，求出在 a 到 b 之间（包含 a 与 b）有多少整数是 cc 的倍数。
输入格式
第一行：两个整数 a 与 b；
第二行：单个正整数 c。
输出格式
单个整数：表示答案。
数据范围
-109≤a≤b≤109
1≤c≤109
样例数据
输入:
4 6
5
输出:
1
分析
题意
输出a~b中c的倍数
思路1
从a循环到b，记录c倍数的个数,但数据量太大，会超时。
思路2
假设a~b中有个数n是c的倍数，那么n+c一定也是c的倍数。
那么我们可以先循环找到从a开始第一个c的倍数n，再求出n~b中有几个c。
代码
#include <bits/stdc++.h>
using namespace std;
long long a, b, c;
int main(){
cin >> a >> b >> c;
int num, ans = 1;
for (int i = a; i <= b; i++)
if (i % c == 0){
num = i;
break;
}
ans += (b - num) / c;
cout << ans << endl;
return 0;
}T3 区间的并
题目描述
给定一个数轴上的 n 个闭区间，第 i 个闭区间的两端点为[a_i,b_i]，它们的并集可以表示为若干不相交的闭区间，请按照左端点从小到大的顺序输出这些区间的并集。
输入格式
第一行：单个整数 n；
第二行到第 n+1 行：每行两个整数 a_i 与 b_i 表示一个闭区间 [a_i,b_i]。
输出格式
若干行：表示输入区间的并集。每行两个整数，表示一个闭区间的两个端点，这些闭区间应该按照起点从小到大排序。
数据范围
对于 50% 的数据，1≤n≤104, 0 \leq a_i\leq b_i \leq 104
对于 100% 的数据，1≤n≤105 ,0≤a_i≤b_i≤109
样例数据
输入:
3
10 12
1 3
2 5
输出:
1 5
10 12
分析
题意
告诉你n区间的两个端点，如果有重复的就并成一个
注意：如区间[1,2]和区间[3,4]是两个区间
思路1：模拟
建立一个数组，将区间填上数字，填完从头扫一遍，只要不空格就输出。
而相邻区间的问题可以将区间的首位乘2，这样相邻的区间内会空一个，输出时除2即可。
但时间复杂度太高，只能拿50分。
思路2
先将数据存入结构体中，然后按左端点排序。这是，如果一个区间的左端点在上一个区间的右端点右面，那这一定是两个不同的区间，反之则并为一个区间。
代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
struct nod{
int a, b;
};
bool cmp(nod a, nod b){
return a.a < b.a;
}
nod x[MAXN];
int n;
int be, en;
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> x[i].a >> x[i].b;
}
sort(x + 1, x + n + 1, cmp);
int be = x[1].a, en = x[1].b;
for (int i = 2; i <= n; i++){
if (x[i].a > en){
cout << be << " " << en << endl;
be = x[i].a;
en = x[i].b;
}
if (x[i].b > en){
en = x[i].b;
}
}
cout << be << " " << en << endl;
return 0;
}T4 平分数字（一）
题目描述
给定 n 个整数：a_1,a_2,\cdots,a_n，请判定能否将它们分成两个部分（不得丢弃任何数字），每部分的数字之和一样大。
输入格式
第一行：单个整数 n；
第二行：n 个整数，表示 a_1,a_2,\cdots,a_n 。
输出格式
若能否平分，输出 Matched，否则输出 No
数据范围
对于 50% 的数据，1≤n≤18；
对于 100% 的数据，1≤n≤24；
−10,000,000≤a_i≤10,000,000
样例数据
输入:
4
1 2 3 4
输出:
Matched
说明:
1 + 4 = 2 + 3
输入:
3
2 2 2
输出:
No
分析
题意
给定n个数，判断是否能分为两组和相同的数字。
思路：搜索
这题的n只到24，所以即使把所有可能讨论一遍也只有224(16,777,216<100,000,000)种情况。当然，题目只要求判断是否有解，所以我们找出一种后就可以立即暂停。并且，如果n个数的和是奇数，那么不可能有解。
代码：
#include <bits/stdc++.h>
using namespace std;
int n, sum, a[30];
bool flag = false;
void dfs(int s, int i){
if (flag == true){
return ;
}
if (s == sum){
flag = true;
return ;
}
if (i == n)
return ;
dfs(s + a[i + 1], i + 1);
dfs(s, i + 1);
return ;
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++){
cin >> a[i];
sum += a[i];
}
if (sum % 2 == 0){
sum /= 2;
dfs(0, 0);
}
if (flag)
cout << "Matched" << endl;
else
cout << "No" << endl;
return 0;
}T5 圆环三染色
题目描述
有一个圆环上有 n 个点，一个染色方案需要为每个点分配三种颜色中的一种，且圆环上相邻的点颜色不能相同。
请求出有多少种染色方案。答案可能很大，输出模 1,000,000,007 的余数。
输入格式
单个整数表示 n。
输出格式
表示方案数模 1,000,000,007 的余数。
数据范围
对于 30% 的数据，1≤n≤20；
对于 60% 的数据，1≤n≤1,000,000；
对于 100% 的数据，1≤n≤1018
样例数据
输入:
1
输出:
3
输入:
3
输出:
6
分析
题意
给定一个有n个格子的圆环和三种染料，问有几种涂法。
思路1：搜索(30分）
建立一个数组，在每个位置填数，保证不与前一个相同，如果是第n个，则多判断是否与第一个相同，否则记录。
代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int n, ans = 0;
int a[MAXN];
void dfs(int i){
if (i == n + 1){
if (a[n] != a[1]){
ans++;
}
return;
}
for (int j = 1; j <= 3; j++){
if (i == 1 || j != a[i - 1]){
a[i] = j;
dfs(i + 1);
}
}
return;
}
int main(){
cin >> n;
if (n == 1)
cout << 3 << endl;
else{
dfs(1);
cout << ans << endl;
}
return 0;
}思路2：递归(60分)
我们看一个表格
| n | f(n) |
|---|---|
| 1 | 3 |
| 2 | 6 |
| 3 | 6 |
| 4 | 18 |
| 5 | 30 |
| 6 | 66 |
| 7 | 126 |
| 8 | 258 |
可以看出，当n大于3时
当n为奇数时：f(n)=2f(n-1)+6
当n为偶数时：f(n)=2f(n-1)-6
所以得出代码：
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long n, ans = 0;
int f(long long i){
if (i == 1) return 3;
if (i == 2 || i == 3) return 6;
if (i % 2 == 0){
return (f(i - 1) % mod * 2 % mod + 6) % mod;
}else{
return (f(i - 1) % mod * 2 % mod - 6) % mod;
}
}
int main(){
cin >> n;
cout << f(n) << endl;
return 0;
}思路3：快速幂（100分）
还是这个表格：
| n | f(n) |
|---|---|
| 1 | 3 |
| 2 | 6 |
| 3 | 6 |
| 4 | 18 |
| 5 | 30 |
| 6 | 66 |
| 7 | 126 |
| 8 | 258 |
我们发现，当n>3时：
当n为奇数时：f(n)=2^n-2
当n为偶数时：f(n)=2^n+2
所以只要明如何求出2n即可。这是我们可以用快速幂（参考染色问题）
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
long long n;
long long f(long long a){
if (a == 0) return 1;
long long x = f(a / 2);
if (a % 2)
return x * x % mod * 2 % mod;
return x * x % mod;
}
int main(){
cin >> n;
int ans = f(n);
if (n == 1)
cout << 3 << endl;
else if (n % 2 == 0)
cout << (ans + 2) % mod << endl;
else
cout << (ans - 2 + mod) % mod << endl;
return 0;
}