每日一题dive2-week14

2023-11-08 10:59
文章标签 一题 每日 dive2 week14

本文主要是介绍每日一题dive2-week14，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

加一

 思路:

开始没多想直接用栈写了个简单的逻辑,一试,超时

栈超时代码

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
stack<long long int>zanshi3;
int main() {int x;cin >> x;for (int e = 0; e < x; e++) {long long int b;string a;cin >> a >> b;for (int i = 0; i < b; i++) {cout << i << endl;while (a.size() != 0) {long long int zanshi = a.back() - '0';zanshi += 1;zanshi3.push(zanshi);a.resize(a.size() - 1);}while (!zanshi3.empty()) {if (zanshi3.top() >= 10) {int zs3 = zanshi3.top();a += zs3 % 10 + '0';zs3 /= 10;a += zs3 + '0';}else {a += zanshi3.top() + '0';}zanshi3.pop();}cout << a << endl;}cout << a.size() % 1000000007 << endl;}}

感觉栈 进栈出太复杂,直接换成对string数组进行操作,还是超时

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
stack<long long int>zanshi3;
int main() {int x;cin >> x;for (int e = 0; e < x; e++) {long long int b;string a,c;cin >> a >> b;for (int i = 0; i < b; i++) {for (int h = 0; h < a.size(); h++) {int zs3 = a[h] - '0';zs3 += 1;if (zs3 >= 10) {c += zs3 % 10 + '0';zs3 /= 10;c += zs3 + '0';}else {c += zs3 + '0';}}a = c;c.clear();}cout << a.size() % 1000000007 << endl;}}

果然还是我想的太简单,最后试着用模拟,

先建立一个三维数组x[10][2e9][10],用来计算0-9这几个数每个数加一了n次之后得到的数包含数字0-9的数量,

比如9,加一一次之后成了10,包含一个1和一个0,所以x[9][1][0]=1,x[9][1][1]=1;以这个逻辑进行计算.

先手动录入0-9加一一次后的结果包含数字0-9的情况

之后用循环为之后空余的位置填入数据

for (int e = 0; e <= 9; e++) {//最外层0-9循环for (int i = 1; i <= 2e5; i++) {//加一第n次for (int c = 0; c < 10; c++) {//循环遍历x[e][i]下的0-9for (int d = 0; d < 10; d++) {//x[e][i+1]每个0-9对应的大小应该加上x[c][1]的结果乘上x[e][i][c]的数量x[e][i + 1][d] += x[c][1][d] * x[e][i][c];x[e][i + 1][d] %= 1000000007;}}}}

之后就是轻松简单的接收数据然后获取数据每位数字对应结果的大小,相加,%1000000007,输出,结束

还有个问题就是,用cin和cout会超时,所以建议用scanf和printf

下面附上完整代码

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
long long int x[10][200005][10];
int main(){int n1;scanf("%d", &n1);for (int e = 0; e < 9; e++) {x[e][1][e + 1] = 1;}x[9][1][1] = 1;x[9][1][0] = 1;for (int e = 0; e <= 9; e++) {for (int i = 1; i <= 2e5; i++) {for (int c = 0; c < 10; c++) {for (int d = 0; d < 10; d++) {x[e][i + 1][d] += x[c][1][d] * x[e][i][c];x[e][i + 1][d] %= 1000000007;}}}}for (int f = 0; f < n1; f++) {long long int  n, m;scanf("%lld%lld", &n, &m);long long int jishu = 0;while (n) {int z = n % 10;n /= 10;for (int i = 0; i < 10; i++) {jishu += x[z][m][i];jishu %= 1000000007;}}		printf("%lld\n", jishu);}
}

跳跳

 思路:

开始还在想要怎么做,看着很复杂,有没有什么高深的算法,结果一看数据顶天了也超不了时,直接暴力,用map记录数据,遍历一遍,对两点坐标差除以最大公约数之后录入,最后输出map的size,结束.

需要注意的是,如果差值里面有0,需要额外提取出来单独录进去

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int>>zuobiao;
map<pair<int ,int>,int>a;
int GCD(int a, int b)
{return b == 0 ? a : GCD(b, a % b);
}
int main() {int x;scanf("%d",&x);for (int e = 0; e < x; e++) {int x1, x2;scanf("%d%d", &x1, &x2);zuobiao.push_back(make_pair(x1, x2));}for (int e = 0; e < zuobiao.size(); e++) {for (int e1 = 0; e1 < zuobiao.size(); e1++) {if (e1 == e) {continue;}else {int x1 = zuobiao[e].first-zuobiao[e1].first;int x2 = zuobiao[e].second-zuobiao[e1].second;//cout << x1 << " " << x2 << endl;if (x1 == 0) {if (x2 > 0) {a.insert(make_pair(make_pair(0, 1),1));}else {a.insert(make_pair(make_pair(0, -1),1));}}else if(x2==0) {if (x1 > 0) {a.insert(make_pair(make_pair(1, 0),1));}else {a.insert(make_pair(make_pair(-1, 0),1));}}else {int gys=GCD(abs(x1),abs(x2));a.insert(make_pair(make_pair(x1 / gys, x2 / gys),1));}}}}cout << a.size() << endl;
}

异或和或

思路:

开始先来捋一下这个题给了些什么条件,

首先,按位异或就是,两者相同为0,不同为1,或就是两者有1就是1,全是0才是0

因此可以得出结论

//抓1 1的话,x=0,y=1;
//抓1 0的话,x=1,y=1;
//抓0 1的话,x=1,y=1;

再深思一下就会发现,只要字串力有一个1,就可以把整个字符串全部变成1,之后想变成什么都可以
,所以只要两个字符串都有1,或者两个字符串都没1,这时两者就相等 

先摆出来一个lj代码,好不容易写的而且过了,丢了心疼(恼)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
//抓1 1的话,x=0,y=1;
//抓1 0的话,x=1,y=1;
//抓0 1的话,x=1,y=1;
//只要字串力有一个1,就可以把整个字符串全部变成1,之后想变成什么都可以
//所以只要两个字符串都有1,或者两个字符串都没1,这时两者就可能相等
int main() {int x;cin >> x;for (int e = 0; e < x; e++) {string a, b;cin >> a >> b;if (a.size() != b.size()) {printf("%s\n", "NO");}else {int a1 = 0;for (int i = 0; i < a.size(); i++) {if (a[i] - '0' == 1) {a1 += 1;if (a1 == 2) {break;}}}int panduan = 1;int b0 = 0;for (int i = 0; i < b.size(); i++) {b0 += b[i] - '0';}for (int i = 0; i < a.size(); i++) {if (a[i] != b[i]) {if (a[i] - '0' == 1) {if (b0 == 0) {printf("%s\n", "NO");panduan = 0;break;}if (a1 > 0) {}else {printf("%s\n", "NO");panduan = 0;break;}}else {if (a1 > 0) {}else {printf("%s\n", "NO");panduan = 0;break;}}}}if (panduan == 1) {printf("%s\n", "YES");}}}
}

接下来是优化以后的代码

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
int main() {int x;cin >> x;for (int e = 0; e < x; e++) {string a, b;cin >> a >> b;if (a.size() != b.size()) {cout << "NO" << endl;continue;}int a1 = 0, b1 = 0;for (int i = 0; i < a.size(); i++) {if (a[i] - '0' == 1)a1++;if (b[i] - '0' == 1)b1++;}if (a1 && b1 || a1 == b1) {cout << "YES"<< endl;}else {cout << "NO" << endl;}}
}

01序列

思路:

超时做法,直接遍历

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
int main() {int x;string y;cin >> x >> y;int kk = 0;int panduan = 1;for (int e = 0; e < y.size(); e++) {int geshu = 0;for (int i = e; i < y.size(); i++) {if (y[i]-'0' == 1) {geshu++;}if (geshu == x) {kk++;}if (geshu == x+1) {break;}}}cout << kk;
}

 因为直接遍历会超时,所以我们需要找一些规律,分为x=0和x!=0;

当x等于0的时候,子序列的数量为子序列长度*(子序列长度+1)/2;

当x!=0时,我们需要找到一个子序列,子序列需要包含x个1,然后我们找到最前面一个一之前的零和最后一个一后面的零的数量分别加一然后乘起来,然后找到所有包含x个1+的子序列,全部加起来,就是答案.

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
int main() {int x;string y;cin >> x >> y;int kk = 0;int panduan = 1;if (x == 0) {long long int ans = 0;for (int e = 0; e < y.size(); e++) {if (y[e] - '0')continue;int j = e;long long int geshu = 0;while (j<y.size()&&y[j] - '0' == 0) {j++;geshu++;}ans += (geshu + 1) * geshu / 2;e = j;}cout << ans;return 0;}int res = 0,cnt=0;for (int i = 0, j = 0; i < y.size(); i++){while (j < y.size()){if (y[j] == '1')cnt++;if (cnt == x)break;j++;}if (cnt == x){int ed = j + 1;while (ed < y.size() && y[ed] != '1')ed++;int c = ed - j;while (i < y.size() && y[i] != '1'){i++;res += c;}res += c;j++;cnt--;}}cout << res << endl;
}

出栈顺序判断

思路:

不能直接用栈,直接用栈操作会超时,得用模拟的法子.遍历一遍,循环用来遍历序列,单独int一个变量负责模拟push,单独int一个变量模拟栈如果不一样就一直push,如果一样就栈--;而且考虑到栈的规则,所以不用纠结像1423这样的情况,这是不可能出现的

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
int n,tt = 0;
int stk[100010], a[100010];
int main()
{scanf("%d", &n);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);int num = 1;for (int i = 1; i <= n; i++){while (!tt || stk[tt] != a[i]){printf("push %d\n", num);stk[++tt] = num;num++;}if (stk[tt] == a[i]){printf("pop\n");tt--;}}return 0;
}

序列维护

思路:

这个题,嘶,额,怎么说呢,开始我认为是要用链表来做,但是因为数据太大,用数字做标识符的话数组开不到那么大,所以只能用序列号做标识符,如果要用序列号做标识符的话,自己写链表,每加一个或减一个,整个后面的链表序列号都得变化,很麻烦,怎么办呢,这不有现成的嘛,直接vector一个,你让插几就插几,你让删哪个就删哪个,本来以为会卡输入输出时间,结果直接过了,挺好.

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
const long long N =1e3+5;
vector<long long int>h;
int main() {int n;cin >> n;for (int p = 0; p < n; p++) {string a;cin >> a;int x, y;if (a == "insert") {cin >> x >> y;h.insert(h.begin() + x, y);}else if (a == "delete") {cin >> x;h.erase(h.begin()+x-1);}else {cin >> x;cout << h[x-1] << endl;}}}

 网格判断

思路:

这题没啥难度,就单纯if+else,for循环遍历

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
string x[30];
int main() {int n;cin >> n;for (int e = 1; e <= n; e++) {cin >> x[e];int x1 = 0, y1 = 0;int cishu2 = 0;char jilu2 = 'R';for (int i = 0; i < n; i++) {if (x[e][i] == 'B') {x1++;}else {y1++;}if (jilu2 == x[e][i]) {cishu2++;}else {jilu2 = x[e][i];cishu2 =1;}if (cishu2 > 2) {cout << 0;return 0;}}if (x1 != y1) {cout << 0;return 0;}}for (int e = 0; e <n; e++) {int cishu = 0;char jilu = 'R';int x1 = 0, y1 = 0;for (int i = 1; i <=n; i++) {if (x[i][e] == 'B') {x1++;}else {y1++;}if (jilu == x[i][e]) {cishu++;}else {jilu = x[i][e];cishu = 1;}if (cishu > 2) {cout << 0;return 0;}}if (x1 != y1) {cout << 0;return 0;}}cout << 1;
}

整齐的数组

 思路:

只需要计算每个数与最小数的差值的最大公约数即可

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 50;int t, n;
int a[N];int gcd(int a, int b)
{if(b == 0)return a;return gcd(b, a % b);
}int main()
{ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin >> t;while(t --){cin >> n;for(int i = 1; i <= n; i ++)cin >> a[i];sort(a + 1, a + n + 1);int ans = 0;for(int i = 2; i <= n; i ++){if(a[i] == a[1]) continue;ans = gcd(ans, a[i] - a[1]);}if(ans) printf("%d\n", ans);else puts("-1");}return 0;
}

删删

 思路:

枚举26个字符,双指针跑字符串，当两边不一样时就判断两边有没有我们当前枚举的字符

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int x;cin >> x;while (x--) {int x2;string a;cin >> x2 >> a;int n, res = 1e9;bool flag = true;for (char e = 'a'; e <= 'z'; e++) {int ans = 0;flag = true;int qian = 0, hou = a.size() - 1;while (qian < hou) {if (a[qian] == a[hou]) {qian++; hou--;}else {if (a[qian] == e) {qian++;ans++;}else if (a[hou] == e) {hou--;ans++;}else {flag = false;break;}}}if (flag) { res = min(res, ans); }}if (res == 1e9) {cout << -1<<endl;}else {cout << res<<endl;}}
}

这篇关于每日一题dive2-week14的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/369381。

相关文章

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎，细嗅蔷薇。你好朋友，这里是锅巴的C\C++学习笔记，常言道，不积跬步无以至千里，希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目： 牛牛发明了一种新的四舍五入应用于整数，对个位四舍五入，规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数
阅读更多...
每日一练7：简写单词（含链接）

每日一练7：简写单词（含链接）

1.链接 简写单词_牛客题霸_牛客网 2.题目 3.代码1（错误经验） #include <iostream>#include <string>using namespace std;int main() {string s;string ret;int count = 0;while(cin >> s)for(auto a : s){if(count == 0){if( a <=
阅读更多...
【每日刷题】Day113

【每日刷题】Day113

【每日刷题】Day113 🥕个人主页：开敲🍉 🔥所属专栏：每日刷题🍍 🌼文章目录🌼 1. 91. 解码方法 - 力扣（LeetCode） 2. LCR 098. 不同路径 - 力扣（LeetCode） 3. 63. 不同路径 II - 力扣（LeetCode） 1. 91. 解码方法 - 力扣（LeetCode） //思路：动态规划。 cl
阅读更多...
力扣 739. 每日温度【经典单调栈题目】

力扣 739. 每日温度【经典单调栈题目】

1. 题目 理解题意： 1.1. 给一个温度集合， 要返回一个对应长度的结果集合， 这个结果集合里面的元素 i 是 当前 i 位置的元素的下一个更高温度的元素的位置和当前 i 位置的距离之差， 若是当前元素不存在下一个更高温度的元素， 则这个位置用0代替； 2. 思路 本题用单调栈来求解；单调栈就适用于来求当前元素左边或者右边第一个比当前元素大或者小的元素；【单调栈：让栈中的元素保持单调
阅读更多...
每日一题——第八十一题

每日一题——第八十一题

打印如下图案: #include<stdio.h>int main() {int i, j;char ch = 'A';for (i = 1; i < 5; i++, ch++){for (j = 0; j < 5 - i; j++){printf(" ");//控制空格输出}for (j = 1; j < 2 * i; j++)//条件j < 2 * i{printf("%c", ch
阅读更多...
每日一题，力扣leetcode Hot100之238.除自身以外数组的乘积

每日一题，力扣leetcode Hot100之238.除自身以外数组的乘积

乍一看这个题很简单，但是不能用除法，并且在O(N)时间复杂度完成或许有点难度。 考虑到不能用除法，如果我们要计算输出结果位置i的值，我们就要获取这个位置左边的乘积和右边的乘积，那么我新设立两个数组L和R。 对于L来说，由于表达的是位置i左边的数的乘积，那么L[0]=1，因为第一个数字左边没数那么为了不影响乘积初始值就设置为1，那么L[1]=L[0]*nums[0]，那么L[i]=L[i-1
阅读更多...
英语每日一段 195

英语每日一段 195

Promising economic indicators won’t instantly reverse the lingering impact of hard times for millions of families, workplace culture expert Jessica Kriegel said. “Perception and reality are sometimes
阅读更多...
GitHub每日最火火火项目（9.7）

GitHub每日最火火火项目（9.7）

项目名称：polarsource / polar 项目介绍：polar 是一个开源的项目，它是 Lemon Squeezy 的替代方案，具有更优惠的价格。该项目旨在让开发者能够凭借自己的热情进行编码并获得报酬。通过使用 polar，开发者可以更轻松地实现自己的创意和项目，并从中获得收益。 项目地址：https://github.com/polarsource/polar项目名称：psf / bla
阅读更多...
【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数（字符串、滑动窗口）

【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数（字符串、滑动窗口）

【每日一题】LeetCode 2379.得到K个黑块的最少涂色次数（字符串、滑动窗口） 题目描述 给定一个字符串 blocks，其中每个字符代表一个颜色块，可以是 ‘W’（白色）或 ‘B’（黑色）。你需要找到一个至少包含 k 个连续黑色块的子串。每次操作可以将一个白色块变成黑色块。你的任务是找到至少出现一次连续 k 个黑色块的最少操作次数。 和该题目类似：【每日一题】LeetCode 202
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2