OJ19 排队打水问题--贪心问题描述有n个人排队到r个水龙头去打水他们装满水桶的时间t1、t2………..tn为整数且各不相等应如何安排他们的打水顺序才能使他们总共花费的时间最少输入说明第一行nr (n500,r75)第二行为n个人打水所用的时间Ti (Ti100)输出说明最少的花费时间个人总结关于总共花费的时间实际上是指--每个人从开始到打完的时间加起来每个人的时间包括等待上一个人的时间自己要打水的时间。利用贪心思路让打水时间短的人先去打水维护一个记录每个水龙头累计打水时间的数组每来一个人找到最短时间的水龙头打水。代码#includebits/stdc.h using namespace std; //n--people r--water t--t1,t2,t3,t4...int int main() { int n,r; cinnr; int t[n]; for(int i0;in;i) cint[i]; sort(t,tn); vectorint water_t(r,0);//每个水龙头累计打水时间 int sum0; for(int i0;in;i) { int min_twater_t[0];//当前最小的累计打水时间 int min_index0;//记录当前最小的累计打水时间的水龙头编号 for(int j0;jr;j) { if(water_t[j]min_t) { min_twater_t[j]; min_indexj; } } summin_tt[i]; water_t[min_index]t[i]; } coutsumendl; return 0; }20 产生数问题描述给出一个整数 nn10^30) 和 k 个变换规则k15。规则一位数可变换成另一个一位数变换得到的数不能为零。例如n234。有规则k22 53 6上面的整数 234 经过变换后可能产生出的整数为包括原数:234534264564共 4 种不同的产生数问题给出一个整数 n 和 k 个规则。求出经过任意次的变换0次或多次能产生出多少个不同整数。仅要求输出个数。输入说明n kx1 y1x2 y2... ...xn yn输出说明一个整数满足条件的个数个人总结定义一个bool类型reach二维数组--reach[a][b]代表a--b是否存在也就是a能不能到bab是大数n的某一位的数字核心思想就是计算每一位上的数字可以通过规则转变到几个数字自己到自己也算一种然后每位数字对应的个数相乘就是最后的结果由于最后结果可能有9*9*9....数字很大所以用大数乘法因为在数组里面是倒着的所以输出时也要倒叙输出。例如n2342 53 6第一位数字 2可以到达 {25}--2第二位数字3可以到达{36}--2第三位数字可以到达{4}--1一共是2*2*14。代码#includebits/stdc.h using namespace std; vectorint mul(const vectorint a,int b) { vectorint res; int carry0; for(int i0;ia.size();i) { carrya[i]*b; res.push_back(carry%10); carry/10; } while(carry) { res.push_back(carry%10); carry/10; } return res; } int main() { string n; int k; cinnk; //reach[a][b]true表示a可以变成b bool reach[10][10]{false}; for(int i0;i10;i) reach[i][i]true; for(int i0;ik;i) { int x,y; cinxy; reach[x][y]true; } //关键步骤 for(int m0;m10;m) { for(int i0;i10;i) { if(reach[i][m]) { for(int j0;j10;j) { if(reach[m][j]) reach[i][j]true; } } } } int cnt[10]{0}; for(int i0;i10;i) { for(int j0;j10;j) { if(reach[i][j]) cnt[i]; } } //cnt[1]*cnt[2]*...最大可能是9*9*9....很大 vectorint ans; ans.push_back(1);//初始化为1 for(char ch:n) { int dch-0; ansmul(ans,cnt[d]);//大数乘法,ans可能是大数 } for(int ians.size()-1;i0;i--) coutans[i]; coutendl; return 0; }21 分分钟的碎碎念--动规问题描述以前有个孩子他分分钟都在碎碎念。不过他的念头之间是有因果关系的。他会在本子里记录每一个念头并用箭头画出这个念头的来源于之前的哪一个念头。翻开这个本子你一定会被互相穿梭的箭头给搅晕现在他希望你用程序计算出这些念头中最长的一条因果链。将念头从1到n编号念头i来源于念头from[i]保证from[i]ifrom[i]0表示该念头没有来源念头只是脑袋一抽灵光一现。样例输入801032424样例输出3样例说明最长的因果链有1-2-5 (from[5]2,from[2]1,from[1]0)1-2-7 (from[7]2,from[2]1,from[1]0)3-4-6 (from[6]4,from[4]3,from[3]0)3-4-8 (from[8]4,from[4]3,from[3]0)输入说明第一行一个正整数n表示念头的数量接下来n行依次给出from[1]from[2]…from[n]1n1000输出说明共一行一个正整数L表示最长的念头因果链中的念头数量个人总结dp[i]表示以节点i为结尾的最长因果链长度若from[i]0--dp[i]1;否则dp[i]dp[from[i]]1;代码#includebits/stdc.h using namespace std; /*1-n 8 0 源头from[1]0 1 from[2]念头2来源于念头from[2]1 1--2 0 from[3]念头3来源于念头from[3]0 3 from[4]念头4来源于念头from[4]3 3--4 2 from[5]念头5来源于念头from[5]2 2--5 4 from[6]念头6来源于念头from[6]4 4--6 2 from[7]念头7来源于念头from[7]2 2--7 4 from[8]念头8来源于念头from[8]4 4--8 from[i]--i dp[i]表示以节点i为结尾的最长因果链长度 若from[i]0--dp[i]1; 否则dp[i]dp[from[i]]1; */ int main() { int n; cinn; vectorint from(n1); for(int i1;in;i) cinfrom[i]; vectorint dp(n1,0); int maxlen0; for(int i0;in;i) { if(from[i]0) dp[i]1; else { dp[i]dp[from[i]]1; } maxlenmax(maxlen,dp[i]); } coutmaxlenendl; return 0; }22 现代诗如蚯蚓问题描述现代诗如蚯蚓断成好几截都不会死字符串断成好几截有可能完全一样请编写程序输入字符串输出该字符串最多能断成多少截完全一样的子串样例输入abcabcabcabc样例输出4样例说明最多能断成四个”abc”也就是abc重复四遍便是原串同时也能断成两个”abcabc”最坏情况是断成一个原串”abcabcabcabc”输入说明一行一个字符串字符串长度1000输出说明一行一个正整数表示该字符串最多能断成的截数个人总结枚举所有可能的长度首先判断这个长度能否被字符串的长度整除然后提取第一个长度为len的作为模式串与后面的串一次比对并且不断更新最大的分段长度。注maxsegmentsmax(maxsegments,(int)s.length()/len);maxsegments是int类型而n/len 是size_type通常是unsigned long long类型类型不匹配导致,强制类型转换为int类型--(int)s.length()/len。代码#includebits/stdc.h using namespace std; int main() { string s; getline(cin,s); int maxsegments1; for(int len1;lens.length();len) { if(s.length()%len!0) continue; bool validtrue; string patterns.substr(0,len);//模式串 for(int ilen;is.length();ilen) { if(s.substr(i,len)!pattern) { validfalse; break; } } if(valid) { maxsegmentsmax(maxsegments,(int)s.length()/len); } } coutmaxsegmentsendl; return 0; }23 函数求值问题描述设 F(N) 表示正整数 1 到正整数 N 中,数字 1,2 总共出现了多少次。例如 N 10 时:1, 2, 3, 4, 5, 6, 7, 8, 9, 10 这 10 个数中,数字 1 出现了两次,数字 2 出现了 1 次,所以数字 1, 2 总共出现了 3 次,因此 F (10) 3。现在给你正整数 N ,请你求出 F(N) 的值。由于 F(N) 可能很大,你仅需输出 F(N) 除以 20123 的余数。输入说明输入数据仅一行,包含一个正整数 N (1 ≤ N ≤ 10100 ),表示函数 F(N)的参数。输出说明输出仅一个整数,为 F(N) 除以 20123 的余数。代码简单超时版#include bits/stdc.h using namespace std; int countDigits(int n) { int count 0; while (n 0) { int digit n % 10; if (digit 1 || digit 2) { count; } n / 10; } return count; } int main() { int N; cin N; int totalCount 0; for (int i 1; i N; i) { totalCount countDigits(i); } totalCount % 20123; cout totalCount endl; return 0; }AC#include iostream #include string using namespace std; const int MOD 20123; // 把字符串 s 转换成整数并取模 MOD int str_to_mod(const string s) { int res 0; for (char ch : s) { res (res * 10 (ch - 0)) % MOD; } return res; } int main() { string N; cin N; int len N.size(); int ans 0; // 数字 1 和数字 2 分别统计 for (int d 1; d 2; d) { // 逐位计算 int factor 1; // 10^(i-1) mod MOD for (int i 1; i len; i) { // 当前位的权重是 10^(i-1) // high 是 N[0..len-i-1] // cur N[len-i] - 0 // low N[len-i1..len-1] // 计算高位部分 string high_str N.substr(0, len - i); int high (high_str.empty() ? 0 : str_to_mod(high_str)); int cur N[len - i] - 0; // 计算低位部分 string low_str N.substr(len - i 1); int low (low_str.empty() ? 0 : str_to_mod(low_str)); if (cur d) { ans (ans (high 1) * factor) % MOD; } else if (cur d) { ans (ans high * factor low 1) % MOD; } else { // cur d ans (ans high * factor) % MOD; } // factor 更新为 10^i mod MOD factor (factor * 10) % MOD; } } cout ans endl; return 0; }英语
3月20日打卡
OJ19 排队打水问题--贪心问题描述有n个人排队到r个水龙头去打水他们装满水桶的时间t1、t2………..tn为整数且各不相等应如何安排他们的打水顺序才能使他们总共花费的时间最少输入说明第一行nr (n500,r75)第二行为n个人打水所用的时间Ti (Ti100)输出说明最少的花费时间个人总结关于总共花费的时间实际上是指--每个人从开始到打完的时间加起来每个人的时间包括等待上一个人的时间自己要打水的时间。利用贪心思路让打水时间短的人先去打水维护一个记录每个水龙头累计打水时间的数组每来一个人找到最短时间的水龙头打水。代码#includebits/stdc.h using namespace std; //n--people r--water t--t1,t2,t3,t4...int int main() { int n,r; cinnr; int t[n]; for(int i0;in;i) cint[i]; sort(t,tn); vectorint water_t(r,0);//每个水龙头累计打水时间 int sum0; for(int i0;in;i) { int min_twater_t[0];//当前最小的累计打水时间 int min_index0;//记录当前最小的累计打水时间的水龙头编号 for(int j0;jr;j) { if(water_t[j]min_t) { min_twater_t[j]; min_indexj; } } summin_tt[i]; water_t[min_index]t[i]; } coutsumendl; return 0; }20 产生数问题描述给出一个整数 nn10^30) 和 k 个变换规则k15。规则一位数可变换成另一个一位数变换得到的数不能为零。例如n234。有规则k22 53 6上面的整数 234 经过变换后可能产生出的整数为包括原数:234534264564共 4 种不同的产生数问题给出一个整数 n 和 k 个规则。求出经过任意次的变换0次或多次能产生出多少个不同整数。仅要求输出个数。输入说明n kx1 y1x2 y2... ...xn yn输出说明一个整数满足条件的个数个人总结定义一个bool类型reach二维数组--reach[a][b]代表a--b是否存在也就是a能不能到bab是大数n的某一位的数字核心思想就是计算每一位上的数字可以通过规则转变到几个数字自己到自己也算一种然后每位数字对应的个数相乘就是最后的结果由于最后结果可能有9*9*9....数字很大所以用大数乘法因为在数组里面是倒着的所以输出时也要倒叙输出。例如n2342 53 6第一位数字 2可以到达 {25}--2第二位数字3可以到达{36}--2第三位数字可以到达{4}--1一共是2*2*14。代码#includebits/stdc.h using namespace std; vectorint mul(const vectorint a,int b) { vectorint res; int carry0; for(int i0;ia.size();i) { carrya[i]*b; res.push_back(carry%10); carry/10; } while(carry) { res.push_back(carry%10); carry/10; } return res; } int main() { string n; int k; cinnk; //reach[a][b]true表示a可以变成b bool reach[10][10]{false}; for(int i0;i10;i) reach[i][i]true; for(int i0;ik;i) { int x,y; cinxy; reach[x][y]true; } //关键步骤 for(int m0;m10;m) { for(int i0;i10;i) { if(reach[i][m]) { for(int j0;j10;j) { if(reach[m][j]) reach[i][j]true; } } } } int cnt[10]{0}; for(int i0;i10;i) { for(int j0;j10;j) { if(reach[i][j]) cnt[i]; } } //cnt[1]*cnt[2]*...最大可能是9*9*9....很大 vectorint ans; ans.push_back(1);//初始化为1 for(char ch:n) { int dch-0; ansmul(ans,cnt[d]);//大数乘法,ans可能是大数 } for(int ians.size()-1;i0;i--) coutans[i]; coutendl; return 0; }21 分分钟的碎碎念--动规问题描述以前有个孩子他分分钟都在碎碎念。不过他的念头之间是有因果关系的。他会在本子里记录每一个念头并用箭头画出这个念头的来源于之前的哪一个念头。翻开这个本子你一定会被互相穿梭的箭头给搅晕现在他希望你用程序计算出这些念头中最长的一条因果链。将念头从1到n编号念头i来源于念头from[i]保证from[i]ifrom[i]0表示该念头没有来源念头只是脑袋一抽灵光一现。样例输入801032424样例输出3样例说明最长的因果链有1-2-5 (from[5]2,from[2]1,from[1]0)1-2-7 (from[7]2,from[2]1,from[1]0)3-4-6 (from[6]4,from[4]3,from[3]0)3-4-8 (from[8]4,from[4]3,from[3]0)输入说明第一行一个正整数n表示念头的数量接下来n行依次给出from[1]from[2]…from[n]1n1000输出说明共一行一个正整数L表示最长的念头因果链中的念头数量个人总结dp[i]表示以节点i为结尾的最长因果链长度若from[i]0--dp[i]1;否则dp[i]dp[from[i]]1;代码#includebits/stdc.h using namespace std; /*1-n 8 0 源头from[1]0 1 from[2]念头2来源于念头from[2]1 1--2 0 from[3]念头3来源于念头from[3]0 3 from[4]念头4来源于念头from[4]3 3--4 2 from[5]念头5来源于念头from[5]2 2--5 4 from[6]念头6来源于念头from[6]4 4--6 2 from[7]念头7来源于念头from[7]2 2--7 4 from[8]念头8来源于念头from[8]4 4--8 from[i]--i dp[i]表示以节点i为结尾的最长因果链长度 若from[i]0--dp[i]1; 否则dp[i]dp[from[i]]1; */ int main() { int n; cinn; vectorint from(n1); for(int i1;in;i) cinfrom[i]; vectorint dp(n1,0); int maxlen0; for(int i0;in;i) { if(from[i]0) dp[i]1; else { dp[i]dp[from[i]]1; } maxlenmax(maxlen,dp[i]); } coutmaxlenendl; return 0; }22 现代诗如蚯蚓问题描述现代诗如蚯蚓断成好几截都不会死字符串断成好几截有可能完全一样请编写程序输入字符串输出该字符串最多能断成多少截完全一样的子串样例输入abcabcabcabc样例输出4样例说明最多能断成四个”abc”也就是abc重复四遍便是原串同时也能断成两个”abcabc”最坏情况是断成一个原串”abcabcabcabc”输入说明一行一个字符串字符串长度1000输出说明一行一个正整数表示该字符串最多能断成的截数个人总结枚举所有可能的长度首先判断这个长度能否被字符串的长度整除然后提取第一个长度为len的作为模式串与后面的串一次比对并且不断更新最大的分段长度。注maxsegmentsmax(maxsegments,(int)s.length()/len);maxsegments是int类型而n/len 是size_type通常是unsigned long long类型类型不匹配导致,强制类型转换为int类型--(int)s.length()/len。代码#includebits/stdc.h using namespace std; int main() { string s; getline(cin,s); int maxsegments1; for(int len1;lens.length();len) { if(s.length()%len!0) continue; bool validtrue; string patterns.substr(0,len);//模式串 for(int ilen;is.length();ilen) { if(s.substr(i,len)!pattern) { validfalse; break; } } if(valid) { maxsegmentsmax(maxsegments,(int)s.length()/len); } } coutmaxsegmentsendl; return 0; }23 函数求值问题描述设 F(N) 表示正整数 1 到正整数 N 中,数字 1,2 总共出现了多少次。例如 N 10 时:1, 2, 3, 4, 5, 6, 7, 8, 9, 10 这 10 个数中,数字 1 出现了两次,数字 2 出现了 1 次,所以数字 1, 2 总共出现了 3 次,因此 F (10) 3。现在给你正整数 N ,请你求出 F(N) 的值。由于 F(N) 可能很大,你仅需输出 F(N) 除以 20123 的余数。输入说明输入数据仅一行,包含一个正整数 N (1 ≤ N ≤ 10100 ),表示函数 F(N)的参数。输出说明输出仅一个整数,为 F(N) 除以 20123 的余数。代码简单超时版#include bits/stdc.h using namespace std; int countDigits(int n) { int count 0; while (n 0) { int digit n % 10; if (digit 1 || digit 2) { count; } n / 10; } return count; } int main() { int N; cin N; int totalCount 0; for (int i 1; i N; i) { totalCount countDigits(i); } totalCount % 20123; cout totalCount endl; return 0; }AC#include iostream #include string using namespace std; const int MOD 20123; // 把字符串 s 转换成整数并取模 MOD int str_to_mod(const string s) { int res 0; for (char ch : s) { res (res * 10 (ch - 0)) % MOD; } return res; } int main() { string N; cin N; int len N.size(); int ans 0; // 数字 1 和数字 2 分别统计 for (int d 1; d 2; d) { // 逐位计算 int factor 1; // 10^(i-1) mod MOD for (int i 1; i len; i) { // 当前位的权重是 10^(i-1) // high 是 N[0..len-i-1] // cur N[len-i] - 0 // low N[len-i1..len-1] // 计算高位部分 string high_str N.substr(0, len - i); int high (high_str.empty() ? 0 : str_to_mod(high_str)); int cur N[len - i] - 0; // 计算低位部分 string low_str N.substr(len - i 1); int low (low_str.empty() ? 0 : str_to_mod(low_str)); if (cur d) { ans (ans (high 1) * factor) % MOD; } else if (cur d) { ans (ans high * factor low 1) % MOD; } else { // cur d ans (ans high * factor) % MOD; } // factor 更新为 10^i mod MOD factor (factor * 10) % MOD; } } cout ans endl; return 0; }英语
