CF#398(Div.2) 解題報告

2019-11-08 02:38:36

字體：大中小

來源：轉(zhuǎn)載

供稿：網(wǎng)友

A

題意簡述

有n個大小為1..n的物品，每一天會得到一個，物品必須由下而上按照從大到小的順序擺放每一天會將已有的物品盡量擺放，問這n天的擺放方案

數(shù)據(jù)范圍

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

題解

只有一個物品只有當(dāng)比它大的所有物品都得到時才能擺放模擬即可

代碼

#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]) B

題意簡述

接待處服務(wù)時間為0點之后ts~tf-1，每一個人需要的服務(wù)時間為t 有一些人在某一個時刻來并且排隊 V也會在某一個時間來，如果這個時間也有別人來，他會排在這些人的后面求V的最小等待時間

數(shù)據(jù)范圍

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

題解

首先判斷服務(wù)是否有斷層，如果有的話即在那個時刻來如果沒有斷層，枚舉V在哪一個時間點來，有價值的時間點只有n個時間點以及兩個時間點之間的斷點預(yù)處理時間點ai $a_i$ 來的人需要辦理服務(wù)到什么時間注意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

題意簡述

一棵有根樹每一個節(jié)點有一個權(quán)值需要將這棵樹斷開兩條邊變成三棵樹，并滿足三棵樹的權(quán)值和相等無解-1 注意：只能將某一個節(jié)點與其父親相連的那條邊斷開

數(shù)據(jù)范圍

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

題解

首先總權(quán)值和被3整除可以滿足條件的只有兩種情況 1、兩棵子樹權(quán)值和為sum3 $sum/over 3$ ，并且互不包含 2、一棵子樹權(quán)值和為2?sum3 $2*sum/over 3$ ，一棵子樹權(quán)值和為sum3 $sum/over 3$ 并且前者包含后者 dfs即可