cf 782# A.Andryusha and Socks B.The Meeting Place Cannot Be Changed C.Andryusha and Colored Balloons

看来快掉到灰名的蒟蒻涨rating也快。。。

A题模拟一下就好（一开始还sb，，

 1 #include<bits/stdc++.h>
 2 #define LL long long
 3 using namespace std;
 4 bool vis[100005];
 5 int ans,tot,a[100005],n;
 6 int main()
 7 {
 8     scanf("%d",&n);
 9     for (int i=1; i<=2*n; i++)
10     {
11         int x; scanf("%d",&x);
12         if (!vis[x]) tot++,vis[x]=1; else tot--;
13         ans=max(ans,tot);
14     }
15     cout<<ans;
16 }

B的话，比较神。。读完题一看，这不是个三分嘛。。B题怎么可能出三分。。然而还是水了个三分交上，（各种怕卡精度卡精度，然而还是可以的）

 1 #include<bits/stdc++.h>
 2 #define LL long long
 3 #define eps 1e-8
 4 using namespace std;
 5 int n,x[60005],v[60005];
 6 double get_dis(double pos)
 7 {
 8     double t=0;
 9     for (int i=1; i<=n; i++)
10         t=max(t,fabs((double)pos-x[i])/(double)v[i]);
11     return t;
12 }
13 int main()
14 {
15     scanf("%d",&n);
16     for (int i=1; i<=n; i++) scanf("%d",&x[i]);
17     for (int i=1; i<=n; i++) scanf("%d",&v[i]);
18     double l=0,r=1e9; int tot=0;
19     double mid1,mid2;
20     while (r-l>eps)
21     {
22         mid1=(r-l)/3+l,mid2=(r-l)/3*2+l;
23         if (get_dis(mid1)-get_dis(mid2)>eps) l=mid1;
24             else r=mid2;
25         if (++tot>5000) break;
26     }
27     printf("%.10lf",get_dis(mid1));
28     return 0;
29 }

C题的话，，比较难写（其实是我太弱了），比较好想，最多就是儿子最多节点，儿子加上自己。（自己画个图就看出来了），

知道了这个就可以构造了。。

 1 #include<bits/stdc++.h>
 2 #define LL long long
 3 #define N 100005
 4 #define eps 1e-8
 5 using namespace std;
 6 int pos,n,col[N<<1],mx;
 7 struct edge{
 8     int to,next;
 9 }e[N<<2];
10 int head[N<<1],cnt;
11 void insert(int x, int y)
12 {
13     e[++cnt].to=y; e[cnt].next=head[x]; head[x]=cnt;
14 }
15 void dfs(int x, int fa)
16 {
17     int size=0;
18     for (int i=head[x];i;i=e[i].next)
19     {
20         if (e[i].to==fa) continue;
21         size++;
22         dfs(e[i].to,x);
23     }
24     if (x==1)
25     {
26         if (size+1>mx) mx=size+1,pos=x;
27     }
28     else if (size+2>mx) mx=size+2,pos=x;
29 }
30 void solve_paint(int x, int fa)
31 {
32     int orz=1; 
33     for (int i=head[x];i;i=e[i].next)
34     {
35         while (orz==col[x] || orz==col[fa]) orz++;
36         if (e[i].to==fa) continue;
37         col[e[i].to]=orz; orz++;
38         solve_paint(e[i].to,x);
39     }
40 }
41 int main()
42 {
43     scanf("%d",&n);
44     for (int i=1; i<n; i++)
45     {
46         int x,y; scanf("%d%d",&x,&y);
47         insert(x,y);
48         insert(y,x);
49     }
50     dfs(1,0);
51     cout<<mx<<endl;
52     col[pos]=1;
53     solve_paint(pos,0);
54     for (int i=1; i<=n; i++)
55         printf("%d ",col[i]);
56     return 0;
57 }

D题看不懂题，随便做了一个交上过了pretext满心欢喜，结果还是最后挂掉了。。