翻车!翻车!
codeforces782A
A题:
水。
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int num[100010];
int main()
{
int n,x;
memset(num,0,sizeof(num));
scanf("%d",&n);
int sum=0,ans=0;
for(int i=1;i<=2*n;i++)
{
scanf("%d",&x);
if(!num[x])
{
num[x]++;
sum++;
}
else
{
sum--;
num[x]--;
}
ans=max(ans,sum);
}
printf("%d\n",ans);
return 0;
}
codeforces782B
B题:
三分,最短时间的位置位于最大位置和最小位置区间内,而时间是咋算的?所有点到位置的max,so两边扩散,肯定是越来越大,凹形曲线,三分求极值。
PS:注意精度1e-6.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const double eps=1e-6;
const int N=6e4+10;
struct asd{
double x,v;
}e[N];
int n;
bool cmp(asd a,asd b)
{
if(a.x<b.x) return true;
return false;
} double fun(double x)
{
double ans=0.0;
for(int i=1;i<=n;i++)
if(ans<(fabs(e[i].x-x)/e[i].v))
ans=(fabs(e[i].x-x)/e[i].v);
return ans;
} int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf",&e[i].x);
for(int i=1;i<=n;i++)
scanf("%lf",&e[i].v);
sort(e+1,e+n+1,cmp);
double Left=e[1].x,Right=e[n].x;
double mid, midmid;
double mid_value, midmid_value;
while (Left +eps < Right)
{
mid = (Left + Right) / 2;
midmid = (mid + Right) / 2;
mid_value = fun(mid);
midmid_value = fun(midmid);
///求最大值改成>= 最小值改成<=
if (mid_value <= midmid_value) Right = midmid;
else Left = mid;
}
double ans=fun(Left);
printf("%.9lf\n",ans);
return 0;
}
codeforces782C
C题:
利用BFS可以轻松处理。
BFS是一层一层的,对于每个结点的儿子结点,都会有一些可以使用的颜色,except(他父亲的颜色,他父亲的父亲的颜色)。
外送两个案例:
7
1 2
3 2
2 4
4 5
5 6
5 7 7
1 2
2 3
2 4
2 5
5 6
5 7
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL; const int N=4e5+10; struct asd{
int to;
int next;
}e[N];
int head[N],tol;
bool vis[N];
int col[N],pre[N],in[N],t; void BFS(int pos)
{
queue<int>q;
memset(vis,0,sizeof(vis));
pre[0]=pre[pos]=0;
vis[pos]=true;
col[pos]=1;
t=1;
q.push(pos);
while(!q.empty())
{
int u=q.front();q.pop();
int tmp=t;
int num=t;
for(int i=head[u];~i;i=e[i].next)
{
int v=e[i].to;
if(vis[v]) continue;
q.push(v);
pre[v]=u;
vis[v]=true;
while(num&&(num==col[u]||num==col[pre[u]]))
num--;
if(num)
col[v]=num--;
else
col[v]=++tmp;
}
t=tmp;
}
}
void init()
{
tol=0;
memset(head,-1,sizeof(head));
memset(in,0,sizeof(in));
}
void add(int u,int v)
{
e[tol].to=v;
e[tol].next=head[u];
head[u]=tol++;
} int main()
{
int n,u,v;
scanf("%d",&n);
init();
for(int i=2;i<=n;i++)
{
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
in[u]++;
in[v]++;
}
int pos;
for(int i=1;i<=n;i++)
{
if(in[i]==1)
{
pos=i;
break;
}
}
BFS(pos);
int ans=0;
for(int i=1;i<=n;i++)
ans=max(ans,col[i]);
printf("%d\n",ans);
for(int i=1;i<=n;i++)
printf("%d ",col[i]);
return 0;
}