SGU 210

210. Beloved Sonstime limit per test: 2 sec.
memory limit per test: 65536 KBinput: standard
output: standard

Once upon a time there lived a king and he had N sons. And the king wanted to marry his beloved sons on the girls that they did love. So one day the king asked his sons to come to his room and tell him whom do they love.

But the sons of the king were all young men so they could not tell exactly whom they did love. Instead of that they just told him the names of the girls that seemed beautiful to them, but since they were all different, their choices of beautiful girls also did not match exactly.

The king was wise. He did write down the information that the children have provided him with and called you, his main wizard.

"I want all my kids to be happy, you know," he told you, "but since it might be impossible, I want at least some of them to marry the girl they like. So please, prepare the marriage list."

Suddenly you recalled that not so long ago the king told you about each of his sons, so you knew how much he loves him. So you decided to please the king and make such a marriage list that the king would be most happy. You know that the happiness of the king will be proportional to the square root of the sum of the squares of his love to the sons that would marry the girls they like.

So, go on, make a list to maximize the king’s happiness.
Input
The first line of the input file contains N — the number of king’s sons (1 ≤ N ≤ 400). The second line contains N integer numbers Ai ranging from 1 to 1000 — the measures of king’s love to each of his sons.

Next N lines contain lists of king’s sons’ preferences — first Ki — the number of the girls the i-th son of the king likes, and then Ki integer numbers — the girls he likes (all potentially beautiful girls in the kingdom were numbered from 1 to N, you know, beautiful girls were rare in those days).
Output
Output N numbers — for each son output the number of the beautiful girl he must marry or 0 if he must not marry the girl he likes.

Denote the set of sons that marry a girl they like by L, then you must maximize the value of

Sample test(s)
Input 4
1 3 2 4
4 1 2 3 4
2 1 4
2 1 4
2 1 4
Output

2 1 0 4
看上去好像是一个最优匹配的问题,可以很显然将所有孩子排个序,然后一个个匹配过去就可以了囧。。
MS那个八中的OJ不能上了囧。。只好A SGU了囧。。
Code:

#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstdlib>#include<cstring>#include<string>#include<vector>#include<set>#include<queue>#include<map>#define rep(i,n) for(int i=0;i<n;i++)#define For(i,a,b) for(int i=a;i<=b;i++)#define tr(i,x) for(typeof(x.begin()) i=x.begin();i!=x.end();i++)#define all(x) x.begin(),x.end()#define pb push_backusing namespace std;const int inf=~0U>>1,maxn=400;typedef vector<int> vi;typedef vector<vi> vvi;typedef pair<int,int> ii;vi E[maxn];int Link[maxn],n;bool Vis[maxn]={0};bool dfs(int x){ if(Vis[x]) return false; Vis[x]=true; tr(i,E[x])if(Link[*i]==-1||dfs(Link[*i])) return Link[*i]=x,true; return false;}int A[maxn];bool cmp(const int&a,const int&b){ return A[a]>A[b];}int main(){ //freopen("in","r",stdin); int P[maxn]; cin>>n; rep(i,n)cin>>A[i],P[i]=i; rep(i,n) { int t,x;cin>>t; while(t–)cin>>x,E[i].pb(x-1); } rep(i,n) Link[i]=-1; sort(P,P+n,cmp); rep(i,n) { memset(Vis,0,sizeof(Vis)); dfs(P[i]); } int Ans[maxn]={0}; rep(i,n) Ans[Link[i]]=i+1; rep(i,n) cout<<Ans[i]<<" "; cout<<endl;}

[SCOI2009]游戏

[SCOI2009]游戏

Time Limit:1000MS Memory Limit:165536K
Total Submit:15 Accepted:11

Description

windy学会了一种游戏。
对于1到N这N个数字,都有唯一且不同的1到N的数字与之对应。
最开始windy把数字按顺序1,2,3,……,N写一排在纸上。
然后再在这一排下面写上它们对应的数字。
然后又在新的一排下面写上它们对应的数字。
如此反复,直到序列再次变为1,2,3,……,N。

如:
1 2 3 4 5 6
对应的关系为
1->2 2->3 3->1 4->5 5->4 6->6
windy的操作如下

1 2 3 4 5 6
2 3 1 5 4 6
3 1 2 4 5 6
1 2 3 5 4 6
2 3 1 4 5 6
3 1 2 5 4 6
1 2 3 4 5 6

这时,我们就有若干排1到N的排列,上例中有7排。
现在windy想知道,对于所有可能的对应关系,有多少种可能的排数。

Input

包含一个整数,N。

Output

包含一个整数,可能的排数。

Sample Input

Sample Output

Source

Day1
这道题目很明显就是给你一个N,然后求在和的N的数列中,最小公倍数有几种可能的情况。
很明显如果一个数A=p1^a1*p2^a2*….的话,他能被表达出来的充分必要条件是:
p1^a1+p2^a2+…..<=N这是很好证明的,就不说了。那么很显然就变成一个DP的问题了。
设F(i,j)为第i个素数开始和小于j有多少情况,具体看代码把(*^__^*) 。。这可以说是一道数学问题了。。看来数学学多了也是有好处的囧。。
Code:

#include<iostream>using namespace std;const int maxn=1000+100;bool IsPrime(int p){ if(p==2) return true; if(p%2==0) return false; for(int x=3;x*x<=p;x+=2) if(p%x==0) return false; return true;}int Ps[maxn],cnt=0,n;void GetPrime() //直接写暴力了,懒得写筛法了。。{ for(int x=2;x<=n;x++) if(IsPrime(x)) Ps[cnt++]=x;}typedef long long ll;ll F[maxn][maxn];bool s[maxn][maxn]={0};ll dfs(int pos,int N) //记忆化搜索 pos-cnt的素数,和小于N有多少种情况{ if(pos==cnt&&N>=0) return 1; //边界情况 ll&ans=F[pos][N]; //用引用比较方便 if(s[pos][N]) return ans; ans=0;s[pos][N]=true; for(int x=Ps[pos];x<=N;x*=Ps[pos]) //枚举第pos个素数的幂数 { ans+=dfs(pos+1,N-x); } ans+=dfs(pos+1,N); //如果不选这个素数的话 return ans;}int main(){ cin>>n;GetPrime(); cout<<dfs(0,n)<<endl;}【输出样例一】3【输出样例二】16【数据规模和约定】30%的数据,满足 1 <= N <= 10 。100%的数据,满足 1 <= N <= 1000 。【输入样例一】3【输入样例二】10

[ZJOI2007]最大半连通子图

[ZJOI2007]最大半连通子图

Time Limit:30000MS  Memory Limit:165536K
Total Submit:45 Accepted:14
Case Time Limit:3000MS

Description

Input

第一行包含两个整数N,M,X。N,M分别表示图G的点数与边数,X的意义如上文所述。接下来M行,每行两个正整数a, b,表示一条有向边(a, b)。图中的每个点将编号为1,2,3…N,保证输入中同一个(a,b)不会出现两次。

Output

应包含两行,第一行包含一个整数K。第二行包含整数C Mod X.

Sample Input

6 6 20070603
1 2
2 1
1 3
2 4
5 6
6 4

Sample Output

3
3

Hint

对于20%的数据, N ≤18;
对于60%的数据, N ≤10000;
对于100%的数据, N ≤100000, M ≤1000000;
对于100%的数据, X ≤10^8。

Source

爆栈你二大爷啊!!
我晕。搞了半天WA意思就是爆栈啊。。这下没办法了。我弄了数据发现有一个点无论怎么搞都爆栈,C++又不像Pascal能调栈的,难不成自己写一个模拟版dfs囧囧,就这样吧。不去A这题了。。
这道题很明显要强联通缩点,我用的是Tarjan,然后很明显就变成了TAG上的最长路问题,可以DP解决。。
Code(爆栈一个点。我也没办法囧):
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#include<set>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=100000;
int n,m,mod;
vector<int> E[maxn];
typedef vector<int>::iterator it;
int ord[maxn]={0},low[maxn],stack[maxn],top=0,cnt=0,id[maxn],snt=0;
bool inStack[maxn]={0};
void dfs(int x)
{
ord[x]=low[x]=++cnt;
stack[top++]=x;inStack[x]=true;
for(it i=E[x].begin();i!=E[x].end();++i)
if(!ord[*i])
dfs(*i),low[x]=min(low[x],low[*i]);
else if(inStack[*i])
low[x]=min(low[x],ord[*i]);
if(low[x]==ord[x])
{
int u;do{u=stack[–top];id[u]=snt;inStack[u]=false;}while(u!=x);
snt++;
}
}
struct State
{
int Ans,Num;
State():Ans(0),Num(1){}
void Renew(const State&o)
{
if(o.Ans<Ans)return;
if(o.Ans>Ans){*this=o;return;}
Num+=o.Num;Num%=mod;
}
};
State Dp[maxn];
set<int> Edge[maxn];
typedef set<int>::iterator sit;
int In[maxn]={0},Num[maxn]={0};
int main()
{
//freopen("in","r",stdin);
scanf("%d %d %d",&n,&m,&mod);int s,t;
while(m–)scanf("%d %d",&s,&t),E[s-1].pb(t-1);
rep(i,n)if(!ord[i])dfs(i);
rep(i,n)
{
int own=id[i];Num[own]++;
for(it e=E[i].begin();e!=E[i].end();++e)
if(id[*e]!=own)
Edge[own].insert(id[*e]);
}
rep(i,snt) for(sit e=Edge[i].begin();e!=Edge[i].end();++e) In[*e]++;
queue<int> Q;vector<int> S;
rep(i,snt) if(!In[i]) Q.push(i);
while(Q.size())
{
int t=Q.front();Q.pop();
S.push_back(t);
for(sit i=Edge[t].begin();i!=Edge[t].end();++i)
if(!–In[*i]) Q.push(*i);
}
for(vector<int>::reverse_iterator i=S.rbegin();i!=S.rend();++i)
{
for(sit e=Edge[*i].begin();e!=Edge[*i].end();++e)
Dp[*i].Renew(Dp[*e]);
Dp[*i].Ans+=Num[*i];
}
State Ans;
rep(i,snt) Ans.Renew(Dp[i]);
cout<<Ans.Ans<<endl;
cout<<Ans.Num<<endl;
}

[ZJOI2007]棋盘制作

[ZJOI2007]棋盘制作

Time Limit:20000MS  Memory Limit:165536K
Total Submit:33 Accepted:23
Case Time Limit:10000MS

Description

国际象棋是世界上最古老的博弈游戏之一,和中国的围棋、象棋以及日本的将棋同享盛名。据说国际象棋起源于易经的思想,棋盘是一个8*8大小的黑白相间的方 阵,对应八八六十四卦,黑白对应阴阳。而我们的主人公小Q,正是国际象棋的狂热爱好者。作为一个顶尖高手,他已不满足于普通的棋盘与规则,于是他跟他的好 朋友小W决定将棋盘扩大以适应他们的新规则。
小Q找到了一张由N*M个正方形的格子组成的矩形纸片,每个格子被涂有黑白两种颜色之一。小Q想在这种纸中裁减一部分作为新棋盘,当然,他希望这 个棋盘尽可能的大。不过小Q还没有决定是找一个正方形的棋盘还是一个矩形的棋盘(当然,不管哪种,棋盘必须都黑白相间,即相邻的格子不同色),所以他希望 可以找到最大的正方形棋盘面积和最大的矩形棋盘面积,从而决定哪个更好一些。
于是小Q找到了即将参加全国信息学竞赛的你,你能帮助他么?

Input

第一行包含两个整数N和M,分别表示矩形纸片的长和宽。接下来的N行包含一个N * M的01矩阵,表示这张矩形纸片的颜色(0表示白色,1表示黑色)。

Output

包含两行,每行包含一个整数。第一行为可以找到的最大正方形棋盘的面积,第二行为可以找到的最大矩形棋盘的面积(注意正方形和矩形是可以相交或者包含 的)。

Sample Input

3 3
1 0 1
0 1 0
1 0 0

Sample Output

4
6

Hint

对于20%的数据,N, M ≤ 80
对于40%的数据,N, M ≤ 400
对于100%的数据,N, M ≤ 2000

Source

61.187.179.132:8080/JudgeOnline/showproblem
原来的算法是没有问题,但是写的太沙茶了。首先那玩意根本不是那么递推的,要用到类似单调队列的结构,一层层扫描过去,对每层维护交替的能向上延伸多少,然后用单调队列算出对于每个点来说,往左第一个高度小于它的和往右第一个小于它的同时注意交替性,然后更新答案就可以了。。
细节很要紧,WA了N次囧。。速度鬼慢但长度不到1K,(*^__^*)
更WS的是我原来那个错误的算法居然能过SPOJ上的数据天哪。。我被雷到了。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n,m,MaxS=0,MaxR=0;
const int maxn=2000+10;
int Line[maxn]={0};
int H[maxn]={0};
void ReadLine()
{
int x;
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
if(x!=Line[i])H[i]++;
else H[i]=1;
Line[i]=x;
}
}
void Renew(int a,int b)
{
if(a>b) swap(a,b);
MaxS=max(MaxS,a*a);
MaxR=max(MaxR,a*b);
}
void CalLine()
{
static int L[maxn],R[maxn];
for(int i=1;i<=m;++i)
{
L[i]=i-1;
while(L[i]&&H[L[i]]>=H[i]&&Line[L[i]+1]!=Line[L[i]])
L[i]=L[L[i]];
}
for(int i=m;i>=1;–i)
{
R[i]=i+1;
while(R[i]<=m&&H[R[i]]>=H[i]&&Line[R[i]]!=Line[R[i]-1])
R[i]=R[R[i]];
}
for(int i=1;i<=m;i++) Renew(H[i],R[i]-L[i]-1);
}
int main()
{
scanf("%d %d",&n,&m);
rep(i,n)ReadLine(),CalLine();
cout<<MaxS<<endl<<MaxR<<endl;
}

小猴打架

小猴打架

Time Limit:5000MS  Memory Limit:165536K
Total Submit:30 Accepted:22
Case Time Limit:1000MS

Description

一开始森林里面有N只互不相识的小猴子,它们经常打架,但打架的双方都必须不是好朋友。每次打完架后,打架的双方以及它们的好朋友就会互相认识, 成为好朋友。经过N-1次打架之后,整个森林的小猴都会成为好朋友。
现在的问题是,总共有多少种不同的打架过程。
比如当N=3时,就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同 的打架过程。

Input

一个整数N。

Output

一行,方案数mod 9999991。

Sample Input

4

Sample Output

96

Hint

50%的数据N<=10^3。
100%的数据N<=10^6。

Source

61.187.179.132:8080/JudgeOnline/showproblem
额。首先他们打架的关系是一颗无根树,就有n^(n-2)种情况,还有打架的顺序,是(n-1)!种,乘起来就可以了囧。。
Code:
#include<iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int inf=~0U>>1,mod=9999991;
int main()
{
int n;long long ans=1;cin>>n;
rep(i,n-2)ans*=n,ans%=mod;
rep(i,n-1)ans*=i+1,ans%=mod;
cout<<ans<<endl;
}

[SCOI2009]生日礼物

[SCOI2009]生日礼物

Time Limit:10000MS  Memory Limit:165536K
Total Submit:42 Accepted:22
Case Time Limit:1000MS

Description

小西有一条很长的彩带,彩带上挂着各式各样的彩珠。已知彩珠有N个,分为K种。简单的说,可以将彩带考虑为x轴,每一个彩珠有一个对应的坐标(即 位置)。某些坐标上可以没有彩珠,但多个彩珠也可以出现在同一个位置上。
小布生日快到了,于是小西打算剪一段彩带送给小布。为了让礼物彩带足够漂亮,小西希望这一段彩带中能包含所有种类的彩珠。同时,为了方便,小西希 望这段彩带尽可能短,你能帮助小西计算这个最短的长度么?彩带的长度即为彩带开始位置到结束位置的位置差。

Input

第一行包含两个整数N, K,分别表示彩珠的总数以及种类数。接下来K行,每行第一个数为Ti,表示第i种彩珠的数目。接下来按升序给出Ti个非负整数,为这Ti个彩珠分别出现的 位置。

Output

应包含一行,为最短彩带长度。

Sample Input

6 3
1 5
2 1 7
3 1 3 8

Sample Output

3

Hint

有多种方案可选,其中比较短的是1~5和5~8。后者长度为3最短。
【数据规模】
对于50%的数据, N≤10000;
对于80%的数据, N≤800000;
对于100%的数据,1≤N≤1000000,1≤K≤60,0≤彩珠位置<2^31。

Source

61.187.179.132:8080/JudgeOnline/showproblem
额。。算法是很好想的,就是从小到大枚举每个位置,然后找出每种颜色在它后面的第一个然后取其中最大的那个更新答案。。我早上就想出来了囧。。
一开始我想的算法是NK的。。超的很厉害囧。。
后来我想用一个set来保存所有颜色大于当前位置的最小位置,然后运用set的找最大值和最小值操作,就很方便了。每次看set中的最小值是不是小于当前位置,是的话后移这个值。就是NLogK了。。可惜极限数据要1.6S。还是超时。。
我又优化了一下还是超时,没办法只好先放着了。。
现在突然发现由于最大值肯定是递增的,所以插入的时候更新一下就OK了。真正只需要知道最小值,那么用一个heap就可以了。。为了方便编程我用了priority_queue
Code:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<set>
#include<queue>
#include<map>
#include<ctime>
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=1000000,maxk=60;
typedef vector<int> vi;
typedef vi::iterator it;
vi A,S[maxk];
int n,k;
void Init()
{
cin>>n>>k;A.resize(n);it nowA=A.begin();
rep(i,k)
{
int t,x;scanf("%d",&t);S[i].resize(t+1);it nowS=S[i].begin();
rep(j,t)scanf("%d",&x),(*nowA++)=(*nowS++)=x;
*nowS++=inf;
}
}
struct cmp
{
bool operator()(const it&a,const it&b)const
{return *a>*b;}
};
void Work()
{
int s=clock();
sort(all(A));
int ans=inf,Max=0;
priority_queue<it,vector<it>,cmp> Q;
rep(i,k)Q.push(S[i].begin()),Max=max(Max,*S[i].begin());
rep(i,n)
{
int t=A[i];
while(*Q.top()<t)
{
it j=Q.top();Q.pop();
Max=max(Max,*++j);
if(Max==inf)break;
Q.push(j);
}
if(Max==inf)break;
ans=min(ans,Max-t);
}
cout<<ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
int s=clock();
Init();
Work();
}

[HNOI2005]狡猾的商人

[HNOI2005]狡猾的商人

Time Limit:10000MS  Memory Limit:165536K
Total Submit:44 Accepted:26
Case Time Limit:1000MS

Description

刁姹接到一个任务,为税务部门调查一位商人的账本,看看账本是不是伪造的。账本上记录了n个月以来的收入情况,其中第i 个月的收入额为Ai(i=1,2,3…n-1,n), 。当 Ai大于0时表示这个月盈利Ai 元,当 Ai小于0时表示这个月亏损Ai 元。所谓一段时间内的总收入,就是这段时间内每个月的收入额的总和。
刁姹的任务是秘密进行的,为了调查商人的账本,她只好跑到商人那里打工。她趁商人不在时去偷看账本,可是她无法将账本偷出来,每次偷看账本时她都 只能看某段时间内账本上记录的收入情况,并且她只能记住这段时间内的总收入。
现在,刁姹总共偷看了m次账本,当然也就记住了m段时间内的总收入,你的任务是根据记住的这些信息来判断账本是不是假的。

Input

第一行为一个正整数w,其中w < 100,表示有w组数据,即w个账本,需要你判断。每组数据的第一行为两个正整数n和m,其中n < 100,m < 1000,分别表示对应的账本记录了多少个月的收入情况以及偷看了多少次账本。接下来的m行表示刁姹偷看m次账本后记住的m条信息,每条信息占一行,有三 个整数s,t和v,表示从第s个月到第t个月(包含第t个月)的总收入为v,这里假设s总是小于等于t。

Output

包含w行,每行是true或false,其中第i行为true当且仅当第i组数据,即第i个账本不是假的;第i行为false当且仅当第i组数据,即第i 个账本是假的。

Sample Input

2
3 3
1 2 10
1 3 -5
3 3 -15
5 3
1 5 100
3 5 50
1 2 51

Sample Output

true
false

Source

这道题的话dfs和并查集都可以,dfs是首先dfs一下把所有的值推出来,在遇到反向边的时候再判断一下就可以了。不过这样还要构图,还是直接并查集爽,
并查集关键就是信息,为此考虑部分和序列,告诉你s到t的和实际上就是Sum(t)-Sum(s-1)=v。那么这两个的信息就关联起来了,那么并在一起并保存相对信息就可以了。。
Code:
#include<cstdio>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
const int maxn=100;
int n,m,F[maxn],G[maxn];
int Find(int x)
{
if(x==F[x])return x;
Find(F[x]);G[x]+=G[F[x]];return F[x]=F[F[x]];
}
void solve()
{
int s,t,v;
scanf("%d %d",&n,&m);
rep(i,n+1)F[i]=i,G[i]=0;
bool Right=1;
while(m–)
{
scanf("%d %d %d",&s,&t,&v);–s;
int i=Find(s),j=Find(t),a=G[s],b=G[t];
if(i!=j)
{
F[i]=j;
G[i]=b-a-v;
}
else if(b-a!=v)Right=false;
}
Right?puts("true"):puts("false");
}
int main()
{
int t;scanf("%d",&t);while(t–)solve();
}

[HNOI2007]紧急疏散evacuate

[HNOI2007]紧急疏散evacuate

Time Limit:10000MS  Memory Limit:165536K
Total Submit:57 Accepted:19
Case Time Limit:1000MS

Description

发生了火警,所有人员需要紧急疏散!假设每个房间是一个N M的矩形区域。每个格子如果是’.’,那么表示这是一块空地;如果是’X’,那么表示这是一面墙,如果是’D’,那么表示这是一扇门,人们可以从这儿撤出 房间。已知门一定在房间的边界上,并且边界上不会有空地。最初,每块空地上都有一个人,在疏散的时候,每一秒钟每个人都可以向上下左右四个方向移动一格, 当然他也可以站着不动。疏散开始后,每块空地上就没有人数限制了(也就是说每块空地可以同时站无数个人)。但是,由于门很窄,每一秒钟只能有一个人移动到 门的位置,一旦移动到门的位置,就表示他已经安全撤离了。现在的问题是:如果希望所有的人安全撤离,最短需要多少时间?或者告知根本不可能。

Input

输入文件第一行是由空格隔开的一对正整数N与M,3<=N <=20,3<=M<=20,以下N行M列描述一个N M的矩阵。其中的元素可为字符’.’、’X’和’D’,且字符间无空格。

Output

只有一个整数K,表示让所有人安全撤离的最短时间,如果不可能撤离,那么输出’impossible’(不包括引号)。

Sample Input

5 5
XXXXX
X…D
XX.XX
X..XX
XXDXX

Sample Output

3

Source

61.187.179.132:8080/JudgeOnline/showproblem
写了半天的代码,累死了。不过SAP还真是快啊。。
首先我的第一感觉是最优性改判定性,那么如何判断能否在限定时间T内将所有人转移走呢?很显然先特判一下无解的情况,首先从每个门BFS出它到每个节点的最短路,那么它最多能配上T个点且这T个点到他的最短路长度要小于T。那么就可以转化成网络流问题,从源向每个门连一条容量为T的边,从每个空地向汇连一条容量为1的边,然后不断增加T就可以了。。
就这么A掉了。可为什么这样是可以的?我感觉如果配上的T个点离的比较远的话在门上会卡住的囧,也就不可能完全利用T的时间了甚至好像可以找出反例(我没找出来)。。
也许是因为一个距离为d的点之前必然有一个距离为d-1的点之类的性质?迷茫了。。
Code(超过最大长度发不上来囧。。):
放在ideone上吧:
www.ideone.com/OdFo4hbA#

[Baltic2001]Mars Maps

[Baltic2001]Mars Maps

Time Limit:5000MS  Memory Limit:65536K
Total Submit:19 Accepted:7
Case Time Limit:1000MS

Description

给出N个矩形,N<=10000.其坐标不超过10^9.求其面积并

Input

先给出一个数字N,代表有N个矩形.
接下来N行,每行四个数,代表矩形的坐标.

Output

输出面积并

Sample Input

2
10 10 20 20
15 15 25 30

Sample Output

225

Source

这是很经典的题目了。离散化之后用扫描线扫过去,用线段树维护当前与扫描线相交的矩形的长度并。就可以降维了。。
不过我悲剧了。数组开小了囧。。WA了好几次。。
Code:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=10000;
int n;
int Y[maxn*2];
struct Event
{
int x,l,r,d;
Event(){}
Event(int _x,int _l,int _r,int _d):x(_x),l(_l),r(_r),d(_d){}
bool operator<(const Event&o)const
{
return x<o.x;
}
}E[maxn*2];
void Init()
{
scanf("%d",&n);
int x[2],y[2],cnt=0;
rep(i,n)
{
rep(j,2)scanf("%d %d",x+j,y+j),Y[cnt++]=y[j];
E[2*i]=Event(x[0],y[0],y[1],1);
E[2*i+1]=Event(x[1],y[0],y[1],-1);
}
}
int Cover[8*maxn]={0},Sum[8*maxn]={0};
void change(int t,int l,int r,int a,int b,int d)
{
if(a>=r||b<=l) return;
if(a<=l&&b>=r)Cover[t]+=d;
else change(t*2,l,(l+r)/2,a,b,d),change(t*2+1,(l+r)/2,r,a,b,d);
if(Cover[t]>0)
Sum[t]=Y[r]-Y[l];
else
Sum[t]=(l+1==r)?0:(Sum[t*2]+Sum[t*2+1]);
}
void Work()
{
n<<=1;
sort(Y,Y+n);
rep(i,n)
{
E[i].l=lower_bound(Y,Y+n,E[i].l)-Y;
E[i].r=lower_bound(Y,Y+n,E[i].r)-Y;
}
sort(E,E+n);int last=E[0].x;long long Ans=0;
rep(i,n)
{
Event now=E[i];
if(now.x!=last)
{
Ans+=(long long)(Sum[1])*(now.x-last);
last=now.x;
}
change(1,0,n-1,now.l,now.r,now.d);
}
cout<<Ans<<endl;
}
int main()
{
//freopen("in","r",stdin);
Init();
Work();
}

Page 3 of 712345...Last »