暑期笔记 | 刷题题解
有学习新知识中的水题，也有需要思考的好题。暑假的题将会堆这里。
- 区间加和问题
- [NOIP2001 普及组] 数的计算
- [NOIP1998 普及组] 幂次方
- 确定进制(进制，暴力枚举)
- 花钱买车牌(贪心)
- 连续整数的和(数学，枚举的优化)
- 小b学进制(数学，进制，枚举的优化)
- [CSP-J2020] 直播获奖
- 数字1的数量
- 和为k的倍数
- 搬砖块
- 多米诺骨牌游戏
- 大鱼吃小鱼
- 和为S(前缀和优化)
- 区间和的和
区间加和问题
将数组$A={0}$上进行 $N$ 次操作$(l,r,s_i)$。第$i$次操作将区间$[l,r]$上的每一个值加上$s_i$，求 $N$ 次操作后数组所有数中的最大值。
可以采用扫描线的方法：
首先标记数组：只需将$A[l]$加上$s_i$，将$A[r+1]$减去$s_i$。然后扫描数组时，在每一位上计算出的前缀和就是操作后这一位的实际值。
例如，对$A={0,0,0,0,0,0}$进行操作$(0,3,2)$，先把数组标记成$A={2,0,0,0,-2,0}$，扫描时计算前缀和：${2,2,2,2,0,0}$。
参考代码
#include <bits/stdc++.h>
using namespace std;
int A[1005];
int main(){
int N,l,r,s,max_n=0;
cin >> N;
for(int i=1;i<=N;i++){
cin >> l >> r >> s;
A[l]+=s;
A[r+1]-=s;
} //标记
for(int i=1;i<=1005;i++){
A[i]+=A[i-1];
max_n=max(max_n,A[i]);
}//扫描，加前缀和
cout << max_n;
return 0;
}
时间复杂度：$O(n)$
[NOIP2001 普及组] 数的计算
题目描述
我们要求找出具有下列性质数的个数（包含输入的正整数 $n$）。
先输入一个正整数 $n$（$n \le 1000$），然后对此正整数按照如下方法进行处理：
- 不作任何处理；
- 在它的左边拼接一个正整数，但该正整数不能超过原数，或者是上一个被拼接的数的一半；
- 加上数后，继续按此规则进行处理，直到不能再加正整数为止。
题解
递归（记忆化搜索）
暴力搜索的思路为：当调用 f(n)时，枚举 1~(n/2) 中的数(i)，然后再调用 f(i)，直到 f(1)直接返回。每一次调用都让计数器 t++（因为每调用一次函数就意味着有一个合法答案）。
但是如果不记忆化的话，上述思路会TLE(因为 f(999)=1955133450，意味着要调用1955133450次函数)。不过实际考试中可以考虑打表。
更好的选择是写成记忆化，也就是以下代码：
#include <bits/stdc++.h>
using namespace std;
int t,memory[1001],i;
int f(int n){
t=1;//这个数本身就算一个答案
for(i=1;i<=n/2;i++){
if(!memory[i]) memory[i]=f(i);
t+=memory[i];
}
return t;
}
int main(){
int n;
cin >> n;
cout << f(n);
return 0;
}
添加了 memory数组进行记忆。注意到，若写记忆化算法，函数需要有返回值，而不采用暴力计数器。这其实算是比较典型的递归算法。
写成递归公式为：
\[f(n)=\begin{cases} \sum\limits_{i=1}^{n/2}f(i) & (n>1)\\ 1 & (n=1) \end{cases}\]递推
其实这题的最好写法是递推。
可以推出，递推公式为：
\[f[1]=1\\ f[n]=1+\sum\limits_{i=1}^{n/2}f[i]\]这样一来，代码就好写多了。
#include <bits/stdc++.h>
using namespace std;
int f[1001];
int main(){
f[1]=1;
int n;
cin >> n;
for(int i=2;i<=n;i++){
for(int j=1;j<=i/2;j++){
f[i]+=f[j];
}
f[i]++;
}
cout << f[n];
return 0;
}
[NOIP1998 普及组] 幂次方
题目描述
任何一个正整数都可以用 $2$ 的幂次方表示。例如 $137=2^7+2^3+2^0 $。
同时约定方次用括号来表示，即 $a^b$ 可表示为 $a(b)$。
由此可知，$137$ 可表示为 $2(7)+2(3)+2(0)$
进一步：
$7= 2^2+2+2^0$ ( $2^1$ 用 $2$ 表示)，并且 $3=2+2^0$。
所以最后 $137$ 可表示为 $2(2(2)+2+2(0))+2(2+2(0))+2(0)$。
又如 $1315=2^{10} +2^8 +2^5 +2+1$
所以 $1315$ 最后可表示为 $2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)$。
题解
这题一看就是个二进制题…正好这两天有学过这部分内容，其实挺水的也挺好理解的。所以直接看代码吧。
#include <iostream>
#include <cstring>
using namespace std;
string get_cl(int x){
string ans;
int tmp = 0;
while(x){
//使用二进制， tmp 为当前计算的位数
if(x%2 == 1){ // 当前的二进制位为 1 即 存在这个分解： 2^(tmp)
string t = to_string(tmp);
if(tmp != 0 && tmp != 1 && tmp != 2) t = get_cl(tmp);//要继续分解的几种情况
if(tmp == 1) ans = "+2" + ans;
else ans = "+2("+t+")" + ans; //推入答案
}
tmp++;
x /= 2;
}
ans.erase(ans.begin()); // 开头会有一个加号要抹去
return ans;
}
int main(){
int n;
cin >> n;
cout << get_cl(n);
return 0;
}
确定进制(进制，暴力枚举)
$6\times 9=42$对于$10$进制来说是错误的，但是对于$13$进制来说是正确的。
现在编写一段程序，读入三个整数$p$、$q$和$r$，然后确定一个进制$B$（$2\le B\le 16$）使得$p\times q=r$。如果$B$有很多选择，输出最小的一个。
题解
由于进制数$B$的范围较小，可以枚举所有进制，然后把这个$B$进制数转换成十进制来检验等式是否成立。知识点主要是复习怎么写转换成十进制的函数。
参考代码
#include <iostream>
#include <cmath>
using namespace std;
int p, q, r;
int to_10(int a, int i){
int cnt = 0, a_10 = 0;
while(a){
if(a%10 >= i) return -1; // 如果这一位大等于进制数，那么显然不合法
a_10 += (a%10)*pow(i, cnt);
cnt++; a /= 10;
}
return a_10;
}
bool check(int i){
int a = p, b = q, c = r;
int a_10 = to_10(a, i);
int b_10 = to_10(b, i);
int c_10 = to_10(c, i);
if(a_10==-1||b_10==-1||c_10==-1) return false;
if(a_10*b_10==c_10) return true;
return false;
}
int main(){
cin >> p >> q >> r;
for(int i=2; i<=16; i++){
if(check(i)){
cout << i;
return 0;
}
}
cout << 0;
return 0;
}
花钱买车牌(贪心)
一个车牌号由$n$位数字组成。如果一个车牌至少有$k$位数字是相同的，那么我们就说这个车牌漂亮的车牌。现在华沙想要改变他自己的车牌，使得他的车牌变得漂亮。当然，改车牌是要花钱的。每改变一位数字所要花费的费用等于当前位上的新旧数字之差的绝对值。那么总费用就是每位上所花费用的总和。
华沙想用最少的钱，使他的车牌变得漂亮起来。现在给定$n$，$k$，和旧牌的号码，请你计算换牌的最少费，以及新牌的号码。如果最少费用的号码有多个，我们取字典序最小的那个。（$2 \le k \le n \le 10^4$）
题解
考虑从 $0$ 到 $9$ 枚举每一个数作为目标的相同的数， 求出以它为相同的数时的最少价格与对应车牌，再取这$10$个答案中价格与字典序最小的答案。
以$i$为相同的数的最少价格的求法，需要一点贪心的思想，即：
先从前往后修改每一个找到的 $i + 1$ ，再从后往前修改每一个找到的$i-1$。这样的修改代价是$1$。
先从前往后修改每一个找到的 $i + 2$ ，再从后往前修改每一个找到的$i-2$。这样的修改代价是$2$。
$…$
先从前往后修改每一个找到的 $i + p$ ，再从后往前修改每一个找到的$i-p$。这样的修改代价是$p$。
（先后顺序是因为修改$i+p$使得字典序变小，修改$i-p$使得字典序变大）
在此过程中，每次修改使得相同的数的个数加$1$。如果使得相同的数达到了目标的个数，则退出循环，也就找到了最小的价格。
参考代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int cp[11];
int main(){
int n, k, cur_p, min_p = 1 << 30;
string sign, ans;
cin >> n >> k;
cin >> sign;
string sign_c = sign; // copy一份，枚举时重置sign
for(int i=0; i<n; i++) cp[sign[i]-'0']++; //统计某个数字的个数
for(int i=0; i<=9; i++){
// 从 0 到 9 枚举每一个数作为相同的数， 比较价格
sign = sign_c; cur_p = 0; // cur_p : 当前价格
if(cp[i]>=k){ cout << cur_p << endl << sign; return 0;}
else{
int cur_n = cp[i]; // 当前有几个数字i
int p = 1;
while(cur_n<k){
for(int m=0; m<n; m++){ // 从前往后查找 i + p
if(cur_n >= k) break;
if(sign[m]-'0' == i+p){
sign[m] = char(i+'0');
cur_n++;
cur_p += p;
}
}
for(int m=n-1; m>=0; m--){ // 从后往前查找 i - p
if(cur_n >= k) break;
if(sign[m]-'0' == i-p){
sign[m] = char(i+'0');
cur_n++;
cur_p += p;
}
}
p++;
}
if(cur_p < min_p){ ans = sign; min_p = cur_p;}
if(cur_p == min_p) ans = min(ans, sign);
}
}
cout << min_p << endl << ans;
return 0;
}
连续整数的和(数学，枚举的优化)
给出一个正整数$N$，将$N$写为若干个连续数字和的形式(长度 $\ge$ 2)。例如$N=15$，可以写为$1 + 2 + 3 + 4 + 5$，也可以写为$4 + 5 + 6$，或$7 + 8$。如果不能写为若干个连续整数的和，则输出$No Solution$。
题解
数据比较强，$10^9$。如果使用枚举每一个首项来判断是否能得到和的话，复杂度至少是$O(n\sqrt n)$，会$TLE$。
考虑枚举序列的长度$l$ 。设首项为$x$，由等差数列求和公式，有
\[(2x+l-1)\times l=2n \tag{1}\]从而$l \mid 2n$，且$l\le\sqrt {2n}$。
所以只需枚举$[2,\sqrt{2n}]$中的所有$2n$的约数$l$，再由公式$(1)$直接求出相应的$x$即可。
参考代码
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int n;
bool flag = 1;
cin >> n;
for(int l=sqrt(2*n); l>=2; l--){
if(2*n%l == 0){
int ans = 2*n/l+1-l;
if(ans%2 == 0){
cout << ans/2 << endl;
flag = 0;
}
}
}
if(flag) cout << "No Solution";
return 0;
}
小b学进制(数学，进制，枚举的优化)
(from 51nod)
小b最近在学习进制转化。
对于一个10进制整数n和一个数k，她能快速求出k进制下的n。
如果k进制下的n所有数位都是1，即形如11111111，那么小b就会觉得开心。
现在给定n，请你求出最小的k使得k进制下的n能让小b开心。
题解
暴力每一个$k$能$AC$一半的测试点。。其他$TLE$
我个人觉得这题在 51nod上给的题解还是很麻烦很神的。。代码是抄来的，因为思路就花了很多时间理解，而且代码还挺难写的。。
目前记下的知识点就是 pow(a, x)函数也可以计算 $x=\frac{1}{k}$的情况，即$k$次根号$a$。
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
// sum of (k^0 to k^l)
ld sum(ll k, int l){
ld mul = 1, sum = 1;
for(int i = 1; i <= l; i++){
mul *= k;
sum += mul;
}
return sum;
}
int main(){
ll n, ans = 0;
bool flag = 1;
cin >> n;
for(int l = 60; l > 2; l--){
for(ll k = ll(pow(n, 1.0/l)+0.5); k >= 2; k--){
ld s = sum(k, l);
if(s == n){
cout << k;
flag = 0;
break;
}
if(s < n){
break;
}
}
}
if(flag) cout << n-1;
return 0;
}
[CSP-J2020] 直播获奖
题目描述
NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 $w\%$，即当前排名前 $w\%$ 的选手的最低成绩就是即时的分数线。
更具体地，若当前已评出了 $p$ 个选手的成绩，则当前计划获奖人数为 $\max(1, \lfloor p * w \%\rfloor)$，其中 $w$ 是获奖百分比，$\lfloor x \rfloor$ 表示对 $x$ 向下取整，$\max(x,y)$ 表示 $x$ 和 $y$ 中较大的数。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。
作为评测组的技术人员，请你帮 CCF 写一个直播程序。
（其他信息见洛谷）
题解
写这道题完美踩到了所有可能踩到的坑。
第一遍写自然是想偷懒，用 sort每读入一次都排一次序来模拟。奈何复杂度要上到$O(n^2\log n)$了，对于大一点的数据束手无策，只有$50 pts$。
之后就想到试试插入排序。每一次读入都遍历数组，进行一次插入操作，时间复杂度能降到$O(n^2)$。然而还是只有$85pts$。
结果看了下正解是桶排序，恍然大悟，三分钟就写出来了。因为分数的范围极其小，桶排是最适合的且最快的，$O(n)$。给到的提醒就是先根据数据范围估计时间复杂度，先思考再写才容易写出正解。
参考代码
#include <bits/stdc++.h>
using namespace std;
int scores[601];
int get(int p){
int cnt = 0;
for(int i = 600; i >= 0; i--){
cnt += scores[i];
if(cnt >= p) return i;
}
}
int main(){
int n, w, tmp, p;
scanf("%d%d", &n, &w);
for(int i = 1; i <= n; i++){
scanf("%d", &tmp);
scores[tmp]++;
p = max(1, (i*w/100));
printf("%d ", get(p));
}
return 0;
}
数字1的数量
给定一个十进制正整数N，写下从1开始，到N的所有正数，计算出其中出现所有1的个数。
例如：n = 12，包含了5个1。1,10,12共包含3个1，11包含2个1，总共5个1。
题解
数据给到$10^9$，暴力肯定TLE。可以打表或者DP但不是正解。
给的正解比较数学，枚举每一位是1的情况数，求和即为答案。注意根据当前位的值分类讨论
参考代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int n, ans = 0, d = 1; // d 为 位数
cin >> n;
while(n >= d){
int n1 = n / d;
int n2 = n1 % 10; // 当前枚举到的位
int n3 = n1 / 10; // 前面的位
int n4 = n % d; //后面的位
if(n2 == 1) ans += n3 * d + n4 + 1;
else if(n2 == 0) ans += n3 * d;
else if (n2 >= 2) ans += (n3+1) * d;
d *= 10;
}
cout << ans;
return 0;
}
和为k的倍数
小b喜欢和为K的倍数的序列。
现在有一个长度为n的序列A，请问A有多少个非空连续子序列是小b喜欢的。
题解
思路0 $O(n^3)$
枚举每一个序列，循环求和，判断合法序列数。
思路1 $O(n^2)$
用前缀和来代替循环求和的过程。
思路2 $O(n)$
使用前缀和$sum_i$来维护某个区间的和。
则问题转化为有多少对$(i, j)$，使得$k \mid (sum_j - sum_i)$。
也就是有多少对$(i, j)$，使得$sum_i \equiv sum_j(\mod\ k)$。只需要用 $cnt$ 数组统计同余的数量。其中$cnt_i$记录的 是有几个$sum\mod k=i$。
则答案为$\sum\limits_{i=0}^{k-1}\binom{2}{cnt_i}$。
搬砖块
看了题解之后感觉写的有点麻烦了，不过也还好…长度差不多。题解是用链表来模拟。
复习这题时代码不用看，就是想一想框架。
#include <iostream>
using namespace std;
int bl_pos[26]; // 第i个木块的当前位置为bl_pos[i]
int pos[26][26];// 第i个位置上的第j个块的编号为pos[i][j]
// why do we need the above arrays?
void move(int a, int b){
// what to do?
}
void clear(int a){
// what to do?
}
void print(){
// what to do?
}
int main(){
cin >> n >> m;
string op;
for(int i = 1; i <= n; i++){
// what to do?
}
for(int t = 1; t <= m; t++){
getline(cin, op);
if(op[0] == 'm'){
int a, b;
// ...
// get int(a) and int(b) from (string)op
if(some condition) move(a, b);
}
else{
int a;
// ...
// get (int)a from (string)op
clear(a);
}
}
print();
return 0;
}
多米诺骨牌游戏
有 n 张垂直竖立的多米诺骨牌。我们在某一时刻，同时推到一些骨牌，推的方向或向左或向右。
每过一秒：
倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。
倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。
如果同时有多米诺骨牌落在一张垂直竖立的多米诺骨牌的两边，由于受力平衡， 该骨牌仍然保持不变。
给出骨牌初始时被推向的方向，由你来求出骨牌最终的状态。
输入格式
第一行输入一个数N，表示骨牌的数量（0≤N≤100000） 第二行输入一个长度为N的字符串”S” 表示骨牌状态。如果第 i 张多米诺骨牌被推向左边，则 S[i] = ‘L’；如果第 i 张多米诺骨牌被推向右边，则 S[i] = ‘R’；如果第 i 张多米诺骨牌没有被推动，则 S[i] = ‘.’。
输出格式
输出一个长度为N的字符串，表示骨牌最终状态
输入样例
14
.L.R...LR..L..
输出样例
LL.RR.LLRRLL..
题解
开两个数组。其中$L[i]$和$R[i]$，分别记录第$i$个位置被初始的$L$或$R$推到的时间。时间比较小的那个就是最终状态。时间相同则保持竖立。
#include <iostream>
using namespace std;
const int MAX_N = 100010;
int L[MAX_N], R[MAX_N];
int main(){
int n, cnt = 0;
string str;
cin >> n >> str;
for(int i = 0; i < n; i++){
if(str[i] == 'R') cnt = 1;
else if(str[i] == 'L') cnt = 0;
else if(cnt) cnt++;
R[i] = (cnt == 0 ? MAX_N : cnt);
}
for(int i = n-1; i >= 0; i--){
if(str[i] == 'L') cnt = 1;
else if(str[i] == 'R') cnt = 0;
else if(cnt) cnt++;
L[i] = (cnt == 0 ? MAX_N : cnt);
}
for(int i = 0; i < n; i++){
if(L[i] == R[i]) cout << ".";
else if(L[i] < R[i]) cout << "L";
else cout << "R";
}
return 0;
}
大鱼吃小鱼
有N条鱼每条鱼的位置及大小均不同，他们沿着X轴游动，有的向左，有的向右。游动的速度是一样的，两条鱼相遇大鱼会吃掉小鱼。从左到右给出每条鱼的大小和游动的方向（0表示向左，1表示向右）。问足够长的时间之后，能剩下多少条鱼？
题解
需要思考到这是个有关栈的题目。用栈来模拟鱼的游动，将向右的鱼入栈。每次遇到向左的鱼，把栈顶的所有比它小的向右的鱼出栈。
注意特判一下栈空的情况，说明这个向左的鱼不会被吃掉。所以答案加一。
#include <bits/stdc++.h>
using namespace std;
struct fish{
int rank; bool face;
};
stack <fish> fishes;
int main(){
int n, cnt = 0;
fish tmp;
cin >> n;
for(int i = 1; i <= n; i++){
cin >> tmp.rank >> tmp.face;
if(tmp.face == 1) fishes.push(tmp);
else{
while(!fishes.empty() && fishes.top().rank < tmp.rank){
fishes.pop();
}
if(fishes.size() == 0) cnt++;
}
}
cout << fishes.size() + cnt;
return 0;
}
和为S(前缀和优化)
小b有一个 01 序列 $A$，她想知道 $A$ 有多少个非空连续子序列和为 $S$。
你能帮帮她吗？
题解
暴力枚举区间的$l$和$r$的时间复杂度为$O(n^2)$。
考虑维护一个前缀和变量$sum$和一个计数数组$cnt$。让$cnt_i$记录前缀和为$i$的数的个数。那么只需要遍历数组，将$cnt_{sum-S}$加和即可。时间复杂度为$O(n)$。
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 30005;
int cnt[MAX_N], a[MAX_N];
int main(){
int n, S, num, sum = 0, ans = 0;
cnt[0] = 1;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
cin >> S;
for(int i = 1; i <= n; i++) {
sum += a[i];
if(sum - S >= 0) ans += cnt[sum-S];
cnt[sum]++;
}
cout << ans;
return 0;
}
区间和的和
输入一个长度为$n$的数组$a$，$a$包括$(n+1)n/2$个区间。每个区间所有数的和，被称为区间和，求所有$(n+1)n/2$个区间和的和。由于数值较大，输出$\mod 1e9+7$的结果。
题解
考虑每一个数会被多少个区间覆盖。
对于数组中的某一个数$a_i$，只需要区间的左端点$l$满足$1 \le l \le i$ 且 区间的右端点$r$满足$i \le r \le n$即可。根据乘法原理，共有$i \times (n-i+1)$种选法。
于是答案为$\sum\limits_{i=1}^n [a_i \times i \times (n-i+1)]$ ，复杂度为$O(n)$。
♥