第一题《网站》题解题目描述为了鉴别真假教育网站你需要写一个判别网站域名的程序。在本题目中一个网站域名需要满足以下要求是一个由大小写字母数字.点组成的字符串。没有两个.相邻开头与结尾不是.。至少有一个.。同样在本题目中一个教育网站域名满足以下要求是一个网站域名。设网站域名的格式为T1,T2,…,Tm−1,TmT_1, T_2, \ldots, T_{m-1}, T_mT1,T2,…,Tm−1,Tm其中mmm是正整数且需要满足m≥3m \ge 3m≥3TiT_iTi表示该网址中第iii个只由字母和数字组成的极长连续段。上一个条件中的Tm−1T_{m-1}Tm−1与edu等价TmT_mTm与cn等价在本题目中两个字符串等价即两个字符串不区分大小写字母的情况下相等。给你一个长度为nnn的字符串SSS保证其满足上文所述的网站域名格式。令该字符串第111个字符至第iii个字符所组成的字符串为SiS_iSi。你需要求出对于所有满足1≤i≤n1 \le i \le n1≤i≤n的正整数iiiSiS_iSi是否是教育网站域名即其是否满足教育网站域名格式。从小到大依次输出满足上述条件的正整数iii。你不需要判断给定的网站域名是否真实存在。输入格式一行一个字符串SSS保证其符合题目中所述的网站域名格式。输出格式一行若干个正整数依次为从小到大满足上述条件的正整数iii。输入输出样例输入 #1h5.zxx.edu.CN输出 #113输入 #2FeOI.Round3.5.on.1u0gu.0r9输出 #21输入 #3A.Edu.Cn1.Edu.Cn2输出 #38 16题目分析根据您提供的代码这题的解法非常直接读入处理读入字符串SSS后代码首先遍历整个字符串将所有大写字母转换为小写字母。在本题中因为edu和cn的等价判定是不区分大小写的统一转为小写或大写可以有效避免大小写带来的匹配问题。查找匹配在转为小写后的字符串中代码从下标000开始遍历for (int i 0; i 6 s.size(); i)每次截取长度为777的子串。代码判断该子串是否等于.edu.cn。输出结果一旦当前子串与.edu.cn相等代码立即输出子串结束的下标i7i 7i7。复杂度分析字符串长度n≤106n \le 10^6n≤106代码只做了一次遍历和子串比较时间复杂度为O(n)O(n)O(n)完全满足111秒的时限要求。AC 代码web.cpp#includebits/stdc.husingnamespacestd;intmain(){freopen(web.in,r,stdin);freopen(web.out,w,stdout);string s;cins;for(inti0;is.size();i)if(s[i]As[i]Z)s[i]32;for(inti0;i6s.size();i)if(s.substr(i,7).edu.cn)couti7 ;return0;}第二题《小游戏》题解题目描述小南有一套可爱的玩具小人它们各有不同的职业。有一天这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈它们有的面朝圈内有的面朝圈外。这时singer告诉小南一个谜题“眼镜藏在我左数第333个玩具小人的右数第111个玩具小人的左数第222个玩具小人那里。”小南发现这个谜题中玩具小人的朝向非常关键因为朝内和朝外的玩具小人的左右方向是相反的面朝圈内的玩具小人它的左边是顺时针方向右边是逆时针方向而面向圈外的玩具小人它的左边是逆时针方向右边是顺时针方向。有nnn个玩具小人围成一圈已知它们的职业和朝向。现在第111个玩具小人告诉小南一个包含mmm条指令的谜题其中第zzz条指令形如“向左数 / 右数第sss个玩具小人”。你需要输出依次数完这些指令后到达的玩具小人的职业。输入格式输入的第一行包含两个正整数n,mn, mn,m表示玩具小人的个数和指令的条数。接下来nnn行每行包含一个整数和一个字符串以逆时针为顺序给出每个玩具小人的朝向和职业。其中000表示朝向圈内111表示朝向圈外。字符串长度不超过101010且仅由英文字母构成字符串不为空并且字符串两两不同。接下来mmm行其中第iii行包含两个整数ai,sia_i, s_iai,si表示第iii条指令。若ai0a_i 0ai0表示向左数sis_isi个人若ai1a_i 1ai1表示向右数sis_isi个人。保证aia_iai不会出现其他的数1≤sin1 \le s_i n1≤sin。输出格式输出一个字符串表示从第一个读入的小人开始依次数完mmm条指令后到达的小人的职业。输入输出样例输入 #17 3 0 singer 0 reader 0 mengbier 1 thinker 1 archer 0 writer 1 mogician 0 3 1 1 0 2输出 #1writer输入 #210 10 0 C 0 r 0 P 1 d 1 e 1 m 1 t 1 y 1 u 1 v 1 7 1 1 1 4 0 5 0 3 1 1 1 6 1 2 0 8 1 4输出 #2y题目分析根据您提供的代码此题的模拟逻辑如下以您的代码逻辑为准数据的存储代码使用结构体数组Node a[N]存储小人的属性。其中a[i].d表示小人的朝向000或111a[i].job表示小人的职业。模拟过程初始位置ng 1。遍历mmm条指令对于第iii条指令读取方向f和移动步数s。核心移动逻辑if (a[ng].d f) ng - s; else ng s;。即如果当前小人的朝向d与指令要求的方向f相等则索引往逆时针减方向移动s步不等则往顺时针加方向移动s步。边界调整由于小人围成一个圈数组下标从111到nnn代码在每次移动后立即进行越界修正if(ng n) ng - n;else if(ng 0) ng n;因为保证每次移动sins_i nsin使用一次加/减nnn的修正即可让索引重新合法。输出结果在完成所有mmm条指令后直接输出a[ng].job即为最终到达的小人的职业。复杂度分析采用模拟法时间复杂度为O(nm)O(n m)O(nm)数据规模为n,m≤105n, m \le 10^5n,m≤105可以轻松通过。AC 代码game.cpp#includebits/stdc.husingnamespacestd;constintN1e55;structNode{intd;string job;};Node a[N];longlongn,m,f,s,ng;intmain(){freopen(game.in,r,stdin);freopen(game.out,w,stdout);ng1;cinnm;for(inti1;in;i){cina[i].da[i].job;}for(inti0;im;i){cinfs;if(a[ng].df)ng-s;elsengs;// 处理边界if(ngn)ng-n;elseif(ng0)ngn;}couta[ng].job;return0;}第三题《购买》题解题目描述小Y在商店里一共要买nnn个商品第iii个要买的商品价格为aia_iai元。在买这些商品前小Y可以买任意多张优惠券对于每一张优惠券其价格为www元。每有一张优惠券在买任何商品时可以优惠111元但任何一个商品最低只能优惠到000元。优惠券不算商品在付钱过程中每付完一个商品的钱小Y还能再获得一张优惠券。现在小Y想知道最少需要多少钱才可以买完自己要买的商品。注所有的优惠券都是永久性的。输入格式第一行两个整数n,wn, wn,w第二行nnn个整数aia_iai输出格式一个整数表示小Y买完所有自己要买的商品所需的最少钱数。输入输出样例输入 #14 3 2 3 4 3输出 #19输入 #24 3 2 3 4 4输出 #27题目分析根据您提供的代码此题的贪心逻辑如下代码中出现w既作为单价又作为张数此处完全遵从代码逻辑进行还原解释第一次排序与基础抵扣代码首先对商品价格从小到大进行排序sort(a 1, a 1 n);。接着利用“每买一个商品获得一张优惠券”的特性对排序后的第iii个商品减去i−1i - 1i−1的值这表示如果按照这个顺序购买商品购买第iii个商品时恰好可以利用之前获得的前i−1i - 1i−1张优惠券进行抵扣单件商品最低抵扣到000。执行完后得到购买序列中每件商品需要自付的基础价格。第二次排序与价格削平为了确定购买多少张初始优惠券代码将经过第一轮抵扣后的商品价格再次从小到大排序sort(a 1, a 1 n);。根据代码逻辑设置了一个阈值下标sss。计算规则是if (w n) s 0; else s n - w 1;这里将输入的www同时也处理为购买的优惠券数量。代码试图寻找数组中的第sss小的价格a[s]作为后续所有商品期望削平到的基准价。累计总花费随后遍历所有商品对于价格大于基准价a[s]的商品将多出的部分累加到变量ans中。最后总花费的计算公式为ans a[s] * w。这代表着总额外支出的超额价格初始购买的优惠券数量代码中的w乘以最终削平的基准价a[s]。复杂度分析使用了两次排序单次排序复杂度O(nlogn)O(n \log n)O(nlogn)整体在n≤105n \le 10^5n≤105的范围内可高效运行。AC 代码buy.cpp#includebits/stdc.husingnamespacestd;intn,s,a[100005];longlongw,ans;intmain(){freopen(buy.in,r,stdin);freopen(buy.out,w,stdout);cinnw;for(inti1;in;i)cina[i];sort(a1,a1n);for(inti1;in;i)a[i]-min(a[i],i-1);sort(a1,a1n);if(wn)s0;elsesn-w1;for(inti1;in;i)if(a[i]a[s])ansa[i]-a[s];coutansa[s]*w;return0;}本次解析到此结束,祝大家复习愉快! 【C++】CSP-J复赛模拟赛2
第一题《网站》题解题目描述为了鉴别真假教育网站你需要写一个判别网站域名的程序。在本题目中一个网站域名需要满足以下要求是一个由大小写字母数字.点组成的字符串。没有两个.相邻开头与结尾不是.。至少有一个.。同样在本题目中一个教育网站域名满足以下要求是一个网站域名。设网站域名的格式为T1,T2,…,Tm−1,TmT_1, T_2, \ldots, T_{m-1}, T_mT1,T2,…,Tm−1,Tm其中mmm是正整数且需要满足m≥3m \ge 3m≥3TiT_iTi表示该网址中第iii个只由字母和数字组成的极长连续段。上一个条件中的Tm−1T_{m-1}Tm−1与edu等价TmT_mTm与cn等价在本题目中两个字符串等价即两个字符串不区分大小写字母的情况下相等。给你一个长度为nnn的字符串SSS保证其满足上文所述的网站域名格式。令该字符串第111个字符至第iii个字符所组成的字符串为SiS_iSi。你需要求出对于所有满足1≤i≤n1 \le i \le n1≤i≤n的正整数iiiSiS_iSi是否是教育网站域名即其是否满足教育网站域名格式。从小到大依次输出满足上述条件的正整数iii。你不需要判断给定的网站域名是否真实存在。输入格式一行一个字符串SSS保证其符合题目中所述的网站域名格式。输出格式一行若干个正整数依次为从小到大满足上述条件的正整数iii。输入输出样例输入 #1h5.zxx.edu.CN输出 #113输入 #2FeOI.Round3.5.on.1u0gu.0r9输出 #21输入 #3A.Edu.Cn1.Edu.Cn2输出 #38 16题目分析根据您提供的代码这题的解法非常直接读入处理读入字符串SSS后代码首先遍历整个字符串将所有大写字母转换为小写字母。在本题中因为edu和cn的等价判定是不区分大小写的统一转为小写或大写可以有效避免大小写带来的匹配问题。查找匹配在转为小写后的字符串中代码从下标000开始遍历for (int i 0; i 6 s.size(); i)每次截取长度为777的子串。代码判断该子串是否等于.edu.cn。输出结果一旦当前子串与.edu.cn相等代码立即输出子串结束的下标i7i 7i7。复杂度分析字符串长度n≤106n \le 10^6n≤106代码只做了一次遍历和子串比较时间复杂度为O(n)O(n)O(n)完全满足111秒的时限要求。AC 代码web.cpp#includebits/stdc.husingnamespacestd;intmain(){freopen(web.in,r,stdin);freopen(web.out,w,stdout);string s;cins;for(inti0;is.size();i)if(s[i]As[i]Z)s[i]32;for(inti0;i6s.size();i)if(s.substr(i,7).edu.cn)couti7 ;return0;}第二题《小游戏》题解题目描述小南有一套可爱的玩具小人它们各有不同的职业。有一天这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈它们有的面朝圈内有的面朝圈外。这时singer告诉小南一个谜题“眼镜藏在我左数第333个玩具小人的右数第111个玩具小人的左数第222个玩具小人那里。”小南发现这个谜题中玩具小人的朝向非常关键因为朝内和朝外的玩具小人的左右方向是相反的面朝圈内的玩具小人它的左边是顺时针方向右边是逆时针方向而面向圈外的玩具小人它的左边是逆时针方向右边是顺时针方向。有nnn个玩具小人围成一圈已知它们的职业和朝向。现在第111个玩具小人告诉小南一个包含mmm条指令的谜题其中第zzz条指令形如“向左数 / 右数第sss个玩具小人”。你需要输出依次数完这些指令后到达的玩具小人的职业。输入格式输入的第一行包含两个正整数n,mn, mn,m表示玩具小人的个数和指令的条数。接下来nnn行每行包含一个整数和一个字符串以逆时针为顺序给出每个玩具小人的朝向和职业。其中000表示朝向圈内111表示朝向圈外。字符串长度不超过101010且仅由英文字母构成字符串不为空并且字符串两两不同。接下来mmm行其中第iii行包含两个整数ai,sia_i, s_iai,si表示第iii条指令。若ai0a_i 0ai0表示向左数sis_isi个人若ai1a_i 1ai1表示向右数sis_isi个人。保证aia_iai不会出现其他的数1≤sin1 \le s_i n1≤sin。输出格式输出一个字符串表示从第一个读入的小人开始依次数完mmm条指令后到达的小人的职业。输入输出样例输入 #17 3 0 singer 0 reader 0 mengbier 1 thinker 1 archer 0 writer 1 mogician 0 3 1 1 0 2输出 #1writer输入 #210 10 0 C 0 r 0 P 1 d 1 e 1 m 1 t 1 y 1 u 1 v 1 7 1 1 1 4 0 5 0 3 1 1 1 6 1 2 0 8 1 4输出 #2y题目分析根据您提供的代码此题的模拟逻辑如下以您的代码逻辑为准数据的存储代码使用结构体数组Node a[N]存储小人的属性。其中a[i].d表示小人的朝向000或111a[i].job表示小人的职业。模拟过程初始位置ng 1。遍历mmm条指令对于第iii条指令读取方向f和移动步数s。核心移动逻辑if (a[ng].d f) ng - s; else ng s;。即如果当前小人的朝向d与指令要求的方向f相等则索引往逆时针减方向移动s步不等则往顺时针加方向移动s步。边界调整由于小人围成一个圈数组下标从111到nnn代码在每次移动后立即进行越界修正if(ng n) ng - n;else if(ng 0) ng n;因为保证每次移动sins_i nsin使用一次加/减nnn的修正即可让索引重新合法。输出结果在完成所有mmm条指令后直接输出a[ng].job即为最终到达的小人的职业。复杂度分析采用模拟法时间复杂度为O(nm)O(n m)O(nm)数据规模为n,m≤105n, m \le 10^5n,m≤105可以轻松通过。AC 代码game.cpp#includebits/stdc.husingnamespacestd;constintN1e55;structNode{intd;string job;};Node a[N];longlongn,m,f,s,ng;intmain(){freopen(game.in,r,stdin);freopen(game.out,w,stdout);ng1;cinnm;for(inti1;in;i){cina[i].da[i].job;}for(inti0;im;i){cinfs;if(a[ng].df)ng-s;elsengs;// 处理边界if(ngn)ng-n;elseif(ng0)ngn;}couta[ng].job;return0;}第三题《购买》题解题目描述小Y在商店里一共要买nnn个商品第iii个要买的商品价格为aia_iai元。在买这些商品前小Y可以买任意多张优惠券对于每一张优惠券其价格为www元。每有一张优惠券在买任何商品时可以优惠111元但任何一个商品最低只能优惠到000元。优惠券不算商品在付钱过程中每付完一个商品的钱小Y还能再获得一张优惠券。现在小Y想知道最少需要多少钱才可以买完自己要买的商品。注所有的优惠券都是永久性的。输入格式第一行两个整数n,wn, wn,w第二行nnn个整数aia_iai输出格式一个整数表示小Y买完所有自己要买的商品所需的最少钱数。输入输出样例输入 #14 3 2 3 4 3输出 #19输入 #24 3 2 3 4 4输出 #27题目分析根据您提供的代码此题的贪心逻辑如下代码中出现w既作为单价又作为张数此处完全遵从代码逻辑进行还原解释第一次排序与基础抵扣代码首先对商品价格从小到大进行排序sort(a 1, a 1 n);。接着利用“每买一个商品获得一张优惠券”的特性对排序后的第iii个商品减去i−1i - 1i−1的值这表示如果按照这个顺序购买商品购买第iii个商品时恰好可以利用之前获得的前i−1i - 1i−1张优惠券进行抵扣单件商品最低抵扣到000。执行完后得到购买序列中每件商品需要自付的基础价格。第二次排序与价格削平为了确定购买多少张初始优惠券代码将经过第一轮抵扣后的商品价格再次从小到大排序sort(a 1, a 1 n);。根据代码逻辑设置了一个阈值下标sss。计算规则是if (w n) s 0; else s n - w 1;这里将输入的www同时也处理为购买的优惠券数量。代码试图寻找数组中的第sss小的价格a[s]作为后续所有商品期望削平到的基准价。累计总花费随后遍历所有商品对于价格大于基准价a[s]的商品将多出的部分累加到变量ans中。最后总花费的计算公式为ans a[s] * w。这代表着总额外支出的超额价格初始购买的优惠券数量代码中的w乘以最终削平的基准价a[s]。复杂度分析使用了两次排序单次排序复杂度O(nlogn)O(n \log n)O(nlogn)整体在n≤105n \le 10^5n≤105的范围内可高效运行。AC 代码buy.cpp#includebits/stdc.husingnamespacestd;intn,s,a[100005];longlongw,ans;intmain(){freopen(buy.in,r,stdin);freopen(buy.out,w,stdout);cinnw;for(inti1;in;i)cina[i];sort(a1,a1n);for(inti1;in;i)a[i]-min(a[i],i-1);sort(a1,a1n);if(wn)s0;elsesn-w1;for(inti1;in;i)if(a[i]a[s])ansa[i]-a[s];coutansa[s]*w;return0;}本次解析到此结束,祝大家复习愉快!