1分糖果分析本题是初赛第一题按照以往经验这一题一般是小模拟题或者数学题。我们可以发现本题的大意是要求我们那一些糖果并分给n个人直到糖果数小于n。看得出来本题的考察范围是数学计算如果我们能找到通用公式计算就可以避免模拟。其核心思路就是取余和特判如果l和r达到某某要求则使用特别公式。解题思路我们可以分析一下由于题目的特殊性质这道题我们直接使用区域公式计算的同时也有某些情况无需计算只需直接输出n即可。题目的核心是在[l,r]区间中找一个数k使得k % n最大。当l和r于同一个周期内说明其中所有值%n的值都相同我们就可以输出r%n代表所以区间内值的最优。、反之不在同一个周期内则小朋友会一直那直到小于n这样最大只有n-1就输出理论极限n-1。我们来模拟下样例证明思路。7 16 2316和23不在同一周期则输出理论极限n-1即6正确。样例通过证明我们的思路正确接下来构造代码#includebits/stdc.h using namespace std; long long n,l,r;//初始化 int main(){ cinnlr;//输入 if (l/n!r/n)//跨越周期输入理论极限 coutn-1; else coutr%n;//在同一个周期内余数随着数字的增大而严格单调递增商相同我们只需输出区间最大值r取余n的区间公共余数即可 return 0; }2插入排序分析本题要求输入一个数组然后进行q次查询排序或改值。不难看出来这是一道大模拟题或者交互题。每次进行查询然后进行相对修改即可。注意一个要点本题的排序操作不可以永久修改。然后我们对样例模拟一下证明我们的思路。3 4为首先输入的两个。3 2 1为输入的序列。接下来4行输入。2 3插入排序并输出原来第3个元素的新位置由于进行了排序a被排到了第一个输出1。1 3 23的位置变为2现在是3 2 2。2 22的位置是2经排序后相对位置不变为1。2 33的位置为2经排序后相对位置不变为2。样例证明我们的猜想是正确的接下来我们来构建代码#includebits/stdc.h using namespace std; struct Node{ int m; bool f;//定义标记结构体 }; int n,q,a[8020];//初始化 int main(){ cinnq; for (int i 1;i n;i){ cina[i];//输入 } while (q--){//q次查询 int w;cinw; if (w 1){//路径1 int x,v; cinxv; a[x] v;//修改 continue;//跳过 } int x;cinx;Node b[8020];//标记数组 for (int i 1;i n;i){ b[i].m a[i]; b[i].f false;//标记给定下标 } b[x].f true;//修改 for (int i 1;i n;i) for (int j i;j 2;j--) if (b[j].m b[j-1].m) swap(b[j-1],b[j]);//插入排序 for (int i 1;i n;i){ if (b[i].f true){//查找下标 coutiendl; break; } } } return 0; }然而我们发现这题因为样例很大此做法只有50分。接下来我们来优化。这道题的TLE罪魁祸首是排序导致代码复杂度变为O(n^n)如果我们能够修改代码变为去除循环内的代码则复杂度为O(n)就可以通过。我们可以将插入排序转换为局部的修改这样可以达到线性复杂度。我们可以新建一个映射这个映射包含排序前的内容可以保存信息。然后我们每次修改只需对表修改对局部进行插入即可。每次我们进行1操作时更新原数组更新复制数组然后扫描数组找到局部可插入位置插入并重新映射修改原数组即可这样2操作只要查询即可。#includebits/stdc.h using namespace std; int n,q; vectorpairint,int a;//原数组 vectorpairint,int temp;复制数组 int main(){ cinnq; for (int i 0;i n;i){//输入 int x;cinx; a.push_back({x,i});//插入信息 }temp a; sort(temp.begin(),temp.end());//排一次序保证以后局部有序 vectorint pos(n);//映射数组 for (int i 0;i n;i) pos[temp[i].second]i;//映射 while (q--){//多次操作 int k; cink; if (k 1){ int x,y;cinxy; x--; int ppos[x];//找到旧元素在temp中的位置 for(int ip;itemp.size()-1;i) temp[i] temp[i1];//后面的元素整体前移覆盖掉旧元素 temp.pop_back();//删除尾部多余元素 for (int i p;i temp.size();i) pos[temp[i].second]i;//更新映射 a[x].first y;//更新原数组值 int ispos 0;//线性扫描找到新值应该插入的位置 while (ispostemp.size()temp[ispos]a[x]) ispos; temp.push_back({0,0});//更新复制数组 for (int itemp.size()-1;iispos;i--) temp[i] temp[i-1];//从后往前移动元素腾出ispos位置 temp[ispos] a[x];//插入新元素 for (int i ispos;i temp.size();i) pos[temp[i].second] i;//建立新映射 }else{ int x;//因为每次修改都更新所以这里只需直接查询即可 cinx; x--; coutpos[x]1endl;//下标对齐 } } }3网络连接分析不愧是绿题连描述都那么长。实则翻译过来只有几句话。核心意思给定任意个机器每台机器有一个独立ip号。若是服务器则新建服务并查看如果格式正确且ip没有被占用则是一个可用的端口号注册新服务器。若是客户端则判断加入的ip是否存在如果是则加入并输出改ip服务器的编号否则报错。每一台机器都有一个独立编号比上一个1。这大概就是题目意思。我们来模拟下样例。第一个server且格式正确建立服务器。第二个ip被占用所以输出FAIL。第三个ip正确加入并输出编号。第四个不存在服务器所以报错FAIL。第五个格式错误直接报ERR。这就是我们的想法完全一样接下来展示代码#includebits/stdc.h using namespace std; struct Node{ string j;//状态结构体 int id; }; int n; bool check(string ip){ int cnt1 0,cnt2 0; for (int i 0;i ip.size();i){ if (ip[i] .) cnt1; if (ip[i] :)//统计符号数量 cnt2; } if (cnt1 ! 3) return false; if (cnt2 ! 1) return false;//不对剔除 string be ;//线性字符串扫描be用来存之前截下来的 for (int i 0;i ip.size();i){//扫描 if (ip[i] . || ip[i] :){//是符号 if (be.empty()) return false;//符号前的内容是空剔除 if (be.size() 1 be[0] 0) return false;//前导0太多剔除 for (int j 0;j be.size();j) if (!isdigit(be[j])) //不是数字 return false;//剔除 long long num stoll(be);//字符串转long long if (num 0 || num 255) //超出范围剔除 return false; be ; }else be ip[i];//累加以便判断 } if (be.empty()) return false;//最后一段为空剔除 if (be.size() 1 be[0] 0) return false;//前导0太多剔除 for (int j 0;j be.size();j) if (!isdigit(be[j])) return false;//不是数字 long long num stoll(be);//转换类型 if (num 0 || num 65535) return false;//范围不符合 return true;//正确的地址 } pairbool,int in(string ip,vectorNode a){//当前地址是否存在 for (int i 0;i a.size();i) if (ip a[i].j) return {true,a[i].id};//返回 return {false,-1}; } int main(){ ios::sync_with_stdio(false); cin.tie(nullptr);cinn; vectorNode a;//服务器数组 int i 1;//编号 while (n--){ string m;cinm; string ip;cinip;//输入 if (!check(ip))//不是正确地址 coutERRendl; else if (m Server){//服务器 auto ans in(ip,a);//当前地址状态 if (ans.first){ coutFAILendl;//已经存在这次申请失效 }else{ coutOKendl;//申请成功 a.push_back({ip,i});//更新 } }else if (m Client){//客户端 auto ans in(ip,a); if (ans.first)//存在 coutans.secondendl;//成功访问输出编号 else coutFAILendl;//失败没有地址 } i;//编号累加 } return 0; }完成了现在分数来到了300分一等奖