设f[n]表示青蛙到达n位置最少需要踩到的石子数。rock[n]=1(n位置有石子)，0(n位置无石子)f[n]=min{f[n-i]+rock[n]}(s<=i<=t)这个方程时间复杂度是O(n)，在本题的1e9极限数据是无法出解的。优化方法：压缩法结论：px+(p+1)y=Q若采用跳跃距离p，p+1时可以跳至任何位置Q，则在Q>=p(p+1)时是一定有解的。证明：由于p和p+1互质，因此该不定方程有解，设解为x=x0+(p+1)t,y=y0+pt那么使得0<=x<=p,则当Q>p(p-1)-1时，有(p+1)y=Q-px>p(p-1)-1-pp=-...

南京签到二题，博弈/思维。https://vjudge.net/contest/412295#problem/H1.a、b、c是王子一开始知道的。2.只有能够准确确定出才行。把题目解读成出题人想让你理解的那样就会发现这题很简单。特判1 0 0直接输出0即可如果a<=b, b总可以指定一个假公主来与a对峙如果a>b+c,那么2*(b+c)+1就肯定会有一个出现次数b+c+1的答案就是正确的公主位置。如果a<=b+c，王子不能确定，输出“NO”。 #include<bits/stdc++.h> using namespace std; int main(){ ...

A.让所有的都到sum即可 #include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int t; cin >> t; while(t--){ int n; cin >> n; cout << n << endl; for(int i=1; i<=n; i++){ cout...

反思：cf题目需要抓住问题的根来解题。A.发现为了不让trygub出现只需要对字符串排一下序即可。 #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while(t--) { int n; cin >> n; string s; cin >> s; sort(s.begin(), s.end()); cout <&l...

A.一个n，m的监狱，每个格子都有人，一个时间每人都可往以上下左右移动一格，允许一个格子多个人，问所有人都到(r,c)需要的时间是多少？x，y坐标分开考虑x最远是abs(x-r)与abs(r-1)的最大值y坐标最远是abs(y-c)与abs(c-1)的最大值，二者都取最大即可得到花费时间最长的坐标点 #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while(t--) { int n, m, r, c; c...

前言：好久没打cf了，确实感觉手生了，立个flag：一天来一场cf练习。A.无脑方式：直接看样例，输出输入数字的长度x/f((x))的作用就是把后缀零都给删了，对于一个数x，x/f(f(x))，实际上表示的值与x的后缀0有多少个有关，比如100就是100，90就是10...，而后缀0有多少个与位数有关。code： #include<bits/stdc++.h> using namespace std; int main() { int t; cin >> t; string s; while(t--) { cin ...

链接：https://ac.nowcoder.com/acm/contest/7079/C题解：可以和旅游那道题一起分类到最小生成树里面，都是基于最小生成树的思想d(u,v)定义为无向图中点 u 能到达点 v 的所有路径中权值最小的路径的权值。而路径的权值定义为为路径中权值最大值。L按从小到大排序，如果当前L满足，那么集合当中两两之间都满足。代码： #include <bits/stdc++.h> #define fastcall __attribute__((optimize("-O3"))) #pragma GCC optimize(2) #pragma G...

链接：https://ac.nowcoder.com/acm/contest/7329/C题解：在选择排列的时候，从边权最大的递减构造，那么这条边就是当前待选择边权中的最大值了。因此构造一个最大生成树即可。 #include <bits/stdc++.h> using namespace std; #define IO ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" ...

链接：https://ac.nowcoder.com/acm/contest/4743/C换元后三分，这题三分是利用三分确定极值存在的一个区间，然后在这个区间上再求解。 #include <bits/stdc++.h> using namespace std; #define IO ios::sync_with_stdio(false);cin.tie(0); cout.tie(0) #define all(__vv__) (__vv__).begin(), (__vv__).end() #define endl "\n" #define SZ(x) ((int...

三分，主要解决单峰问题（求单峰），不过递增或递减链接：https://loj.ac/p/10013画图可以看出F(x)是一个单峰函数，在函数定义域内使用三分法即可。 int a[N], b[N], c[N]; int t, n; inline double cal(double x) { double res = -INF; for (int i = 1; i <= n; i++) { res = max(res, a[i] * x * x + b[i] * x + 1.0 * c[i]); } return res; } int ma...

链接：https://ac.nowcoder.com/acm/contest/5026/C先dfs一遍，求出每个连通块有多少个点，把这个东西作为一个连通块的体积，一个连通块就是一个物品,这样就是在求恰好装满这4个体积分别为na，nb，nc，nd的背包有多少种方案。dp[i][x1][x2][x3][x4]表示枚举到i的时候，四个背包被装填的体积分别为x1,x2,x3,x4的方案数。 #include <bits/stdc++.h> using namespace std; #define IO ios::sync_with_stdio(false);cin.tie(0); cout...

链接：https://ac.nowcoder.com/acm/contest/5026/B贪心：如果x==y，直接输出x，假设x < y, x不断乘以2，直到x > y/2 && x<=y，可以想象，如果x，y同时减1，肯定会到y是x两倍的情况，这时候x*2即可，这个过程中y的贡献就是y，我们看一下为了多做了多少，ceil(log2(y/x)) int t, n, m; int main() { t = read(); while(t--) { n = read(), m = read(); int x ...

链接：https://ac.nowcoder.com/acm/contest/5633/C解法1：这题看到一个不停使用前缀和优化最后达成O(n)计算的方法，感觉很有趣他的分析过程是这样：首先暴力4重循环 for(int l=1; l<=n; l++){ for(int r=l; r<=n; r++){ for(int i=l; i<=r; i++){ for(int j=i; j<=r; j++){ ans += a[i]*a[j]; } } ...

链接：https://ac.nowcoder.com/acm/contest/9033/C求a的所有子集的mex之和思路：虽然a[i]到1e9，但这n个数的任意子集的mex只会是1到n+1的一个数，因此从1到n+1枚举每个数作为mex的情况即可。一个数i作为mex，显然1~i-1的数都要每个至少选一个，大于i的数随便选代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 5e5+10, mod = 20000311; ll q_pow(ll a, ll b){ ...