展示型网站建设的标准,教育机构做网站素材,东莞制作企业网站,如何 网站收录情况文章目录#x1f4ac;前言#x1f332;day192. 递归实现指数型枚举843. n-皇后问题#x1f332;day2日志统计1209. 带分数#x1f332;day3844. 走迷宫1101. 献给阿尔吉侬的花束#x1f332;day41113. 红与黑#x1f332;day51236. 递增三元组#x1f332;day63491. 完全…
文章目录前言day192. 递归实现指数型枚举843. n-皇后问题day2日志统计1209. 带分数day3844. 走迷宫1101. 献给阿尔吉侬的花束day41113. 红与黑day51236. 递增三元组day63491. 完全平方数[简单数论]day7466. 回文日期前言 第一周从最高频-分数占比最高开始练习涉及算法标签[⚽️DFS,⚽️BFS,⚽️日期问题,⚽️哈希统计] DFS乃是暴力搜索的基础,BFS常用于解决迷宫问题,日期问题可以视为常规题 ⏳最后三个星期大家一起冲刺祝大家rp 如果对您有帮助的话还请动动小手 点赞收藏⭐️关注❤️ day1
92. 递归实现指数型枚举
从 1∼n 这 n 个整数中随机选取任意多个输出所有可能的选择方案。
输入格式 输入一个整数 n。
输出格式 每行输出一种方案。
同一行内的数必须升序排列相邻两个数用恰好 1 个空格隔开。
对于没有选任何数的方案输出空行。
本题有自定义校验器SPJ各行不同方案之间的顺序任意。
数据范围 1≤n≤15 输入样例
3输出样例
3
2
2 3
1
1 3
1 2
1 2 3[按选取个数的枚举所有情况]- 选0~n个
#includeiostreamusing namespace std;const int N 20;
int n;
bool st[N];
int q[N];void dfs(int u, int start, int m) //当前位置u start开始选择升序填数 填满m个数结束分支
{if(u m){for(int i 0; i m; i) printf(%d , q[i]);puts();}for(int i start; i n; i){if(!st[u]){q[u] i;st[u] true;dfs(u 1, i 1, m);st[u] false;}}
}int main()
{scanf(%d, n);for (int i 0; i n; i ) //填满任意个数 - 枚举位数dfs(0, 1, i); return 0;
}算法枚举到第u位前面每一位选或不选 三种状态st[] 0,未枚举此位; st[] 1此位选, st[] 2此位不选
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 16;int n;
int st[N]; // 状态记录每个位置当前的状态0表示还没考虑1表示选它2表示不选它void dfs(int u)
{if (u n){for (int i 1; i n; i )if (st[i] 1)printf(%d , i);puts();return; //必须return【当做好习惯】}st[u] 2;dfs(u 1); // 第一个分支不选st[u] 0; // 恢复现场st[u] 1;dfs(u 1); // 第二个分支选st[u] 0;
}int main()
{cin n;dfs(1);return 0;
}843. n-皇后问题
n−皇后问题是指将 n 个皇后放在 n×n 的国际象棋棋盘上使得皇后不能相互攻击到即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数 n请你输出所有的满足条件的棋子摆法。
输入格式 共一行包含整数 n。
输出格式 每个解决方案占 n 行每行输出一个长度为 n 的字符串用来表示完整的棋盘状态。
其中 . 表示某一个位置的方格状态为空Q 表示某一个位置的方格上摆着皇后。
每个方案输出完成后输出一个空行。
注意行末不能有多余空格。
输出方案的顺序任意只要不重复且没有遗漏即可。
数据范围 1≤n≤9 输入样例 4 输出样例
.Q..
...Q
Q...
..Q...Q.
Q...
...Q
.Q..正对角线 y -x b 与 副对角线y x b (b为截距枚举) 判断截距b是否被选择 正对角线 b x y u i 副对角线b (-x y) % n 【映射[0,n-1]】 -u i n : [注意加n为了防止负数超出数组范围]** 按行枚举 - u当前行
#include iostreamusing namespace std;const int N 20;int n;//棋盘大小-n皇后
char g[N][N];//棋盘
bool col[N], dg[N], udg[N];//列 正对角线 反对角线void dfs(int u) // u为x
{if (u n){for (int i 0; i n; i ) puts(g[i]);//简用puts(输出一行 换行)puts();return;}for (int i 0; i n; i )//按行枚举 [u行][i列] u为x, i为yif (!col[i] !dg[u i] !udg[n - u i]) //列标记 对角线截距标记{g[u][i] Q;//()col[i] dg[u i] udg[n - u i] true;dfs(u 1);col[i] dg[u i] udg[n - u i] false;g[u][i] .;}
}int main()
{scanf(%d, n);for (int i 0; i n; i )for (int j 0; j n; j )g[i][j] .;dfs(0);return 0;
}第二种搜索顺序
#include iostreamusing namespace std;const int N 10;int n;
bool row[N], col[N], dg[N * 2], udg[N * 2]; //注意行列都要边标记
char g[N][N];void dfs(int x, int y, int s) //s统计已放皇后个数
{if (s n) return;if (y n) y 0, x ; //每行按列搜索 (每行搜索完需换到下一行)if (x n) //说明搜索到了终点(上一个y换行前(x, y)为(n - 1, n - 1):已经遍历完){if (s n) //如果放入个数为n, 说明成功输出答案{for (int i 0; i n; i ) puts(g[i]);puts();}return;}g[x][y] .;dfs(x, y 1, s); if (!row[x] !col[y] !dg[x y] !udg[x - y n]){row[x] col[y] dg[x y] udg[x - y n] true;g[x][y] Q;dfs(x, y 1, s 1); //每行按列遍历g[x][y] .;row[x] col[y] dg[x y] udg[x - y n] false;}
}int main()
{scanf(%d, n);dfs(0, 0, 0);return 0;
}day2
日志统计
小明维护着一个程序员论坛。现在他收集了一份”点赞”日志日志共有 N 行。
其中每一行的格式是
ts id 表示在 ts 时刻编号 id 的帖子收到一个”赞”。
现在小明想统计有哪些帖子曾经是”热帖”。
如果一个帖子曾在任意一个长度为 D 的时间段内收到不少于 K 个赞小明就认为这个帖子曾是”热帖”。
具体来说如果存在某个时刻 T 满足该帖在 [T,TD) 这段时间内(注意是左闭右开区间)收到不少于 K 个赞该帖就曾是”热帖”。
给定日志请你帮助小明统计出所有曾是”热帖”的帖子编号。
输入格式 第一行包含三个整数 N,D,K。
以下 N 行每行一条日志包含两个整数 ts 和 id。
输出格式 按从小到大的顺序输出热帖 id。
每个 id 占一行。
数据范围 1≤K≤N≤105, 0≤ts,id≤105, 1≤D≤10000 输入样例 7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3 输出样例 1 3 双指针[j,i]理解为滑动窗口 维护大小为d的窗口
//有重复统计就有优化【类似滑动窗口进去一个出来一个】
#include cstdio
#include cstring
#include iostream
#include algorithm#define x first
#define y secondusing namespace std;typedef pairint, int PII; const int N 100010;int n, d, k;
PII logs[N]; // (ts,id)
int cnt[N];
bool st[N]; // 记录每个帖子是否是热帖int main()
{scanf(%d%d%d, n, d, k);for (int i 0; i n; i ) scanf(%d%d, logs[i].x, logs[i].y);sort(logs, logs n);//【按时间ts排序】for (int i 0, j 0; i n; i )//[j, i]区间长度 d{int id logs[i].y; cnt[id] ; //统计区间内对应id收到的赞while (logs[i].x - logs[j].x d) //if(i位置当前赞 - j位置前一次赞 d时间跨度[区间长度限制]) j向前移动 【看做滑动窗口理解,窗口大小 d】{cnt[logs[j].y] -- ;//j向前移动位置 ,原本的j位置出窗口, i在循环中i [类比最长连续不重复子序列]j ;}if (cnt[id] k) st[id] true; //id在满足小于时间跨度[区间长度限制]d获得k个赞}for (int i 0; i 100000; i )//输出满足热度的帖子的idif (st[i])printf(%d\n, i);return 0;
}1209. 带分数
100 可以表示为带分数的形式100369258714 还可以表示为100823546197 注意特征带分数中数字 1∼9 分别出现且只出现一次不包含 0。
类似这样的带分数100 有 11 种表示法。
输入格式 一个正整数。
输出格式 输出输入数字用数码 1∼9 不重复不遗漏地组成带分数表示的全部种数。
数据范围 1≤N10610^6106 输入样例1 100 输出样例1 11 输入样例2 105 输出样例2 6
//y总思路全排列 划分枚举a、c判断b是否成立 等式 n a b / c
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 10;int n;
bool st[N], backup[N];
int ans;bool check(int a, int c)//检查b等式是否成立
{ //可以开个全局LLlong long b n * (long long)c - a * c; //n a b / c 鉴于int向上取整,两边同乘c避开int特性: n * (long long c) a * c bif (!a || !b || !c) return false; //a,b,c中含有0falsememcpy(backup, st, sizeof st); //使用备份数组复制原标记数组while (b){int x b % 10; // 取个位b / 10; // 个位删掉if (!x || backup[x]) return false; //x不为0且x被标记过a或c已经使用则b不能选此数falsebackup[x] true;}for (int i 1; i 9; i )//1-9没有全部用上falseif (!backup[i])return false;return true;
}void dfs_c(int u, int a, int c) //当前位u a的值 c的值
{if (u 9) return;if (check(a, c)) ans ;for (int i 1; i 9; i )if (!st[i]){st[i] true;dfs_c(u 1, a, c * 10 i);st[i] false;}
}void dfs_a(int u, int a)//枚举a
{if (a n) return; //a n 等式不成立剪枝if (a) dfs_c(u, a, 0); for (int i 1; i 9; i )if (!st[i]){st[i] true;dfs_a(u 1, a * 10 i); //判断下一组aa加位数st[i] false;}
}int main()
{cin n;dfs_a(0, 0);cout ans endl;return 0;
}next_permutation
#include bits/stdc.h
using namespace std;
int num[10] {1,2,3,4,5,6,7,8,9}; //[1-9]
int cnt;int get(int l,int r) //区间[l, r]组成一个数
{int sum 0;for(int i l; i r; i){sum sum * 10 num[i];}return sum;
}int main()
{int n;cin n;while(next_permutation(num, num 9)) //【全排列】{for(int i 0;i 9; i) //枚举a的位数{int a get(0, i);for(int j i 1; j 9; j) //枚举b与c的分界位数{int b get(i 1, j); int c get(j 1, 8);if(n * c a * c b){cnt ;}}}}cout cnt;return 0;
}day3
844. 走迷宫
给定一个 n×m 的二维整数数组用来表示一个迷宫数组中只包含 0 或 1其中 0 表示可以走的路1 表示不可通过的墙壁。
最初有一个人位于左上角 (1,1) 处已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
请问该人从左上角移动至右下角 (n,m) 处至少需要移动多少次。
数据保证 (1,1) 处和 (n,m) 处的数字为 0且一定至少存在一条通路。
输入格式 第一行包含两个整数 n 和 m。
接下来 n 行每行包含 m 个整数0 或 1表示完整的二维数组迷宫。
输出格式 输出一个整数表示从左上角移动至右下角的最少移动次数。
数据范围 1≤n,m≤100 输入样例
5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0输出样例
8#include bits/stdc.h#define x first
#define y secondusing namespace std;typedef pairint, int PII;const int N 110;int n, m;int g[N][N], d[N][N]; //不用标记st【d[][] -1 未走过】
PII q[N * N];//空间大小N * N 组坐标元素int bfs() //宽搜从(0, 0)走到终点(n-1, m-1)
{int hh 0, tt -1;// memset(d, -1, sizeof d);int dx[] {-1, 0, 1, 0}, dy[] {0, 1, 0, -1};d[0][0] 0;q[ tt] {0, 0};while(hh tt){auto t q[hh ];for(int i 0; i 4; i){int a t.x dx[i], b t.y dy[i];// printf(%d %d\n, a, b);if(a 0 a n b 0 b m g[a][b] 0){d[a][b] d[t.x][t.y] 1;q[ tt] {a, b};g[a][b] 1;}}}return d[n - 1][m - 1];
}int main()
{scanf(%d%d, n, m); for(int i 0 ; i n; i)for(int j 0; j m; j)scanf(%d, g[i][j]); printf(%d, bfs());return 0;
}STL
#include iostream
#include cstring
#include queue
#includestack#define x first
#define y secondusing namespace std;typedef pairint, int PII;const int N 110;int n, m;
int g[N][N], d[N][N];
queuePII path;int bfs()
{queuePII q;memset(d, -1, sizeof d);d[0][0] 0;q.push({0, 0});int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};while (q.size()){auto t q.front();q.pop();for (int i 0; i 4; i ){int x t.first dx[i], y t.second dy[i];if (x 0 x n y 0 y m g[x][y] 0 d[x][y] -1){d[x][y] d[t.first][t.second] 1;q.push({x, y});path.push({x, y});}}}int x, y;while(path.size())//queuePII path FIFO先进先出 -正序输出 【若逆序存入,则用stackPII path : LIFO后进先出 -正序输出】{x path.front().x, y path.front().y;path.pop();printf(%d %d\n, x, y); //逆序输出路径 【正序改用栈stackPII path[N * N]存入】}return d[n - 1][m - 1];
}int main()
{scanf(%d%d, n, m);for (int i 0; i n; i )for (int j 0; j m; j )scanf(%d, g[i][j]);printf(%d, bfs());return 0;
}1101. 献给阿尔吉侬的花束
阿尔吉侬是一只聪明又慵懒的小白鼠它最擅长的就是走各种各样的迷宫。
今天它要挑战一个非常大的迷宫研究员们为了鼓励阿尔吉侬尽快到达终点就在终点放了一块阿尔吉侬最喜欢的奶酪。
现在研究员们想知道如果阿尔吉侬足够聪明它最少需要多少时间就能吃到奶酪。
迷宫用一个 R×C 的字符矩阵来表示。
字符 S 表示阿尔吉侬所在的位置字符 E 表示奶酪所在的位置字符 # 表示墙壁字符 . 表示可以通行。
阿尔吉侬在 1 个单位时间内可以从当前的位置走到它上下左右四个方向上的任意一个位置但不能走出地图边界。
输入格式 第一行是一个正整数 T表示一共有 T 组数据。
每一组数据的第一行包含了两个用空格分开的正整数 R 和 C表示地图是一个 R×C 的矩阵。
接下来的 R 行描述了地图的具体内容每一行包含了 C 个字符。字符含义如题目描述中所述。保证有且仅有一个 S 和 E。
输出格式 对于每一组数据输出阿尔吉侬吃到奶酪的最少单位时间。
若阿尔吉侬无法吃到奶酪则输出“oop!”只输出引号里面的内容不输出引号。
每组数据的输出结果占一行。
数据范围 1T≤10, 2≤R,C≤200 输入样例
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.输出样例 5 1 oop! 经典迷宫BFS 记bfs步骤①初始化队列q和dist取-1 dist[start.x][start.y] 0(x,y为define全局定义)起点start放入队列方向向量dx[4](从-1开始) ,dy[4]②遍历所有元素依次入队while(队不为空)③取队头出队 遍历所有方向 依据题目判断边界条件④放入对列 中间加个if(end make_pair(x, y) ) return dist[x][y];判断直接结束#include cstdio
#include cstring
#include iostream
#include algorithm
#include queue#define x first//pair的代码简化
#define y secondusing namespace std;typedef pairint, int PII;const int N 210;int n, m;
char g[N][N];
int dist[N][N];int bfs(PII start, PII end)//bfs模板【STL队列版】
{queuePII q;memset(dist, -1, sizeof dist);//不可达则未更新,标记为-1dist[start.x][start.y] 0;//0标记走过 q.push(start);//起点入队 int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};//dx[4](从-1开始)模式化while (q.size()) {auto t q.front();//取队头 q.pop();//出队 for (int i 0; i 4; i ){int x t.x dx[i], y t.y dy[i];if (x 0 || x n || y 0 || y m || g[x][y] # || dist[x][y] ! -1) continue; // 出界 || 障碍物 || 已经走过 -- 判断下一个 dist[x][y] dist[t.x][t.y] 1;if (end make_pair(x, y)) return dist[x][y]; //make_pair返回pair ,也可以放在最后返回distq.push({x, y});}}return -1;
}int main()
{int T;scanf(%d, T);while (T -- ){scanf(%d%d, n, m);for (int i 0; i n; i ) scanf(%s, g[i]);//按字符串读入每行PII start, end;//设置终点、起点, 寻找终点、起点for (int i 0; i n; i )for (int j 0; j m; j )if (g[i][j] S) start {i, j};else if (g[i][j] E) end {i, j};int distance bfs(start, end);//起点---终点 if (distance -1) puts(oop!);//返回-1未更新,不可达else printf(%d\n, distance);}return 0;
}
day4
1113. 红与黑
有一间长方形的房子地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上只能向相邻上下左右四个方向的黑色瓷砖移动。
请写一个程序计算你总共能够到达多少块黑色的瓷砖。
输入格式 输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H 分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中每行包括 W 个字符。每个字符表示一块瓷砖的颜色规则如下
1‘.’黑色的瓷砖 2‘#’红色的瓷砖 3‘’黑色的瓷砖并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时表示输入结束。
输出格式 对每个数据集合分别输出一行显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
数据范围 1≤W,H≤20 输入样例
6 9
....#.
.....#
......
......
......
......
......
#...#
.#..#.
0 0输出样例
45BFS
#includebits/stdc.h
#define x first
#define y secondusing namespace std;typedef pairint, int PII;const int N 25;int n, m;
char g[N][N];
int dx[] {-1, 0, 1, 0}, dy[] {0, 1, 0, -1};
PII q[N * N]; //【最多遍历所有点N * N】int bfs(int x, int y)
{int cnt 1;int hh 0, tt -1;q[tt] {x, y};while(hh tt){auto t q[hh]; for(int i 0; i 4; i){int a t.x dx[i], b t.y dy[i];if(a 0 a n b 0 b m g[a][b] .) {g[a][b] #; //【直接修改为障碍物-等效标记走过-不会重复统计】q[tt] {a, b};cnt ;}}}return cnt;
}int main()
{while (cin m n, n || m){for (int i 0; i n; i ) scanf(%s, g[i]); //读入一行int x, y;for (int i 0; i n; i )for (int j 0; j m; j )if (g[i][j] )//找到起点{x i;y j;}printf(%d\n, bfs(x, y));}return 0;
}DFS
#include cstring
#include iostream
#include algorithmusing namespace std;const int N 25;int n, m;
char g[N][N];
bool st[N][N];//int ne[4][2] {{-1,0}, {0,1}, {1,0}, {0,-1}};
int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1};int dfs(int x, int y)//起点开始
{int cnt 1;st[x][y] true;for (int i 0; i 4; i ){int a x dx[i], b y dy[i];if (a 0 || a n || b 0 || b m) continue;//合并: if(越界 || 不是黑色 || 标记走过) continue; 判断下一个 if (g[a][b] ! .) continue;if (st[a][b]) continue;cnt dfs(a, b);//能到的点的数量【看成树则为加上所有叶子节点数量】}return cnt;
}int main()
{while (cin m n, n || m) //所有表达式都会执行只不过返回值是最后一个表达式的值{for (int i 0; i n; i ) cin g[i];int x, y;for (int i 0; i n; i )for (int j 0; j m; j )if (g[i][j] )//起点{x i;y j;}memset(st, 0, sizeof st);//多组数据,每次要把标记数组清空一遍cout dfs(x, y) endl;}return 0;
}day5
1236. 递增三元组
给定三个整数数组
A[A1,A2,…AN], B[B1,B2,…BN], C[C1,C2,…CN],
请你统计有多少个三元组 (i,j,k) 满足
1≤i,j,k≤N AiBjCk 输入格式 第一行包含一个整数 N。
第二行包含 N 个整数 A1,A2,…AN。
第三行包含 N 个整数 B1,B2,…BN。
第四行包含 N 个整数 C1,C2,…CN。
输出格式 一个整数表示答案。
数据范围 1≤N≤105, 0≤Ai,Bi,Ci≤105 输入样例
3
1 1 1
2 2 2
3 3 3输出样例
27暴力for三重 if(a[i] b[i] b[i] c[i])res; 通过时间复杂度需限制再O(nlogn) 则只能枚举一个数组 应枚举B[i],因为A[i]与C[i]只需被B[i]限制 再把A、C中满足的个数相乘 [等效满足的ABC的组合] 实现O(n)法①前缀和 O(nlogn)法②sort(A) 二分法(B[j])找到A中小于B[j]的下标res 答案个数就为 res 1 前缀和映射hash有减1操作,但有数值0的所以每位加1取值映射变为[1,1e5 1](相对大小不变) 把数值映射为hash值 , 前缀和数组存储值小于当前下标的个数同理c就存储大于当前下标的个数【类似桶排序】 前缀和实现
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;typedef long long LL;const int N 100010;int n;
int a[N], b[N], c[N];
int as[N]; // as[i]表示在A[]中有多少个数小于b[i]
int cs[N]; // cs[i]表示在C[]中有多少个数大于b[i]
int cnt[N], s[N];//cnt[]存a的值的数量int main()
{scanf(%d, n);for (int i 0; i n; i ) scanf(%d, a[i]), a[i] ;for (int i 0; i n; i ) scanf(%d, b[i]), b[i] ;for (int i 0; i n; i ) scanf(%d, c[i]), c[i] ;// 求as[]for (int i 0; i n; i ) cnt[a[i]] ;//将数组a中所有元素出现的次数存入一个哈希表中for (int i 1; i N; i ) s[i] s[i - 1] cnt[i]; // 求cnt[]的前缀和for (int i 0; i n; i ) as[i] s[b[i] - 1];//a[]中小于b[i]的元素个数前缀和 前缀和s可表示为不超过下标值的元素个数(所以减1)// 求cs[]memset(cnt, 0, sizeof cnt);memset(s, 0, sizeof s);for (int i 0; i n; i ) cnt[c[i]] ;//将数组c中所有元素出现的次数存入一个哈希表中for (int i 1; i N; i ) s[i] s[i - 1] cnt[i];for (int i 0; i n; i ) cs[i] s[N - 1] - s[b[i]]; //s[N-1] - s[b[i]]表示c[]所有元素中大于b[i]的个数// 枚举每个b[i]LL res 0;for (int i 0; i n; i ) res (LL)as[i] * cs[i];//1e5*1e5 会爆int 开LLcout res endl;return 0;
}简版STL
#include bits/stdc.h
using namespace std;
typedef long long LL;
const int N 1e5 10;
int a[N], b[N], c[N];int main()
{int n;scanf(%d, n);for(int i 0; i n; i) scanf(%d, a[i]);for(int i 0; i n; i) scanf(%d, b[i]);for(int i 0; i n; i) scanf(%d, c[i]);sort(a, a n), sort(b, b n), sort(c, c n);LL cnt 0;for(int i 0; i n; i) //b比a大 且 比c小 - 【枚举b[] 乘积 {LL A lower_bound(a, a n, b[i]) - a; //a[]中第一个大等于b[i]的位置 (从0开始刚好 个数 下标) LL C n - (upper_bound(c, c n, b[i]) - c); //c[]中第一个小于b的位置 (剩下均大于b[i]) cnt A * C;}printf(%lld, cnt);return 0;
}三指针
#include bits/stdc.h
using namespace std;
typedef long long LL;
const int N 1e5 10;
int a[N], b[N], c[N];int main()
{int n;scanf(%d, n);for(int i 0; i n; i) scanf(%d, a[i]);for(int i 0; i n; i) scanf(%d, b[i]);for(int i 0; i n; i) scanf(%d, c[i]);sort(a, a n), sort(b, b n), sort(c, c n);LL sum 0,s1 0,s2 0;for(int i0;in;i){while(s1 n a[s1] b[i]) s1;while(s2 n c[s2] b[i]) s2;sum s1 * (n - s2);}printf(%lld, sum);return 0;
}day6
3491. 完全平方数[简单数论]
一个整数 a 是一个完全平方数是指它是某一个整数的平方即存在一个整数 b使得 ab2b^2b2。
给定一个正整数 n请找到最小的正整数 x使得它们的乘积是一个完全平方数。
输入格式 输入一行包含一个正整数 n。
输出格式 输出找到的最小的正整数 x。
数据范围 对于 30% 的评测用例1≤n≤1000答案不超过 1000。 对于 60% 的评测用例1≤n≤10810^8108答案不超过 10810^8108。 对于所有评测用例1≤n≤101210^{12}1012答案不超过 101210^{12}1012。
输入样例1 12 输出样例1 3 输入样例2 15 输出样例2 15
质因子的次数为偶数 — 则为平方数 — 解法等效让所有质因子为偶数 还需乘上哪些质因子
#include iostream
#include cstring
#include algorithmusing namespace std;typedef long long LL; //1e12int main()
{LL n;cin n;LL res 1;for (LL i 2; i * i n; i ) //模板if (n % i 0){int s 0;while (n % i 0) s , n / i; //统计质因子i个数s, n除去质因子iif (s % 2) res * i; //i为奇数,则乘上一个i变为偶数}if (n 1) res * n; //【还有一个为奇数的质因子】cout res endl;return 0;
}day7
466. 回文日期
(枚举,模拟) O(104)O(10^4)O(104) 由于只有八位数而且回文串左右对称因此可以只枚举左半边这样只需枚举 0∼9999总共一万个数然后判断
①枚举回文串 ②是否在给定范围[date1,date2]内 ③日期是否合法
时间复杂度:一共枚举 10410^4104 个数判断每个数是否合法的计算量是常数级别的因此总计算量是 O(104)O(10^4)O(104)。
【想法】 %10n10^n10n : 取末尾n位 /10n10^n10n : 删除末尾n位
#include cstdio
#include cstring
#include iostream
#include algorithmusing namespace std;int months[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};bool check(int date)//检查年月日是否合法
{int year date / 10000;int month date % 10000 / 100;//%10000等效取后四位 /100删去后两位 int day date % 100;if (!month || month 13 || !day) return false;if (month ! 2 day months[month]) return false;//先不管二月if (month 2)//特判二月{bool leap year % 4 0 year % 100 || year % 400 0;//是否闰年if (day 28 leap) return false;}return true;
}int main()
{int date1, date2;cin date1 date2;int res 0;for (int i 0; i 10000; i ){int x i, r i;for (int j 0; j 4; j ) r r * 10 x % 10, x / 10;//拼接,取最后一位加上 原数值乘10 如1234 -- 12344321 if (r date1 r date2 check(r)) res ;//检查是否在区间[date1,date2]内}printf(%d\n, res);return 0;
}
