Codeforces Round #398 (Div. 2) BCD

B：The Queue

题目大意：你要去办签证,那里上班时间是[s,t), 你知道那一天有n个人会来办签证,他们分别是在时间点a_i来的。每个人办业务要花相同的时间x,问你什么时候来排队等待的时间最少。 (如果你和某个人同时来排队,你会排在他后面) 所有时间为正整数。

题解：

首先可以模拟出每个人的业务什么时候会办好,那么最优解要么是在第一个人来之前的一分钟来,即a₁-1,要么是在某个人的业务刚办好的时候来。分别求出要等待的时间即可。

注意如果有多个人同时来,那么只能在这些人里的最后的业务办好之后来。

代码：

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <map>

 #include <cstdlib>

 #include <set>

 #include <queue>

 using namespace std;

 #define X first

 #define Y second

 #define Mod 1000000007

 #define N 1000010

 #define M 101

 typedef long long ll;

 typedef pair<int,int> pii;

 int n;

 ll s,t,x,ans1,ans2;

 ll v[N];

 int main()

 {

     //freopen("in.in","r",stdin);

     //freopen("out.out","w",stdout);

     scanf("%I64d%I64d%I64d",&s,&t,&x);

     scanf("%d",&n);

     for (int i=;i<=n;i++) scanf("%I64d",&v[i]);

     while (n && v[n]+x>t) n--;

     if (n==)

     {

         printf("%I64d\n",s);

         return ;

     }

     ans1=v[]-; ans2=s-ans1;

     ll cur=s;

     for (int i=;i<=n;i++)

     {

         if (v[i]<=cur) cur+=x;

         else cur=v[i]+x;

         if (i<n && v[i]==v[i+]) continue;

         if (i<n)

         {

             ll tmp=v[i+]-,tt=max(0ll,cur-tmp);

             if (tt<ans2) ans1=tmp,ans2=tt;

         }

         //cout<<i<<' '<<cur<<endl;

     }

     if (cur+x<=t)

     {

         ans1=cur,ans2=;

     }

     printf("%I64d\n",ans1);

     return ;

 }

C：Garland

题目大意：

给出一棵树,要求分成3部分,每个部分的点权和相同。

题解：

首先所有点的点权之和必须是3的倍数,否则无解。记s[x]为以x为根的子树点权和,tmp=所有点权和/3。假设我们选了u,v这两个点,并且切掉了它们到它们的父节点的边。那么符合要求的只有2种情况：

1. s[u]=s[v]=tmp. lca(u,v)!=u && lca(u,v)!=v.

2. s[u]=tmp*2,s[v]=tmp, lca(u,v)=u.

首先做一次dfs求出所有s[x]。

然后做第二次dfs：对于第2种情况,只要记录从根到当前节点是否存在s[u]=tmp*2的点, 如果存在,且当前节点s[v]=tmp,那么就找到了一种分割方案。

对于第1种情况, 对于当前节点v, 且s[v]=tmp, 我们需要知道是否存在一个点u,满足s[u]=tmp*2,且u不在根到v的路径中。这里用点小技巧, 假设dfs到了v,那么根到v的路径中的点都还在栈里, 所以只要考虑已经不在栈里的点u。具体实现看代码。

代码：

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <map>

 #include <cstdlib>

 #include <set>

 #include <queue>

 using namespace std;

 #define X first

 #define Y second

 #define Mod 1000000007

 #define N 1000010

 #define M 101

 typedef long long ll;

 typedef pair<int,int> pii;

 int n,t1,t2,rt,tmp,tt;

 int father[N],v[N],s[N];

 vector<int> g[N];

 void Dfs(int x)

 {

     s[x]=v[x];

     for (int i=;i<g[x].size();i++)

     {

         int y=g[x][i]; if (y==father[x]) continue;

         Dfs(y); s[x]+=s[y];

     }

 }

 void Dfs2(int x,int pre)

 {

     if (pre && s[x]==tmp) t1=pre,t2=x;

     if (tt && s[x]==tmp) t1=tt,t2=x;

     for (int i=;i<g[x].size();i++)

     {

         int y=g[x][i]; if (y==father[x]) continue;

         if (x!=rt && s[x]==tmp*) Dfs2(y,x);

         else Dfs2(y,pre);

     }

     if (s[x]==tmp) tt=x;

 }

 int main()

 {

     //freopen("in.in","r",stdin);

     //freopen("out.out","w",stdout);

     scanf("%d",&n);  int sum=;

     for (int i=;i<=n;i++)

     {

         scanf("%d%d",&father[i],&v[i]);

         if (father[i]) g[father[i]].push_back(i);

         else rt=i;

         sum+=v[i];

     }

     if (sum%){printf("-1\n"); return ;}

     tmp=sum/;

     Dfs(rt);

     Dfs2(rt,);

     if (t1 && t2) printf("%d %d\n",t1,t2);

     else printf("-1\n");

     return ;

 }

D：

有n瓶牛奶,分别还有ai天过期,每天最多喝k瓶。超市里有m瓶牛奶,分别还有bi天过期, 问最多能从超市里买多少瓶牛奶,使得买来的牛奶加上本来已有的,都可以在过期之前喝完。

n<=100w.

题解：

显然要先买保质期长的牛奶,所以可以考虑二分答案。如何判断可行性呢？根据贪心策略,显然要先喝保质期短的牛奶。所以只要把牛奶按保质期排序就好。这里就涉及到将两个单调的序列合并成一个单调序列的问题。数据范围100w应该是为了卡掉暴力sort合并的O(nlognlogn)解法.

代码：

 #include <iostream>

 #include <cstdio>

 #include <cmath>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 #include <map>

 #include <cstdlib>

 #include <set>

 #include <queue>

 using namespace std;

 #define X first

 #define Y second

 #define Mod 1000000007

 #define N 1000010

 #define M 101

 typedef long long ll;

 typedef pair<int,int> pii;

 int n,m,k;

 int a[N],q[N<<];

 struct node

 {

     int v,id;

     bool operator < (const node &t)const

     {

         return v<t.v;

     }

 }b[N];

 bool check(int mid)

 {

     int i=,j=mid,cnt=;

     while (i<n || j<m)

     {

         if (i>=n) q[cnt]=b[j].v,j++;

         else if (j>=m) q[cnt]=a[i],i++;

         else

         {

             if (a[i]<b[j].v) q[cnt]=a[i],i++;

             else q[cnt]=b[j].v,j++;

         }

         if (cnt/k>q[cnt]) return false;

         cnt++;

     }

     return true;

 }

 int main()

 {

     //freopen("in.in","r",stdin);

     //freopen("out.out","w",stdout);

     scanf("%d%d%d",&n,&m,&k);

     for (int i=;i<n;i++) scanf("%d",&a[i]);

     for (int i=;i<m;i++) scanf("%d",&b[i].v),b[i].id=i+;

     sort(a,a+n);sort(b,b+m);

     bool flag=true;

     for (int i=;i<n;i++) if (a[i]<i/k) flag=false;

     if (!flag){printf("-1\n"); return ;}

     int l=,r=m,mid,ans;

     while (l<r)

     {

         mid=(l+r)>>;

         if (check(mid)) r=mid;

         else l=mid+;

     }

     ans=m-l;

     printf("%d\n",ans);

     for (int i=m-ans;i<m;i++) printf("%d ",b[i].id);

     printf("\n");

     return ;

 }

巴特西

Codeforces Round #398 (Div. 2) BCD

最新文章

热门文章