这个稍微想想就会发现可以这么做 枚举每一个数当作正确序列的一点,就可以知道此时序列有多少需要改变 这样枚举,检验是的 考虑只检验第一个数,那么后续的每一个数为了迎合第一个数都有一个预期值 那么对于以第一个数作为标准来算,所有需要与预期值相差为才是正确的 那么当检验第二个数时,如果比预期值大1,说明需要比预期值大才行 所以,可以开一个来保存第一个数的预期值,然后一直取即可 #include <bits/stdc++.h> using namespace std; const int maxn=2e5+10; int a[maxn],b[maxn],vis[maxn],n; map&l...

CF 522D 最多存在个数对会贡献答案 就是每个数和前面第一个和自己相同的数,把下标记作 那么想象一下,现在要统计的最短相同数对距离 我们可以直接对所有的投射到线段树上去 线段树上的下标就是,值就是 这样我们查询的最小值,查到的所有的 都属于,而由于是下标,所以也肯定满足 由于每个区间只需要的数插入,所以按照端点排序 这样每个点只需要插入一次,非常快 非常巧妙的思路 关于找前一个相同的数,可以用,也可以离散化 #include <bits/stdc++.h> using namespace std; #define ls (rt<<1) #define rs (rt&...

最小值最大,果断二分 二分之后就是裸题了 遇到第一个不满足二分值的必须要加了,而且是从这个位置开始加 维护用差分就好了 看代码吧,这个没什么好说的 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn=3e5+10; int n,m,w; int a[maxn],b[maxn]; bool isok(int mid) { int ans=0; for(int i=0;i<=n+w;i++) b[i]=0; for(int i=1;i&l...

一眼感觉转移,但是状态炸了 然后想到线性,但没有明显的转移顺序 所以可以考虑把步数设进状态,这样最外层只需要循环即可转移 又因为转移牵涉到上一次的移动方向 所以设表示走了步,目前在位置,利用方向走到当前位置的 转移很显然了 #include <iostream> #include <math.h> #include <string.h> using namespace std; #define int long long const int mod=1e9+7; int n,m,dp[2][209][209][5],t,d,x1,x2,y11,y2; cha...

发现题面很类似这样一个经典问题: 给出一堆数字,再给你一个数,找到那堆数中与这个数异或最大的 这个问题很经典了,直接建立字典树 对于每个数,二进制分解,然后把二进制从高位到低位插入到字典树上 形成一个深度为的字典树,异或最大值就不停的贪心选择走还是走即可 但是树上路径没那么简单了,不再是简单的两数异或...... 但是如果处理一个数组,表示根到自己的异或值 那么和的路径异或值不就是吗 因为他们的部分异或了两次,消掉了 这样一来,转化为把插入字典树了 #include <bits/stdc++.h> using namespace std; const int maxn=8e6+10...

#include <bits/stdc++.h> using namespace std; const int maxn=5e5+10; #define int long long double a[maxn],b[maxn]; int n,k; struct p{ double a,b; double c; bool operator < (const p &tmp ) const{ return c>tmp.c; } }; bool isok(int mid) { priority_queue<p&...

不得不说是个垃圾题目,这样可以卡空间真的没必要..... 圆排列个数是,因为可以以任意一个点开头 那么考虑至少有一对情侣相邻,也就是,选一对情侣出来 现在把这对情侣看成一个整体,就只剩下个人排列了 情侣内部可以正反,再乘以 接下来就上容斥把 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn=3e7+10; const int mod=1e9+7; ll quick_pow(ll x,ll n) { ll ans=1; while( n ) { ...

最短路用的是 #include <bits/stdc++.h> using namespace std; #define id(i,j) (i-1)*m+j const int maxn=2e5+10; const int inf=1e9; int a[109][109],n,ju[109][109],vis[maxn],dis[maxn],m; int x[5]={0,0,1,-1},y[5]={1,-1,0,0},T; double ans; struct edge{ int to,nxt,w; }d[maxn]; int head[maxn],cnt=1; void...

题意 给你个区间 选出最少长度的序列,满足按序列顺序操作,每次对 的元素进行排序 最后在位置的数需要是最大的数(你必须保证对于任意的元素顺序,都满足这点) 分析 非常经典的题 很容易想到当最大的数在位置时如果都能满足条件,任意情况都能满足条件 于是定义表示当前覆盖了的最小区间个数 转移从里找最小值就好了 用线段树优化找最小值的过程即可 #include <iostream> #include <algorithm> #include <string.h> #include <stdio.h> using namespace std; #defin...

话说我不是首杀好难过 但是这样连边,复杂度是的 #include <bits/stdc++.h> using namespace std; #define ls (rt<<1) #define rs (rt<<1|1) #define mid (l+r>>1) #define lson ls,l,mid #define rson rs,mid+1,r const int maxn=6e6+10; const int inf=1e9; int n,m,s,t,dis[maxn],id; struct edge{ int to...

我真是个nc啊~ 这么简单的概率,居然想了几分钟??? 白球和黑球没有本质上的区别,所以各占一半 定义为取次球后剩下白球个数的期望 所以贡献乘概率相加就算期望了 而且这题正推逆推都无所谓了 #include <bits/stdc++.h> using namespace std; int n; double dp[1000009]; int main() { cin >> n; dp[0]=1; for(int i=1;i<=n;i++) { double p= dp[i-1]/(i-1+2 ); ...

用什么并查集啊!! 树的定义白学了嘛!!! 根节点没有入度,其他节点有且仅有一个入度(唯一的父亲) 特判树没有节点的时候,这个很坑 #include <iostream> #include <algorithm> #include <map> using namespace std; map<int,int>mp; int n,m,in[10000009],id,k=1,l,r; int main() { while( cin >> l >> r ) { if( l+r==-2 ) b...

#include <bits/stdc++.h> using namespace std; const int maxn=5009; int a[maxn],n,dp[maxn][maxn],f[maxn][maxn]; int main() { cin >> n; for(int i=1;i<=n;i++) cin >> a[i],dp[i][i]=a[i],f[i][i]=a[i]; for(int i=1;i<n;i++) { dp[i][i+1]=a[i]^a[i+1]; ...

代码链接 我们发现枚举每一次的操作几乎是必要的,因为没有什么规律 #include <bits/stdc++.h> using namespace std; #define int long long const int maxn=1e7; bool com(int a,int b){ return a>b; } int n,m,qq,u,v,now,tt; int ans[maxn],h[4],t[4],q[4][maxn]; double p; void run(int x) { int sumn=0,num=0;//找当前最大 ...