当前位置：首页 > news >正文

2019 南京网络赛 A.The beautiful values of the palace 构造螺旋矩阵 + CDQ / 离线 + 树状数组

news 来源：原创 2023/6/7 2:48:35

题目链接：https://nanti.jisuanke.com/t/41298

题解：首先我们要把每个坐标的val求出来，很明显每一圈的个数是一个等差数列，第x圈 a[x] = -8x+4n+4，然后就是先等差前n项和求出之前每一圈的总个数，然后对于x 与 y x + y 与 n + 1 的大小分4种情况，求出该点是该圈的第几个即可，然后用这就是个三维偏序问题，CDQ分治或者离线+树状数组都能解决

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define lowbit(x) (x & (-x))
const int N = 1e5 + 10;ll getnum(ll n, ll x, ll y) {ll p = 0;ll ans = 0;if(x <= y && x + y <= n + 1) {   p = x;ans = y - p + 1;} else if(x <= y && x + y >= n + 1) {   p = n - y + 1;ans = n - 3 * p + x + 2;}else if(x >= y && x + y >= n + 1) {   p = n - x + 1;ans = 3 * n - 5 * p - y + 4;} else {   p = y;   ans = 4 * n - 7 * p - x + 5;}ans += 4 * (p - 1) * (n - p + 1);return ans;
}
int n, m, p;
struct node {int x, y;ll val;int op;int pos;bool operator <(const node &xx)const {return x == xx.x ? op < xx.op : x < xx.x;}
}q[N * 5], tmp[N * 5];
int len;
ll ans[N];
ll sum[N * 10];
void update(int x,ll val)
{while(x<=1000000){sum[x]+=val;x+=lowbit(x);}
}
int query(int x)
{ll res=0;while(x){res+=sum[x];x-=lowbit(x);}return res;
}
void sum_clear(int x)
{while(x<=1000000){sum[x]=0;x+=lowbit(x);}
}
void CDQ(int l,int r)
{if(r-l<=1) return;int mid=(r+l)>>1;CDQ(l,mid);CDQ(mid,r);int ll=l,rr=mid;int cnt=0;while(ll<mid&&rr<r){if(q[ll]<q[rr]){if(q[ll].op==1) update(q[ll].y,q[ll].val);tmp[cnt++]=q[ll++];}else{if(q[rr].op==2) ans[q[rr].pos]+=query(q[rr].y);if(q[rr].op==3) ans[q[rr].pos]-=query(q[rr].y);tmp[cnt++]=q[rr++];}}while(ll<mid) tmp[cnt++]=q[ll++];while(rr<r){if(q[rr].op==2) ans[q[rr].pos]+=query(q[rr].y);if(q[rr].op==3) ans[q[rr].pos]-=query(q[rr].y);tmp[cnt++]=q[rr++];}for(int i=0;i<cnt;i++){q[l+i]=tmp[i];if(tmp[i].op==1)sum_clear(tmp[i].y);}
}int main() {int T;int x1, x2, y1, y2;ll tmp;ll num;scanf("%d", &T);while(T--) {scanf("%d %d %d", &n, &m, &p);len = 0;for(int i = 0; i < m; i++) {scanf("%d %d", &q[i].x, &q[i].y);swap(q[i].x, q[i].y);tmp = getnum(n, n - q[i].y + 1, n - q[i].x + 1);num = 0;while(tmp) {num += tmp % 10;tmp /= 10;}q[i].val = num;q[i].op = 1;}len = m;for(int i = 1; i <= p; i++) {ans[i] = 0;scanf("%d%d%d%d",&x1,&y1,&x2,&y2);swap(x1, y1);swap(x2, y2);q[len].op=2;q[len].x=x2;q[len].y=y2;q[len].pos=i;len++;q[len].op=3;q[len].x=x1-1;q[len].y=y2;q[len].pos=i;len++;q[len].op=3;q[len].x=x2;q[len].y=y1-1;q[len].pos=i;len++;q[len].op=2;q[len].x=x1-1;q[len].y=y1-1;q[len].pos=i;len++;}CDQ(0, len);for(int i =1; i <= p; i++)printf("%lld\n", ans[i]);}	return 0;
}

2019 南京网络赛 A.The beautiful values of the palace 构造螺旋矩阵 + CDQ / 离线 + 树状数组

题目链接：https://nanti.jisuanke.com/t/41298 题解：首先我们要把每个坐标的val求出来，很明显每一圈的个数是一个等差数列，第x圈 a[x] -8x4n4，然后就是先等差前n项和求出之前每一圈的总个数，然后对于x 与…...

编程日记 2023/6/7 2:48:35

2018北京网络赛 HihoCoder - 1835 K-Dimensional Foil II 计算几何贪心二分

题目链接：https://vjudge.net/problem/HihoCoder-1835 题解：首先我们应该能想到到达图形的距离最近那肯定是垂直过去，也就是坐标变为(x1 - k, x2 - k, x3 - k...)，假设图形原点的坐标为(x10, x20, x30 ...)，如果某个x…...

编程日记 2023/5/20 18:11:29

$dp[u]=\frac{1}{size + 1} * dp[u] + \sum\frac{1}{size + 1} * dp[to] + d[u]$

相关文章：