AtCoder Beginner Contest 450（ABC449）
A - π
\(S = \pi (\frac{d}{2})^2\)，而且通过第一个样例就可以知道\(\pi\)是多少。
点击查看代码
//再次相聚之前，谢谢你带我回到这人世间。
#include<bits/stdc++.h>
using namespace std;
signed main(){
double d;
cin >> d;
d /= 2;
printf("%.8lf",d*d*3.1415926535);
return 0;
}
B - Deconstruct Chocolate
记录当前的\(n\)和\(m\)即可。
具体来说，\(op = 1\)时，少\(x\)行，\(x \times m\)个格，\(n\)减去\(x\)；\(op = 2\)时，少\(x\)列，\(x \times n\)个格，\(m\)减去\(x\)。
点击查看代码
//再次相聚之前，谢谢你带我回到这人世间。
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
signed main(){
cin >> n >> m >> q;
while(q--){
int op,x;
cin >> op >> x;
int ans = 0;
if(op == 1) ans = x*m,n -= x;
else ans = x*n,m -= x;
cout << ans << '\n';
}
return 0;
}
C - Comfortable Distance
对于这样的二元组计数，我们一般固定一个，找另一个有多少个。
这里，我们固定\(j\)，看满足条件的\(i\)有多少个。
维护一个桶存下标在\([j-r,j-l]\)范围内的每个字母有多少个，每次查一下和当前\(j\)相同的字母有多少个即可。
怎样维护？每当\(j\)向后挪一个的时候，也就是说\(j-r-1\)这个字母就不再范围内了，而\(j-l\)这个字母会变到范围内，那么我们去掉\(S_{j-r-1}\)，加上\(S_{j-l}\)即可。
点击查看代码
//再次相聚之前，谢谢你带我回到这人世间
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,l,r;
char s[5000005];
int gs[3000];
signed main(){
cin >> n >> l >> r;
for(int i = 1;i <= n;++ i)
cin >> s[i];
int ans = 0;
for(int i = 1;i <= n;++ i){
if(i-l >= 1) gs[s[i-l]-'a']++;
if(i-r-1 >= 1) gs[s[i-r-1]-'a']--;
ans += gs[s[i]-'a'];
}
cout << ans;
return 0;
}
D - Make Target 2
被我做的比较炸裂的一个题。。。
首先，我们考虑仅有第一象限的情况。（其实就是代码的\(cl\)函数做的事情）
这个像C题一样，二元组计数，定一数一。我们定\(x\)数\(y\)，要满足\(l \leq x \leq r\)且\(d \leq y \leq u\)且\(max(x,y)\)是偶数（这里只有第一象限，所以去掉绝对值）。如果\(x\)是偶数，那么对于所有的\(d \leq y \leq x\)的\(y\)，都可以计入答案，对于所有的\(x < y \leq u\)且\(y\)为偶数的\(y\)，都可以计入答案；如果\(x\)是奇数，那么就只有\(x < y \leq u\)且\(y\)为偶数的\(y\)可以计入答案。
但是，这是比较理想的状态，如果\(x < d\)，也就是所有的\(y\)都大于\(x\)，那么\(y\)只要满足\(d \leq y \leq u\)且为偶数即可；如果\(x > u\)，也就是所有的\(y\)都小于\(x\)，那么\(x\)是偶数，所有满足\(d \leq y \leq u\)的\(y\)都可以，\(x\)是奇数，所有\(y\)均不行。
这样，求\(y\)就变成了求某个范围内数的个数或偶数的个数，很好做了吧，注意判断一下如果下界大于上界的情况是\(0\)。
这样，仅有第一象限的情况我们就做完了，剩下三个象限怎么办呢？
发现，剩下三个象限均可以对称到第一象限去，而且大小关系非常正确，那么我们只需要沿\(x\)轴和\(y\)轴把所求范围切开即可。注意\(x\)轴和\(y\)轴切到哪一部分的问题，比如\(x\)轴切到三四象限，\(y\)轴切到二三象限。
还要注意判断一下每个象限都有没有的问题，也就是\(L\)和\(R\)，\(D\)和\(U\)的正负性是否相同。（去看一下代码吧，相信你可以看懂）。
还还要注意如果对称是直接取了绝对值，上下界可能会反，比如\([-4,-2]\)取绝对值会变为\([4,2]\)，但实际上应该变为\([2,4]\)，要判断一下，如果反了要交换。
点击查看代码
//再次相聚之前，谢谢你带我回到这人世间
#include<bits/stdc++.h>
#define int long long
using namespace std;
int getou(int x,int y){
if(x > y) return 0;
int len = y-x+1;
if(len%2 == 0) return len/2;
int ans = len/2;
if(x%2 == 0) ans++;
return ans;
}
int getgs(int x,int y){
if(x > y) return 0;
return y-x+1;
}
int cl(int l,int r,int d,int u){
int ans = 0;
for(int x = l;x <= r;++ x){
if(x%2 == 0){
if(x < d){
ans += getou(d,u);
}
else if(x > u){
ans += getgs(d,u);
}
else ans += getgs(d,x)+getou(x+1,u);
}
else{
if(x < d){
ans += getou(d,u);
}
else if(x > u){
ans += 0;
}
else ans += getou(x+1,u);
}
}
return ans;
}
signed main(){
int a,b,c,d;
cin >> a >> b >> c >> d;
int fa,fb,fc,fd;
if(a > 0) fa = 1;
else fa = -1;
if(b > 0) fb = 1;
else fb = -1;
if(c > 0) fc = 1;
else fc = -1;
if(d > 0) fd = 1;
else fd = -1;
a = abs(a);
b = abs(b);
if(a > b) swap(a,b);
c = abs(c);
d = abs(d);
if(c > d) swap(c,d);
int ans = 0;
if(fa == fb){
if(fc == fd){
ans = cl(a,b,c,d);
}
else{
ans = cl(a,b,0,c);
ans += cl(a,b,1,d);
}
}
else{
if(fc == fd){
ans = cl(0,a,c,d);
ans += cl(1,b,c,d);
}
else{
ans = cl(0,a,0,c);
ans += cl(0,a,1,d);
ans += cl(1,b,0,c);
ans += cl(1,b,1,d);
}
}
cout << ans;
return 0;
}
E - A += v
OK啊，又是一个被我做的十分炸裂的一个题。
讲一下正常做法吧。
先来一个序列：
1 3 5 3 1 4 3 4 2 4 5
我们对每一个数开一个桶，画成如图的形状。
那么我们可以发现，题目要我们做的就是填坑（嗯对。），从高度低的开始填，高度相同的从小到大填。然后把填的坑的标号写下来。
也就是:
2 1 2 5 1 2 3 5 1 2 3 4 5 ……
再往后就都是1 2 3 4 5这样了。
那么怎么求答案呢？对于\(x \leq n\)的，肯定不用做什么，对于\(x > m \times mxgs\)的，求一个小学的周期问题即可。（\(mxgs\)就是个数最多的数的个数，也就是最大高度）
然后我们就要求\(n < x \leq m \times mxgs\)的那些\(x\)的答案了。我们如果按高度从小到大为第一关键字，编号从小到大为第二关键字排序的话，图会变成这样：
再从下到上从左到右给空的位置编个号：
那么如果我们把\(x\)减去\(n\)的话，就变成了求编号为\(x\)的空位置是多少。（想想为什么，应该很好想吧）这个可以转化为第几行的第几小，第几行就可以转化为前几个，也就可以转化为前几个的第几小（注意这里最下面的是第1行，最左面的是第1个），离线下来从前往后扫一遍树状数组加二分即可。
（这个代码还没有调过，不知道为什么，请不要妄想用这份代码AC）
点击查看代码
//再次相聚之前，谢谢你带我回到这人世间
#include<bits/stdc++.h>
#define int long long
#define lb(i) i&(-i)
using namespace std;
int n,m;
int a[500005];
int p[200005];
int gs[500005],mxgs;
bool cmp(int x,int y){
if(gs[x] == gs[y]) return x < y;
return gs[x] < gs[y];
}
int emp[500005];
int s[500005];
int quegs;
int ans[200005];
struct nd{
int a,b,id;
//前a个的第b小
}que[200005];
int quecnt;
bool cmpq(nd x,nd y){
return x.a < y.a;
}
int c[500005];
void add(int x,int v){
for(int i = x;i <= m;i += lb(i))
c[i] += v;
}
int sum(int x){
int res = 0;
for(int i = x;i;i -= lb(i))
res += c[i];
return res;
}
signed main(){
cin >> n >> m;
for(int i = 1;i <= n;++ i)
cin >> a[i],mxgs = max(mxgs,(++gs[a[i]]));
for(int i = 1;i <= m;++ i)
p[i] = i;
sort(p+1,p+1+m,cmp);
for(int i = 1;i <= m;++ i)
emp[gs[i]+1]++;
for(int i = 2;i <= mxgs+1;++ i)
emp[i] += emp[i-1];
for(int i = 1;i <= mxgs+1;++ i)
s[i] = s[i-1]+emp[i];
cin >> quegs;
for(int i = 1;i <= quegs;++ i){
int x;cin >> x;
if(x <= n){
ans[i] = a[x];
continue;
}
if(x > mxgs*m){
x -= mxgs*m;
x %= m;
if(x == 0) x = m;
ans[i] = x;
continue;
}
x -= n;
int w = lower_bound(s+1,s+1+mxgs+1,x)-s;
x -= s[w-1];
que[++quecnt] = {emp[w],x,i};
}
sort(que+1,que+1+quecnt,cmpq);
for(int i = 1;i <= quecnt;++ i){
int a = que[i].a;
int b = que[i].b;
int id = que[i].id;
for(int j = que[i-1].a+1;j <= a;++ j)
add(p[j],1);
int l = 1,r = m;
while(l < r){
int mid = (l+r)/2;
if(sum(mid) < b) l = mid+1;
else r = mid;
}
ans[id] = l;
}
for(int i = 1;i <= quegs;++ i)
cout << ans[i] << '\n';
return 0;
}
F - Grid Clipping
很板子的扫描线板子，对的，但是主播并不会扫描线板子。。。
没什么好讲的吧，上代码。
作为主播除了板子题以外做的第一道扫描线题，主播决定讲一下。
把一个黑点变为以这个黑点为右下角的一个\(h \times w\)的矩形，那么如果一个点被一个黑点所形成的矩形包含，那么以这个点为左上角的\(h \times w\)的矩形一定会包含这个黑点（想一下为什么）。
那么我们只需要求出所有个黑点所形成的矩形一共包含了几个点，那么以这些点为左上角的矩形就是包含黑点的，用总点数减去这些点得到的那些点即为以那些点为左上角的矩形不包含黑点的那些点。
求多个矩形一共包含了几个点就是矩形面积并，扫描线即可。
需要注意的几点：
1.扫描线事实上是求包含的面积而非点，所以我们要进行转化，将点转化为方块，将方块转化为点，大概是这样，红色是题目中的网格，黑色是我们转化过后的。
2.那么相应的，一个矩形对应的\(x_1,y_1,x_2,y_2\)都要注意一下它们的变化。
3.写扫描线的时候，矩形的上下边界一定要是边，不能是点，否则我调不出来/ll/ll/ll。
4.大概没啥了，看代码理解一下吧。
点击查看代码
//再次相遇之前，谢谢你带我回到这人世间。
#include<bits/stdc++.h>
#define int long long
#define ls tr[x].lc
#define rs tr[x].rc
using namespace std;
int mxn,mxm,n,m,_n_;
struct question{
int x,l,r,op;
}q[400005];
int qcnt;
vector<int> vx,vy;
void addx(int x){vx.push_back(x);}
void addy(int x){vy.push_back(x);}
int getx(int x){
return lower_bound(vx.begin(),vx.end(),x)-vx.begin();
}
int gety(int x){
return lower_bound(vy.begin(),vy.end(),x)-vy.begin();
}
int qzh[400005];
vector<question> v[400005];
struct nd{
int lc,rc;
int cnt,len;
}tr[1600005];
void pushup(int x,int xl,int xr){
if(tr[x].cnt) tr[x].len = qzh[xr]-qzh[xl-1];
else tr[x].len = tr[ls].len+tr[rs].len;
}
void build(int x,int xl,int xr){
tr[x] = {0,0,0,0};
if(xl == xr) return;
int xm = (xl+xr)>>1;
tr[x] = {x*2,x*2+1,0,0};
build(ls,xl,xm);
build(rs,xm+1,xr);
pushup(x,xl,xr);
}
void change(int x,int xl,int xr,int l,int r,int val){
if(l <= xl&&xr <= r){
tr[x].cnt += val;
pushup(x,xl,xr);
return;
}
int xm = (xl+xr)>>1;
if(l <= xm) change(ls,xl,xm,l,r,val);
if(r > xm) change(rs,xm+1,xr,l,r,val);
pushup(x,xl,xr);
}
signed main(){
cin >> mxn >> mxm >> n >> m >> _n_;
mxn = mxn-n+1+1;mxm = mxm-m+1+1;
if(_n_ == 0){
cout << (mxn-1)*(mxm-1);
return 0;
}
while(_n_--){
int r,c;
cin >> r >> c;
int a,b;
a = max(1ll,r-n+1);
b = max(1ll,c-m+1);
r = min(r+1,mxn);
c = min(c+1,mxm);
q[++qcnt] = {a,b,c,1};
q[++qcnt] = {r,b,c,-1};
addx(a);addy(b);addx(r);addy(c);
}
addx(-1);addy(-1);
sort(vx.begin(),vx.end());
vx.erase(unique(vx.begin(),vx.end()),vx.end());
sort(vy.begin(),vy.end());
vy.erase(unique(vy.begin(),vy.end()),vy.end());
for(int i = 1;i <= qcnt;++ i){
q[i] = {getx(q[i].x),gety(q[i].l),gety(q[i].r)-1,q[i].op};
v[q[i].x].push_back(q[i]);
}
int ans = (mxn-1)*(mxm-1);
int vys = vy.size()-2;
for(int i = 1;i <= vys;++ i)
qzh[i] = vy[i+1]-vy[i];
for(int i = 1;i <= vys;++ i)
qzh[i] += qzh[i-1];
build(1,1,vys);
for(int i = 1;i < vx.size()-1;++ i){
int _w_ = vx[i+1]-vx[i];
for(auto qu:v[i])
change(1,1,vys,qu.l,qu.r,qu.op);
ans -= tr[1].len*_w_;
}
cout << ans;
return 0;
}
浙公网安备 33010602011771号