214 条题解
-
7
学习阶段的刘锦钰 LV 9 @ 6 年前
送上一好理解+简短的题解
因为这道题的数据范围较小,所以我们可以直接暴力拿到100分:
同时,如果提高数据范围,我们要怎么办呢?
(抄题解!!!)我们可以用一种更加高级的做法:树状数组!(妙不可言)
具体可以在网上搜一下 -
28 年前@
编译成功
测试数据 #0: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 864 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 860 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 864 KiB, score = 10
Accepted, time = 0 ms, mem = 864 KiB, score = 100
数据弱啊 直接树状数组排序后秒杀~
```
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;char rd; int pn;
template<typename Type>
inline void read(Type& v)
{
pn=1;
while((rd=getchar())<'0'||rd>'9')
if(rd=='-')
pn=-1;
v=rd-'0';
while((rd=getchar())>='0'&&rd<='9')
v=v*10+rd-'0';
v*=pn;
}
template<typename Type>
inline void out(Type v,bool c=1)
{
if(v==0)
putchar(48);
else
{
if(v<0)
{
putchar('-');
v=-v;
}
int len=0,dg[20];
while(v>0)
{
dg[++len]=v%10;
v/=10;
}
for(int i=len;i>=1;i--)
putchar(dg[i]+48);
}
if(c)
putchar('\n');
else
putchar(' ');
}const int MAXN=15005;
const int MAXV=32005;
struct node
{
int x,y;
bool operator<(const node& b)const
{
if(x==b.x)
return y<b.y;
else
return x<b.x;
}
}a[MAXN];
int t[MAXV];
int ans[MAXN];
int maxy;
int n;inline int lowbit(int& x)
{
return x&(-x);
}void init()
{
read(n);
for(int i=1;i<=n;i++)
{
read(a[i].x); read(a[i].y);
maxy=max(maxy,a[i].y);
}
sort(a+1,a+n+1);
}int sum(int x)
{
int ans=0;
while(x>0)
{
ans+=t[x];
x-=lowbit(x);
}
return ans;
}void add(int x,int d)
{
while(x<=maxy)
{
t[x]+=d;
x+=lowbit(x);
}
}void work()
{
for(int i=1;i<=n;i++)
{
ans[sum(a[i].y)]++;
add(a[i].y,1);
}
for(int i=0;i<n;i++)
out(ans[i]);
}int main()
{
init();
work();
}
``` -
15 年前@
很显然的树状数组
何为树状数组?
写在前面:
原码,反码,补码:
正数:原==反==补
负数:
原码略;
反码:第一位(符号位)不变,其他位取反;
补码:反码+1;
栗子:-10
原码:10001010;
反码:11110101;
补码:11110110;
树状数组:
ccs:树状数组,顾名思义,就是橡树一样的数组..
看这张图就一目了然了。
两个数组:
a[i]储存原序列;
c[i]树状数组;c[1]存第一个数(如图),
c[2]存前两个数的和,
c[3]存第三个数,
c[4]存前四个数的和...以此类推。树状数组储存方式独特,其中储存的和的个数为其lowbit值。
举个栗子:
c[1]中存了1个数,lowbit(1)=1;
c[2]中存了2个数,lowbit(2)=2;
c[4]中存了4个数,lowbit(4)=4;
而lowbit怎么算呢?~~(先逃)~~
树状数组主要包括三个函数
first. 求lowbit值
second.给第x个数加k
third.查询区间和
~~(手动模拟一下就知道了)~~
题目
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某一个数加上x
2.求出某区间每一个数的和
输入格式
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3个整数,表示一个操作,具体如下:
操作1: 格式:1 x k 含义:将第x个数加上k
操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和
输出格式
输出包含若干行整数,即为所有操作2的结果。
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数数加上x
2.求出某一个数的值
输入格式
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含2或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k
操作2: 格式:2 x 含义:输出第x个数的值
输出格式
输出包含若干行整数,即为所有操作2的结果。
而这个题就是树状数组的应用,先将坐标从左到右排序,再往里面加点就可以了。
-
16 年前@
先把所有点按x从小到大排序,这样就只需要y了
枚举每个点,要统计之前有多少个点的y坐标小于等于x,于是考虑树状数组
别忘了查询之后要更新到树上去哦 -
17 年前@
不正解:前缀和,死无葬身之所,空间复杂度太高。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<climits>
using namespace std;
const int maxn=20000,inf=INT_MAX;
inline const void read(int &a)
{
a=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=a*10+c-'0';
c=getchar();
}
}
int n,p[maxn],x[maxn],y[maxn],range;
int ans[maxn][maxn],num[maxn];
int main()
{
memset(ans,0,sizeof(ans));
memset(num,0,sizeof(num));
read(n);
for(int i=1;i<=n;i++)
{
read(x[i]);read(y[i]);
range=max(range,max(x[i],y[i]));
ans[x[i]][y[i]]++;
}
for(int i=1;i<=range;i++)
for(int j=1;j<=range;j++)
ans[i][j]=ans[i][j]+ans[i-1][j]+ans[i][j-1]-ans[i-1][j-1];
for(int i=1;i<=n;i++)num[ans[x[i]][y[i]]-1]++;
for(int i=0;i<=n-1;i++)printf("%d\n",num[i]);
return 0;
}
二维线段树(四叉树)记录每一个区间内的个数,然后统计就是了。不过效率并不高。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
using namespace std;
const int maxn=32001;
inline const void read(int &a)
{
a=0;
char c=getchar();
while(c<'0'||c>'9')c=getchar();
while(c>='0'&&c<='9')
{
a=a*10+c-'0';
c=getchar();
}
}
class node
{
public:
int left,right,up,down,num;
int son1,son2,son3,son4;
void clean()
{
left=right=up=down=num=son1=son2=son3=son4=0;
}
}p[2*maxn];
int n,x[maxn],y[maxn],x_range=0,y_range=0,d=0,ans[maxn];
void build_tree(int i,int o)
{
p[o].num++;
if(p[o].right==p[o].left&&p[o].up==p[o].down)return ;
int midx=(p[o].left+p[o].right)/2,midy=(p[o].up+p[o].down)/2;
if(x[i]<=midx&&y[i]>midy)
{
if(!p[o].son1)
{
d++;
p[o].son1=d;
p[d].left=p[o].left;p[d].right=midx;
p[d].down=midy+1;p[d].up=p[o].up;
}
build_tree(i,p[o].son1);
return ;
}
if(x[i]>midx&&y[i]>midy)
{
if(!p[o].son2)
{
d++;
p[o].son2=d;
p[d].left=midx+1;p[d].right=p[o].right;
p[d].down=midy+1;p[d].up=p[o].up;
}
build_tree(i,p[o].son2);
return ;
}
if(x[i]<=midx&&y[i]<=midy)
{
if(!p[o].son3)
{
d++;
p[o].son3=d;
p[d].left=p[o].left;p[d].right=midx;
p[d].down=p[o].down;p[d].up=midy;
}
build_tree(i,p[o].son3);
return ;
}
if(x[i]>midx&&y[i]<=midy)
{
if(!p[o].son4)
{
d++;
p[o].son4=d;
p[d].left=midx+1;p[d].right=p[o].right;
p[d].down=p[o].down;p[d].up=midy;
}
build_tree(i,p[o].son4);
return ;
}
}
inline const bool intersection(int i,int o)
{
if(p[o].down<=y[i]&&p[o].left<=x[i])return true;
else return false;
}
int find_ans(int i,int o)
{
if(x[i]>=p[o].right&&y[i]>=p[o].up)return p[o].num;
int result=0;
if(p[o].son1&&intersection(i,p[o].son1))result+=find_ans(i,p[o].son1);
if(p[o].son2&&intersection(i,p[o].son2))result+=find_ans(i,p[o].son2);
if(p[o].son3&&intersection(i,p[o].son3))result+=find_ans(i,p[o].son3);
if(p[o].son4&&intersection(i,p[o].son4))result+=find_ans(i,p[o].son4);
return result;
}
int main()
{
memset(ans,0,sizeof(ans));
for(int i=0;i<=2*maxn-1;i++)p[i].clean();
read(n);
for(int i=1;i<=n;i++)
{
read(x[i]);read(y[i]);
x_range=max(x_range,x[i]);y_range=max(y_range,y[i]);
}
p[1].left=1;p[1].right=x_range;p[1].down=1;p[1].up=y_range;d++;
for(int i=1;i<=n;i++)build_tree(i,1);
for(int i=1;i<=n;i++)ans[find_ans(i,1)-1]++;
for(int i=0;i<=n-1;i++)printf("%d\n",ans[i]);
return 0;
}
最终还是要写二维树状数组(此处略) -
18 年前@
树状数组,妙不可言,学习了
-
06 年前@
-
07 年前@
參考@continue;的解法:
-
07 年前@
http://zory.cf/2018-01/弱弱的战壕.html
来源和评测点
<!-- more -->
题目
<p id="div-border-top-green">【题目大意】
永恒和mx正在玩一个即时战略游戏,名字嘛~~~~~~恕本人记性不好,忘了。
mx在他的基地附近建立了n个战壕,每个战壕都是一个独立的作战单位,
射程可以达到无限。但是,战壕有一个弱点,就是只能攻击它的左下方,
说白了就是横纵坐标都不大于它的点(mx:“我的战壕为什么这么菜”ToT)。
这样,永恒就可以从别的地方进攻摧毁战壕,从而消灭mx的部队。
战壕都有一个保护范围,同它的攻击范围一样,
它可以保护处在它左下方的战壕。
所有处于它保护范围的战壕都叫做它的保护对象。
这样,永恒就必须找到mx的战壕中保护对象最多的点,从而优先消灭它。
现在,由于永恒没有时间来计算,所以拜托你来完成这个任务:
给出这n个战壕的坐标xi、yi,要你求出保护对象个数为0,1,2……n-1的战壕的个数。【输入格式】
第一行,一个正整数n(1<=n<=15000)
接下来n行,每行两个数xi,yi,代表第i个点的坐标
(1<=xi,yi<=32000)
注意:可能包含多重战壕的情况(即有数个点在同一坐标)【输出格式】
输出n行,分别代表保护对象为0,1,2……n-1的战壕的个数。【输入样例】
5
1 1
5 1
7 1
3 3
5 5【输出样例】
1
2
1
1
0</p>
分析
做做难度不大但有所创新的题目还是挺好的
先排序一遍确保形如这样
* -
按顺序处理就保证了y更小
接着用树状数组维护x的前缀和即可代码
-
08 年前@
-
08 年前@
先对横坐标排序,手写BST,看每一个点前有多少个横纵坐标都比它小的。
先默认每人都能保护自己,最后全都减一 -
08 年前@
只能sort+一维搞。。二维的话炸内存了。。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>using namespace std;
const int N=33000;
vector<pair<int,int> >v;
int n,x,y;int a[N];
int ans[16000];void add(int x){
for(int i=x;i<=N;i+=i&(-i))
a[i]++;
}int ask(int x){
int ret=0;
for(int i=x;i;i-=i&(-i))
ret+=a[i];
return ret;
}int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d%d",&x,&y);
v.push_back(make_pair(x,y));
}
sort(v.begin(),v.end());for(int i=0;i<n;i++){
ans[ask(v[i].second)]++;
add(v[i].second);
}
for(int i=0;i<n;i++){
printf("%d\n",ans[i]);
}
} -
08 年前@
简粗
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x[15001],y[15001],f[15001]={0},i,j,s;
cin>>n;
for(i=1;i<=n;i++)
cin>>x[i]>>y[i];
for(i=1;i<=n;i++)
{
s=0;
for(j=1;j<=n;j++)
{
if(j==i) continue;
else
if(x[j]<=x[i]&&y[j]<=y[i]) s++;
}
f[s]++;
}
for(i=0;i<=n-1;i++)
cout<<f[i]<<endl;
return 0;
} -
09 年前@
数据超弱~朴素150ms十个点……
```c++
#include<cstdio>
#include<cstring>
using namespace std;int n;
int ans1[15200],x[15200],y[15200],ans[15200];int main()
{
memset(ans,0,sizeof(ans));
memset(ans1,0,sizeof(ans1));
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&(x[i]>=x[j])&&y[i]>=y[j]) ans[i]++;
for(int i=1;i<=n;i++)
ans1[ans[i]]++;
for(int i=0;i<n;i++)
printf("%d\n",ans1[i]);
return 0;
}
``` -
09 年前@
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n,ans[15000];
struct node{int r,l,v;}tr[100001];
struct data{int x,y;}f[15000];inline bool cmp(data a,data b){return (a.x==b.x)?(a.y<b.y):(a.x<b.x);}
void build(int size,int lf,int rt){
tr[size].v=0;
tr[size].l=lf;
tr[size].r=rt;
if(lf==rt)return;
int mid=(lf+rt)>>1;
build(size<<1,lf,mid);
build(size<<1|1,mid+1,rt);
}void insert(int st,int ed,int size){
int mid=(tr[size].l+tr[size].r)>>1;
if(tr[size].l==st&&tr[size].r==ed){
tr[size].v++;
return;
}
else if(tr[size].r==tr[size].l)return;
else if(ed<=mid)insert(st,ed,size<<1);
else if(st>mid)insert(st,ed,size<<1|1);
else{
insert(st,mid,size<<1);
insert(mid+1,ed,size<<1|1);
}
}int query(int x,int size){
if(tr[size].r==tr[size].l)return tr[size].v;
int mid=(tr[size].r+tr[size].l)>>1;
if(x<=mid)return tr[size].v+(query(x,size<<1));
else return tr[size].v+(query(x,size<<1|1));
}int main(){
cin>>n;
build(1,0,32001);
for(int i=0;i<n;i++){
cin>>f[i].x>>f[i].y;
}
sort(f,f+n,cmp);
for(int i=0;i<n;i++){
ans[query(f[i].y,1)]++;
insert(f[i].y,32001,1);
}
for(int i=0;i<n;i++){
cout<<ans[i]<<"\n";
}
return(0);
} -
09 年前@
-
09 年前@
#include <iostream>
using namespace std;
int x[5005], y[5005];
int n, k;
int a[5005];
int main(){
cin>>n;
for (int i = 0; i<n; i++)
cin>>x[i]>>y[i];
for (int i = 0; i<n; i++){
k = 0;
for (int j = 0; j < n; j++)
{
if (i != j && x[i] >= x[j] && y[i] >= y[j])
k++;
}
a[k]++;
}
for (int i = 0; i < n; i++)
cout << a[i]<<endl;
return 0;
} -
09 年前@
树状数组秒过
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <stack>
using namespace std;
inline int LC(int x) {return x << 1;}
inline int RC(int x) {return x << 1 | 1;}
typedef long long LL;
const int N = 15000 + 24;
const int M = 32000 + 24;
int n,m,p,Case = 1,top;
int sum[M];
struct node
{
int x,y;
}s[N];
int k[N];
bool cmp(const node& a, const node& b)
{
if(a.x == b.x)
return a.y < b.y;
return a.x < b.x;
}
int lowbit(int x)
{
return x&(-x);
}
void add(int x, int num)
{
while(x <= M)
{
sum[x] += num;
x += lowbit(x);
}
}
int sub(int x)
{
int num = 0;
while(x > 0)
{
num += sum[x];
x -= lowbit(x);
}
return num;
}
int main()
{
#ifdef CDZSC_OFFLINE
freopen("in.txt","r",stdin);
#endif //CDZSC_OFFLINE
while(~scanf("%d",&n))
{
memset(k,0,sizeof(k));
memset(sum,0,sizeof(sum));
for(int i = 0; i < n; i++)
{
scanf("%d%d",&s[i].x,&s[i].y);
}
sort(s,s+n,cmp);
for(int i = 0; i < n; i++)
{
int a = sub(s[i].y);
k[a]++;
add(s[i].y,1);
}
for(int i = 0; i < n; i++)
printf("%d\n",k[i]);
}
} -
09 年前@
测试数据 #0: Accepted, time = 0 ms, mem = 840 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 832 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 836 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 836 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 836 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 836 KiB, score = 10
测试数据 #6: Accepted, time = 1 ms, mem = 836 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 836 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 832 KiB, score = 10
测试数据 #9: Accepted, time = 6 ms, mem = 836 KiB, score = 10
Accepted, time = 37 ms, mem = 840 KiB, score = 100
数据太小不用离散化,树状数组秒过
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int n,ans[15001],a[32001]={0},maxx=0;
struct poi{
int x,y;
}p[15001];
bool cmp(const poi &a,const poi &b){
if(a.y!=b.y)return a.y<b.y;
else return a.x<b.x;
}
int lowbit(int x){
return x&(-x);
}
void change(int pos){
for(int i=pos;i<=32000;i+=lowbit(i))
a[i]++;
}
int findsum(int pos){
int sum=0;
for(;pos>0;pos=pos-lowbit(pos))
sum+=a[pos];
return sum;
}
int main(){
int i,x,y;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%d%d",&p[i].x,&p[i].y);
maxx=max(maxx,p[i].x);
}
sort(p+1,p+n+1,cmp);
for(i=1;i<=n;i++){
ans[findsum(p[i].x)]++;
change(p[i].x);
}
for(i=0;i<n;i++)printf("%d\n",ans[i]);
return 0;
} -
09 年前@
数据真的弱爆了