亚洲欧美卡通另类91av ,国产精品igao视频网网址不卡日韩,久久久精品性

yzhw — Wed, 22 Feb 2012 07:58:00 GMT

题目大意�q�样�Q�给��Z��些节点，�l�出3�U�命令：(x��)
1、将a,b联�?br />2、查询a,b的联通状�?br />3、删除链接a的边。（如果之前a,c通过b联通，那么删除b的联通关�p�d��a,c仍然认�ؓ(f��)联通）(j��)
1�Q?两种操作乍一看MS是�ƈ查集�Q�但是第三种状况让�h很恼火，��其是想用�\径压�~�技巧的时候。那么，我们不妨转换下思�\�Q�删除a的联通关�p�d��以认为将a节点重标��P��把之前那个a节点认�ؓ(f��)是虚拟节点，�q�样联通性啥的都好保证了(ji��n)。详�l�请看代码：(x��)

Source Code

Problem: 3908		User: yzhw
Memory: 1096K		Time: 47MS
Language: G++		Result: Accepted

Source Code

# include 
# define N 100000
using namespace std;
int set[N],id[N];
int find(int pos)
{
	if(set[pos]==pos) return pos;
	else return set[pos]=find(set[pos]);
}
void uni(int a,int b)
{
	set[find(a)]=find(b);
}
int main()
{
	int num;
	while(scanf("%d",&num)!=EOF)
	{
		int c=num+1,n1=0,n2=0;
		for(int i=1;i<N;i++) set[i]=i;
		for(int i=1;i<=num;i++) id[i]=i;
		char jud[5];
		while(scanf("%s",jud)&&*jud!='e')
		{
			int a,b;
			switch(*jud)
			{
			case 'c':
				scanf("%d%d",&a,&b);
				uni(id[a],id[b]);
				break;
			case 'd':
				scanf("%d",&a);
				id[a]=c++;
				break;
			case 'q':
				scanf("%d%d",&a,&b);
				if(find(id[a])==find(id[b])) n1++;
				else n2++;
				break;
			};

		}
		printf("%d , %d\n",n1,n2);
	}
	return 0;
}

yzhw 2012-02-22 15:58 发表评论

pku3907 求多边�Ş面积

yzhw — Fri, 17 Feb 2012 17:34:00 GMT

解法��是用有向面�U�法�Q�叉�U�就可以。最后如果是负数的话取个相反数就O(ji��n)K�?ji��n)，代码也很��单，如下�?br />

1 Show Code - Run ID 1166912
2
3 Submit Time: 2012-02-18 01:33:04     Language: GNU C     Result: Accepted
4     Pid: 3124     Time: 0.00 sec.     Memory: 852 K.     Code Length: 0.6 K.
5 # include
6 # define cross(x1,y1,x2,y2) (x1)*(y2)-(x2)*(y1)
7 # define get_aera(x0,y0,x1,y1,x2,y2) (cross((x1)-(x0),(y1)-(y0),(x2)-(x0),(y2)-(y0)))
8 int main()
9 {
10     int n;
11     while(scanf("%d",&n)!=EOF&&n)
12     {
13        int i;
14
15            double x[3],y[3],aera=0;
16            scanf("%lf%lf",&x[2],&y[2]);
17            for(i=1;i18            {
19                scanf("%lf%lf",&x[i%2],&y[i%2]);
20                if(i>1) aera+=get_aera(x[2],y[2],x[(i+1)%2],y[(i+1)%2],x[i%2],y[i%2]);
21            }
22            aera*=0.5;
23            if(aera<0) aera=-aera;
24            printf("%.0f\n",aera+1e-8);
25
26     }
27     return 0;
28 }

yzhw 2012-02-18 01:34 发表评论

yzhw — Thu, 16 Feb 2012 18:38:00 GMT

最�q�看�?ji��n)�h工智能的��定性推理，�?-SAT有了(ji��n)更深的理解，感觉2-SAT构图�q�程��是构徏的一个推理图�Q�逻辑关系是a->b。根据这题实际来讲讲
��q��W�一�U�情冉|��举例�?br />A被选或者B被选或者两者都发生都是可以被接受的�?br />那么如果A没有被选，我们能推出B被选了(ji��n)。同样如果B没有被选，我们能推出A被选了(ji��n)�Q�其他我们不能推��Z�Q何结论�?br />所以构造关�p?br />!B->A
!A->B
反应到图上就是两条边�?br />�q�样构图完成后找出图里所有的��通分量，如果A�?A在同一个强�q�通分量里�Q�那么就冲突�?ji��n)。（我们能推理出A->!A�Q?br />代码�Q?span style="background-color: #eeeeee; font-size: 13px; color: #008080; "> 1 Source Code

2
3 Problem: 3905        User: yzhw
4 Memory: 16168K        Time: 2297MS
5 Language: GCC        Result: Accepted
6 Source Code
7 # include
8 # include
9 # include <string.h>
10 # define N 2000
11 # define M 1000000*2
12 # define min(a,b) ((a)<(b)?(a):(b))
13 # define abs(a) ((a)>0?(a):-(a))
14 int n,m;
15 int p,nxt[M],g[N],v[M];
16 int stack[N],sp,dfn,low[N];
17 void insert(int a,int b)
18 {
19     v[p]=b;
20     nxt[p]=g[a];
21     g[a]=p++;
22 }
23 int dfs(int pos)
24 {
25     int minnum=dfn++;
26     int p;
27     stack[sp++]=pos;
28     low[pos]=minnum;
29     for(p=g[pos];p!=-1;p=nxt[p])
30     {
31       if(low[v[p]]==-1)
32         if(!dfs(v[p])) return 0;
33       minnum=min(minnum,low[v[p]]);
34     }
35     if(minnum36     else
37     {
38         do
39         {
40             low[stack[sp-1]]=N;
41             if(abs(stack[sp-1]-pos)==n) return 0;
42             sp--;
43         }while(stack[sp]!=pos);
44     }
45     return 1;
46 }
47 int main()
48 {
49     while(scanf("%d%d",&n,&m)!=EOF)
50     {
51         int i,flag=1;
52         memset(g,-1,sizeof(g));
53         p=0;
54         for(i=0;i55         {
56             char str1[32],str2[32];
57             int num1,num2;
58             scanf("%s%s",str1,str2);
59             num1=atoi(str1+1)-1;
60             num2=atoi(str2+1)-1;
61             if(*str1=='+'&&*str2=='+')
62             {
63                 insert(num1+n,num2);
64                 insert(num2+n,num1);
65             }
66             else if(*str1=='-'&&*str2=='-')
67             {
68                 insert(num1,num2+n);
69                 insert(num2,num1+n);
70             }
71             else if(*str1=='+'&&*str2=='-')
72             {
73                 insert(num1+n,num2+n);
74                 insert(num2,num1);
75             }
76             else
77             {
78                 insert(num1,num2);
79                 insert(num2+n,num1+n);
80             }
81         }
82         memset(low,-1,sizeof(low));
83         dfn=sp=0;
84         for(i=0;i<2*n&&flag;i++)
85             if(low[i]==-1)
86                 if(!dfs(i)) flag=0;
87         printf("%d\n",flag);
88     }
89     return 0;
90 }

yzhw 2012-02-17 02:38 发表评论

yzhw — Thu, 16 Feb 2012 18:03:00 GMT

解法发现�|�上一个大牛写的很好，��p�{载过来吧。可怜的我，开始没惛_��法��q��?ji��n)，惛_��法后又��L��依赖STL�l�果o(N)写成o(logN)成功葬送�?br />

解法

题意�Q�给你n个数�Q�求GCD(gcd(a,b),gcd(c,d))=1的方案数�Q�注意a,b,c,d�q�不一定两两互质，有多�l�数�?/p>

本来�q�个题的题解有一大把�Q�但没有讲题解的只有贴代码的�?/p>

本来一直在做题�Q�没有什么时间发题解�Q�但�q�个题加�׃��(ji��n)我对�Ҏ(gu��)��原理的理解，所以讲一�?/p>

�q�个题的��法是个伪多��式

首先�Q�先��算法流�E�说一下，原理后面�?x��)�?/p>

Step 1�Q�用�{�法�{�出10000内的素数�?/p>

Step 2�Q�组合素敎ͼ�用bool数组记录由m(m<=5)个素数相乘所得数的m的奇�?/p>

例如�Q?82=2*7*13 ———> m=3 so�Q�bool[182]=false

2=2 ——>m=1 so�Q�bool[2]=false

91=7*13 ——>m=2 so�Q�bool[91]=true

注意12=2^2*3�{�这�U�是B=p1^k1*p2^k2+...�q�种有质因数指数不�ؓ(f��)一的合��C��要处理因��Z��?x��)用�?/p>

以上是预处理

Step 3�Q�读入当前数为a�Q�将a分解��因数形式�Q�注意每个质因数只被记录一��?/p>

例如�Q?2=2*2*3 �?12�?x��)被分��?f��)2*3�Q�多余的2被消��M��(ji��n)

Step 4�Q�将分出的素数进行组合，��组合出的a的约数的time+1

例如�Q?2=2^2*3——>12=2*3——>time[2]++,time[3]++,time[6]++

Step 5�Q�处理之后，ans赋��gؓ(f��)C(n,4)即n*(n-1)*(n-2)*(n-3)div 24

Step 6�Q�for i 2-->10000

if bool[i] then ans:=ans-C(time[i],4)

else ans:=and+C(time[i],4);

Step 7�Q�输出ans

原理�Q�首先考虑一个问题，1000以内6,7,8,9的倍数有多��个�Q�答案是

1000div6+1000div7+1000div8+1000div9

-1000div(6*7)-1000div(6*8)-1000div(6*9)-1000div(7*8)-1000div(7*9)-1000div(8*9)

+1000div(6*7*8)+1000div(6*8*9)+1000div(7*8*9)

-1000div(6*7*8*9)

�q�是�Ҏ(gu��)��原理的一个最��单的应用�Q�类比这道题�Q�Step3�?其实��每个数a的不重复�U�数记录�?ji��n)下来，有公��q��数的四个数的�Ҏ(gu��)��要从ans中减去，多减的要加上

昄��m为奇时要减，m为偶时要加，�q�和”1000以内6,7,8,9的倍数有多��个�Q?#8220;�q�个问题奇偶是反的，�׃��a最大�ؓ(f��)10000�Q�所以m最大可以有5 (2*3*5*7*11<10000,2*3*5*7*11*13>10000)

至于12=2*2*3�q�种�U�数不处理因为可以分�?*6�Q��?�?�?x��)算一�ơ，所以不��d��?/p>

代码�Q?br />

1 # include
2 # include
3 # include
4 # include
5 using namespace std;
6 int pa[2000],pp=0,sa[10],sp=0;
7 int refer[5][10001];
8 void make_prime()
9 {
10     bool used[10001];
11     memset(used,true,sizeof(used));
12     for(int i=2;i<=10000;i++)
13          if(used[i])
14          {
15              pa[pp++]=i;
16              for(int j=2*i;j<=10000;j+=i)
17                 used[j]=false;
18          }
19 }
20 void spilt(int n)
21 {
22     sp=0;
23     for(int i=0;i24         if(n%pa[i]==0)
25         {
26             sa[sp++]=pa[i];
27             while(n%pa[i]==0)
28                 n/=pa[i];
29         }
30 }
31 void putmap(int n)
32 {
33     spilt(n);
34     for(int i=1;i<(1<35     {
36         int n1=0,n2=1;
37         for(int j=0;j<5;j++)
38             if(i&(1<39                 n1++,n2*=sa[j];
40         refer[n1-1][n2]++;
41     }
42 }
43 long long c(int n)
44 {
45     return (long long)n*(n-1)*(n-2)*(n-3)/4/3/2;
46 }
47 long long getans(int n)
48 {
49     long long ans=c(n);
50     for(int i=0;i<5;i++)
51     {
52         bool flag=false;
53         for(int j=1;j<=10000;j++)
54             if(refer[i][j]>=4)
55                 flag=true,
56                 ans+=c(refer[i][j])*(i%2?1ll:-1ll);
57         if(!flag)break;
58     }
59     return ans;
60 }
61 int main()
62 {
63     int n;
64     make_prime();
65     while(scanf("%d",&n)!=EOF)
66     {
67         memset(refer,0,sizeof(refer));
68         for(int i=0;i69         {
70             int t;
71             scanf("%d",&t);
72             putmap(t);
73         }
74         printf("%lld\n",getans(n));
75     }
76     return 0;
77 }

yzhw 2012-02-17 02:03 发表评论

yzhw — Thu, 09 Feb 2012 11:33:00 GMT

好久不动题目�?ji��n)，今天动�?ji��n)一题，忒背�q�，死都TLE�Q�想�?ji��n)想�Q�算法复杂度没问题啊�Q�n=100000�Q�nlogn的算法拼1S的RP咋崩溃的。。后来想起了(ji��n)无敌的POJ��慢速set�Q�无奈，不想改，到处搜有�q�题的OJ�Q�TOJ上跑�?ji��n)下�Q?0MS。。汗。。下载数据数据来看了(ji��n)看，��是12�l�，��是本地debug也不�?x��)TLE啊。。没办法。�?br />不发牢骚(d��)�?ji��n)，说说�q�题的方法吧�?br />一般的最镉K��增字串用n^2做很好做�Q�就是dp[i]=max{dp[j]+1,height[j]首先�Q�我们知道，要维护这样一个单调队列，当height[i]那么更新�q�的DP方程��是
dp[i]=dp[j]+1,j为满��height[j]然后更新单调队列的策略是把当前决�{�加入单调队列里�Q�然后往后删除dp[i]>=dp[j]�q�且height[i]每个元素最多入队一�ơ，出队一�ơ，所以��d��复杂度o(nlogn)
我是全部用set实现的，��L��好省

1 # include
2 # include <set>
3 using namespace std;
4 struct node
5 {
6    int height,id;
7    node(int h,int i):height(h),id(i){}
8    bool operator<(const node &pos) const
9    {
10        if(height!=pos.height) return height11        else return id12    }
13 };
14 set q;
15 int dp[100005];
16 int main()
17 {
18      int n;
19      while(scanf("%d",&n)!=EOF)
20      {
21         q.clear();
22         for(int i=0;i23         {
24             int t;
25             scanf("%d",&t);
26             set::iterator it=q.lower_bound(node(t,-1));
27             int ans;
28             if(it==q.begin())
29               ans=1;
30             else
31               ans=dp[(--it)->id]+1;
32             it=q.lower_bound(node(t,-1));
33             if(it!=q.end()&&it->height==t)
34                  it=q.erase(it);
35             while(it!=q.end()&&dp[it->id]<=ans)
36                  it=q.erase(it);
37             q.insert(node(t,i));
38             dp[i]=ans;
39         }
40         printf("%d\n",dp[q.rbegin()->id]);
41      }
42      return 0;
43 }
44

yzhw 2012-02-09 19:33 发表评论

pku 3943 Digits on the Floor �q�查集的�zȝ��Q�重点）(j��)+数字识别

yzhw — Sat, 14 Jan 2012 11:57:00 GMT

题意很简单，�l�出一些线�D�，�l�成一些数字，保持数字�q�接点的联通关�p�M��变（��p��是图的逻辑�l�构不变吧）(j��)�Q��ƈ且保证没有相交。要求识别数字�?br />首先�q�题�Q�涉�?qi��ng)到�q�查集的�q�用。开始犯�?ji��n)个很糊涂的错误�Q�本题新加上一条线�D�可能造成2�U�情�?br />1、A - C�Q�新加线为C�Q�就是把C�q�接到某个树(w��i)枝上
2、A-C-B�Q�这�U�情况考虑漏了(ji��n)�Q�就是通过C�q�个�U�把俩个不连通的集合�l�打通了(ji��n)
具体代码应该是这�?br />for(int j=0;j if(find(now)!=find(j)&&cross(now,j))
set[find(now)]=find(j);
开始糊涂蛋的写成了(ji��n)
for(int j=0;j if(cross(now,j))
set[now]=find(j),break;
�q�个��是只考虑�?ji��n)第一�U�情��c(di��n)�?br />
关于数字识别的问题就好办多了(ji��n)�Q�主要根据部分相交和点相交的数目以及(qi��ng)联通集中线�D늚�数目来判断数字（5�?�q�要�Ҏ(gu��)��叉积再来弄下�Q�，�q�题受益最��q��是�q�查集那里，�Ҏ(gu��)��犯的错误�?br />
代码如下�Q?br />

1 Source Code
  2
  3 Problem: 3943        User: yzhw
  4 Memory: 656K        Time: 188MS
  5 Language: G++        Result: Accepted
  6 Source Code
  7 # include
  8 # include
  9 # include
10 # include
11 using namespace std;
12 # define N 1005
13 # define min(a,b) ((a)<(b)?(a):(b))
14 # define max(a,b) ((a)>(b)?(a):(b))
15 struct line
16 {
17     int x1,y1,x2,y2;
18 }l[N];
19 bool in(int x,int y,const line &pos)
20 {
21     if(x>=min(pos.x1,pos.x2)&&x<=max(pos.x1,pos.x2)&&
22        y>=min(pos.y1,pos.y2)&&y<=max(pos.y1,pos.y2)&&
23        (pos.y2-pos.y1)*(pos.x2-x)==(pos.x2-pos.x1)*(pos.y2-y))
24        return true;
25     else return false;
26 }
27 int cross(const line &a,const line &b)
28 {
29     if(a.x1==b.x1&&a.y1==b.y1||
30         a.x2==b.x1&&a.y2==b.y1||
31         a.x1==b.x2&&a.y1==b.y2||
32         a.x2==b.x2&&a.y2==b.y2) return 1;
33     else if(in(a.x1,a.y1,b)||in(a.x2,a.y2,b)||in(b.x1,b.y1,a)||in(b.x2,b.y2,a)) return 2;
34     else return 0;
35 }
36 int cross(int x1,int y1,int x2,int y2)
37 {
38     return x1*y2-x2*y1;
39 }
40 struct node
41 {
42     vector data;
43     int type() const
44     {
45         int num[3]={0,0,0};
46         for(int i=0;i 47             for(int j=i+1;j 48                 num[cross(data[i],data[j])]++;
49         if(num[1]==4&&num[2]==0)
50         {
51             if(data.size()==4) return 0;
52             else
53             {
54                 int target=-1,x1,y1,x2,y2;
55                 for(int i=0;i 56                 {
57                     bool flag=true;
58                     for(int j=0;j 59                         if(j!=i&&(data[i].x1==data[j].x1&&data[i].y1==data[j].y1||data[i].x1==data[j].x2&&data[i].y1==data[j].y2))
60                             flag=false;
61                     if(flag)
62                     {
63                         target=i;
64                         x1=data[i].x2,y1=data[i].y2;
65                         x2=data[i].x1,y2=data[i].y1;
66                         break;
67                     }
68                     flag=true;
69                     for(int j=0;j 70                         if(j!=i&&(data[i].x2==data[j].x1&&data[i].y2==data[j].y1||data[i].x2==data[j].x2&&data[i].y2==data[j].y2))
71                             flag=false;
72                     if(flag)
73                     {
74                         target=i;
75                         x1=data[i].x1,y1=data[i].y1;
76                         x2=data[i].x2,y2=data[i].y2;
77                         break;
78                     }
79                 }
80                 for(int i=0;i 81                     if(i!=target)
82                     {
83                         if(data[i].x1==x1&&data[i].y1==y1)
84                             return cross(data[i].x2-data[i].x1,data[i].y2-data[i].y1,x1-x2,y1-y2)<0?5:2;
85                         else if(data[i].x2==x1&&data[i].y2==y1)
86                             return cross(data[i].x1-data[i].x2,data[i].y1-data[i].y2,x1-x2,y1-y2)<0?5:2;
87                     }
88             }
89             printf("wa!\n");
90             while(true);
91         }
92         else if(num[1]==0&&num[2]==0)
93             return 1;
94         else if(num[1]==4&&num[2]==0)
95             return 2;
96         else if(num[1]==2&&num[2]==1)
97             return 3;
98         else if(num[1]==1&&num[2]==1)
99             return 4;
100         else if(num[1]==4&&num[2]==1)
101             return 6;
102         else if(num[1]==2&&num[2]==0)
103             return 7;
104         else if(num[1]==4&&num[2]==2)
105             return 8;
106         else if(num[1]==3&&num[2]==1)
107             return 9;
108     }
109 };
110 map<int,node> data;
111 int n,set[N],ans[10];
112 int find(int pos)
113 {
114     if(set[pos]==pos) return pos;
115     else return set[pos]=find(set[pos]);
116 }
117 int main()
118 {
119     while(scanf("%d",&n)!=EOF&&n)
120     {
121         data.clear();
122         memset(ans,0,sizeof(ans));
123         for(int i=0;i124         {
125             set[i]=i;
126             scanf("%d%d%d%d",&l[i].x1,&l[i].y1,&l[i].x2,&l[i].y2);
127             for(int j=0;j128                 if(cross(l[i],l[j])&&find(i)!=find(j))
129                     set[find(i)]=find(j);
130         }
131         for(int i=0;i132             data[find(i)].data.push_back(l[i]);
133         for(map<int,node>::iterator i=data.begin();i!=data.end();i++)
134             ans[i->second.type()]++;
135         printf("%d",ans[0]);
136         for(int i=1;i<10;i++)
137             printf(" %d",ans[i]);
138         printf("\n");
139     }
140     return 0;
141 }

yzhw 2012-01-14 19:57 发表评论

pku 3998 Land Division DP斜率优化

yzhw — Mon, 17 Oct 2011 18:17:00 GMT

摘要: 题意�Q�n个点�Q�用水��^�U�或者竖直线划分成k条，要求�q�_��差最��，�q�_��差�ؓ(f��)每条中点的个数减去n/k的绝对倹{��解法：(x��)首先一看就是个DP�Q�与处理不说�?ji��n)，用水�q�x��描线、竖直扫描线��同一直线上的点压�~�成一个带权值的点，然后DP�q�题重要的是DP降维观察DP方程dp[i]=min{dp[j]+|sum[i]-sum[j]-average|}�q�里��p��分成两部分讨�?、当sum[i]-sum[j]>average... 阅读全文

yzhw 2011-10-18 02:17 发表评论

HDU 3682 To Be an Dream Architect �Ҏ(gu��)��原理

yzhw — Sun, 02 Oct 2011 16:06:00 GMT

题意�Q?br />每次可以删除一个木条x=?,y=?或者x=?,z=?或者y=?,z=?�Q�求最后删除的木块��L��
�Q?img src="http://acm.hdu.edu.cn/data/images/3682-1.gif" alt="" />
开始写的时候出��C��BUG�Q�无奈，上网��N��解，更无奈，都是些几句话hash然后��是一堆难懂的代码。�?br />后来仔细想了(ji��n)惻I��把重复的操作去除后（��是两次删除的同一个木条）(j��)�Q�下面就是个很简单的�Ҏ(gu��)��原理�?br />因�ؓ(f��)去除�?ji��n)重复操作，一个木块最多被删除3�ơ，然后删除的个数就��删除臛_��一�ơ的个数-删除臛_��两次的个�?删除臛_��3�ơ的个数。不能强行枚举，可以用map或者传说中的hash记录被删除掉木块的次数。这里，�׃��操作最多m=1000�Q�删除木块数最多�ؓ(f��)C(m,2)�Q�然后两两枚举操作，把相交木块删除次�?1�Q�然后最后map中所有木块删除次数只能有2个��|��(x��)1�?�Q�当��gؓ(f��)1�Ӟ��total-1,��gؓ(f��)3�Ӟ��total-2
��Z��么？因�ؓ(f��)我说�?ji��n)，一个木块最多被删除3�ơ，然后俩俩枚�D的时候，你懂的�?br />

1 # include <cstdio>
2 # include <utility>
3 # include <cstring>
4 # include <algorithm>
5 # include <functional>
6 # include <set>
7 # include <cstdlib>
8 # include <map>
9 using namespace std;
10 struct node
11 {
12     int p[3];
13     bool operator<(const node &pos) const
14     {
15         for(int i=0;i<3;i++)
16             if(p[i]!=pos.p[i])
17                 return p[i]<pos.p[i];
18         return false;
19     }
20 };
21 pair<int,int> data[1000][2];
22 set<pair<pair<int,int>,pair<int,int> > > r1;
23 map<node,int> r2;
24 int main()
25 {
26     int test;
27     scanf("%d",&test);
28     while(test--)
29     {
30        int n,m,p=0;
31        char str[128];
32        scanf("%d%d",&n,&m);
33        r1.clear();r2.clear();
34        while(m--)
35        {
36            scanf("%s",str);
37            char *t=strtok(str,",");
38            data[p][0].first=(*t)-'X';
39            data[p][0].second=atoi(t+2);
40            t=strtok(NULL," ");
41            data[p][1].first=(*t)-'X';
42            data[p][1].second=atoi(t+2);
43            if(data[p][0].first>data[p][1].first) swap(data[p][0],data[p][1]);
44            pair< pair<int,int>,pair<int,int> > tt;
45            tt.first=data[p][0];
46            tt.second=data[p][1];
47            if(data[p][0].second>=1&&data[p][0].second<=n&&data[p][1].second>=1&&data[p][1].second<=n&&r1.find(tt)==r1.end()) p++,r1.insert(tt);
48        }
49        m=p;
50        for(int i=0;i<m;i++)
51         for(int j=i+1;j<m;j++)
52           if(data[i][0]==data[j][0]&&data[i][1].first!=data[j][1].first||
53              data[i][1]==data[j][0]&&data[i][0].first!=data[j][1].first||
54              data[i][0]==data[j][1]&&data[i][1].first!=data[j][0].first||
55              data[i][1]==data[j][1]&&data[i][0].first!=data[j][0].first)
56           {
57               node t;
58               t.p[data[i][0].first]=data[i][0].second;
59               t.p[data[i][1].first]=data[i][1].second;
60               t.p[data[j][0].first]=data[j][0].second;
61               t.p[data[j][1].first]=data[j][1].second;
62               r2[t]++;
63           }
64        int total=m*n;
65        for(map<node,int>::iterator i=r2.begin();i!=r2.end();i++)
66            if(i->second==1) total--;
67            else total-=2;
68        printf("%d\n",total);
69     }
70     //system("pause");
71     return 0;
72 }
73

yzhw 2011-10-03 00:06 发表评论

2010 天��|赛区G hdu 3726 splay

yzhw — Fri, 30 Sep 2011 00:51:00 GMT

摘要: 哎，一道裸splay的题目，�|�上竟然木有解题报告。我�W�一�ơ写splay�Q�犯�?ji��n)很多很多NC的错误。。调�?ji��n)有一个下午，最后写�?ji��n)个��试模�?生成�?ji��n)随机数据，才发现错误。说说我的失误吧。�?、首先zig zag实现的时候一定要配对�Q�不能�ؕ�Q�加个儿子节点就要把儿子节点的父亲节点同时初始化�?、新加入节点的size域及(qi��ng)其祖先的size域名不用调整�Q�会(x��)在splay�q�程中自动修正完�?、千万别要试囑ְ�一颗子�?w��i)的�?.. 阅读全文

yzhw 2011-09-30 08:51 发表评论

yzhw — Fri, 30 Sep 2011 00:44:00 GMT

很久不写划分�?w��i)�?ji��n)�Q�果然各�U�NC错误
按照我的理解�Q�划分树(w��i)即一个线�D�|��(w��i)�Q�用来确定数�l�下标和层次�Q�以�?qi��ng)一个log2(n)*n的数�l�，来记录划分信�?br />�q�题实现4个操作：(x��)
1、插�?br />按照划分�?w��i)的定义�Q�如果小于有序表中中间节点的��|��递归插入左子�?w��i)，否则递归插入叛_��?w��i)。更新当前区间段的划分信息（无非��是往后计��一个）(j��)
2、询问s,e区间�W�k��数
查询s,e区间里面划分到左子树(w��i)的个数i�Q�如果i>=k�Q�那么显焉��归到左子树(w��i)查询�Q�否则就是递归到右子树(w��i)查询k-i��的数。注意！�q�里要重新定位左子树(w��i)和右子树(w��i)中的区间�Q�由于是闭区��_(d��)��那么做端点�ؓ(f��)s+sum(s-1),右端点�ؓ(f��)s+sum(e)-1�Q�这个减一丢了(ji��n)。。调�?ji��n)我半天。。哎。。以前写都是左闭叛_��区间的，�l�果�?f��n)惯了(ji��n)。�?br />3、查询��gؓ(f��)k的数的位��?br />�q�个需要一个辅助数�l�，记录��gؓ(f��)k的数插在最��层区间的哪个位�|�了(ji��n)。这个办好后�Q�就�Ҏ(gu��)��?ji��n)，如果数被划分��C��(ji��n)左子�?w��i)，那么递归查询左子�?w��i)，否则�q�回递归查询叛_��?w��i)的值加上当前区间被划分到左子树(w��i)的个�?br />4、查询rank k的数
同样是这��P��如果当前区间被划分到左子�?w��i)的个数��于�{�于k�Q�那么递归查询左子�?w��i)，否则递归查询叛_��?w��i)中rank为k-左子�?w��i)的size�?br />大概思想��是�q�样�?ji��n)，实现有很多细节，比如说假设p==区间左端点（左区间木有数�Q�，那么��sum(p-1)的时候就要特判下�?ji��n)。我喜欢用三元式�Q�很方便�?br />
代码
# include
# include
# include
using namespace std;
# define N 100005
int arr[20][N];
struct node
{
   int s,e,layer;
   int c;
}st[4*N];
int q[500000][4],c;
int remap[N],position[N];
map<int,int> refer;
void init(int s,int e,int layer,int pos=1)
{
    st[pos].s=s;st[pos].e=e;
    st[pos].layer=layer;
    st[pos].c=st[pos].s;
    if(s!=e) init(s,(s+e)/2,layer+1,pos<<1),init((s+e)/2+1,e,layer+1,(pos<<1)+1);
}
void insert(int value,int pos=1)
{
     if(st[pos].s==st[pos].e)
        arr[st[pos].layer][st[pos].c++]=value;
     else
     {
         if(value<=(st[pos].s+st[pos].e)/2)
         {
             arr[st[pos].layer][st[pos].c]=(st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1])+1;
             st[pos].c++;
             insert(value,pos<<1);
         }
         else
         {
             arr[st[pos].layer][st[pos].c]=(st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1]);
             st[pos].c++;
             insert(value,(pos<<1)+1);
         }
     }
}
int q1(int s,int t,int k,int pos=1)
{
    if(st[pos].s==st[pos].e)
        return remap[arr[st[pos].layer][st[pos].s]];
    else
    {
        if(arr[st[pos].layer][t]-(s==st[pos].s?0:arr[st[pos].layer][s-1])>=k)//left
            return q1(st[pos].s+(s==st[pos].s?0:arr[st[pos].layer][s-1]),st[pos].s+arr[st[pos].layer][t]-1,k,pos<<1);
        else//right
        {
            k-=arr[st[pos].layer][t]-(s==st[pos].s?0:arr[st[pos].layer][s-1]);
            return q1((st[pos].s+st[pos].e)/2+1+s-1-st[pos].s+1-(s==st[pos].s?0:arr[st[pos].layer][s-1]),(st[pos].s+st[pos].e)/2+1+t-st[pos].s+1-arr[st[pos].layer][t]-1,k,(pos<<1)+1);
        }
    }
}
int q2(int s,int pos=1)
{
    if(st[pos].s==st[pos].e) return 1;
    else if(arr[st[pos].layer][s]-(s==st[pos].s?0:arr[st[pos].layer][s-1]))
      return q2(st[pos].s+arr[st[pos].layer][s]-1,pos<<1);
    else
      return (st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1])+q2((st[pos].s+st[pos].e)/2+1+s-st[pos].s+1-arr[st[pos].layer][s]-1,(pos<<1)+1);
}
int q3(int k,int pos=1)
{
    if(st[pos].s==st[pos].e) return remap[arr[st[pos].layer][st[pos].s]];
    else if(k<=(st[pos].c==st[pos].s?0:arr[st[pos].layer][st[pos].c-1])) return q3(k,pos<<1);
    else return q3(k-(st[pos].s==st[pos].c?0:arr[st[pos].layer][st[pos].c-1]),(pos<<1)+1);
}
int main()
{
    int n,test=1;
    while(scanf("%d",&n)!=EOF)
    {
       refer.clear();c=1;
       memset(arr,0,sizeof(arr));
       for(int i=0;i<n;i++)
       {
           char tmp[12];
           scanf("%s",tmp);
           if(*tmp=='I')
             q[i][0]=0;
           else q[i][0]=tmp[6]-48;
           switch(q[i][0])
           {
           case 0:
                scanf("%d",&q[i][1]);
                refer[q[i][1]]=0;
                break;
           case 1:
                scanf("%d%d%d",&q[i][1],&q[i][2],&q[i][3]);
                break;
           default:
                scanf("%d",&q[i][1]);
                break;
           };
       }
       for(map<int,int>::iterator i=refer.begin();i!=refer.end();i++)
         remap[c]=i->first,i->second=c++;
       init(1,c-1,0);
       long long t[4]={0,0,0,0};
       int now=1;
       for(int i=0;i<n;i++)
         switch(q[i][0])
         {
           case 0:
                insert(refer[q[i][1]]);
                position[refer[q[i][1]]]=now++;
                break;
           case 1:
                t[1]+=q1(q[i][1],q[i][2],q[i][3]);
                break;
           case 2:
                t[2]+=q2(position[refer[q[i][1]]]);
                break;
           case 3:
                t[3]+=q3(q[i][1]);
                break;
         };
       printf("Case %d:\n%I64d\n%I64d\n%I64d\n",test++,t[1],t[2],t[3]);
    }
    return 0;
}