jasony_sam

摘要： Solution 通过最短路和 \(n\leq 100\) 得知我们可以拿 \(floyd\) 预处理全源最短路。然后因为要换车，所以我们可以考虑dp，设 \(dp_i\) 为 \(i\) 到终点 \(b\) 的最坏换车次数，但是从起点开始可能会有后效性，所以从终点开始，即 \(dp_b\) 为 $ 阅读全文

摘要： Solution 看题和 \(\gcd\) 有关系，所以我们可以先考虑一下质数，然后发现对于质数 \(x\) ，当他不 \(lonely\) 即满足条件的时候，是 \(x^2\) 出现的时候，因为 \(x+1>x,x+x>1\) 。 现在考虑合数，分两种情况，一种是形似 \(p^2\) 的( \(p 阅读全文

摘要： Solution 这个题意思很显然，是求 \(n\) 个区间重叠最多的地方和值。 那么我们能想到用差分数组，在扫一遍的过程中维护最大值和 \(pos\) 。 但是需要注意的是，区间最大会到 $10^9$ ，直接差分是不行的，我们需要先对所有 \(b\) 和 \(d\) 进行离散化，然后再去差分。 代 阅读全文

摘要： Solution 我们考虑在第 \(i\) 步时，如果此时是 \(Allen\) ，他会将 \(x_s=t\) ( $0\leq s\leq n,0\leq t\leq 1$ )，此时的 \(v_{s,t}\) 为最大，那么 \(v_{v,1-t}\) 就是最小的，也就是 \(Bessie\) 所做 阅读全文

摘要： Solution 可以发现当 \(x\leq10^{18}\) 时， \(f(x)+1=f(10^{18}+x)\) ，令 \(g_x=\sum\limits_{i=1}^xf_i\) ，设 \(g_{10^{18}}\equiv b\pmod a\) ，则 \(l=1+a-b,r=10^{18}+ 阅读全文

摘要： Solution 当我们手模了几组小样例之后，可以发现，只有 \(\min\) 给别的一直往上加，才能达到最优。 我 \(sort\) 了一遍，然后再扫一遍累加答案即可。 代码 #include<bits/stdc++.h> using namespace std; const int N=1010 阅读全文

摘要： Solution 因为要求 \(f\) 最小，我们发现只要将 \(a_i\) 和 \(T-a_i\) 染成不同的颜色就行了。 但是当 \(T\) 为偶数的时候， \(\frac T2\) 是要一个染白，一个染黑这样轮流的。 举个例子：设 \(k\) 为 \(\frac T2\) 的个数，那么如果将 阅读全文

摘要： Solution 我们可以想到构造三条基准线： \(k_{1,2},k_{2,3},k_{1,3}\) ，分别以 \(a_1,a_2\) ，\(a_2,a_3\) 和 \(a_1,a_3\) 为线上的点，然后去判断剩下的点是否是在另一条与某一条基准线平行的线上。 代码 #include<cmath> 阅读全文

摘要： 没有用DP，搞了个搜索 Solution ​ 如果要枚举合法对的话，用脑子想想是很困难的，所以我们正难则反——枚举非法对。 ​ 思考一下如果 \(a\) 和 \(b\) 对应的数为 $0$ 即不能相邻的话，将 \(a,b\) 中间的字符消完就是非法操作。举个例子： \(acadbc\) ，那么删除 阅读全文

摘要： Solution 首先，题的意思是删连续上升的/连续下降的/先上升后的。 然后发现 \(n\leq 400\) ，所以可以考虑区间DP。 设 \(f_{i,j}\) 为删完 \(w_i,\cdots, w_j\) 的最大分数， \(g_{i,j}\) 为将 \(w_i,\cdots,w_j\) 删成 阅读全文