- 博客(98)
- 收藏
- 关注
RSS订阅原创 入门篇3——数学问题（5.1 简单数学）
而二进制是无法准确表示一个浮点数的，只能在有限的精度内逼近这个值。使用long long int，将double小数点后移后保存起来，整数不会存在精度问题。本题的写法值得借鉴。将输入的数转换为数组，升序排列得到最小值，降序排列得到最大值，循环作差直到0或6174。只有形如PAT、PAAT、APAATAA等这样的组合才满足题目要求，且P之前的A、PT之间的A、T之后的A的数量成一定比例关系。在大量或高精度计算中要避免使用 double 类型,原因就在于计算机内部的加减乘除运算是通过加法器二进制运算来完成的，.
2022-08-11 17:16:48
136
1
原创 入门篇2——算法初步（4.6 two pointers）
i、j都指向第一个元素的位置，然后j不断右移，直到a[j]>a[i]*p，记录长度，然后i右移，重复以上操作，最终得到最大长度。two pointers是一种高效的编程技巧，可以同向、反向扫描。用于ai+aj==m、序列合并、归并排序、快速排序。模拟插入、归并排序。先判断是否为插入排序，是就输出下一趟排序的序列，不是就为归并排序。函数调用的写法非常值得借鉴。...
2022-08-07 21:48:59
116
原创 入门篇2——算法初步（4.5二分）
由样例可知，选择的数不一定连续。那么可以考虑升序排列，最长的连续子串就是所求。枚举左端点，ai就是数列中的最小值，查找第一个大于ai*p的数的位置，减一就是右端点，右-左+1即为题目所求。枚举左端点，查找满足sum[j]-sum[i-1]==s的右端点；如果没有，找到第一个和值超过s的右端点，记录最小的和。本题的代码写法非常值得借鉴，充分使用函数之间的调用，即要有面向对象的编程思想。枚举ai，查找m-ai，注意两个数的下标不能一样。...
2022-07-25 22:14:32
98
原创 入门篇2——算法初步（4.4贪心）
贪心：考虑在当前状态下局部最优的策略，从而达到全局最优（不一定）。区间贪心：先选择左端点最大或右端点最小的区间题目情况：3道简单题，3道难题b1023：略b1020/a1070：略a1033：1）优先前往更低油价的加油站。在满油状态下，如果第一次出现更便宜的加油站，就加恰好能够到达这个加油站的油量。2）如果没有，判断能否到达终点。如果不能，优先前往满油状态下最远的加油站。3）如果没有2）所需的加油站，则不能到达终点。a1037：略a1067：1）当0在本位上时，将0和最小的还没有回到本
2022-07-13 22:17:39
203
原创 入门篇2——算法初步（4.3递归）
简单A、吃糖果两种状态：拿一块糖果数≥2时，拿两块#include<bits/stdc++.h>using namespace std;int res;void dfs(int n) { if (!n) { res++; return; } if (n >= 2) dfs(n - 2); dfs(n - 1);}int main() { int n; while (~scanf("%d", &
2022-05-10 16:23:22
130
原创 入门篇2——算法初步（4.2散列）
简单。b1029/a1084：略b1033：当大写字母对应的小写存在以及上档键没有损坏，才能输出；输入字符串用getline（有个测试点可能带空格？）；上档键只有‘+’#include<bits/stdc++.h>using namespace std;char a[100010], b[100010];int main() { map<char, int>mp; cin.getline(a, 100010); cin.getline(b, 100
2022-05-04 21:22:33
154
原创 入门篇2——算法初步（4.1排序）
4.1 排序这一小节题目的代码量是真的大啊b1015/a1062先分类，再排序#include<bits/stdc++.h>using namespace std;struct student{ char id[20]; int de, cai, flag;}arr[100010];bool cmp(student a, student b){ if (a.flag != b.flag) return a.flag < b.flag; e
2022-04-05 22:15:21
351
原创 入门篇1——入门模拟
3.1 简单模拟b1001：略b1032：最好将学校编号初值设为1，分数最大值初值设为-1，防止出错b1011：略b1016：略b1026：略b1046：略b1008：略b1012：略b1018：略a1042：将每张牌当作数字处理，1–13对应S1–S13,14-26对应H1–H13…然后在输出的时候判断下花色和牌号即可。#include<bits/stdc++.h>using namespace std;char sign[5] = {'S', 'H', 'C', '
2022-01-04 22:17:19
322
原创 省赛训练1
1.Cut the Deck题意：选择一个位置，将这个位置及这个位置之前的字符移到后面，问是否存在这么一个最小的位置，使得任意位置的B的数量大于R的数量题解：如果某一位置B的数量小于R的数量，那么舍弃这之前的部分，重新开始计数#include<stdio.h>#include<string.h>char s[1000010];int main() { int t;scanf("%d", &t); while (t--) { scan
2021-10-17 10:22:06
80
原创 2021牛客寒假算法基础集训营6
A.回文括号序列计数题解：因为空串是括号系列，那么空串加’()’，’()’+’()’…括号一定是成对出现的。所以只有空串的时候才能回文，其它情况都不能回文。#include<bits/stdc++.h>using namespace std;int main(){ int t, n; scanf("%d", &t); while (t--){ scanf("%d", &n); if (!n) printf("1\n
2021-04-24 16:26:56
57
原创 2021牛客寒假算法基础集训营4
A.九峰与签到题题解：模拟。注意任意时间，二维数组表示ac和unac两种状态即可。#include<bits/stdc++.h>using namespace std;int mp[30][5];int vis[30];char op[10];int main(){ int m, n, a, i; scanf("%d%d", &m, &n); while (m--){ scanf("%d%s", &a, op);
2021-04-24 15:11:54
171
原创 牛客小白月赛33
A.字符统计题解：模拟。比赛的时候在思考怎么输出最后一个样例，结果发现比赛上面自测能输出，应该是遇到‘\0’结束。然后注意下didn’t是一个单词，根据空格统计单词，而且输入字符串应当合法。#include<stdio.h>#include<string.h>char s[1100];int main(){ int t;scanf("%d", &t); getchar(); while (t--){ int line = 0
2021-04-18 22:39:32
503
4
原创 Codeforces Round #713 (Div. 3)
A. Spy Detected!题解：输出只出现一次的数。#include<bits/stdc++.h>using namespace std;int a[110], mp[110];int main(){ int t, n, i;scanf("%d", &t); while (t--){ memset(mp, 0, sizeof(mp)); scanf("%d", &n); for (i = 1; i
2021-04-15 21:37:48
176
原创 Codeforces Round #712 (Div. 2)
A. Déjà Vu题意：插入一个字符‘a’，输出非回文串。题解：思维。首先全是‘a’肯定不行。往连续’a‘多的一边插入’a’，多的越多，少的越少，那么该字符串就一定不是回文串。#include<bits/stdc++.h>using namespace std;char s[300010];int main(){ int t;scanf("%d", &t); while (t--){ scanf("%s", s); int
2021-04-08 23:24:00
194
原创 并查集练习
A.通信系统题解：只有一个根节点即所有的点在一个集合里，以及有n-1条边时满足yes，其它no。#include<bits/stdc++.h>using namespace std;int p[1010];int n, m;void init(){ for (int i = 1; i <= n; i++) p[i] = i;}int find(int x){ if (x == p[x]) return x; else return
2021-03-29 21:00:16
70
原创 Codeforces Round #710 (Div. 3)
A. Strange Table题意：将按列序排列的x的所处位置，转换成按行序排列时这个位置对应的数字。题解：思维。根据列序求出x所处的行和列，再转换成行序即可。#include<bits/stdc++.h>using namespace std;typedef long long ll;int main(){ int t; ll n, m, x; scanf("%d", &t); while (t--){ scanf("%l
2021-03-28 23:08:10
65
原创 贪心练习
codeup新家本套题比较难的是C和F。A.看电视题解：很自然可以想到，要么按照开始时间排序，要么按照结束时间排序。按开始时间排，可能最早开始的会占后面开始的两个节目，故排除此方法。所以按照结束时间升序排即可，每次选择最早结束的，可以得到最多的节目。#include<bits/stdc++.h>using namespace std;struct node{ int s, e;}a[110];bool cmp(node a, node b){ return a
2021-03-22 14:50:07
78
转载 codeblocks常用快捷键
1.编辑部分：Ctrl + A：全选Ctrl + C：复制Ctrl + X: 剪切Ctrl + V：粘贴Ctrl + Z：撤销（后退一步）Ctrl + S：保存Ctrl + Y:重做（也就是前进一步）Ctrl+Shift+C：注释掉当前行或选中块Ctrl+Shift+X：解除注释（最新版的将其替换为截图功能）Tab：缩进当前行或选中块Shift+Tab：减少缩进按住Ctrl，滚动鼠标滚轮，放大或缩小字体2.编译与运行部分：Ctrl + F9：编译Ctrl + F10：运行上次成
2021-03-14 21:51:37
4626
原创 BFS练习
b#include<bits/stdc++.h>using namespace std;char mp[100][100];//int vis[100][100];int flag;struct node{ int x, y, step;};struct node cur, nxt;void bfs(){ queue<node>q; cur.x = 7, cur.y = 0, cur.step = 0; q.push(cur);
2021-03-13 22:43:48
104
原创 Codeforces Round #706 (Div. 2)
A.Split it!题意：将能否将字符串分成k+1个子串及其k个翻转子串。题解：可以发现，统计字符串首尾相同的对数，这个对数就是字符串能分成的子串个数，只要大于等于k就满足题意。但k=n/2时，如果n为奇数，那么第k+1位空出来不用管；n为偶数，多出一位不满足条件。#include<bits/stdc++.h>using namespace std;char s[110];int calc(char s[]){ int i, l = strlen(s), cnt = 0;
2021-03-11 20:58:51
232
原创 DFS练习
一.入门题A.【递归入门】全排列题解：用数组顺序存储每个数输出，然后回溯即可。#include<bits/stdc++.h>using namespace std;int a[20];int vis[20];int n;void dfs(int step){ if (step == n + 1){ for (int i = 1; i <= n; i++){ if (i > 1) printf(" ");
2021-02-21 19:42:33
149
原创 Educational Codeforces Round 104 (Rated for Div. 2)
A. Arena#include<bits/stdc++.h>using namespace std;int a[110];int main(){ int t, n, i; scanf("%d", &t); while (t--){ int mi = 110; scanf("%d", &n); for (i = 1; i <= n; i++){ scanf("%d",
2021-02-18 21:40:53
88
原创 Codeforces Round #702 (Div. 3)
A. Dense Array题解：每次乘二即可。#include<bits/stdc++.h>using namespace std;int a[60];int main(){ int t, n, i; scanf("%d", &t); while (t--){ scanf("%d", &n); for (i = 1; i <= n; i++) scanf("%d", &a[
2021-02-17 22:14:24
118
原创 CF-Predictor安装教程
本文是谷歌浏览器的安装教程。1.点击下载地址：https://www.crx4chrome.com/crx/46813/2.点击这个划着红线的链接。3.点击右上角的三个点–更多工具–扩展程序，打开开发者模式，将下载好的crx文件拖入进去即可。4.效果如下：...
2021-02-17 16:11:59
5070
1
原创 Codeforces Round #701 (Div. 2)
A. Add and Divide题解：当b=2时，30次就能把1e9除完，除不了几次，所以b的值不会很大，枚举一个b的小区间即可。#include<bits/stdc++.h>using namespace std;int main(){ int t, a, b, i; scanf("%d", &t); while (t--){ scanf("%d%d", &a, &b); if (a < b) p
2021-02-15 00:00:10
155
原创 Codeforces Round #699 (Div. 2)
A. Space Navigation题解：忽略无关命令，统计到达终点的命令类型和数量即可。#include<bits/stdc++.h>using namespace std;char s[100010];int main(){ int t, x, y, i;cin >> t; while (t--){ cin >> x >> y >> s; int len = strlen(s);
2021-02-14 19:20:53
81
原创 Codeforces Round #700 (Div. 2)
A. Yet Another String Game#include<bits/stdc++.h>using namespace std;char s[60];int main(){ int t; scanf("%d", &t); while (t--){ scanf("%s", s); int i, l = strlen(s); for (i = 0; i < l; i++){
2021-02-08 22:12:06
178
原创 2021牛客寒假算法基础集训营3
G.糖果题解：并查集确定好各个集合，每个集合中的顶点值为这个集合中最大的顶点值。#include<bits/stdc++.h>using namespace std;int a[1000010];int f[1000010];int find(int x){ if (f[x] == x) return x; return f[x] = find(f[x]);}int main(){ int n, m, x, y, i;cin >> n &g
2021-02-07 16:54:48
201
2
原创 2021牛客寒假算法基础集训营1
A.串题解：直接求不好删重，可以一位一位地拼接起来。设f[i]为长度为i的包含us的子序列个数，每次在前i-1位的基础上接上一位，分为以下两种情况：1.前面已经有us了，后面可以接上任意一位。2.前面有u但u后面没有s，可以通过总的-有us的-没有u的。#include<bits/stdc++.h>using namespace std;typedef long long ll;ll mod = 1e9 + 7;ll f[1000010];ll qp(ll x, ll y){
2021-02-07 15:57:48
130
原创 第八届“图灵杯”NEUQ-ACM程序设计竞赛个人赛（同步赛）
A.切蛋糕题解：将大小为1的蛋糕看成x份，那么x/k份能整除为x/k份，不能为x/k+1份，减去1/k即减去x/k份，那么前后相减，差值的绝对值为零或1份，而这个差值要<=1/2 ^ 10 ,也就是1份要<=1/2 ^ 10。 取1份=1/2 ^10，那么x=1024。分成1024份需要切2 ^ 0 + 2 ^ 1 + … + 2 ^ 9 = 1023次，打包需要k次，最多2047次。#include<bits/stdc++.h>using namespace std;int
2021-02-02 22:44:50
258
2
原创 Codeforces Round #697 (Div. 3)
A. Odd Divisor题意：判断n有无大于1的奇除数。题解：n本身是奇数可作为奇除数。偶数=偶数 * 偶数=奇数 * 偶数=大于1的奇数 * 2^n。#include<bits/stdc++.h>using namespace std;int main(){ int t, i;long long n;cin >> t; while (t--){ cin >> n; if (n == 2) cout <
2021-01-28 22:05:56
45
原创 位运算
小A的位运算题解：维护一个前缀和的前i-1项与后缀和的后i+1项。#include<bits/stdc++.h>using namespace std;typedef long long ll;int a[5000010];ll b[5000010], c[5000010];int main(){ int n, i;cin >> n; for (i = 1; i <= n; i++) cin >> a[i];
2021-01-26 21:54:01
63
原创 Good Bye 2020
A. Bovine Dilemma题意：求面积不同的三角形个数。#include<bits/stdc++.h>using namespace std;double x[60];int main(){ int t, n, i, j;cin >> t; while (t--){ int res = 0; map<double,int>mp; cin >> n; for (i
2021-01-26 16:16:04
61
原创 牛客IOI周赛22-普及组
A. 战争尾声题解：暴力枚举。#include<bits/stdc++.h>using namespace std;int x[210], y[210];int main(){ ios::sync_with_stdio(0); int n, i, j, k;cin >> n; for (i = 1; i <= n; i++) cin >> x[i] >> y[i]; int flag1 = 0;
2021-01-23 21:10:44
81
1
原创 Codeforces Round #696 (Div. 2)
A. Puzzle From the Future题解：首位1，保证最大。第i位加1和第i-1位相等，0；不相等，1。#include<bits/stdc++.h>using namespace std;char s[100010];int main(){ int t, n, i;cin >> t; while (t--){ cin >> n >> s; for (i = 0; i < n; i
2021-01-22 16:00:08
56
原创 Codeforces Round #695 (Div. 2)
A. Wizard of Orz题意：有一排数字，从零开始，每秒加一，九加一回到零。可暂停在任意时刻任意的一个数字，其它数字的暂停时间为与被暂停数字的距离。问最大的数。题解：暂停第八秒时的第二位数字，这样首位最大，第二位次大，保证数字整体最大。#include<bits/stdc++.h>using namespace std;int main(){ int t, n, i;cin >> t; while (t--){ cin >&g
2021-01-19 18:17:16
92
原创 Educational Codeforces Round 102 (Rated for Div. 2)
A.Replacing Elements题意：可选择不相同的i,j,k，使得ai=aj+ak。问能否使所有的ai<=d。题解：用最小的两个ai的和替代所有>d的数，不能替代则不能。#include<bits/stdc++.h>using namespace std;int a[110];int main(){ int t, n, d, i;cin >> t; while (t--){ cin >> n >&g
2021-01-17 21:04:30
89
原创 Codeforces Round #694 (Div. 2)
A. Strange Partition题意：求最小和最大的bi/x向上取整的和。题解： 最小n个数的和作为一个数除以x，最大n个数分别除以x。#include<bits/stdc++.h>using namespace std;typedef long long ll;int a[100010];int main(){ int t, n, x, i;cin >> t; while (t--){ ll sum = 0, mx =
2021-01-07 22:55:13
290
6
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人