CF#398(Div.2) 解题报告

2019-11-08 02:38:36

字体：大中小

来源：转载

供稿：网友

A

题意简述

有n个大小为1..n的物品，每一天会得到一个，物品必须由下而上按照从大到小的顺序摆放每一天会将已有的物品尽量摆放，问这n天的摆放方案

数据范围

1≤n≤100000 $1/le n/le 100000$

题解

只有一个物品只有当比它大的所有物品都得到时才能摆放模拟即可

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<queue>#include<ctime>#include<cmath>#include<map>using namespace std;#define N 100005int n,x,now;bool vis[N];int main(){ scanf("%d",&n); now=n; for (int i=1;i<=n;++i) { scanf("%d",&x); vis[x]=1; while (vis[now]) PRintf("%d ",now--); puts(""); }}

B

题意简述

接待处服务时间为0点之后ts~tf-1，每一个人需要的服务时间为t 有一些人在某一个时刻来并且排队 V也会在某一个时间来，如果这个时间也有别人来，他会排在这些人的后面求V的最小等待时间

数据范围

0≤n≤100000,ts,tf,t≤1012 $0/le n/le 100000,t_s,t_f,t/le 10^{12}$

题解

首先判断服务是否有断层，如果有的话即在那个时刻来如果没有断层，枚举V在哪一个时间点来，有价值的时间点只有n个时间点以及两个时间点之间的断点预处理时间点ai $a_i$ 来的人需要办理服务到什么时间注意n=0 $n=0$ 需要特判算是贪心吧

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<queue>#include<ctime>#include<cmath>#include<map>using namespace std;#define LL long long#define N 100005const LL inf=1e18;int n,Max;LL s,t,l;LL now,a[N],ed[N],ans,ansp;int main(){ scanf("%I64d%I64d%I64d",&s,&t,&l);--t; scanf("%d",&n); if (!n) {printf("%I64d/n",s);return 0;} for (int i=1;i<=n;++i) scanf("%I64d",&a[i]); now=s;Max=n; for (int i=1;i<=n;++i) { if (a[i]<=now) now+=l,ed[i]=now-1; else {printf("%I64d/n",now);return 0;} if (now>t-l+1) {Max=i;break;} } if (ed[Max]<t-l+1) {printf("%I64d/n",ed[Max]+1LL);return 0;} ans=inf; for (int i=Max-1;i>=1;--i) if (a[i]==a[i+1]) ed[i]=max(ed[i],ed[i+1]); if (a[1]>0) { now=s-(a[1]-1LL); if (now<ans) ans=now,ansp=a[1]-1LL; } for (int i=1;i<=Max;++i) { if (ed[i]<t-l+1) { now=ed[i]+1LL-a[i]; if (now<ans) ans=now,ansp=a[i]; } if (i==Max||a[i+1]-a[i]<=1LL) continue; else { now=ed[i]+1LL-(a[i+1]-1LL); if (now<ans) ans=now,ansp=a[i+1]-1LL; } } printf("%I64d/n",ansp); return 0;}

C

题意简述

一棵有根树每一个节点有一个权值需要将这棵树断开两条边变成三棵树，并满足三棵树的权值和相等无解-1 注意：只能将某一个节点与其父亲相连的那条边断开

数据范围

3≤n≤106,−100≤ti≤100 $3/le n/le 10^6,-100/le t_i/le 100$

题解

首先总权值和被3整除可以满足条件的只有两种情况 1、两棵子树权值和为sum3 $sum/over 3$ ，并且互不包含 2、一棵子树权值和为2∗sum3 $2*sum/over 3$ ，一棵子树权值和为sum3 $sum/over 3$ 并且前者包含后者 dfs即可

代码

#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<queue>#include<ctime>#include<cmath>#include<map>using namespace std;#define N 1000005int n,fa,root,sum,id;int tot,point[N],nxt[N],v[N];int size[N],ans[5];bool pd,flag[N];void add(int x,int y){ ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}void findse(int x){ for (int i=point[x];i;i=nxt[i]) { if (size[v[i]]==sum/3) { ans[2]=v[i]; printf("%d %d/n",ans[1],ans[2]); exit(0); } findse(v[i]); }}void findsy(int x){ if (pd) return; if (size[x]==sum/3) { ans[++id]=x; pd=1; return; } for (int i=point[x];i;i=nxt[i]) findsy(v[i]);}void dfs(int x){ int cnt=0; for (int i=point[x];i;i=nxt[i]) { dfs(v[i]); size[x]+=size[v[i]]; if (flag[v[i]]) ++cnt; } if (cnt>=2) { id=0; for (int i=point[x];i;i=nxt[i]) if (flag[v[i]]) { pd=0; findsy(v[i]); if (id==2) break; } printf("%d %d/n",ans[1],ans[2]); exit(0); } if (x!=root&&(cnt||size[x]==sum/3)) flag[x]=1; if (x!=root&&size[x]==sum/3*2&&flag[x]) { ans[1]=x; findse(x); }}int main(){ scanf("%d",&n); for (int i=1;i<=n;++i) { scanf("%d%d",&fa,&size[i]); sum+=size[i]; if (fa) add(fa,i); else root=i; } if (sum%3!=0) {puts("-1");return 0;} dfs(root); if (ans[1]&&ans[2]) printf("%d %d/n",ans[1],ans[2]); else puts("-1");}