(未完待续)
题目链接:JZOJ 3738/IOI2012, Day2, Ideal City
题目
本题有多种解法(模拟三种、正解),详情请看下一页。
题解
解法 A (直接模拟)
解法 B (另一种直接模拟)
解法 C (面对数据范围模拟)
解法 D (正解)
思路
考虑对解法 B 的更进一步的优化。
代码
代码比较长,要注意多处细节。
时间复杂度为 $\Theta(n\log _ 2n)$,预计得分 $100$ 分。
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::swap;
using std::sort;
#include<vector>
using std::vector;
typedef long long ll;
#define MOD 1000000000ll
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){//快读,无符号
register bool flag=false;
register char ch=getchar();
register int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return flag?-res:res;
}
const int MAXN=100000+5;
struct Point{//定义点的类型
int x,y;
bool operator<(const Point &a)const{
return (x!=a.x)?(x<a.x):(y<a.y);
}
};
struct Node{//定义缩点后得到的节点类型
int x,Miny,Maxy;
vector<int> to;
Node(void){
return;
}
Node(int a,int b,int c){
x=a,Miny=b,Maxy=c;
return;
}
};
int n;
ll res;
Point S[MAXN];
vector<Node> V;
void Build(void);
int weight(int);
ll DFS(int,int);
ll Calc(void);
int Solve(void);
int main(void){
//freopen("city.in","r",stdin);
//freopen("city.out","w",stdout);
register int i;
n=read();
//scanf("%d",&n);
for(i=1;i<=n;++i)
S[i].x=read(),S[i].y=read();
//scanf("%d%d",&S[i].x,&S[i].y);
printf("%d\n",Solve());
//fclose(stdin);
//fclose(stdout);
return 0;
}
void Build(void){
register int i,x,y,Miny,cnt,cnt1,cnt2;
V.clear();
sort(S+1,S+n+1);
cnt1=1;
while(cnt1<=n){
x=S[cnt1].x,Miny=S[cnt1].y,y=Miny;
for(i=cnt1+1;i<=n;++i){
if(S[i].y==y+1)
++y;
else
break;
}
cnt1=i;
V.push_back(Node(x,Miny,y));
}
for(cnt1=0,cnt2=1;cnt2<(int)V.size();++cnt2){
while((V[cnt1].x+1<V[cnt2].x)||(V[cnt1].x+1==V[cnt2].x&&V[cnt1].Maxy<V[cnt2].Miny))
++cnt1;
cnt=0;
while(V[cnt1].x+1==V[cnt2].x&&V[cnt1].Miny<=V[cnt2].Maxy){
++cnt;
V[cnt1].to.push_back((int)cnt2);
V[cnt2].to.push_back((int)cnt1);
++cnt1;
}
if(cnt>0)
--cnt1;
}
return;
}
ll DFS(int ID,int fa){
register int i;
register ll size=V[ID].Maxy-V[ID].Miny+1;
for(i=0;i<(int)V[ID].to.size();++i)
if(V[ID].to[i]!=fa)
size=(size+DFS(V[ID].to[i],ID))%MOD;
res=(res+size*(n-size))%MOD;
return size;
}
ll Calc(void){
Build();
res=0;
DFS(1,0);
return res;
}
int Solve(void){
register int i;
register ll ans1,ans2;
ans1=Calc();
for(i=1;i<=n;++i)
swap(S[i].x,S[i].y);
ans2=Calc();
return (ans1+ans2)%MOD;
}
dalao 牛逼
nope
{{shengqi}}