2017 Multi-University Training Contest - Team 3
04 / hdu6058 链表好题
题意：求所有区间第 k 大的和。
tags： 好像不用链表，暴力都可以。。。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 500005; int n, k, a[N], pre[N], nex[N], pos[N], num1[100], num2[200]; ll cal(int p) { ll res = 0; int c1=0, c2=0; for(int i=p; i>0 && c1<k; i=pre[i]) { num1[++c1] = i - pre[i]; } for(int i=p; i<=n && c2<k; i=nex[i]) { num2[++c2] = nex[i] - i; } for(int i=c1,j=1; i>0 && j<=c2; ) { if(i+j-1!=k) { ++j; continue; } res += num1[i]*num2[j]; --i, ++j; } return res; } void Del(int p) { nex[pre[p]] = nex[p]; pre[nex[p]] = pre[p]; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &k); rep(i,1,n) { scanf("%d", &a[i]); pos[a[i]] = i; pre[i] = i-1, nex[i] = i+1; } ll ans = 0; rep(i,1,n) { ans += cal(pos[i])*i; Del(pos[i]); } printf("%lld\n", ans); } return 0; }
05 dfs，size[]与 k 判一下就好。
#include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a; i<=b; ++i) #define per(i,b,a) for (int i=b; i>=a; --i) #define mes(a,b) memset(a,b,sizeof(a)) #define INF 0x3f3f3f3f #define MP make_pair #define PB push_back #define fi first #define se second typedef long long ll; const int N = 1000005; int n, k; ll ans; struct Edge{int to,next,w; }e[N<<1]; int tot, head[N], Size[N]; void Addedge(int u, int v, int w) { e[tot]={v,head[u],w }; head[u]=tot++; } void dfs(int u, int fa) { Size[u] = 1; for(int i=head[u]; i!=-1; i=e[i].next) if(e[i].to!=fa) { int to=e[i].to, w=e[i].w; dfs(to, u); Size[u] += Size[to]; ans += 1LL*min(Size[to], k)*w; } } void Init() { mes(head, -1); mes(Size, 0); tot=0, ans=0; } int main() { while(~scanf("%d %d", &n, &k)) { Init(); int u, v, w; rep(i,1,n-1) { scanf("%d %d %d", &u, &v, &w); Addedge(u, v, w); Addedge(v, u, w); } dfs(1, 0); printf("%lld\n", ans); } return 0; }