这场比赛编号是 233，好玩好玩
D - Count Interval
给出 \(n\) 个数，求有多少个连续段的和为 \(K\) .
即求出 \((l,r)\) 的个数，\((l,r)\) 满足
\(1. 1\leq l\leq r\leq n\)
\(2. \sum\limits_{i=l}^{r} a_i=K\)
\(1\leq n\leq 2\cdot 10^5,\ |a_i|\leq 10^9,\ |K|\leq 10^{15}\)
考虑 \(\sum\limits_{i=l}^{r} a_i=\sum\limits_{i=1}^{r} a_i-\sum\limits_{i=1}^{l-1} a_i\) .
考虑用 \(\mathrm{map}\) 维护前缀和的数的数量即可.
时间复杂度 : \(O(n\log n)\)
空间复杂度 : \(O(n)\)
code
#include
using namespace std;
const int N=2e5+10;
int n;
long long k;
long long a[N];
mapcnt;
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=0;i>a[i];
for(int i=1;i
E - Σ[k=0..10100]floor(X／10 k)
求 \(\sum\limits_{k=0}^{10^{100}}\lfloor \frac{X}{10^k}\rfloor\) .
\(1\leq X\leq 10^{500000}\)
这个式子相当于每次把这个数的最后一位删掉，得到 \(|X|\) 个数，然后把这些数相加.
这样肯定会 ttt，考虑答案中的第 \(i\) 位是原数位数中不大于 \(i\) 的所有加起来.
不能忘记考虑进位.
时间复杂度 : \(O(n)\)
空间复杂度 : \(O(n)\)
code
#include
using namespace std;
const int N=2e5+10;
int n;
long long k;
long long a[N];
mapcnt;
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>k;
for(int i=0;i>a[i];
for(int i=1;i
F - Swap and Sort
给出一个长度为 \(n\) 的排列 \(P\) .
给出 \(m\) 种操作. 第 \(i\) 种操作交换 \(P\) 中的第 \(a_i\) 个和第 \(b_i\) 个.
求是否能在不多于 \(5\cdot 10^5\) 次操作后排列有序.
如果能，给出方案.
\(1\leq n\leq 1000,1\leq m\leq \min(5\cdot 10^5,\frac{n(n-1}{2})\)
考虑 \(a_i\) 和 \(b_i\) 连边构图.
如果存在 \(i\) 和 \(P_i\) 不连通，那么肯定没有解.
对于一个连通块，保留一棵生成树就可以做到所有点都回到原本的位置上.
但是对于生成树的点操作的顺序是有讲究的. 考虑剥叶子，让位于叶子节点处的节点先通过操作回到原本的位置，然后再删掉这个节点.
操作方案即为 \(i\) 到 \(P_i\) 上的边依次 swap.
时间复杂度 : \(O(n^2)\)
空间复杂度 : \(O(n+m)\)
code
```cpp
#include
#define MP make_pair
#define FI first
#define SE second
using namespace std;
const int N=1010;
int n,m;
int a[N];
int fa[N];
vector<><>,int> >e;
vector<> >g[N];
bool vis[N];
vectorarr;
int pos[N];
vectorop;
vectorans;
inline int get_fa(int x){return fa[x]==x?x:fa[x]=get_fa(fa[x]);}
void work_tree(){
for(int i=0;i>n;
for(int i=0;i>a[i],a[i]--;
cin>>m;
for(int i=0;i>u>>v;
u--;v--;
e.push_back(MP(MP(u,v),i));
}
work_tree();
for(int i=0;i
#### G - Strongest Takahashi
> 给出一个 $n\times n$ 的格子. 每个格子为 `.` 或 `#` .
>
> 每次可以选出其中一个 $d\times d$, 花费 $d$ 的代价将其全部覆盖为 `.`
>
> 问将全部格子覆盖成 `.` 的代价.
>
> $1\leq n\leq 50$
考虑 $dp(x_1,y_1,x_2,y_2)$ 表示左上角为 $(x_1,y_1)$ 右下角为 $(x_2,y_2)$ 的矩形覆盖为 `.` 的最小代价.
转移的时间枚举横着切和纵着切的位置，合并取 $\min$ 即可.
时间复杂度 : $O(n^5)$
空间复杂度 : $O(n^4)$
code
```c++
#include
using namespace std;
const int N=52;
const int INF=0x3f3f3f3f;
const int inf=1061109567;
int n;
char board[N][N];
bool ok[N][N][N][N];
int dp[N][N][N][N];
int dfs(int x1,int y1,int x2,int y2){
if(dp[x1][y1][x2][y2]!=inf)return dp[x1][y1][x2][y2];
if(x1==x2&&y1==y2)return dp[x1][y1][x2][y2]=ok[x1][y1][x2][y2]?0:1;
int&res=dp[x1][y1][x2][y2];
for(int x3=x1;x3>n;
for(int i=0;i>board[i][j];
for(int i=0;i
<>
21
.....................
.....................
...#.#...............
....#.............#..
...#.#...........#.#.
..................#..
.....................
.....................
.....................
..........#.....#....
......#..###.........
........#####..#.....
.......#######.......
.....#..#####........
.......#######.......
......#########......
.......#######..#....
......#########......
..#..###########.....
.........###.........
.........###.........
haha, Merry Christmas and Happy New Year !
Ex - Manhattan Christmas Tree
给出 \(n\) 棵圣诞树的位置. 给出 \(q\) 个询问.
每个询问问距离 \((x,y)\) 位置曼哈顿距离最近的第 \(k\) 个点.
\(1\leq n\leq 10^5,\ 1\leq q\leq 10^5,\ 0\leq x,y\leq 10^5,\) 圣诞树的坐标不相同.
考虑二分距离 \(d\) , 如果是曼哈顿距离，那么构成的图形是一个斜着的矩形，求这个范围内的点是不好求的.
此时，有一个 trick，就是把切比雪夫转化，相当于逆时针旋转 \(45\) 度之后坐标乘上 \(\sqrt 2\) . 在曼哈顿距离下为 \((x,y)\) 的坐标会变成 \((x-y,x+y)\) . 但是此时距离当前询问的点小于等于距离为 \(d\) 的位置是一个正方形. 这就非常惹人喜爱.
看到 \(x,y\) 在 \(0\) 到 \(10^5\) 之内，所以切比雪夫之后，\(x,y\) 在 \(-10^5\) 到 \(2\cdot 10^5\) 之内.
考虑建立主席树，线段树上维护横坐标，每次加入一行，多次单点修改，维护新的根节点.
查询的时候只需要区间询问两次做一个差即可.
时间复杂度 : \(O(n\log^2 x)\)
空间复杂度 : \(o(n\log n)\)
code
```cpp
#include
using namespace std;
char in[100010];
int iiter=0,llen=0;
inline char get(){
if(iiter==llen)llen=fread(in,1,100000,stdin),iiter=0;
if(llen==0)return EOF;
return in[iiter++];
}
inline int rd(){
char ch=getchar();
while(ch<'0'||ch>'9')ch=get();
int res=0;
while(ch>='0'&&ch<='9'){
res=(res<<1)+(res<<3)+ch-'0';
ch=get();
}
return res;
}
inline void pr(int res){
if(res==0){
putchar('0');
return;
}
static int out[10];
int len=0;
while(res){
out[len++]=res%10;
res/=10;
}
for(int i=len-1;i>=0;i--)putchar(out[i]+'0');
}
const int N=1e5+10;
const int M=2e5+10,P=1e5+3;
const int K=4e7+10;
class presi_tree{
public:
int ts[K],ls[K],rs[K],rt[M],cnt=0;
int build(int l,int r){
int x=++cnt;
if(l==r){
ts[x]=0;
return x;
}
int mid=(l+r)>>1;
ls[x]=build(l,mid);
rs[x]=build(mid+1,r);
ts[x]=ts[ls[x]]+ts[rs[x]];
return x;
}
int upd(int pre,int l,int r,int pos){
int cur=++cnt;
if(l==r){
ts[cur]=ts[pre]+1;
return cur;
}
ls[cur]=ls[pre];rs[cur]=rs[pre];
int mid=(l+r)>>1;
if(pos<=mid)ls[cur]=upd(ls[pre],l,mid,pos);
else rs[cur]=upd(rs[pre],mid+1,r,pos);
ts[cur]=ts[ls[cur]]+ts[rs[cur]];
return cur;
}
int qry(int x,int l,int r,int cl,int cr){
if(l==cl&&r==cr)return ts[x];
int mid=(l+r)>>1;
if(cr<=mid)return qry(ls[x],l,mid,cl,cr);
else if(mid+1<=cl)return qry(rs[x],mid+1,r,cl,cr);
else return qry(ls[x],l,mid,cl,mid)+qry(rs[x],mid+1,r,mid+1,cr);
}
}T;
int sum(int x,int y,int k){
return T.qry(T.rt[min(M-1,x+k)],0,M-1,max(y-k,0),min(y+k,M-1))-
T.qry(T.rt[max(0,x-k-1)],0,M-1,max(y-k,0),min(y+k,M-1));
}
void solve(){
int xx,yy,k;
cin>>xx>>yy>>k;
int x=xx-yy+P,y=xx+yy;
int low=0,high=M+1,ans=M;
while(low>1;
if(sum(x,y,mid)>=k){
ans=min(ans,mid);
high=mid;
}else{
low=mid+1;
}
}
cout6)
评论()
编辑
刷新页面返回顶部
Copyright ? 2022 xyangh
Powered by .NET 6 on Kubernetes