百题 其三

1.遇到翻转之类的，优先想到字符串

P5705 【深基2.例7】数字反转 - 洛谷

可以直接用string，reverse（）来搞

1
2
3
4
5
6
7
8
9
10
11
#include<bits/stdc++.h>

using namespace std;

int main(){
	string s;
	cin>>s;
	reverse(s.begin(),s.end());
	cout<<s; 
	return 0;
}

2.P5707 【深基2.例12】上学迟到 - 洛谷

1
//这里要注意的是，走不满一分钟也算一分钟，所以向上取整，以后可直接用(s + v - 1) / v这只是向上取整，不是四舍五入（用三目可以做）

3.P5717 【深基3.习8】三角形分类 - 洛谷

1
//判断三角形的成立，排序a<=b<=c---->只要a+b>c就可，这是最苛刻的条件

4.日期的题目有时候别想复杂了，直接枚举%就好

5.P1980 [NOIP 2013 普及组] 计数问题

1
2
3
4
5
//这道题我的思路是把数字转化为字符串直接拼接
但是如果用i+'0'来做，遇到i>=10的会变成对应ascll码值的字符
所以用to_string()这个函数来搞
string s='';
s+=to_string(i);

6.回文

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//回文数在大量且不知位数下可以这样
int h(int x){
	string s=to_string(x);
	int r=s.size()-1;
	int l=0;
	while(l<r){
		if(s[r]!=s[l]){
			return 0;
		}
		l++;
		r--;
	}
	return 1;
}

7.对数字的各种操作可以转换为字符串来做

8.斐波那契数列这类递归但有数字规律操作超时时，可以用数组记忆来优化

1
2
3
4
5
6
long long fib[100]={0};  //假设n不超过100
long long fac1(int n){
    if(n<=2) return 1;
    if(fib[n]!=0) return fib[n];  //如果已经计算过，直接返回
    return fib[n]=fac1(n-1)+fac1(n-2);  //计算并存储结果
}

image-20250512190504183

速度快了一倍

9.遇到区间问题，对区间进行重复之类操作的要想一下差分

10.遇到旋转数字回旋矩阵，可以定义方向数组，然后循环范围到矩阵面积，如果越界或者不为初值了就转向

11.遇到换行输入且没有给输入数据范围的题，可以：

1
2
3
4
5
6
7
vector<string>s;
	int len=0;
	string x;
	while(cin>>x){
		s.push_back(x);
		len++;
	}
  • 在OJ评测系统或文件重定向时，输入结束自动触发 EOF，循环会结束。
  • Windows：输入完所有数据后，按下 Ctrl + Z，然后回车

能不能在不改动运行后的完整功能的情况下，把所有函数改一下，换一种方法来，我用的是dev c++5.11，原本的图片该是什么还得是什么，不用修改

12.遇到寻找子串在大字符串的位置时，可以用find函数返回第一次出现的位置，如果出现了，就会返回，否则，会返回一个很大的数字string::npos

这时我们可以if(find(s1)==string::npos) cout<<1;

1
2
3
int pos = s.find(s1);
if(pos != string::npos) cout << pos << endl;
else cout << -1 << endl;

13..[P1308 NOIP 2011 普及组] 统计单词数 - 洛谷

如果遇到在字符串中查找很多子串的数量，可以先用find找到（string之间），然后确认，记录光标后，替换光标，再次用find找，遇到要寻找不论大小写的子串，可以把2个串同时搞成大写或者小写，用tolower或者toupper来，读一整行用getline（cin,s）;—》注意前面的回车，用getchar()搞下

14.[P12133 蓝桥杯 2025 省 B] 产值调整 - 洛谷

不断地取平均值会使几个数的极差越来越小，据此，可以如果几者相等就退出，不然会超时

15.高精度乘和高精度加

通：
1.就是把每个数先用string字符串读入，然后存入int数组里面（可以用vector），然后对两个数组进行高精度操作

2.对每一位进行是否进位的操作：（以加法为例）

1
2
3
4
5
6
7
8
9
for(int i=0;i<a.size()||i<b.size();++i){
	int t;
    if(i<a.size()) t+=a[i];
    if(i<a.size()) t+=b[i];
    c.push_back(t%10);//这里处理进位
    t/=10;
}
if(t) c.push_back(1);//处理最后进位，前面的进位都已经好了

阶乘问题：可以转换为大数*整数（大数 * 大数好麻烦）

16.求某些几+几==几的条件判断时，可以用倒序的方式，而且要注意题目是否允许出现重复

[P2141 NOIP 2014 普及组] 珠心算测验 - 洛谷

17.遇到一系列的数，给定一个极限，要求这一系列数组合来求最少数组合问题，可以倒序，先排序，然后从大到小来思考

[P2676 USACO07DEC] Bookshelf B - 洛谷

18.sort中的cmp是个bool类型返回值的参量，所以设置比较函数的时候数据类型要设置为bool，然后return要大于或者小于的比较

P1781 宇宙总统 - 洛谷

1
2
3
4
bool cmp(stu&a,stu&b){
	if(a.s.size()==b.s.size())return a.s>b.s;
    return a.s.size()>b.s.size();
}

19[P1012 NOIP 1998 提高组] 拼数 - 洛谷

这道题可以用排序，定义结构体，不过这题是把字符串拼接后来比较，字符串的比较（string）直接用大于小于就好，字符数组用strcmp

1
2
3
bool cmp(const node& a, const node& b) {
    return a.val + b.val > b.val + a.val;
}