分析 经典的字眼，要求最小值最大。考虑二分答案。如何判断合法性。对于二分出来的最小值。从左向右扫一次，在考虑 时，我们已经保证 是一个合法的区间了，所以只有向后加才有意义。所以遇到小于二分出来的数时，直接 这个区间 。用差分数组维护一下就好了，当操作次数大于 时是不合法答案，时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e5 + 10; #define LL int LL read() {LL x;scanf("%d",&x);return x;} LL A[N],...

分析 对于每个端点维护四个单调栈。表示这个端点作为最小值，最大值可以满足的合法区间 。那么只有 在 的合法区间内， 在 的合法区间内，这个用扫描线维护一下就好了，要记住先加后减，否则会丢掉重合的方案。 一些理解 是我这个点可以延展的范围。如果我都不能到 ，那么我肯定不能作为端点出现。所以需要判断 同理。 假如我已经知道了以 为左端点,的右端点可选的区间范围是 ,也知道以 为右端点,的左端点可选的区间范围是 ，然后差分找答案。 先钦定考虑 这个二元组的贡献。考虑这个值作为最小值可以的区间。再考虑这个作为最大值合法的方案。用差分维护区间。 代码 #include<...

分析 考虑如果一个数有选择，那么可能会影响它的也必须选择。所以这个就是个计数 了。可以写个类似背包的转移来算出所有的可能方案，最后答案再除以所有方案数就好了。时间复杂度为 。当然你可以滚动数组优化空间。 一些细节 表示可以选 个人时的合法方案数，由于从 转移过来的，所以可以滚动数组优化。 关于逆元 保证 为质数，所以 ，那么乘上 ，等于模意义下除以 。 代码 #include<bits/stdc++.h> using namespace std; int read(){int x;scanf("%d",&x);return x;} int n,D; ...

分析 考虑一个最大生成树，变化为序列之后一定有一种方案满足 。所以这道题只需要求一个最大生成树即可。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 5e5+1000; struct E{LL x,y,w;}e[N]; LL f[N],n,m; LL find(int x) {return f[x]==x?x:f[x]=find(f[x]);} bool cmp(E a,E b){return a.w > b.w;} int main() { io...

分析 对于一个确定的 ，答案一定是可以取到前 个最大的值，所以只需要排序，再维护一个前缀和。最后时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 1e5 +10; LL A[N],sum[N],n,X,Y,ans; bool cmp(LL x,LL y) {return x > y;} int main() { scanf("%lld",&n); for(int i = 1;i <= n;i++) scanf...

分析 按题意模拟即可，要注意四舍五入，所以全部 ，最后再除回来就可以了。 代码 #include<bits/stdc++.h> using namespace std; #define LL long long LL T,a; int main() { cin >> T; while(T--) { cin >> a; LL A = 12 * a % 720,B = a % 720; LL ans = abs(A-B); if(ans > 360) ans = 72...

A 分析 分出两个集合要求 。考虑直接贪心选到不能再选，因为每个数的对答案的贡献都是 ，不错的签到题。 代码 #include<bits/stdc++.h> using namespace std; const int N = 4e5+100,inf = 0x3f3f3f3f; int read() {int x;scanf("%d",&x);return x;} int cnt[N],n,m; int main() { int T = read(); while(T--) { n = read(); ...

分析 对于 这个其实是等价于 的。所以只需要判断是否为偶数。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e6+100; char ch[N]; int n,sum; int main() { cin >> n; for(int i = 1;i <= n;i++) { cin >> ch + 1; int len = strlen(ch+1); sum = (sum + (int)(ch[len] - ...

分析 考虑答案的单调性，我们先钦定一个值为最小值或最大值。那么如果 是一个满足的区间，那么 也一定是一个合法区间。对于每一个数都求出它的分界点。那么 。这个直接上单调队列。时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e7 + 100,P = 1e9; int n,a[N],k,b,c; int q[N],ans[N],l,r,len; int main() { cin >> n >> k >> a[0] >> b &gt...

分析 由于没有修改操作，所以可以求出二维前缀和，从而达到 判断。二分边长，对每个节点单独考虑就好了，总的时间复杂度为 。 代码 #include<bits/stdc++.h> using namespace std; const int N = 5e2+100; int n,m,K; int t[N][N][26],sum[N][N][26]; bool check(int x,int y,int D){ for(int i = 0;i < 26;i++) { if(sum[x+D][y+D][i]-sum[x+D][y-1][i]-sum[x-1...

分析 讨论 和其它三个字母出现次数的大小就可以了。有且只有两种状态。 和 的情况。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e7+100; char ch[N]; int ans; void solve(int a,int b,int c,int d) { int Min = min(b,min(c,d)); if(!a||!Min) return; if(a * 2 <= Min) ans = a * 2; else ans = Min; } int k...

分析 因为不等号具有传递性。可以对于一个节点连接比他大的数字，最后看他可以到多少个节点就是答案了。 代码 #include<bits/stdc++.h> using namespace std; const int N = 1e3+100; int f[N],n,m,ans;vector<int> G[N]; void dfs(int x) { f[x] = 1; for(auto y:G[x]) { if(!f[y]) dfs(y),ans++; } } int main() { cin >> n >&...

分析 根据多元均值不等式 。 代码 #include<bits/stdc++.h> using namespace std; int main() { int n;cin >> n; printf("%.3f",pow(n,1.0/3)*3); return 0; }