2016 장락캠프 Day 7
법칙을 찾아 한 발 + 트리 그룹 한 발 O (nlog^2n)
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 2E5 + 20;
typedef long long LL;
struct Day{
int num,t;
Day(int _num = 0,int _t = 0) {num = _num; t = _t;}
bool operator < (const Day &b) const {
return t > b.t;
}
}day[maxn];
struct Work{
int d,r,pos;
Work(int _d = 0,int _r = 0,int _pos = 0){d = _d; r = _r; pos = _pos;}
bool operator < (const Work &b) const {
return d > b.d;
}
}job[maxn];
int n,m,ans[maxn];
LL c1[maxn],c2[maxn];
void Insert(int pos)
{
for (int j = day[pos].num; j <= m; j += j&-j)
c1[j] += 1LL*day[pos].t,c2[j] += 1LL;
}
bool Judge(int now,int x)
{
LL sumt,sumd; sumt = sumd = 0;
for (int j = now; j > 0; j -= j&-j)
sumt += c1[j],sumd += c2[j];
return sumt - 1LL*job[x].d*sumd >= 1LL*job[x].r;
}
int getint()
{
int ret = 0;
char ch = getchar();
while (ch < '0' || '9' < ch) ch = getchar();
while ('0' <= ch && ch <= '9') ret = ret*10 + ch - '0',ch = getchar();
return ret;
}
int main()
{
#ifdef DMC
freopen("DMC.txt","r",stdin);
freopen("test.txt","w",stdout);
#else
freopen("work.in","r",stdin);
freopen("work.out","w",stdout);
#endif
//scanf("%d%d",&n,&m);
n = getint(); m = getint();
for (int i = 1; i <= m; i++) {
int x = getint();
//scanf("%d",&x);
day[i] = Day(i,x);
}
sort(day + 1,day + m + 1);
for (int i = 1; i <= n; i++) {
int x,y; x = getint(); y = getint();
//scanf("%d%d",&x,&y);
job[i] = Work(x,y,i);
}
sort(job + 1,job + n + 1);
int tail = 1;
for (int i = 1; i <= n; i++) {
while (tail <= m && day[tail].t > job[i].d) Insert(tail++);
int L,R; L = 1; R = m+1;
while (R - L > 1) {
int mid = (L+R) >> 1;
if (Judge(mid,i)) R = mid;
else L = mid;
}
int Ans;
if (Judge(L,i)) Ans = L;
else Ans = R;
if (Ans == m + 1) Ans = 0;
ans[job[i].pos] = Ans;
}
for (int i = 1; i <= n; i++) printf("%d ",ans[i]);
return 0;
}
T2:
그림을 그려 보면 두 경로가 서로 교차하면 반드시 LCA와 관련이 있고, 두 개의 매거진 충돌 노선이 있고, 가장자리를 만들어 최대 독립 서브집합을 만들어야 한다
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1E5 + 10;
const int S = 0;
const int T = 4901;
const int INF = ~0U>>1;
typedef long long LL;
struct E{
int from,to,cap,flow;
E(int _from = 0,int _to = 0,int _cap = 0,int _flow = 0) {
from = _from; to = _to; cap = _cap; flow = _flow;
}
}edgs[maxn*10];
int n,L,P,cnt,tot,fa[maxn][20],Deep[maxn],cur[maxn];
LL ans = 0;
vector v[maxn];
vector v2[maxn];
queue Q;
void dfs(int x,int from)
{
for (int i = 1; i < 20; i++)
fa[x][i] = fa[fa[x][i-1]][i-1];
for (int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if (to == from) continue;
Deep[to] = Deep[x] + 1;
fa[to][0] = x;
dfs(to,x);
}
}
int LCA(int p,int q)
{
if (Deep[p] < Deep[q]) swap(p,q);
int Log; for (Log = 0; Deep[p] - (1< 0; Log++); --Log;
for (int j = Log; j >= 0; j--)
if (Deep[p] - (1<= Deep[q])
p = fa[p][j];
if (p == q) return p;
for (int j = Log; j >= 0; j--)
if (fa[p][j] != fa[q][j])
p = fa[p][j],q = fa[q][j];
return fa[p][0];
}
struct B{
int a,b,w,num,lca;
B(int _a = 0,int _b = 0,int _w = 0,int _num = 0) {
a = _a; b = _b; w = _w; num = _num; lca = LCA(_a,_b);
}
}lpf[maxn],pyz[maxn];
bool arg(int x,int y)
{
B p = lpf[x],q = pyz[y];
if (Deep[p.lca] > Deep[q.lca]) swap(p,q);
/*if (q.a != q.lca) {
int Lca = LCA(p.a,q.lca);
if (Lca == q.lca && p.a != q.lca) {
Lca = LCA(p.a,q.a);
if (Lca == p.a || Lca == q.a) return 1;
}
Lca = LCA(p.b,q.lca);
if (Lca == q.lca && p.b != q.lca) {
Lca = LCA(p.b,q.a);
if (Lca == p.b || Lca == q.a) return 1;
}
}
if (q.b != q.lca) {
int Lca = LCA(p.a,q.lca);
if (Lca == q.lca && p.a != q.lca) {
Lca = LCA(p.a,q.b);
if (Lca == p.a || Lca == q.b) return 1;
}
Lca = LCA(p.b,q.lca);
if (Lca == q.lca && p.b != q.lca) {
Lca = LCA(p.b,q.b);
if (Lca == p.b || Lca == q.b) return 1;
}
}*/
int Lca = LCA(q.lca,p.a);
if (Lca == q.lca) return 1;
Lca = LCA(q.lca,p.b);
if (Lca == q.lca) return 1;
return 0;
}
void Add(int from,int to,int cap)
{
v2[from].push_back(cnt); edgs[cnt++] = E(from,to,cap,0);
v2[to].push_back(cnt); edgs[cnt++] = E(to,from,0,0);
}
bool BFS()
{
for (int i = 1; i <= tot; i++) Deep[i] = 0;
Deep[T] = 0; Deep[S] = 1; Q.push(S);
while (!Q.empty()) {
int k = Q.front(); Q.pop();
for (int i = 0; i < v2[k].size(); i++) {
E e = edgs[v2[k][i]];
if (e.cap == e.flow) continue;
if (Deep[e.to]) continue;
Deep[e.to] = Deep[k] + 1;
Q.push(e.to);
}
}
return Deep[T];
}
int Dicnic(int x,int a)
{
if (x == T) return a;
int flow = 0;
for (int &i = cur[x]; i < v2[x].size(); i++) {
E &e = edgs[v2[x][i]];
if (e.cap == e.flow) continue;
if (Deep[e.to] != Deep[x] + 1) continue;
int f = Dicnic(e.to,min(a,e.cap - e.flow));
if (f > 0) {
flow += f;
e.flow += f;
edgs[v2[x][i]^1].flow -= f;
a -= f;
if (!a) return flow;
}
}
if (!flow) Deep[x] = -1;
return flow;
}
int main()
{
#ifdef DMC
freopen("DMC.txt","r",stdin);
#else
freopen("bus.in","r",stdin);
freopen("bus.out","w",stdout);
#endif
cin >> n >> L >> P;
for (int i = 1; i < n; i++) {
int x,y; scanf("%d%d",&x,&y);
v[x].push_back(y); v[y].push_back(x);
}
Deep[1] = 1; dfs(1,0);
for (int i = 1; i <= L; i++) {
int x,y,w; scanf("%d%d%d",&x,&y,&w);
lpf[i] = B(x,y,w,++tot);
ans += 1LL*w;
}
for (int i = 1; i <= P; i++) {
int x,y,w; scanf("%d%d%d",&x,&y,&w);
pyz[i] = B(x,y,w,++tot);
ans += 1LL*w;
}
for (int i = 1; i <= L; i++)
for (int j = 1; j <= P; j++)
if (arg(i,j))
Add(lpf[i].num,pyz[j].num,INF);
for (int i = 1; i <= L; i++) Add(S,lpf[i].num,lpf[i].w);
for (int i = 1; i <= P; i++) Add(pyz[i].num,T,pyz[i].w);
LL flow = 0;
while (BFS()) {
for (int i = 1; i <= tot; i++) cur[i] = 0;
cur[S] = cur[T] = 0;
flow += 1LL*Dicnic(S,INF);
}
cout << ans - flow;
return 0;
}
T3:
트리 dp f[i][j]: i의 하위 트리에 예(아니오)가 완전히 채워져 있습니다. (아니오)일 경우 j 단위를 위(아래)로 확장할 수 있습니다.
분명히 0<=j<=100, 이 답안의 우열 정도는 명백한 단조성을 가지고 있다. 즉, f[i][j+1]
if[i][w[i]]=1+∑min(f[son][j])-w[i]<=j<=100
if[i][j]를 선택하지 않으면
if (j >= 0) f[k][j+1] + ∑min(f[son][x]) (son != k,-j <= x <= 100)
if (j <= 0) f[k][j+1] + ∑min(f[son][x]) (son != k,j < x <= 100)
k 매거와 최대치, 차대치의 특판을 통해
min 상기 단조성 O(1)로 유지보수 및 조회 가능
f의 불법 상태에 대해 직접 값을 부여하고 f수 그룹을 LL로 열어 쓰기 편리하게 합니다
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1E5 + 10;
const int INF = maxn;
typedef long long LL;
LL sum[210],f[maxn][210];
int n,m,t,w[maxn],Maxw[maxn];
vector v[maxn];
void Work(int x,int from)
{
memset(sum,0,sizeof(sum));
for (int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if (to == from) continue;
for (int j = 0; j <= 201; j++) sum[j] += f[to][j];
}
for (int i = 0; i <= 200; i++) {
f[x][i] = INF;
if (i > 100)
for (int j = 0; j < v[x].size(); j++) {
int to = v[x][j];
if (to == from) continue;
//if (f[to][i+1] == INF) continue;
f[x][i] = min(f[x][i],f[to][i+1] + sum[202-i] - f[to][202-i]);
}
else f[x][i] = sum[i+1];
}
f[x][201] = INF;
}
void dfs(int x,int from)
{
if (v[x].size() == 1 && from) {
for (int i = 101; i <= w[x] + 101; i++) f[x][i] = 1;
for (int i = w[x] + 102; i <= 201; i++) f[x][i] = INF;
for (int i = 0; i <= 100; i++) f[x][i] = 0;
return;
}
for (int i = 0; i < v[x].size(); i++) {
int to = v[x][i];
if (to == from) continue;
dfs(to,x);
}
Work(x,from);
LL tot = 1LL + sum[101-w[x]];
f[x][w[x]+101] = min(f[x][w[x]+101],tot);
for (int i = 200; i >= 0; i--)
f[x][i] = min(f[x][i],f[x][i+1]);
}
int main()
{
#ifdef DMC
freopen("DMC.txt","r",stdin);
#else
freopen("city.in","r",stdin);
freopen("city.out","w",stdout);
#endif
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d",&w[i]);
for (int i = 1; i < n; i++) {
int x,y; scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
printf("%d
",f[1][101]);
for (int i = 1; i <= n; i++) v[i].clear();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[네트워크 흐름 24문제] [codevs1906] 최장 증자 서열 (dp+isap)전송문 제목의 bug:1、데이터 범위는 주지 않았지만 눈대중으로 아무렇게나 열면 돼요. 한 점을 두 점으로 나누어 각 점의 사용 횟수를 보증하다.관계의 전이 dp 이후 i가 j 이전에 만족해야 하며 i의 값이 j의 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
