文章目录
- 1. 正确率优先
- 2. 高精度模板
- 3. 前缀和模板 —— 保证不要出现数据0
- 4. 状态转移模板
- 5. 哈希模板
- 6. sqrt()函数 —— 大数 long double 转换
- 7. 直线斜率与截距 —— 利用 a b 关系直接求
- 8. 最短路径模板
- 9. 闰年年月判定模板
- 10. 并查集模板
- 11. 二分模板
- 12. 进制转换细节 —— 如果不是从0 —> x 是不可以直接进制转换的
- 13. 双指针模板 —— 指针位置和所求区间一定要一致
- 14. 审题 —— 边界划分要明确
- 15. 大整数求余 —— 结果保证正数
- 16. 除法操作 —— 除数不能作为0
- 17. 审题 —— 注意限制条件
- xx. 思维题
1. 正确率优先
关键1 —— 正确率优先：题目数量有限，并且无法及时得到结果验证。所以一定要先审题 + 多组测试数据检验(或者直接输出求解过程验证)，正确率永远是第一位的。
一定要首先保证正确率，题目数量有限并且压轴的思维题有难度可以少写两个都无关紧要，正确率永远是第一位。
关键2 —— 审题必须仔细，相关数是否有大小，倍数等要求，结果的输出一般都会要求唯一(按照字典序结果输出等等)， 一定要注意限制条件。
2. 高精度模板
题目描述：
题目链接： 乘积尾0
分析过程：
这个题目的优化思路是将整数进行质因数 2 和 5 的分解，最后去求有多少对完整的2和5就会产生多少个10
但建议能暴力求解的就直接进行暴力求解，因为暴力求解省去了分析思考的过程，这里我们可以直接套用高精度模板进行连乘得到结果.
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
vector<int> mul(vector<int> a, int b){
vector<int> c;
int sum = 0;
for(int i = 0; i < a.size() || sum; i ++ ){
if(i < a.size()) sum += a[i] * b; // 保证范围 < a.size() 才可以乘
c.push_back(sum % 10);
sum /= 10;
}
while(c.size() > 0 && c.back() == 0) c.pop_back(); // 清楚后导0
return c;
}
int main(){
vector<int> v;
v.push_back(1);
for(int i = 0; i < 100; i ++ ){
int x;
cin >> x;
v = mul(v, x);
}
int ret = 0;
for(int i = 0; i < v.size(); i ++ ){
if(v[i] == 0) ret ++;
else break;
}
cout << ret;
return 0;
}
3. 前缀和模板 —— 保证不要出现数据0
题目描述：
题目链接： 递增三元组
分析过程：
总体思路：先求出 sa[x] 表示 a 数组当中小于等于 x 的元素的个数，再去求 sb[x] 表示数组 b 当中小于等于 x 的元素方案数(可以合法连接上a组当中元素)，最后求c 数组直接进行连接即可。
关键：通常我们想要让元素大小从1开始，因为这样我们就不必要对首个元素进行特判处理(如果从0开始不能直接操作 f[x] = f[x] + f[x - 1])，所以我们为了不必要进行特判，所以我们可以让元素全部自加一下，保证最小的元素大小都1.
关键：必须要自加，否则对元素处理的时候会出现错误。例如此题sb[0]是b元素为0能合法连接a的方案数，如果未自加如果b组出现0，sb[0] != 0，这里在之后的递归上面会出现大错误
前缀和为实现元素统一处理(直接从1开始)：保证不要出现数据0
运行代码：
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL sa[N], sb[N];
int main(){
int n, x;
scanf("%d", &n);
for(int i = 0; i < n; i ++ ){
scanf("%d", &x);
sa[++ x] ++;
}
for(int i = 1; i < N; i ++ ) sa[i] += sa[i - 1];
for(int i = 0; i < n; i ++ ){
scanf("%d", &x);
sb[++ x] ++ ;
}
for(int i = 1; i < N; i ++ ) sb[i] = sb[i] * sa[i - 1] + sb[i - 1];
LL ret = 0;
for(int i = 0; i < n; i ++ ){
scanf("%d", &x);
ret += sb[(x + 1) - 1];
}
cout << ret;
return 0;
}
4. 状态转移模板
题目描述：
题目链接： 积木画
分析过程：
关键：f[ i ][ j ] 表示处理完前 i - 1 列 且第 i 列状态为 j 的方案数
关键：列出状态转移的方程 + 枚举状态转移 + 结果往往为f[n + 1][0] (处理完前 n 列)
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
const int mod = 1000000007;
int f[2][4];
int to[4][4] = { // 状态转移
{1, 1, 1, 1},
{0, 0, 1, 1},
{0, 1, 0, 1},
{1, 0, 0, 0}
};
int main(){
int n;
cin >> n;
f[1][0] = 1;
for(int i = 2; i <= n + 1; i ++ ){
memset(f[i & 1], 0, sizeof(f[0])); // 注意清空本层数据
for(int j = 0; j < 4; j ++ ){ // 得到状态 j , 从上层四个状态 k 依次判断能否转换
for(int k = 0; k < 4; k ++ ){
f[i & 1][j] = (f[i & 1][j] + f[i - 1 & 1][k] * to[k][j]) % mod;
}
}
}
cout << f[n + 1 & 1][0]; // 结果一定是处理完前 n 层的结果
return 0;
}
5. 哈希模板
题目描述：
题目链接： 扫雷
分析过程：
关键：将x, y坐标映射成一个唯一的哈希值，记录下该哈希值键对应的炸弹编号和访问状态
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int M = 999997, N = 5e4 + 10;
struct Cir{
int x, y, r;
}cir[N];
LL h[M];
int id[M];
bool st[M];
int sqr(int x){
return x * x;
}
LL get_hash(int x, int y){
return 1000000001ll * x + y;
}
int get_key(int x, int y){
LL hash = get_hash(x, y);
int key = (hash % M + hash) % M;
while(h[key] != -1 && h[key] != hash){
if(++ key == M) key = 0;
}
return key;
}
void dfs(int x, int y, int r){
int key = get_key(x, y);
st[key] = true;
for(int i = x - r; i <= x + r; i ++ ){
for(int j = y - r; j <= y + r; j ++ ){
int key = get_key(i, j);
if(id[key] && !st[key] && sqr(x - i) + sqr(y - j) <= sqr(r)) dfs(i, j, cir[id[key]].r);
}
}
}
int main(){
memset(h, -1, sizeof(h));
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ ){
int x, y, r;
scanf("%d%d%d", &x, &y, &r);
cir[i] = {x, y, r};
int key = get_key(x, y);
h[key] = get_hash(x, y);
if(id[key] == 0 || r > cir[id[key]].r ) id[key] = i;
}
while(m -- ){
int x, y, r;
scanf("%d%d%d", &x, &y, &r);
for(int i = x - r; i <= x + r; i ++ ){
for(int j = y - r; j <= y + r; j ++ ){
int key = get_key(i, j);
if(id[key] && !st[key] && sqr(x - i) + sqr(y - j) <= sqr(r)) dfs(i, j, cir[id[key]].r);
}
}
}
int ret = 0;
for(int i = 1; i <= n; i ++ ){
int key = get_key(cir[i].x, cir[i].y);
if(st[key]) ret ++;
}
cout << ret;
return 0;
}
6. sqrt()函数 —— 大数 long double 转换
题目描述：
题目链接： 砍竹子
分析过程：
关键：大数开根号的时候使用sqrtl()函数，将默认数据类型提到 long double，防止出现误差
关键：也可以使用sqrt()函数，但是要在数之前加入一个long double的强制数据类型转换也可以要不然sqrt()函数本身在c++ 11里面它可以匹配(double, long double)并不会自动提升数据精度
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
#include<cmath>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
LL f[N][10];
int main(){
int n, mx = -1, ret = 0;
scanf("%d", &n);
for(int i = 0; i < n; i ++ ){
LL x, top = 0, stk[10];
scanf("%lld", &x);
while(x > 1) stk[++ top] = x, x = sqrt((long double)(x / 2 + 1));
mx = max(mx, (int)top);
ret += top;
for(int j = 0, k = top; k; j ++ , k --) f[i][j] = stk[k];
}
for(int i = 0; i < mx; i ++ ){
for(int j = 1; j < n; j ++ ){
if(f[j][i] && f[j][i] == f[j - 1][i]) ret --;
}
}
cout << ret;
return 0;
}
7. 直线斜率与截距 —— 利用 a b 关系直接求
题目描述：
题目链接： 直线
分析过程：
关键：求直线的斜率和截距。注意因为浮点数类型本身就会造成误差，所以尽可能使用题目本身的变量直接计算相关结果，不要利用求得的浮点数再去求解结果.
关键：利用 y = k * x + b ，消去 k 得到 b，再消去 b 得到 k， 不要利用间接得到的 k 求 b
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<vector>
using namespace std;
typedef long double LD;
typedef pair<LD, LD> PLL;
set<PLL> s;
bool check(int x1, int y1, int x2, int y2){
LD k = (LD)(y2 - y1) / (x2 - x1);
LD b = (LD)(y1 * x2 - y2 * x1) / (x2 - x1);
if(s.count({k, b}) != 0) {
return false;
}
else{
s.insert({k, b});
return true;
}
}
int main(){
int ret = 20;
for(int i = 0; i < 20; i ++ ){
for(int j = 0; j < 21; j ++ ){
for(int u = 0; u < 20; u ++ ){
for(int v = 0; v < 21; v ++ ){
if(i == u) continue;
else if (check(i, j, u, v)) ret ++;
}
}
}
}
cout << ret;
return 0;
}
8. 最短路径模板
题目描述：
题目链接： 路径
分析过程：
正常情况，正权单源最短路 —— Dijkstra算法直接套用就行了
填空题 —— 可以用Floy去写(运行耗时但代码短)快速得结果
运行代码：
Dijkstra算法
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef pair<int, int> PII;
const int N = 2030;
int h[N], e[N * 50], ne[N * 50], w[N * 50], idx = 0;
long long dis[N];
bool st[N];
int gcm(int x, int y){
return x / __gcd(x, y) * y;
}
void add(int x, int y, int v){
e[++ idx] = y, w[idx] = v, ne[idx] = h[x], h[x] = idx;
}
void Dijkstra(){
priority_queue<PII, vector<PII>, greater<PII> > q;
q.push({0, 1});
dis[1] = 0;
while(!q.empty()){
PII t = q.top();
q.pop();
int x = t.second;
if(st[x]) continue;
st[x] = true;
for(int i = h[x]; ~i; i = ne[i]){
int j = e[i];
if(dis[j] > dis[x] + w[i]){
dis[j] = dis[x] + w[i];
q.push({dis[j], j});
}
}
}
}
int main(){
memset(h, -1, sizeof(h));
memset(dis, 0x3f, sizeof(dis));
for(int i = 1; i <= 2021; i ++ ){
for(int j = i + 1; j <= i + 21 && j <= 2021; j ++ ){
int v = gcm(i, j);
add(i, j, v), add(j, i, v);
}
}
Dijkstra();
cout << dis[2021];
return 0;
}
Floyd算法
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
using namespace std;
typedef long long LL;
const int N = 2030;
LL dis[N][N];
int gcm(int x, int y){
return x / __gcd(x, y) * y;
}
int main(){
memset(dis, 0x3f, sizeof(dis));
for(int i = 1; i <= 2021; i ++ ){
for(int j = i; j <= i + 21 && j <= 2021; j ++ ){
if(i == j) dis[i][j] = 0;
else dis[i][j] = dis[j][i] = gcm(i, j);
}
}
for(int k = 1; k <= 2021; k ++ ){
for(int i = 1; i <= 2021; i ++ ){
for(int j = 1; j <= 2021; j ++ ){
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
}
cout << dis[1][2021];
return 0;
}
9. 闰年年月判定模板
题目描述：
a. 跑步锻炼
b. 回文日期
题目链接： 跑步锻炼 回文日期
分析过程：
关键：掌握闰年判断的代码 和 月日合法判断代码
运行代码：
跑步锻炼
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; // 注意 day[0] = 0;
int main(){
int y = 2000, m = 1, d = 1, ret = 1, wek = 6;
while(true){
if(y == 2020 && m == 10 && d == 2) break;
d ++, wek ++;
bool leap = y % 4 == 0 && y % 100 || y % 400 == 0; // 闰年判断
int mx = (leap && m == 2) ? 29 : day[m]; // 月份最大日期
if(d > mx) m ++, d = 1;
if(m > 12) y ++, m = 1;
if(wek > 7) wek = 1;
if(d == 1 || wek == 1) ret += 2;
else ret += 1;
}
cout << ret;
return 0;
}
回文日期
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int day[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
bool check(int s){
int y = s / 10000, m = s % 10000 / 100, d = s % 100; // 年月日获得
if(m < 1 || m > 12) return false; // 月期合法
bool leap = y % 4 == 0 && y % 100 || y % 400 == 0; // 闰年判断
int mx = (leap && m == 2) ? 29 : day[m];
if(d < 1 || d > mx) return false; // 日期合法
return true;
}
int main(){
int n;
cin >> n;
int ret1 = 0, ret2 = 0;
for(int i = 0; i <= 10000; i ++ ){
int s = i, j = i;
while(j){
s = s * 10 + j % 10;
j /= 10;
}
if(s > n && check(s)){
if(ret1 == 0) ret1 = s;
int c1 = s / 1000000, c2 = s % 1000000 / 10000;
if(c1 == c2){
ret2 = s;
break;
}
}
}
cout << ret1 << endl << ret2;
return 0;
}
10. 并查集模板
题目描述：
题目链接： 七段码
分析过程：
依次枚举每个状态 + 状态当中并查集判断是否存在唯一的集体
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int f[10];
int k[7][7] = {
{0, 1, 0, 0, 0, 1, 0},
{1, 0, 1, 0, 0, 0, 1},
{0, 1, 0, 1, 0, 0, 1},
{0, 0, 1, 0, 1, 0, 0},
{0, 0, 0, 1, 0, 1, 1},
{0, 0, 0, 0, 1, 0, 1},
{0, 1, 1, 0, 1, 1, 0}
};
int find(int x){ // 并查集模板
return x == f[x] ? x : f[x] = find(f[x]);
}
bool check(int s){
for(int i = 0; i < 7; i ++ ) f[i] = i; // 并查集初始化
for(int i = 0; i < 7; i ++ )
for(int j = i + 1; j < 7; j ++ )
if(k[i][j] && s >> i & 1 && s >> j & 1){
int fi = find(i), fj = find(j);
f[fi] = fj;
}
int sum = 0;
for(int i = 0; i < 7; i ++ )
if(f[i] == i && (s >> i & 1)) sum ++;
if(sum == 1) return true;
else return false;
}
int main(){
int ret = 0;
for(int i = 1; i < (1 << 7); i ++ ){
if(check(i)) ret ++;
}
cout << ret;
return 0;
}
11. 二分模板
题目描述：
题目链接： 杨辉三角形
分析过程：
对称 + 斜着寻找每一斜列结果 + 二分搜索
二分模板 ：当最后区间大小为2时，一定要测试判断 mid = l + r + 1 >> 1是否需要 + 1这个操作，能否跳出最终的循坏
二分模板 ：当一组有多个答案，想要靠左的答案 mid = l + r >> 1，想要靠右位置的答案一般 mid = l + r + 1 >> 1
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
int x;
LL C(int a, int b){
LL ret = 1;
for(LL i = a, j = 1; j <= b; i --, j ++ ){
ret = ret * i / j;
if(ret > x) return ret;
}
return ret;
}
int main(){
cin >> x;
LL n, m;
for(int i = 16; i >= 0; i -- ){
LL l = i * 2, r = x;
while(l < r){ // 二分模板: 先写 l 和 r 再回头来判断 mid 是否需要 + 1 操作
LL mid = l + r >> 1;
if(C(mid, i) >= x) r = mid;
else l = mid + 1;
}
if(C(l, i) == x){
cout << (1 + l) * l / 2 + i + 1;
break;
}
}
return 0;
}
12. 进制转换细节 —— 如果不是从0 —> x 是不可以直接进制转换的
题目描述：
题目链接： 年号字串
分析过程：
关键：因为不是从0开始的进制，所以一般是没有规律的.
对于填空题：直接暴力搜结果即可，对于 0 的存在进行特判即可
对于程序题：对每个位进行特判处理不能为0即可。
运行代码：
填空题 —— 暴力结果
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
int main(){
// 2019 = 2 * 26 * 26 + 25 * 26 + 17; // 不含数字0, 所以不需要处理
string s = "";
s += ('A' - 1 + 2);
s += ('A' - 1 + 25);
s += ('A' - 1 + 17);
cout << s;
return 0;
}
程序题 —— 特判处理每个位(保证没有0的存在)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 10;
int ret[N];
int main(){
int k = 2019;
for(int i = 0; k; i ++ ){
if(k % 26 == 0){ // 余数为0，用'Z'填充
k -= 26;
ret[i] = 26;
}
else ret[i] = k % 26;
k /= 26;
}
string s = "";
for(int i = 0; ret[i] != 0; i ++ )
s += (ret[i] - 1 + 'A');
reverse(s.begin(), s.end());
cout << s;
return 0;
}
13. 双指针模板 —— 指针位置和所求区间一定要一致
题目描述：
题目链接： 统计子矩阵
分析过程：
首先前缀和每一列的区间和, 然后遍历两个横坐标，纵坐标可以用双指针完成
关键：指针移动得到结果的区间一定要和指针位置保持一致，要注意左右指针的自加自减的位置.
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
int s[N][N];
int main(){
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= n; i ++ ){
for(int j = 1;j <= m; j ++ ){
scanf("%d", &s[i][j]);
s[i][j] += s[i - 1][j];
}
}
long long ret = 0;
for(int u = 1; u <= n; u ++ )
for(int d = u; d <= n; d ++ ){ /* 一定要注意左右区间指针的处理 */
int sum = 0;
for(int i = 1, j = 0; i <= m; i ++ ){
while(j <= m && sum <= k){ // 先让 j ++ ，保证 i - j 指针指向 i - j 区间对应
j ++;
sum += s[d][j] - s[u - 1][j];
}
ret += j - i;
sum -= s[d][i] - s[u - 1][i]; // 处理左区间就是先处理，再 i ++
}
}
cout << ret;
return 0;
}
14. 审题 —— 边界划分要明确
题目描述：
题目链接： 螺旋折线
分析过程：
找规律进行划分，对于每个边界位置点一定要精确划分到某一部分当中(如果没有精确划分到某一个部分，求解的时候可能会在其他方程当中求解到此位置造成误差)
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
void solve(LL x, LL y){ // 以左上角端点进行每一层的划分
LL k = max(abs(x), abs(y));
LL ret = 4 * k * k;
if(x == k || y == -k) ret += abs(k - x) + abs(k - y);
else ret -= abs(k - x) + abs(k - y);
cout << ret;
return ;
}
int main(){
LL x, y;
cin >> x >> y;
solve(x, y);
return 0;
}
15. 大整数求余 —— 结果保证正数
题目描述：
题目链接： x进制减法
分析过程：
在每一位取最小进制的条件下不断进行求解即可
关键：因为在求解过程当中可能存在某位a[] - b[]为负数，尤其是不同的代码(先对每位结果求余再进行求和操作会出现错误，先求和则不会)最后可能导致结果出现负数的存在(所以涉及求余的结果计算的时候要保证求余完结果为正数)
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, mod = 1000000007;
int a[N], b[N];
int main(){
int k, n, m;
scanf("%d", &k);
scanf("%d", &n);
for(int i = n - 1; i >= 0; i -- )
scanf("%d", &a[i]);
scanf("%d", &m);
for(int i = m - 1; i >= 0; i -- )
scanf("%d", &b[i]);
LL p = 1, sum = 0, mx = max(n, m);
for(int i = 0; i < mx; i ++ ){
sum = (sum + 1ll * (a[i] - b[i]) * p) % mod;
k = max(2, max(a[i], b[i]) + 1);
p = p * k % mod;
}
cout << (sum + mod) % mod; // cout << sum; 也可以过
return 0;
}
/*
// 如果这样子写，可能导致 t 出现负数带入sum，然后之后的高位的值被取余较小无法将负数带回正数导致错误
// 这个样子写就需要对答案进行 (sum + mod) % mod;
for(int i = 0; i < mx; i ++ ){
LL t = (a[i] - b[i]) * p % mod;
sum = (sum + t) % mod;
k = max(2, max(a[i], b[i]) + 1);
p = p * k % mod;
}
*/
16. 除法操作 —— 除数不能作为0
题目描述：
题目链接： 等差数列
分析过程：
关键：求差值之间的gcd
关键：当除数为0时要进行特判处理
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int a[N];
int main(){
int n;
scanf("%d", &n);
for(int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
int d = 0;
sort(a, a + n);
for(int i = 1; i < n; i ++ ){
d = __gcd(d, a[i] - a[i - 1]);
}
if(d == 0) cout << n; // 对 0 进行特判处理
else cout << (a[n - 1] - a[0]) / d + 1;
return 0;
}
17. 审题 —— 注意限制条件
1. 题目描述：
题目链接： 砝码称重
分析过程：
类似于背包，注意转移过程方程.
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 110, M = 1e5 + 10;
int f[N][M], w[N];
int main(){
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);
f[0][0] = 1;
for(int i = 1; i <= n; i ++ ){
for(int j = 0; j < M; j ++ ){
f[i][j] = f[i - 1][j];
f[i][j] |= f[i - 1][abs(j - w[i])];
if(j + w[i] < M) f[i][j] |= f[i - 1][j + w[i]];
}
}
int ret = 0;
for(int i = 1; i < M; i ++ )
if(f[n][i]) ret ++;
cout << ret;
return 0;
}
2. 题目描述：
题目链接： 数的分解
分析过程：
审题清楚 —— 注意数字有大小和倍数要求
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
bool check(int x){
while(x){
int t = x % 10;
if(t == 2 || t == 4) return false;
x /= 10;
}
return true;
}
int main(){
int ret = 0, k = 2019;
for(int i = 1; i <= 2019; i ++ )
for(int j = i + 1; j <= 2019; j ++ )
for(int u = j + 1; u <= 2019; u ++ ){
if(i + j + u == k && check(i) && check(j) && check(u)) ret ++;
}
cout << ret; // 40785
return 0;
}
3. 题目描述：
题目链接： 迷宫
分析过程：
审题清楚 —— 结果要求字典序
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef pair<pair<int, int>, string> PPS;
const int N = 35, M = 55; // D L R U
char s[N][M], ds[] = {'D', 'L', 'R', 'U'};
bool st[N][M];
int dx[] = {1, 0, 0, -1}, dy[] = {0, -1, 1, 0};
void bfs(){
queue<PPS> q;
q.push({{1, 1}, ""});
st[1][1] = true;
while(!q.empty()){
PPS t = q.front();
q.pop();
int x = t.first.first, y = t.first.second;
string path = t.second;
if(x == 30 && y == 50){
cout << path;
return ;
}
for(int i = 0; i < 4; i ++ ){
int x2 = x + dx[i], y2 = y + dy[i];
if( s[x2][y2] == '0' && !st[x2][y2]){
string path2 = path + ds[i];
q.push({{x2, y2}, path2});
st[x2][y2] = true;
}
}
}
}
int main(){
for(int i = 1; i <= 30; i ++ )
scanf("%s", s[i] + 1);
bfs();
return 0;
}
xx. 思维题
1. 题目描述：
题目链接： 测试次数
分析过程：
若有多个手机可以区间测(枚举中间层数)，单个手机只能从低层开始测
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int f[5][N]; // f[i][j] i台手机，j层楼最小测试次数
int main(){
for(int i = 1; i <= 1000; i ++ ) f[1][i] = i;
for(int k = 2; k <= 3; k ++ ){
for(int i = 1; i <= 1000; i ++ ){
int mx = 1010, st = -1;
for(int j = 1; j <= i; j ++ ){
f[k][i] = max(f[k - 1][j - 1], f[k][i - j]) + 1;
if(f[k][i] < mx) mx = f[k][i];
}
f[k][i] = mx;
}
}
2. 题目描述：
题目链接：字串排序
分析过程：
元素均匀排布含字典序最多(zzyyxx…ccbbaa)。首先求出合法序列最短长度，再从从依次自小到大枚举同时判断当右边剩余部分取最大逆序对时是否满足条件，依次枚举得到最小字母即可.
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 30;
int cnt[N], ret, len, v, cnt_back[N];
int check(int k){
int x = (k % 26) * (k / 26 + 1) * (k - (k / 26 + 1));
int y = (26 - k % 26) * (k / 26) * (k - k / 26);
return (x + y) / 2;
}
bool solve(int x, int n){
int add1 = 0, add2 = 0;
for(int i = x + 1; i < 26; i ++ ) add1 += cnt[i];
cnt[x] ++;
memset(cnt_back, 0, sizeof(cnt_back));
for(int i = 0; i < n; i ++ ){
int mx = -1, ps = -1, sum = 0;
for(int j = 25; j >= 0; j -- ){
sum = sum + cnt[j + 1];
if(sum + i - cnt_back[j] > mx){
mx = sum + i - cnt_back[j];
ps = j;
}
}
add2 += mx, cnt_back[ps] ++;
}
if(ret + add1 + add2 >= v){
ret += add1;
return true;
}
else{
cnt[x] --;
return false;
}
}
int main(){
cin >> v;
for(int i = 1; ; i ++ ){
if(check(i) >= v){
len = i;
break;
}
}
string s = "";
for(int i = 1; i <= len; i ++ ){
for(int j = 0; j < 26; j ++ ){
if(solve(j, len - i)){
s += ('a' + j);
break;
}
}
}
cout << s;
return 0;
}
3. 题目描述：
题目链接： 括号序列
分析过程：
结果左括号和右括号互不干扰，互相单独求解再将结果相乘.
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const int N = 5010, mod = 1e9 + 7;
char s[N];
LL f[N][N], n;
LL clac(){
memset(f, 0, sizeof(f));
f[0][0] = 1;
for(int i = 1; i <= n; i ++ ){
if(s[i] == '('){
for(int j = 1; j <= n; j ++ ) f[i][j] = f[i - 1][j - 1];
}
else{
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
for(int j = 1; j <= n; j ++ )
f[i][j] = (f[i - 1][j + 1] + f[i][j - 1]) % mod;
}
}
for(int i = 0; i <= n; i ++ )
if(f[n][i]) return f[n][i];
}
int main(){
scanf("%s", s + 1);
n = strlen(s + 1);
LL l = clac();
reverse(s + 1, s + 1 + n);
for(int i = 1; i <= n; i ++ ){
if(s[i] == '(') s[i] = ')';
else s[i] = '(';
}
LL r = clac();
printf("%lld", l * r % mod);
return 0;
}
4. 题目描述：
题目链接： 双向排序
分析过程：
找规律：两种操作必须交替出现并且相同类型操作长度必须递减
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
typedef pair<int, int> PII;
PII stk[N];
int ret[N], top = 0;
int main(){
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i ++ ){
int p, q;
scanf("%d%d", &p, &q);
if(p == 0){ // 降序
while(top && stk[top].x == 0) q = max(q, stk[top -- ].y);
while(top >= 2 && stk[top - 1].y < q) top -= 2;
stk[++ top] = {p, q};
}
else if(top){
while(top && stk[top].x == 1) q = min(q, stk[top --].y);
while(top >= 2 && stk[top - 1].y > q) top -= 2;
stk[++ top] = {p, q};
}
}
int l = 1, r = n, k = n;
for(int i = 1; i <= top; i ++ ){
int p = stk[i].x , q = stk[i].y;
if(p == 0){
while(l <= r && r > q) ret[r -- ] = k --;
}
else{
while(l <= r && l < q) ret[l ++ ] = k --;
}
}
if(top % 2){
while(l <= r) ret[l ++ ] = k --;
}
else{
while(l <= r) ret[r -- ] = k --;
}
for(int i = 1; i <= n; i ++ ){
if(i == n) cout << ret[i];
else cout << ret[i] << ' ';
}
return 0;
}
5. 题目描述：
题目链接： 子串分值和
分析过程：
将字符分为第一次出现和之后出现进行考虑
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
char s[N];
int f[30];
int main(){
scanf("%s", s + 1);
int n = strlen(s + 1);
LL ret = 0;
for(int i = 1; i <= n; i ++ ){
int l = i - f[s[i] - 'a'];
int r = n - i + 1;
f[s[i] - 'a'] = i;
ret += 1ll * l * r;
}
cout << ret;
return 0;
}
6. 题目描述：
题目链接： 后缀表达式
分析过程：
分为存在负号和不存在负号进行分别考虑
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int a[N];
int main(){
int n, m;
scanf("%d%d", &n, &m);
LL s = 0, ret = 0;
for(int i = 0; i < n + m + 1; i ++ ){
scanf("%d", &a[i]);
s = s + abs(a[i]);
ret = ret + a[i];
}
if(m){
sort(a, a + n + m + 1);
s = s - abs(a[0]) - abs(a[n + m]);
s = s + a[n + m] - a[0];
ret = s;
}
cout << ret;
return 0;
}
7. 题目描述：
题目链接： 灵能传输
分析过程：
前缀和分析
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
typedef long long LL;
const int N = 300010;
LL a[N], s[N];
bool st[N];
int main(){
int T;
scanf("%d", &T);
while(T -- ){
memset(st, false, sizeof(st));
s[0] = 0;
int n;
scanf("%d", &n);
for(int i = 1; i <= n; i ++ ){
scanf("%lld", &s[i]);
s[i] += s[i - 1];
}
LL s0 = s[0], sn = s[n];
if(s0 > sn) swap(s0, sn);
sort(s, s + n + 1);
for(int i = 0; i <= n; i ++ ){
if(s[i] == s0){
s0 = i;
break;
}
}
for(int i = n; i >= 0; i -- ){
if(s[i] == sn){
sn = i;
break;
}
}
int l = 0, r = n;
for(int i = s0; i >= 0; i -= 2){
a[l ++ ] = s[i];
st[i] = true;
}
for(int i = sn; i <= n; i += 2 ){
a[r -- ] = s[i];
st[i] = true;
}
for(int i = 0; i <= n; i ++ ){
if(!st[i]) a[l ++ ] = s[i];
}
LL ret = 0;
for(int i = 1; i <= n; i ++ ){
ret = max(ret, abs(a[i] - a[i - 1]));
}
cout << ret << endl;
}
return 0;
}
8. 题目描述：
题目链接： 平面切分
分析过程：
结论: 每增加一条直线，对平面数的贡献值是其与先前直线的交点数（不重合）+1
涉及精度处理全部使用long double 处理.(保证不出问题)
运行代码：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
typedef pair<long double,long double> PDD;
typedef long long LL;
const int N = 1010;
int k[N], b[N], top = 0;
int main(){
int n;
set<pair<int, int> > s;
scanf("%d", &n);
for(int i = 0; i < n; i ++ ){
int x, y;
scanf("%d%d", &x, &y);
s.insert({x, y});
}
set<pair<int, int> > :: iterator it;
for(it = s.begin(); it != s.end(); it ++ ){
k[top] = it -> first;
b[top ++ ] = it -> second;
}
LL ret = 2;
for(int i = 1; i < top; i ++ ){
set<PDD> s;
for(int j = 0; j < i; j ++ ){
if(k[i] == k[j]) continue;
long double x = (long double)(b[j] - b[i]) / (k[i] - k[j]);
long double y = (long double)(b[i] * k[j] - b[j] * k[i]) / (k[j] - k[i]);
s.insert({x, y});
}
ret += (s.size() + 1);
}
cout << ret;
return 0;
}