第一题《网站》题解

题目描述

为了鉴别真假教育网站，你需要写一个判别网站域名的程序。

在本题目中，一个网站域名需要满足以下要求：

• 是一个由大小写字母，数字，.（点）组成的字符串。
• 没有两个.相邻，开头与结尾不是.。
• 至少有一个.。

同样在本题目中，一个教育网站域名满足以下要求：

• 是一个网站域名。
• 设网站域名的格式为T1,T2,…,Tm−1,TmT_1, T_2, \ldots, T_{m-1}, T_mT1​,T2​,…,Tm−1​,Tm​，其中mmm是正整数且需要满足m≥3m \ge 3m≥3，TiT_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的正整数iii，SiS_iSi​是否是教育网站域名，即其是否满足教育网站域名格式。从小到大依次输出满足上述条件的正整数iii。

你不需要判断给定的网站域名是否真实存在。

输入格式

一行一个字符串SSS，保证其符合题目中所述的网站域名格式。

输出格式

一行若干个正整数，依次为从小到大满足上述条件的正整数iii。

输入输出样例

输入 #1

h5.zxx.edu.CN

输出 #1

13

输入 #2

FeOI.Round3.5.on.1u0gu.0r9

输出 #2

1

输入 #3

A.Edu.Cn1.Edu.Cn2

输出 #3

8 16

题目分析

根据您提供的代码，这题的解法非常直接：

1. 读入处理：读入字符串SSS后，代码首先遍历整个字符串，将所有大写字母转换为小写字母。在本题中，因为edu和cn的等价判定是不区分大小写的，统一转为小写（或大写）可以有效避免大小写带来的匹配问题。
2. 查找匹配：在转为小写后的字符串中，代码从下标000开始遍历（for (int i = 0; i + 6 < s.size(); i++)），每次截取长度为777的子串。代码判断该子串是否等于".edu.cn"。
3. 输出结果：一旦当前子串与".edu.cn"相等，代码立即输出子串结束的下标i+7i + 7i+7。
4. 复杂度分析：字符串长度n≤106n \le 10^6n≤106，代码只做了一次遍历和子串比较，时间复杂度为O(n)O(n)O(n)，完全满足111秒的时限要求。

AC 代码（web.cpp）

#include<bits/stdc++.h>usingnamespacestd;intmain(){freopen("web.in","r",stdin);freopen("web.out","w",stdout);string s;cin>>s;for(inti=0;i<s.size();i++)if(s[i]>='A'&&s[i]<='Z')s[i]+=32;for(inti=0;i+6<s.size();i++)if(s.substr(i,7)==".edu.cn")cout<<i+7<<" ";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条指令。若ai=0a_i = 0ai​=0，表示向左数sis_isi​个人；若ai=1a_i = 1ai​=1，表示向右数sis_isi​个人。保证aia_iai​不会出现其他的数，1≤si<n1 \le s_i < n1≤si​<n。

输出格式

输出一个字符串，表示从第一个读入的小人开始，依次数完mmm条指令后到达的小人的职业。

输入输出样例

输入 #1

7 3 0 singer 0 reader 0 mengbier 1 thinker 1 archer 0 writer 1 mogician 0 3 1 1 0 2

输出 #1

writer

输入 #2

10 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

输出 #2

y

题目分析

根据您提供的代码，此题的模拟逻辑如下（以您的代码逻辑为准）：

1. 数据的存储：代码使用结构体数组Node a[N]存储小人的属性。其中a[i].d表示小人的朝向（000或111），a[i].job表示小人的职业。
2. 模拟过程：
   • 初始位置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;
       因为保证每次移动si<ns_i < nsi​<n，使用一次加/减nnn的修正即可让索引重新合法。
3. 输出结果：在完成所有mmm条指令后，直接输出a[ng].job即为最终到达的小人的职业。
4. 复杂度分析：采用模拟法，时间复杂度为O(n+m)O(n + m)O(n+m)，数据规模为n,m≤105n, m \le 10^5n,m≤105，可以轻松通过。

AC 代码（game.cpp）

#include<bits/stdc++.h>usingnamespacestd;constintN=1e5+5;structNode{intd;string job;};Node a[N];longlongn,m,f,s,ng;intmain(){freopen("game.in","r",stdin);freopen("game.out","w",stdout);ng=1;cin>>n>>m;for(inti=1;i<=n;i++){cin>>a[i].d>>a[i].job;}for(inti=0;i<m;i++){cin>>f>>s;if(a[ng].d==f)ng-=s;elseng+=s;// 处理边界if(ng>n)ng-=n;elseif(ng<=0)ng+=n;}cout<<a[ng].job;return0;}

第三题《购买》题解

题目描述

小Y在商店里一共要买nnn个商品，第iii个要买的商品价格为aia_iai​元。
在买这些商品前，小Y可以买任意多张优惠券，对于每一张优惠券，其价格为www元。每有一张优惠券，在买任何商品时可以优惠111元，但任何一个商品最低只能优惠到000元。（优惠券不算商品）
在付钱过程中，每付完一个商品的钱，小Y还能再获得一张优惠券。

现在小Y想知道，最少需要多少钱才可以买完自己要买的商品。
注：所有的优惠券都是永久性的。

输入格式

第一行两个整数n,wn, wn,w
第二行nnn个整数aia_iai​

输出格式

一个整数，表示小Y买完所有自己要买的商品所需的最少钱数。

输入输出样例

输入 #1

4 3 2 3 4 3

输出 #1

9

输入 #2

4 3 2 3 4 4

输出 #2

7

题目分析

根据您提供的代码，此题的贪心逻辑如下（代码中出现w既作为单价又作为张数，此处完全遵从代码逻辑进行还原解释）：

1. 第一次排序与基础抵扣：

   • 代码首先对商品价格从小到大进行排序（sort(a + 1, a + 1 + n);）。
   • 接着，利用“每买一个商品获得一张优惠券”的特性，对排序后的第iii个商品减去i−1i - 1i−1的值，这表示如果按照这个顺序购买商品，购买第iii个商品时恰好可以利用之前获得的前i−1i - 1i−1张优惠券进行抵扣（单件商品最低抵扣到000）。
   • 执行完后，得到购买序列中每件商品需要自付的基础价格。

2. 第二次排序与价格削平：

   • 为了确定购买多少张初始优惠券，代码将经过第一轮抵扣后的商品价格再次从小到大排序（sort(a + 1, a + 1 + n);）。
   • 根据代码逻辑，设置了一个阈值下标sss。计算规则是：if (w > n) s = 0; else s = n - w + 1;（这里将输入的www同时也处理为购买的优惠券数量）。
   • 代码试图寻找数组中的第sss小的价格a[s]，作为后续所有商品期望削平到的基准价。

3. 累计总花费：

   • 随后遍历所有商品，对于价格大于基准价a[s]的商品，将多出的部分累加到变量ans中。
   • 最后，总花费的计算公式为：ans + a[s] * w。这代表着：总额外支出的超额价格+初始购买的优惠券数量（代码中的w）乘以最终削平的基准价（a[s]）。

4. 复杂度分析：使用了两次排序，单次排序复杂度O(nlog⁡n)O(n \log n)O(nlogn)，整体在n≤105n \le 10^5n≤105的范围内可高效运行。

AC 代码（buy.cpp）

#include<bits/stdc++.h>usingnamespacestd;intn,s,a[100005];longlongw,ans;intmain(){freopen("buy.in","r",stdin);freopen("buy.out","w",stdout);cin>>n>>w;for(inti=1;i<=n;i++)cin>>a[i];sort(a+1,a+1+n);for(inti=1;i<=n;i++)a[i]-=min(a[i],i-1);sort(a+1,a+1+n);if(w>n)s=0;elses=n-w+1;for(inti=1;i<=n;i++)if(a[i]>a[s])ans+=a[i]-a[s];cout<<ans+a[s]*w;return0;}

本次解析到此结束,祝大家复习愉快!😛