Atcoder 233
Atcoder 233
\(D.\)Count Intervaul
题意：
给定一个长度为\(N\)的序列\(A=\{A_1,A_2,...,A_n\}\)和一个整数\(K\)，问有多少个数对\((l,r)\)，\(st.\) \(\sum_{i=l}^rA_i=K\)
\(1\le N\le2\times10^5\) \(-10^9\le A_i \le 10^9\) \(1\le K\le10^{18}\)
Sol
很容易想到前缀和，但求完前缀和之后如果暴力枚举左右端点\(O(n^2)\)无法承受
由于要求\(S[r]-s[l-1]=K\)，转换一下，对于每个\(r\)求有多少个\(l\)满足要求，即求\(S[r]-k\)有多少个，用\(map\) 记录一下即可 \(O(nlogn)\)
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=2e5+10;
int a[N];
ll s[N];
maphs;
int main()
{
int n;
ll k;
rd(n),rd(k);
for(int i=1;i<=n;i++) rd(a[i]);
for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];
ll ans=0;
for(int i=1;i<=n;i++)
{
hs[s[i-1]]++;
ans+=hs[s[i]-k];
}
cout< \(F.\)Swap and Sort
题意
有一个关于\((1,2,...,N)\)的排列\(P=(P_1,P_2,...,P_n)\)
现在有\(M\)中操作：第\(i\)种操作是交换\(P\)的第\(a_i\)和第\(b_i\)个元素
问是否可以操作不大于\(5\times10^5\)次使得\(P\)变为\((1,2,...,N)\)
如果可以输出操作次数和操作顺序，如果不可以输出-1
\(1\le N \le5000\) \(1\le M\le min(2\times10^5,\frac{N(N-1)}{2})\)
\((a_i,b_i)!=(a_j,b_j)\) if \(i!=j\)
Sol
对于这种全排序序列的问题，很常见的一个想法就是构造连通图
对于所有种类的操作，将它们用并查集划分成一个个连通块
然后判断一遍\(P_i\)是否和\(i\)在一个连通块内，如果不在，说明\(P_i\)和\(i\)无法通过交换的到，输出\(-1\)
否则，说明有解，那么从一个没有被访问过且点度为\(1\)的数\(P_i\)开始复位并删点，如果他可以通过这些操作到达\(i\),说明这条寻找路径上的所有交换操作都可以使用，加入答案中即可，等价于在生成树上找。
由于最多交换\(999+998+...+2+1=499500\)次，所有有解的话一定满足条件
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=1005;
int p[N],fa[N],st[N];
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
struct edges{int v,id;};
vectore[N];
vectorans;
bool dfs2(int u,int to,int f)
{
if(p[u]==to) return true;
for(auto t:e[u])
{
int v=t.v,id=t.id;
if(v==f) continue;
if(dfs2(v,to,u))
{
swap(p[u],p[v]);
ans.pb(id);
return true;
}
}
return false;
}
void dfs1(int u) //从点度为1的点开始搜
{
st[u]=1;
for(auto t:e[u])
{
int v=t.v;
if(st[v]) continue;
dfs1(v);
}
dfs2(u,u,-1);
}
int main()
{
int n;
rd(n);
for(int i=1;i<=n;i++) rd(p[i]),fa[i]=i;
int m;
rd(m);
for(int i=1;i<=m;i++)
{
int x,y;
rd(x),rd(y);
int fx=find(x),fy=find(y);
if(fx!=fy)
{
fa[fx]=fy;
e[x].pb({y,i});
e[y].pb({x,i});
}
}
for(int i=1;i<=n;i++)
{
int fx=find(p[i]),fy=find(i);
if(fx!=fy)
{
puts("-1");
return 0;
}
}
for(int i=1;i<=n;i++)
if(!st[i]) dfs1(i);
printf("%d\n",ans.size());
for(auto id:ans) printf("%d ",id);
return 0;
}
\(G.\)Strongest Takahashi
题意
给定一个\(N\times N\)的网格图，里面有若干个障碍#，每次可以选择一个整数\(D\)(\(1\le D\le N\))，然后选择一个\(D\times D\)的区域把里面的障碍都消掉，每次消耗为\(D\)，请问最少需要消耗多少可以把障碍全部消完。
\(1\le N \le 50\)
Sol
定义\(dp[x_1][y_1][x_2][y_2]\)为消掉以(\(x_1,y_1\))为左上角，以(\((x_2,y_2)\))为右下角的矩形内的障碍最少需要的消耗。
一个\(A\times B\)的矩形的最大消耗为\(max(A,B)\)
可以考虑将一个矩形按划分方式递推
1.横着划分:\(dp[x_1][y_1][x_2][y_2]=min(dp[x_1,y_1,x_2,y_2],dp[x_1][y_1][k][y_2]+dp[k+1][y_1][x_2][y_2])\) \(x_1\le k \lt x_2\)
2.竖着划分:\(dp[x_1][y_1][x_2][y_2]=min(dp[x_1][y_1][x_2][y_2],dp[x_1][y_1][x_2][k]+dp[x_1][k+1][x_2][y_2])\) \(y_1 \le k \lt y_2\)
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
char g[55][55];
int dp[55][55][55][55];
int dfs(int x1,int y1,int x2,int y2)
{
int &t=dp[x1][y1][x2][y2];
if(t!=-1) return t;
if(x1==x2&&y1==y2) return g[x1][y1]=='#';
t=max(x2-x1+1,y2-y1+1);
for(int k=x1;k>g[i][j];
printf("%d\n",dfs(1,1,n,n));
return 0;
}
\(Ex.Manhattan Christmas Tree\)
题意
在二维平面上给定\(N\)个点，有\(Q\)个询问，每次询问给定一个点\((a_i,b_i)\)和\(K_i\)，问这\(N\)个点距离\((a_i,b_i)\)第\(K_i\)近的距离是多少
距离的计算是曼哈顿距离.
所有数据的范围都是\(1\le data \le 10^5\)
Sol
前置知识:
假设\(A(x_1,y_1),B(x_2,y_2)\)
曼哈顿距离:\(d1=|x_1-x_2|+|y_1-y_2|\)
切比雪夫距离:\(d_2=max(|x_1-x_2|,|y_1-y_2|)\)
曼哈顿距离到切比雪夫距离：\((x,y)->(x+y,x-y)\) 可以看做把坐标系旋转\(45^{。}\)
推导:
(1) \(d_1=x_1-x_2+y_1-y_2\) (2) \(d_1=x_1-x_2+y_2-y_1\) (3) \(d_1=x_2-x_1+y_1-y_2\) (4) \(d_1=x_2-x_1+y_2-y_1\)
求这4中情况中最大的
其中(1)(4)得到\(|(x_1+y_1)-(x_2+y_2)|\) (2)(3)得到\(|(x_1-y_1)-(x_2-y_2)|\)
最大就是\(max(|(x_1+y_1)-(x_2+y_2)|,|(x_1-y_1)-(x_2-y_2)|)\)
最小值同理
切比雪夫距离到曼哈顿距离转化：\((x,y)->(\frac{x+y}{2},\frac{x-y}{2})\)
于是对每个询问就可以二分一下第\(k\)近的距离，\(check\)就是查询有多少个点到\((a_i,b_i)\)的切比雪夫距离\(\le\)二分距离\(mid\)，这就是一个二维数点问题，可以用树状数组或者主席树解决。这里采用树状数组。
#include
#define ll long long
#define inf 0x7f7f7f7fll
#define fi first
#define se second
#define mod 998244353
#define pb push_back
using namespace std;
template void rd (T &x)
{
x=0;int f=1;char s=getchar();
while(s<'0'||s>'9'){if(s=='-') f=-1;s=getchar();}
while(s>='0'&&s<='9') x=x*10+(s^48),s=getchar();
x*=f;
}
template void chkMax(T &x, T y) { if (y > x) x = y; }
template void chkMin(T &x, T y) { if (y < x) x = y; }
const int N=2e5+10;
struct Point{
int x,y;
bool operator < (const Point &t) const
{
return ytr[N];
int lowbit(int x){return x&-x;}
void add(int x,int y)
{
for(int pos=x;pos=k;
}
int n,t;
int main()
{
rd(n);
for(int i=1;i<=n;i++)
{
int x,y;
rd(x),rd(y);
p[i].x=x+y+1,p[i].y=x-y+1;
}
sort(p+1,p+1+n);
for(int i=1;i<=n;i++)
add(p[i].x,p[i].y);
rd(t);
while(t--)
{
int a,b,k;
rd(a),rd(b),rd(k);
int l=0,r=2e5+10;
while(l>1;
if(check(a,b,k,mid)) r=mid;
else l=mid+1;
}
cout<