Time：Solo
A
题意
分析
B
题意
分析
C
题意
分析
D
签到
E
题意
分析
ym：前缀和排序后贪心取即可，注意要0加进去，表示到起点开始！！
#include#define ll long longusing namespace std;int t,a[100007],sum[100007],n,m,c;bool vis[100007];ll ans=0;int main(){ while(scanf("%d%d%d",&n,&m,&c)!=EOF) { ans=0; memset(sum,0,sizeof(sum)); memset(vis,false,sizeof(vis)); // scanf("%d%d%d",&n,&m,&c); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); sum[i]=sum[i-1]+a[i]; } sort(sum,sum+n+1); int l=0,r=n; ll tmp=0; for(int i=1;i<=m;i++) { tmp+=sum[r]-sum[l]-c; r--; l++; ans=max(ans,tmp); } cout< <
F
题意
分析
G
题意
分析
ym：贪心的将左括号变成右括号，有优先队列贪心的维护一下这个过程即可
#include#define ll long longusing namespace std;const int maxn = 1e5+7;char s[5];ll sum[maxn];struct node{ ll num,w; node(){} node(int x,int y){num=x,w=y;} friend bool operator < (node a,node b) { return a.w>b.w; }}a[maxn];priority_queue q;int n;ll ans=0;int main(){ while(scanf("%d",&n)!=EOF) { ans=0; while(!q.empty())q.pop(); for(int i=1;i<=n;i++) { scanf("%lld%s%lld",&a[i].num,s,&a[i].w); sum[i]=sum[i-1]+a[i].num; if(s[0]=='(') { ans+=a[i].w*a[i].num; a[i].w=-a[i].w; } } ll l=0; for(int i=1;i<=n;i++) { q.push(a[i]); ll ca=(sum[i]+1)/2-l; l=(sum[i]+1)/2; while(ca) { node now=q.top(); q.pop(); if(now.num>ca) { ans+=now.w*ca; now.num-=ca; ca=0; q.push(now); } else { ans+=now.w*now.num; ca-=now.num; } } } printf("%lld\n",ans); } return 0;}
H
题意
分析
ym：树上任意一点距离最远的点一定是树的直径两个点中的一个，三次dfs即可
#include#define ll long longusing namespace std;const int maxn = 2e5+7;int tot,head[maxn*2],nxt[maxn*2],to[maxn*2];ll w[maxn*2];int n,u,v;ll c;ll maxx;int ml,mr;ll d1[maxn],d2[maxn],ans;void add(int u,int v,ll c){ to[++tot]=v; w[tot]=c; nxt[tot]=head[u]; head[u]=tot;}void dfs1(int x,int fa,ll sum){ if(sum>maxx) { maxx=sum; ml=x; } for(int i=head[x];i;i=nxt[i]) { int v=to[i]; if(v==fa) continue; dfs1(v,x,sum+w[i]); }}void dfs2(int x,int fa,ll sum){ d1[x]=sum; if(sum>maxx) { maxx=sum; mr=x; } for(int i=head[x];i;i=nxt[i]) { int v=to[i]; if(v==fa) continue; dfs2(v,x,sum+w[i]); }}void dfs3(int x,int fa,ll sum){ d2[x]=sum; for(int i=head[x];i;i=nxt[i]) { int v=to[i]; if(v==fa) continue; dfs3(v,x,sum+w[i]); }}int main(){ while(scanf("%d",&n)!=EOF) { if(n==0) break; ans=0; tot=0; memset(d1,0,sizeof(d1)); memset(d2,0,sizeof(d2)); memset(head,0,sizeof(head)); memset(nxt,0,sizeof(nxt)); memset(w,0,sizeof(w)); memset(to,0,sizeof(to)); for(int i=1;i<=n-1;i++) { scanf("%d%d%lld",&u,&v,&c); add(u,v,c),add(v,u,c); } maxx=0; dfs1(1,0,0); maxx=0; dfs2(ml,0,0); maxx=0; dfs3(mr,0,0); ans=d1[mr]; for(int i=1;i<=n;i++) { if(i!=mr&&i!=ml) ans+=max(d1[i],d2[i]); } ///ans+=max(max(d1[ml],d1[mr]),max(d2[ml],d2[mr])); cout< <
I
ym：猜一下？？？
J
题意
分析
Summary
Ym：
Czh: