D：敌情侦察 令 a[i]=b[i-1]+b[i]+b[i+1] 特别的对于 i=1 有 a[1]=b[1]+b[2] 对于 i=n有 a[n]=b[n-1]+b[n] 枚举每个b[1]可能的值（0-a[i]）此时b[2]确定，从而递推出整个b数组 若此时满足i=n的条件则为一种可行方案 #include <bits/stdc++.h> using namespace std; const int N=1e4+5; int a[N],b[N]; int main() { int n,ans=0; cin>>n; for(int i=1;i<=n;i++) cin&...

B交通改造：Kruskal 思路：1.接受改造的道路能够令所有的交叉路口直接或间接相连2.并且改造的道路数量应尽可能的少.这两条信息提示我们最终形成的是一颗生成树。但并非是最小生成树，而是最大边权最小生成树。那么只需要二分答案，每次看是否能够形成一棵生成树即可。形成的生成树的充要条件为共有n-1条边 #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 100010, M = 200010, INF = 0x3f3f3f3f...

E:QQ宠物 解题突破点：好消息是只有n-1对NPC直接认识，并且将所有相互认识的NPC连在一起能形成一个树形的结构图。 可以发现只需要把给出的关系维护成树型结构，就可以在这棵树上跑一遍树形DP。具体的做法是用并查集维护两个人是否在同一棵树上，如果已经在同一棵树上，那就把这条边舍去。 DP[i][1]表示选了第i号节点的最大值 DP[i][0]表示不选i号节点的最大值 状态转移方程： DP[i][1]=max(DP[i][1],DP[i][1]+DP[j][0])(j为i的儿子)选了第i号节点那它的儿子一定不能选了 Dp[i][0]=max(DP[i][0],DP[i][0]+max(DP[j...

同标题

题意：找到一个数组中满足子数组之和可以被k整除的最大长度。 暴力：求一个前缀和然后两重循环判断每一个子数组能否被k整除，这里值得注意的是正向循环和逆向循环所形成的子数组集合是一样的所以选取一个方向即可。时间复杂度为O（n^2^） 优化：我们在用前缀和求是否能够被k整除所用的公式为（sum[r]-sum[l-1]）%k=0？ 根据同余定理我们可以知道只要满足sum[r]%k==sum[l-1]%k即可满足上述式子，由于是求最大长度，我们我们只要记录每个余数最先出现的位置，在后续的如果出现相同余数，子数组长度即为当前位置减去第一次出现位置，时间复杂度为O(n) #include<bits/s...

广度优先搜索算法的思想主要是将每种状态用队列储存起来,再对每种状态进行拓展,例如说对于(20,1)这个状态,我们依次上下左右走一步得到除了(19,1)(21,1)(20,0)(20,2)将越界和障碍物外合法进入队列,储存下状态(19,1)(20,2)再依次扩展直到历遍所有可到达点. 对于该题目我们需要做的是输出两只企鹅到达目的地的字典序最短路径(下 左 右 上)的总步数与操作方法以及路径地图,需要注意企鹅走路是镜像的,且可只操作一只企鹅.那么我们还需要记录下当前状态是由哪个状态来转移过来的,在输出时使用深搜打印路径,用语言描述总是那么苍白下面配合代码解释 #include<bits/st...

K题:(搞不懂拓扑排序的超小白讲解)总体思路为利用已知b[i]推出b[i-1]信息,将1-n每个数填充至ans数组构造答案.直接进行代码讲解:首先读入数据,我们用一个book数组来记录当前位置是否有约束,显然当下标小于需要长度或者两者大于n时输出-1 #include<bits/stdc++.h> using namespace std; int b[N],book[N],ans[N]; int main() { int n,k,f=1; cin>>n>>k; for(int i=0;i<n;i++) { int t,w; cin>>t&g...

C题:求无重复数字的子串个数本题使用双指针算法,用hash来检验是否存在相同的数双指针l,r我们先让r一直往右走直到出现重复元素,累加起始下标为l满足条件的子串个数,再将l往左走.样例二模拟:8 ****2 12 3 12 3 2 6 9初始l=r=1,未有重复元素直到l=1,r=4时出现重复元素我们计算下标为l开始满足条件的子串{2}{2,12}{2,12,3}ans+=r-l下一步将l左移l=2,r=4,还有重复元素满足条件子串{12}{12,3}ans+=r-l如此l=3,r=4时无重复r继续往前走将上述过程用代码实现  #include<bits/stdc++.h> usi...

G题：题目大意对于数组大小为n的两个数组a，b在a上操作k次交换使得 最大。看到这题想到的是如果我能定量的知道每次交换带来的收益就好了，如果每次交换的收益都是最优的那么结果也是最优的这就是经典的贪心算法，下面对交换的贡献进行讨论：对于（a1，b1）（a2，b2）由于绝对值的存在无论a1，b1大小其值都等与大数减小数，理解到了这一点其实对a操作也可以视为对b操作，我们一定可以满足（a1>b1&&a2>b2）（不满足将其对应位置的ai，bi互换结果保持不变）有小伙伴可能不明白为什么可以交换,理由是交换过后绝对值之和保持不变,且我们保证每次交换都是最优的,也就是对于一个数...

F题 题意寻找l到r区间中的一个数x连续子序列mod3=0的个数（1<=l<r<1e18）观察到数据范围十分的大，正常做法比如前缀和一定是不可做的，那么我们硬要暴力做第一时间想到的肯定是打表，打表后发现当x>=100答案数每次递增1，也就是每个x都满足条件，这样我们很容易得到最终结果，在赛场上我们直接算出前100个对应的数值即可，这样前缀和就可以做了，由于T数量较少更加暴力每次历遍前100个数字也可以。但是赛后我们该思考一下为什么当x>=100时x一定满足条件，在听直播时我听到一个词叫鸽笼效应然后就显然成立了（由于太菜完全联想不到），鸽笼效应的大意是假设有n+1只...

A题 Alice and Bob我们知道当面临两堆石头数量为（0，0）时为失败，那么如果能一次操作能取光石头此时为必胜态，我们用一个二维数组f[i][j]来表示第一堆石头数量为i第二堆石头数量为j的情况，f[i][j]=1表示状态面临两堆石头数量为i，j时可以一步取光石头，f[i][j]=0表示状态面临两堆石头数量为i，j时无法一次取光石头。初始f[0][0]=0,根据题目f[k][sk]或f[sk][k]一定能够一次性取完,我们可以从（i=0，j=0）开始自小变大枚举s与k找出所有先手必胜的状态，由于是自小变大枚举所以发现有f[i][j]=0就发现了一个必败的局面再对它枚举s与k，当初始状态...