第四周 6.7-6.13

6.7

可怕的一周从BC开始。

hdu5265 pog loves szh II

只是想写一个二分。然被骇。

错误还不止一个。

1.没用LL

2.ans初值赋错

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <algorithm>
 4 typedef long long LL;
 5 using namespace std;
 6 LL a[100005];
 7 
 8 int main(void)
 9 {
10     int n;LL p;
11     while(cin>>n>>p)
12     {
13         for(int i=0;i<n;i++)
14         {
15             scanf("%d",a+i);
16             a[i]=a[i]%p;
17         }
18         sort(a,a+n);
19         LL ans=(a[n-2]+a[n-1])%p;
20         for(int i=0;i<n;i++)
21         {
22             if(a[i]>p/2) break;
23             int L=i+1,R=n-1,mid;
24             while(L<=R)
25             {
26                 mid=(L+R)/2;
27                 if(a[mid]+a[i]>=p) R=mid-1;
28                 else L=mid+1;
29             }
30             if(R>i&&a[i]+a[R]<p) ans=max(ans,a[i]+a[R]);
31         }
32         printf("%d
",ans);
33     }
34     return 0;
35 }

Aguin

第三题是一个最近公共祖先

后来反正写不出来了。就去学习了一下。

理解能力差。看了好几篇没懂。

后来看到一篇不怎么长的但是很直观。

Link：http://scturtle.is-programmer.com/posts/30055.html

6.8

POJ 1330 Nearest Common Ancestors LCA

本来是打BC碰到LCA想学习一下。然而发现那个题比较复杂。

就暂且放那不管了。

写了一个简单的。但是只有一个query。连做模板都不合适阿。

写的时候并查集没有带秩。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <vector>
 5 using namespace std;
 6 # define maxn 10000+5
 7 # define CLR(x) memset(x,0,sizeof(x))
 8 vector <int> vec[maxn];
 9 int pa[maxn],ind[maxn],begin,end;
10 bool vis[maxn];
11 
12 int fa(int x)
13 {
14     return pa[x]==x?x:pa[x]=fa(pa[x]);
15 }
16 
17 void LCA(int x)
18 {
19     for(int i=0;i<vec[x].size();i++)
20     {
21         LCA(vec[x][i]);
22         pa[fa(vec[x][i])]=x;
23     }
24     vis[x]=1;
25     if(x==begin&&vis[end]) printf("%d
",fa(end));
26     else if(x==end&&vis[begin]) printf("%d
",fa(begin));
27     return;
28 }
29 
30 int main(void)
31 {
32     int T;cin>>T;
33     while(T--)
34     {
35         int N;scanf("%d",&N);
36         CLR(vis); CLR(ind);
37         for(int i=1;i<=N;i++) {vec[i].clear(); pa[i]=i;}
38         for(int i=1;i<N;i++)
39         {
40             int from,to; scanf("%d%d",&from,&to);
41             vec[from].push_back(to);
42             ind[to]++;
43         }
44         scanf("%d%d",&begin,&end);
45         for(int i=1;i<=N;i++)
46             if(!ind[i]) { LCA(i); break; }
47     }
48     return 0;
49 }

Aguin

6.9

想尝试hdu5266但是不会处理多点的LCA。

自己测数据在devcpp下跑到25000层的时候爆栈。

加黑科技交C++自然是T的。

毕竟学的少有能力了在搞。

附个失败品。

 1 # pragma comment(linker, "/STACK:1024000000,1024000000")
 2 # include <iostream>
 3 # include <cstdio>
 4 # include <cstring>
 5 using namespace std;
 6 # define maxn 300000+10
 7 # define CLR(x) memset(x,0,sizeof(x))
 8 int Q,t,pa[maxn],Ql[maxn],Qr[maxn],time[maxn],ans[maxn];
 9 int start[maxn],to[2*maxn],Next[2*maxn];
10 bool vis[maxn];
11 
12 int fa(int x)
13 {
14     return pa[x]==x?x:pa[x]=fa(pa[x]);
15 }
16 
17 void LCA(int x)
18 {
19     time[x]=++t;
20     int tem=start[x];
21     while(tem)
22     {
23         if(!time[to[tem]])
24         {
25             LCA(to[tem]);
26             pa[to[tem]]=x;
27         }
28         tem=Next[tem];
29     }
30     vis[x]=1;
31     for(int i=0;i<Q;i++)
32         if(x>=Ql[i]&&x<=Qr[i])
33         {
34             int ok=1,min=maxn,pos;
35             for(int j=Ql[i];j<=Qr[i];j++)
36                 if(time[j]){ if(min>time[j]) {min=time[j];pos=j;} }
37                 else{ok=0;break;}
38             if(ok) ans[i]=fa(pos);
39         }
40     return;
41 }
42 
43 int main(void)
44 {
45 //    freopen("data.in","r",stdin);
46     int n;
47     while((scanf("%d",&n))!=EOF)
48     {
49         CLR(vis); CLR(time); CLR(start);
50         for(int i=1;i<=n;i++) pa[i]=i;
51         for(int i=1;i<2*n-1;i+=2)
52         {
53             int FROM,TO; scanf("%d%d",&FROM,&TO);
54             to[i]=TO; Next[i]=start[FROM]; start[FROM]=i;
55             to[i+1]=FROM; Next[i+1]=start[TO]; start[TO]=i+1;
56         }
57         scanf("%d",&Q);
58         for(int i=0;i<Q;i++) scanf("%d%d",Ql+i,Qr+i);
59         t=0; LCA(1);
60         for(int i=0;i<Q;i++) printf("%d
",ans[i]);
61     }
62     return 0;
63 }

Aguin

6.10-6.13

什么都没干。