没人写题解..那我来水一发.A：博弈论。可以发现连续的一段可以看成一样的。那么由于1起手。所以如果两边都是黑。相当于后手变先手。然后统计下能操作的次数为奇偶即可。Code: void run() { int n;sd(n); string s;cin >> s; char c = s[n-1]; int ma = 0; for(int i = n-2;i >= 0;--i) { if(s[i] != c) { ma++; c ...

前言：太懒了，有些题懒得详细写。代码中有些注释。应该能看懂。（大概？）代码会崩就直接发链接了..A：dp转移。用mp来dp了.https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43975592B：bfs搜。当搜到了站进去就可以一直呆着的就说明到了安全区。然后注意的是。先处理每个时刻的爆炸点。然后queryhttps://ac.nowcoder.com/acm/contest/view-submission?submissionId=43976051C：对于显然可以发现。因为要反复回来。所以要先把最慢的人运到对面。可...

因为代码崩了，先给下代码链接吧。A:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43962918B:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43965176D:https://ac.nowcoder.com/acm/contest/view-submission?submissionId=43965712E:https://ac.nowcoder.com/acm/contest/view-submission?submi...

D：手动打表递推式dp[i][j]表示以i结尾长度为j.dp[i][j] = dp[i-1][j]+dp[i][j-1].20分做法：直接N^2循环。100分：写出部分表X/L:1 2 3 4 5 6 71 1 1 1 1 1 1 12 1 2 3 4 5 6 73 1 3 6 10 15 21 284 1 4 10 20 35 565 1 5 15 35 70 1266 1 6 21 56 126 .观察后从上往下看就是杨辉三角的那个图.杨辉三角的值有C(i-1,j-1)的求法.那么对于向下一个位置就是改变i,j不变.那么就有下一个位置为C(i-1+1,j-1)的公式...

E：思路：区间dp.dp[i][j]表示区间[i,j]的最优解对于划分区间[i,j]这个面积区域时。起点为i,终点为j,显然划分点k为[i+1,j-1]之间的某一点.从这个图可见,我们现在划分区间[1,5]的面积。对于分割点肯定是2,3,4中的任意一点。例如我们选定点3位划分点。那么显然三角形{1-3-5}为新划分出来的面积区域,面积大小为 a[1] * ...

D：概率论条件概率：求在某个条件发生的概率下，另一个条件发生的概率.公式P(A|B) = P(AB)/P(A).在这题中即可看成 恰好有k枚的概率/至少m枚的概率.对于至少m枚的概率.容斥求最多m-1枚反面的概率.0枚反面时 C(n,0) * (1/2)^n1枚反面时 C(n,1) * (1/2)^2....1减去这个和即为至少m枚反面的概率. 恰好k枚正面的概率C(n,k)*(1/2)^n.Code: LL f[N]; void init() { f[0] = 1;for(int i=1;i<N;++i) f[i] = (f[i-1]*i)%Mod; } LL quick_mi...

K：思路：最优的操作就是一直操作一个数。证明：设最后的结果为(a[i]+xi)-(a[j]-yj).= abs(a[i]-a[j])+xi+yj (x+y = m);因为i,j肯定不一样。那么max(i,j)x+max(i,j)y >= xi+yj.所以全部分给下标最大的那个更优.所以只需要去枚举操作哪个数,然后操作这个数为最大时和最小时都和最大值最小值计算下即可。Code: LL a[N]; int main() { int n,m;sdd(n,m); LL minn = INF,maxx = -INF; for(int i=1;i<=n;++i) ...

思路：前缀和优化.一层层去优化掉循环.至于怎么优化？写成L,r的形式就可以慢慢优化成ans += (sum4[n]-sum4[L-1])-sum[L-1](sum3[n]-sum3[L-1])-(sum5[n]-sum5[L-1])+sum2[L-1](n-L+1);这样的一维循环.细节讲一下：因为涉及到了减的操作,所以注意+Mod然后%Mod来防负数.然后因为我这代码里把后面分开来下了，那个+应该是-.Code: LL a[N]; LL sum[N];//a值的前缀和 LL sum2[N];//a[i]*sum[i-1]的前缀和 LL sum3[N];//sum[i]的前缀和 LL sum4...

C：思路：dp.定义dp[i][j]为前i天工作了j天的最小代价.思考如何转移：当第i天为0时,直接可以从i-1继承.那么为什么要继承？为了后续的计算.当第i天为1时.先继承i-1,然后再加入第i天去更新.如果更新？枚举到i的连续天数。列如1 1 0 0 0 1 1 1.我们当前位置i为最后一个1,那么枚举连续的前面的天i-1,i-2.当遇到了0,那就退出.因为这就不连续了,这时候的之前的连续的影响已经在之前被计算,所以就不用再去考虑.然后我们既然保证了连续天应该是j-i。那么显然j-1要保持休息,那么就从j-2开始转移.很显然,当j=1的时候j-2已经会越界,这个时候显然j~i全部都连续,那...

D：思路：概率论.计算出每个卡池拿不到的概率,最后1-即可.注意1-之后可能会<0,所以要加上模数再取模.这里的概率计算直接上逆元就可以了.小细节:ma *= a%mod,是不对的这样本质上是先对a取模再乘ma.这样存在爆精度的问题.Code: LL quick(LL a,LL b) { LL re = 1; while(b) { if(b&1) re = (re*a)%Mod; b >>= 1; a = (a*a)%Mod; } return re; } LL a[N],b[N]...

贪心：首先注意题目说这个数列肯定是1-n的一个全排列。那么说明这个数列一开始的数都是1~n中的,并且最小的是1.那么,很显然最后的结果肯定全部为1.因为想要替换为全部都一样,且每次替换都是在变小,那么最后肯定是全部为1才能实现.所以我们直接用1去替换更优.为什么呢？因为如果用其他的数去替换,最终还是要被替换成1,这样还多了不必要的中间替换步数.所以可知用1替换更优.那么就枚举一开始的那段区间,然后不断向左向右延伸,最后比较其中最小的即可. int a[N]; int main() { int n,k,pos,ans = INF;sdd(n,k); for(int i=1;i&l...

题意：问的是给定比例的齿轮能否旋转.思路：首先,如果这个齿轮不成环,那么肯定可以通过相邻的齿轮转动.所以我们需要的是判断成环的时候是否也能够转动.首先,我们dfs时进行赋值,通过这个比例来赋值,让起始点为1.0即可.然后当我们第二次来到这个点时,它已经判断下成环后重新赋的值和之前赋的值是否一样,一样就说明可以一起旋转.不一样说明无法旋转.实现上,我们成环后判断的只是起始点,然后就不再继续dfs,保证了不会死循环. Code: double eps = 1e-6; struct Node { int to; double x,y; }; vector<Node> G[...

二分图的多重匹配问题解法:1.带限制的匈牙利算法.对匈牙利做一点调整就行了.Code: #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 2505; const int M = 10000; #define pi acos(-1) #define INF 1e8 #define INM INT_MIN #define pb(a) push_back(a) #define mk(a,b) make_pair...

C：分层图的最短路.思路：对于每一层里面的点建边.然后给每个车站开一个虚点,和每个地铁里对应的车站建边。这里的对应应该每次都要和对应地铁里建边。建边:对于每一层,最多的点数就是总车站数n。所以给每一层开n个点存这一层的信息,可能会有空缺,但是没什么影响。然后和前面的点建立双向边,因为地铁也可以往回坐.边的权值是这一条线路坐一站的花费bi.这里默认虚点为[1,n].第一条地铁就是[1n+1,1n+n]可以从图中理解下。a1为坐地铁1的花费,b1为地铁1之间坐多一站的花费.a,b2同理.Code: #include<bits/stdc++.h> using namespace std;...