A.Yura'sNewName 题意： 给出一个仅由_或^组成的字符串，你可以在任意位置添加_或^字符，使得字符串满足：任意字符要么属于^_^的一部分，要么属于^^的一部分。求最少添加的字符数量。 分析： 对于_我们只需处理没有组成^_^的_:①如果_在首位置且左边没有^则添加^②如果_在尾位置且右边没有^则添加^③如果_在中间部分且右边没有^则添加^ 当字符串只有一个^时末尾添加一个^ code: include<bits/stdc.h> usingnamespacestd; intmain() { std::ios::sync_with_stdio(false); c...

A.猫猫与广告 题目： 分析： 只需考虑cd的矩阵竖着摆和横着摆两种情况。本题提示了考虑两矩阵对应边平行的情况，实际上可以证明倘若能斜着放，那么一定可以横着放或竖着放，证明方式可已通过构造三角形来证明ab的矩阵的长宽一定小于cd矩阵的长宽。 code: include<iostream> include<cmath> usingnamespacestd; intmain() { inta,b,c,d; cin>>a>>b>>c>>d; if(a>b)swap(a,b); if(c>d)swap(c,d)...

A.TubeTubeFeed 分析: 从所有a[i]+i-1<=t的选择种取个max即可 code: include<bits/stdc.h> usingnamespacestd; constintN=55; inta[N],b[N]; intmain() { std::ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); intt; cin>>t; while(t--) { intn,m; cin>>n>>m; for(inti=0;i<n;...

A.LoveStory 题意: 给定n个长度为10的字符串，问其与codeforces字符串的对应下标字母不同的个数。 分析: 对于每个字符串从前往后依次和“codeforces”对应字符比较然后统计不同字母数即可 code: include<bits/stdc.h> usingnamespacestd; intmain() { std::ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); strings="codeforces"; intt; cin>>t; while(t--) { ...

A.跳跃游戏 题目： 分析： 根据跳跃规则，只要中间存在高度介于起点和终点之间的平台即可让小Z从第一个平台跳到最后一个平台。 code: include<bits/stdc.h> usingnamespacestd; constintN=1e5+5; inta[N]; intmain() { std::ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); intn; cin>>n; for(inti=0;i<n;i) cin>>a[i]; boolcheck=false; if(a[0]&...

A.MusicalPuzzle 题意： 用最少的长度为2的字符串按一定规则拼出s。规则是：前一个字符串的尾与后一个字符串的首相同。 分析： 统计s中长度为2的不同字符串数量。 代码： include<bits/stdc.h> usingnamespacestd; typedeflonglongLL; constintN=1e5; intmain() { std::ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); intt; cin>>t; while(t--) { unordered_map&...

A.最小的数字 题目： 分析： 简单枚举一下，找到第一个大于等于n的且是3的倍数的数 代码： include<bits/stdc.h> usingnamespacestd; intmain() { intn; cin>>n; boolloop=true; if(n%30) loop=false; while(loop) { n; if(n%30) loop=false; } cout<<n; return0; } B.优美的GCD 题目: 分析: 根据题目条件，用两个质数分别乘以n即可构造出答案。 代码： include<bits/s...

A.上班 题意： 分析： 签到题 代码： include<bits/stdc.h> usingnamespacestd; intmain() { intx,y,z; cin>>x>>y>>z; cout<<x+min(y,z); return0; } B.崇拜 题意： 分析： 按知识点难度从大到小排序，然后计算按这个顺序讲解的最大崇拜值。 代码： include<bits/stdc.h> usingnamespacestd; constintN=2e5+5; inta[N]; boolcmp(intA,in...

D.Chocolate 题意： 有一个n×m的矩形巧克力，Kelin先手WalkAlone后手选一个点(i,j)并吃掉所有x<=i,y<=j的巧克力，谁吃掉最后一块巧克力则输。 分析： 对矩形大小进行讨论：①1×1时，Kelin必输②1×n或1×m时：Kelin可以选择吃掉n-1或m-1块巧克力，因此Kelin必胜③n×m时：Kelin吃掉一块后WalkAlone将面对一个对角形状，此时WalkAlone只有两种选择：维持对角形状或者将其吃成矩形。（1）如果WalkAlone选择维持对角形状，那么Kelin可以选择镜像的和WalkAlone吃同样大小的巧克力，始终保持对称。因此，留...

1001Hide-And-SeekGame 题意: 给出一颗树，两人在树上特定两点来回走，问最早在那个节点相遇。 分析： 两条路径相交，则一条路径的LCA一定在另一条路径上。我们可以预处理一个dfs时间戳，结合LCA来判断路径相交。由于本题的点数较小,所以我们可以枚举相交链上的每一个点，然后计算他们在这个点最早相遇的时间，找到其中相遇时间最早的点作为答案输出。对于相交链上的一个点x,我们可以计算出A到达x的时间满足2k1·dis(Sa,Ta)+dis(Sa,x)或者2k1.dis(Sa,Ta)+dis(Sa,Ta)+dis(Ta,x)。(其中k为任意正整数)类似的，B到达x的时间满足2k2·d...

1001AliceGame 题意： 起初有n个物品，玩家可以有如下操作：①若该堆物品数量小于等于k，全部拿走。②若该堆物品数量大于k，则只能选择拿走k个物品，并将剩余物品分成不为空的两堆。Alice先手，问谁必胜。 分析： 打表可知当n%(4k+2)k+1时Alice必败，其他时候必胜。打表代码： include<bits/stdc.h> usingnamespacestd; typedeflonglongLL; constintN=1e6+5; LLf[N]; intsg(intx,intk){ if(f[x]!=-1) returnf[x]; set<i...

D.TheGameofEating 题意: 一共有m道菜，n个人轮流点，一共点k道。第i个人对第j道菜的喜爱程度\(A_i\)公开,一个人点了菜所有人都可以吃到。每个人都希望最大化自己的喜爱程度之和，求最终的点菜集合。 分析： 倒着贪心，如果最后一个人最喜欢吃的菜没被选那么他一定会选择这道菜，则其他人不会浪费机会选这道菜，他们会选择从剩下的菜中选择自己最喜欢的，以此类推，可以保证最大化每个人的收益。 代码: include<bits/stdc.h> usingnamespacestd; constintN=2007; inta[N][N]; boolvis[N]; vector&...

A.WorldFragmentsI 题意: 给定两个非负二进制数a和b，每次从a中选择某个数位x(0/1)，并令a=a+x或a=ax,问将a变成b的最小操作数，无解输出-1。 分析： ①a=b时输出0②a≠b时，若a=0，b≠0则无解，否则输出|ab| 代码： include<bits/stdc.h> usingnamespacestd; typedeflonglongLL; LLget(string&s){ LLres=0; reverse(s.begin(),s.end()); for(inti=0;i<s.size();i){ if(s[i]'1') re...

1005.OutofControl 题意: 有n个数\(x_1,x_2,...,x_n\)，在其中选k个数依次放入栈中。如果当前放入栈中的数\(x_i\)小于栈顶的数，则向栈中放入与先前的栈顶相同的数而不是\(x_i\)。求对于每个k对应的方案数。 分析： 先排序离散化，然后考虑dp。状态定义:f[i][j]表示长度为i且最后一个数是j的方案数。状态转移：f[i][j]=\(\sum_{t=1}^jf[i1][t]\)答案：长度为i的栈由长度为i1的栈转移过来,且长度为i1的栈最后一位要小于等于j。那么对于长度为i的这类问题的答案即\(\sum_{j=i+1}^nf[i][j]\)，条件就是小...

1003SimpleSetProblem 题意： 分别从k个集合中选一个元素组成一个数组\((a_1,a_2,a_3,...,a_k)\)，求max\((a_1,a_2,a_3,...,a_k)\)min\((a_1,a_2,a_3,...,a_k)\)的最小值。 分析： 我们给每个集合中的元素添加一个id标识它属于哪个集合，然后将所有集合合并并按数值大小从小到大排序，这样问题就转化成：找一个最小区间，该区间满足每个id都至少出现一次，求这些最小区间右端点的值减去左端点的值的最小值是多少？显然可以用双指针来做，用st数组维护[i,j]不同id的出现次数，cnt统计区间[i,j]内的id种类数，...

A.BoboStringConstruction 题意: 给定一个01串t，构造一个长度为n的01串s，时的t+s+t中t只在首和尾出现。 分析： 结论，s取全0或者全1。①t全0或者全1，那我s和t取相反的即可。②t既包含0又包含1，首先t不可能是s的子串，那我们只需考虑t是否可以由t的后缀加上s再加上t的前缀得到。假设对于当前的串s全0且存在t的后缀加上s加上t的前缀等于t，那么我们将s变为全1则一定不等于t，当前串s全为1同理。综上，我们只需要分别判断s全为0和全为1即可。 代码： include<bits/stdc.h> usingnamespacestd; intche...

1001Typhoon 题意： 给你台风的轨迹坐标以及避难所的坐标，台风的半径不可预测，求让每个避难所不安全的最小台风半径是多少。 分析: 枚举每个点到所有“线段”的距离取个min。 代码: 附上队友的代码（懒）: include<bits/stdc.h> include<math.h> definerep(i,a,b)for(inti=a;i<=b;i) constdoubleeps=1e-8; intprecision_cmp(doublex){ if(x<eps&&x>-eps)return0; if(x>0)retur...