洛谷 P2181 对角线全面分析

发表于 2020-08-10 更新于 2021-04-29

对于一个 $n$ 个顶点的凸多边形，它的任何三条对角线都不会交于一点。请求出图形中对角线交点的个数。

练python刷简单题刷到了这个，挺有趣的一道题目。

1

对于一个 $n$ 边形，选任意一个点A可以引出 $n - 3$ 条对角线。相邻的点B再引出 $n - 3$ 条线，分别与前者有 $1, 2 . . . n - 3$ 个交点。与B相邻且不与A相邻的C引出 $n - 4$ 条线，交A引出的对角线有 $1, 2 . . . n - 4$ 个交点，B亦然。

有一篇论文介绍得十分详细链接

故结果应为 $\sum_{i = 1}^{n - 3} (i * \sum_{j = 1}^{n - 2 - i}) = \sum_{i = 1}^{n - 3} i * \frac{(n - i - 1) (n - i - 2)}{2}$

代码如下

n=int(input())
ans=0
i=1
while True :
    ans+=i*(n-(2+i))*(n-(1+i))//2
    if n-(1+i)<=2 :
        break
    i+=1
print(ans)

此方法可以解决这个问题，时间复杂度 $O (n)$

2

我暂时不会对上述和式求和，但推测通项可能是或四次的。故希望能 $O (1)$ 解决这个问题。

令 $f (n) = \sum_{i = 1}^{n - 3} \frac{(n - i - 1) (n - i - 2)}{2}$ 易知 $f (3) = 0, f (4) = 1, f (5) = 5, f (6) = 15, f (7) = 35$ 构建范德蒙德矩阵

$V = v a n d e r ([\begin{matrix} 3 & 4 & 5 & 6 & 7 \end{matrix}])$ $V * \vec{A} = {[\begin{matrix} 0 & 1 & 5 & 15 & 35 \end{matrix}]}^{T}$ $\vec{A} = {[\begin{matrix} \frac{1}{24} & - \frac{1}{4} & \frac{11}{24} & - \frac{1}{4} & 0 \end{matrix}]}^{T}$ 验证 $n >= 8$ ，成立。则 $f (n) = [n^{4} n^{3} n^{2} n 1] \vec{A}$ 使用matlab计算这个问题

>> format rat
>> V=vander([3 4 5 6 7]);
>> inv(V)*[0;1;5;15;35]

ans =

       1/24    
      -1/4     
      11/24    
      -1/4     
      -1/25588634246423

所以代码为此简单的三行

1
2
3

a=int(input())
a=a*a*a*a-a*a*a*6+a*a*11-a*6
print(a//24)

# 3 实际上，用组合数学的方法，我们知道，每四个不同的顶点有一个交点，答案即是

C_{n}^{4} = \frac{n (n - 1) (n - 2) (n - 3)}{24}

与以上结果相同。

LeetCode 337. House Robber III 打家劫舍

发表于 2020-08-05 更新于 2021-04-29

第一次用结构体代替dp数组，这个题没有标明树的深度，用数组存二叉树会爆内存。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
struct dp{
    int v0,v1;
    dp *lf;
    dp *rt;
    dp() : v0(0),v1(0),lf(NULL),rt(NULL){}
};

class Solution {
public:
    void dfs(TreeNode *p,dp *u){
        if(!p){
            return;
        }
        if(!p->left&&!p->right){
            u->v0=0;
            u->v1=p->val;
            return ;
        }
        u->lf=new dp(),u->rt=new dp();
        if(p->left){
            dfs(p->left,u->lf);
        }
        if(p->right){
            dfs(p->right,u->rt);
        }
        /*
        dp[1][u]=dp[0][L(u)]+dp[0][R(u)]+p->val;
        dp[0][u]=max(dp[0][L(u)],dp[1][L(u)])+max(dp[0][R(u)],dp[1][R(u)]);
        */
        u->v1=p->val+u->lf->v0+u->rt->v0;
        u->v0=max(u->lf->v0,u->lf->v1)+max(u->rt->v0,u->rt->v1);
    }
    int rob(TreeNode* root) {
        dp *ans=new dp();
        dfs(root,ans);
        return max(ans->v0,ans->v1);
    }
};

贪吃蛇，C++

发表于 2020-07-31 更新于 2021-04-29

好久之前写的，登陆博客看了下好久没更新了，就随手发出来吧。用这份代码，QT套了个界面设置速度和地图大小。QT的代码就不发了hhh，毕竟源代码分好几个文件懒。用了Windows.h 所以只能在Windows下运行。

#include<Windows.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<conio.h>
#include<deque>
using namespace std;

const int MAXC=100,MAXR=100;
typedef pair<int,int> pii;

class Game{
public:
    int mat[MAXC][MAXR];
    int dx[5],dy[5];
    deque<pii> q;
    int d,col,row;
    bool food;
    HANDLE hOut;
    void pt(int x, int y,char c){
        COORD pos;
        pos.X=x*3+2;
        pos.Y=y*2+1;
        SetConsoleCursorPosition(hOut, pos);
        putchar(c);
    }
    int dir(){
        char c1,c2;
        if(!_kbhit())
            return 4;
        c1=getch(),c2=getch();
        switch(c2){
            case 72:return 1;//up
            case 75:return 0;//left
            case 77:return 3;//right
            case 80:return 2;//down
        }
    }
    void topblock(){
        printf("┌");
        for(int i=0;i<col-1;++i)
            printf("──┬");
        puts("──┐");
    }
    void buttonblock(){
        printf("└");
        for(int i=0;i<col-1;++i)
            printf("──┴");
        puts("──┘");
    }
    void commonblock(){
        printf("├");
        for(int i=0;i<col-1;++i)
            printf("──┼");
        puts("──┤");
    }
    void feed()
    {
        while(!food){
            int xx=rand()%col,yy=rand()%row;
            if(!mat[xx][yy]){
                mat[xx][yy]=2;
                food=1;
                pt(xx,yy,'*');
            }
        }
    }
    Game(){
        row=11,col=11;//settings
        dx[0]=dy[1]=-1,dx[3]=dy[2]=1;
        dx[1]=dx[2]=dy[0]=dy[3]=dx[4]=dy[4]=0;
        d=4;
        food=0;
        hOut=GetStdHandle(STD_OUTPUT_HANDLE);
    }
    void start(){
        system("chcp 437");
        system("mode con:cols=36 lines=24");
        system("chcp 65001");
        print_init();
        while(1){
            if(!food){
                feed();
            }
            int t=dir(),nx,ny;
            pii tmp=q.front();
            if(t==4||(t==0&&d==3)||(t==3&&d==0)||(t==1&&d==2)||(t==2&&d==1)){
                nx=tmp.first+dx[d],ny=tmp.second+dy[d];
            }
            else{
                nx=tmp.first+dx[t],ny=tmp.second+dy[t];
                d=t;
            }
            bool death=0;
            if(nx>=0&&ny>=0&&nx<row&&ny<col){
                if(mat[nx][ny]==1){
                    death=1;
                }
                else if(mat[nx][ny]==2){
                    pt(tmp.first,tmp.second,'O');
                    q.push_front(pii(nx,ny));
                    pt(nx,ny,'@');
                    mat[nx][ny]=1;
                    food=0;
                }
                else{
                    pii tt=q.back();
                    q.pop_back();
                    mat[tt.first][tt.second]=0;
                    pt(tt.first,tt.second,' ');
                    q.push_front(pii(nx,ny));
                    pt(tmp.first,tmp.second,'O');
                    pt(nx,ny,'@');
                    mat[nx][ny]=1;
                }
            }
            else{
                death=1;
            }
            if(death){
               system("cls");
               puts("你输了");
               system("pause");
            }
            Sleep(200);
        }
    }
    void print_init(){
        system("cls");
        topblock();
        for(int i=0;i<row;++i){
            printf("│");
            for(int j=0;j<col;++j){
                printf("  │");
            }
            puts("");
            if(i==row-1)
                buttonblock();
            else commonblock();
        }
        int xx=rand()%col,yy=rand()%row;
        q.push_front(pii(xx,yy));
        mat[xx][yy]=1;
        pt(xx,yy,'@');
        while(1){
            int td=rand()%4;
            int nx=xx+dx[td],ny=yy+dy[td];
            if(nx>=0&&ny>=0&&nx<row&&ny<col){
                q.push_back(pii(nx,ny));
                mat[nx][ny]=1;
                pt(nx,ny,'O');
                break;
            }
        }
        feed();
        while(1){
            int ttt;
            if((ttt=dir())!=4){
                d=ttt;
                break;
            }
        }
    }
};

int main(){
    srand((unsigned)time(0));
    Game().start();
	return 0;
}

C语言预处理学习记录

发表于 2020-02-27 更新于 2021-04-29

#include<stdio.h>

#define LOCAL //无参宏

//条件编译 
#ifdef LOCAL
int a=1;
#else
int a=2;
#endif

#ifndef LOCAL
int b=1;
#else 
int b=2;
#endif

#define PI 3.1415926535 //有参宏

#define max_wrong(a,b) a>b?a:b
#define max(a,b) ((a)>(b)?(a):(b))
#define maxwell(a,b) ({\
	__typeof(a) _a=(a),_b=(b);\
	_a>_b?_a:_b;\
}) 

#define DEBUG//

#ifdef DEBUG
#define log(frm,args...) {\
	printf("[%s %s %d] : %s = ",__FILE__,__func__,__LINE__,#args);\
	printf(frm,##args);\
}
#else
#define log(frm,args...)
#endif

int main(){
	printf("a = %d b = %d\n",a,b);
	printf("max_wrong(2,max_wrong(3,4)) = %d\n",max_wrong(2,max_wrong(3,4)));
	//展开后： 2>3>4?3:4?2:3>4?3:4 实际执行 ((2>3>4)?(3):(4))? (2) : (3>4?3:4)
	//使用 -E 编译选项获得预编译结果 
	printf("max(2,max(3,4)) = %d\n",max(2,max(3,4)));
	
	int a=1;
	printf("%d\n",max(a++,0));
	log("%d\n",a);
	a=1;
	log("%d\n",maxwell(a++,0));
	log("%d\n",a);
	
	log("Hello world");
	return 0;
}

一个无聊的游戏——吃豆人

发表于 2018-01-10 更新于 2021-04-29

退役后无聊自制了一个游戏...
本想打个2048，限于能力，就照着半成品改成了这个。
Cmd输出太慢有点晃眼。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<conio.h>
#include<Windows.h>
using namespace std;

const int MAXC=100,MAXR=100;

class Game{
	int mat[MAXC][MAXR],dx[4],dy[4];
	bool f;
	int x,y,score,col,row,tar;
	private:
	void cls(){
		system("cls");
	}
	int dir(){
		char c1,c2;
		c1=getch(),c2=getch();
		switch(c2){
			case 72:return 0;//up
			case 75:return 1;//left
			case 77:return 2;//right
			case 80:return 3;//down
		}
	}
	void topblock(){
		printf("┌");
		for(int i=0;i<col-1;++i)
			printf("─┬");
		puts("─┐");
	}
	void buttonblock(){
		printf("└");
		for(int i=0;i<col-1;++i)
			printf("─┴");
		puts("─┘");
	}
	void commonblock(){
		printf("├");
		for(int i=0;i<col-1;++i)
			printf("─┼");
		puts("─┤");
	}
	public:
	Game(){
		memset(mat,0,sizeof mat);
		dx[0]=dy[1]=-1,dx[3]=dy[2]=1;
		dx[1]=dx[2]=dy[0]=dy[3]=0;
		mat[0][0]=1;
		x=0,y=0;
		tar='*';
		score=0;//initation 
		row=11,col=19;//settings
	}
	void start(){
		print();
		while(1){
			int t=dir(),nx=x+dx[t],ny=y+dy[t];
			if(nx>=0&&ny>=0&&nx<row&&ny<col){
				if(mat[nx][ny]==tar)
					f=0;
				mat[nx][ny]=mat[x][y];
				mat[x][y]=0;
				x=nx,y=ny;
				print();
				if(!f){
					nx=rand()%row,ny=rand()%col;
					if(!mat[nx][ny])
						mat[nx][ny]=tar,f=1;
				}
			}
		}
	}
	void print(){
		cls();
		topblock();
		for(int i=0;i<row;++i){
			printf("│");
			for(int j=0;j<col;++j){
				switch(mat[i][j]){
					case 0:printf("  │");break;
					default:printf("%2c│",mat[i][j]);
				}
			}
			puts("");
			if(i==row-1)
				buttonblock();
			else commonblock();
		}
	}
};

int main(){
	srand((unsigned)time(0));
	Game().start();
	return 0;
}

Strategic game树形DP解法(Poj1463,Uva1292)

发表于 2017-11-02 更新于 2021-04-29

已经写过本题用二分图的做法，见这儿。
本题的图是一棵树，求最小点覆盖也可以用树形DP的做法。
定义状态f[0/1][u]表示以u为根的子树，u选取/不选最少需要选取多少点来覆盖。
显然 f[0][u] = Sigma{f[1][v]},f[1][u] = Sigma{min(f[0][v],f[1][v])}+1 ( < u,v > 属于G且v!=u.father)

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=2000+5;
int hd[MAXN],outd[MAXN];
int n,cnt;
struct Edge
{
	int t,n;
}e[MAXN<<1];
int f[2][MAXN];

inline void build(int f,int t)
{
	e[++cnt]=(Edge){t,hd[f]};
	hd[f]=cnt;
	++outd[f];
}

void dfs(int u,int fa)
{
	for(int i=hd[u];i;i=e[i].n)
	{
		int v=e[i].t;
		if(v==fa)
			continue;
		dfs(v,u);
		f[0][u]+=f[1][v];
		f[1][u]+=min(f[1][v],f[0][v]);
	}
	++f[1][u];
}

int main()
{
	while(~scanf("%d",&n))
	{
		cnt=0;
		memset(hd,0,sizeof hd);
		memset(e,0,sizeof e);
		memset(f,0,sizeof f);
		memset(outd,0,sizeof outd);
		int to,from,m;
		for(int i=0;i<n;++i)
		{
			scanf("%d:(%d)",&from,&m);
			for(int i=1;i<=m;++i)
				scanf("%d",&to),build(from,to),build(to,from);
		}
		dfs(0,0);
		printf("%d\n",min(f[0][0],f[1][0]));
	}
	return 0;
}

[USACO08JAN]Haybale Guessing(LuoguP2898)

发表于 2017-11-01 更新于 2021-04-29

The cows, who always have an inferiority complex about their intelligence, have a new guessing game to sharpen their brains.A designated 'Hay Cow' hides behind the barn and creates N (1 ?? N ?? 1,000,000) uniquely-sized stacks (conveniently numbered 1..N) of hay bales, each with 1..1,000,000,000 bales of hay.The other cows then ask the Hay Cow a series of Q (1 ?? Q ?? 25,000) questions about the the stacks, all having the same form:What is the smallest number of bales of any stack in the range of stack numbers Ql..Qh (1 ?? Ql ?? N; Ql ?? Qh ?? N)?The Hay Cow answers each of these queries with a single integer A whose truthfulness is not guaranteed.Help the other cows determine if the answers given by the Hay Cow are self-consistent or if certain answers contradict others.
???鼯+?????
?????????ì????????
????е??????????????κ??????????????????????????С????????????н????????????????????ì???
??????????????????С?????С???????????ì???
?????????ж?????????С?
???????ì??????????????????????С???С????????鼯?????????????????????????????????????鼯???????????????????????????????????鼯????????????????????????????????????????????????????????????????????????δ????????????????????????????????????ì???

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

typedef long long ll;
#define rint register int

inline void getint(int &x)
{
	char c;
	for(c=getchar();c>'9'||c<'0';c=getchar());
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
}
const int MAXN=1000000+5;
struct Seg
{
	int l,r,v;
}e[MAXN];
int lim,n;
int srt[MAXN],fa[MAXN];

bool cmp(int a,int b)
{
	if(e[a].v==e[b].v)
		return e[a].l==e[b].l?e[a].r<e[b].r:e[a].l<e[b].l;
	return e[a].v>e[b].v;
}

int find(int x)
{
	return fa[x]==x?x:fa[x]=find(fa[x]);
}

bool check(int mid)
{
	for(rint i=1;i<=mid;++i)
		srt[i]=i;
	for(rint i=1;i<=lim;++i)
		fa[i]=i;
	sort(srt+1,srt+mid+1,cmp);
	int x,y;
	for(int i=1;i<=mid;++i)
	{
		int t=e[srt[i]].v,l=e[srt[i]].l,
                r=e[srt[i]].r,lm=e[srt[i]].l,rm=e[srt[i]].r;
		while(i+1<=mid&&t==e[srt[i+1]].v)
		{
			++i;
			if(e[srt[i]].l>r)
				return 0;
			l=max(l,e[srt[i]].l);
			r=min(r,e[srt[i]].r);
			lm=min(lm,e[srt[i]].l);
			rm=max(rm,e[srt[i]].r);
		}
		int x=find(l),y=find(r);
		if((l!=r&&x==y&&y!=r)||(l==r&&y!=r)) //??????ж?
			return 0;
		x=lm,y=rm;
		int rg=find(y+1);
		while(rg!=find(x))
		{
			int fx=find(x);
			fa[fx]=fa[fx+1];
		}
	}
	return 1;
}

int main()
{
	scanf("%d%d",&lim,&n);
	for(int i=1;i<=n;++i)
		getint(e[i].l),getint(e[i].r),getint(e[i].v);
	int l=1,r=n+1;
	while(r-l>1)
	{
		int mid=l+r>>1;
		if(check(mid))
			l=mid;
		else r=mid;
	}
	printf("%d",l==n?0:l+1);
	return 0;
}

计算系数(NOIP2011提高LuoguP1313)

发表于 2017-10-30 更新于 2021-04-29

一道数论好题，知识点涉及扩展欧几里得，快速幂，逆元，二项式定理，模运算，组合数等。
（~~别问为啥打了快速幂不用费马小求逆元...我就练习下扩欧~~）
（~~数据就应该再加大些卡掉n^2递推求组合数的~~）

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

typedef long long ll;
const int mod=10007;

void exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,x,y);
	ll t=x;
	x=y;
	y=t-a/b*y;
}

ll inv(ll a)
{
	ll x,y;
	exgcd(a,mod,x,y);
	return x;
}

ll fac(int x)
{
	ll ret=1;
	for(ll i=2;i<=x;++i)
		ret*=i,ret%=mod;
	return ret;
}

ll C(int a,int b)
{
	return (fac(a)*inv(fac(b)*fac(a-b))%mod+mod)%mod;
}

ll qpow(ll a,ll b)
{
	if(b==0)
		return 1;
	if(b==1)
		return a%mod;
	ll t=qpow(a,b>>1);
	t=(t*t)%mod;
	if(b&1)
		t=(t*a)%mod;
	return t;
}

int main()
{
	int a,b,k,n,m;
	scanf("%d%d%d%d%d",&a,&b,&k,&n,&m);
	printf("%lld",(ll)((C(k,m)*qpow(a,n)%mod)*qpow(b,m)%mod+mod)%mod);
	return 0;
}

Strategic game(无向)二分图最小点覆盖(Poj1463,Uva1292)

发表于 2017-10-27 更新于 2021-04-29

原题链接
此题求二分图的最小点覆盖，数值上等于该二分图的最大匹配。得知此结论可以将图染色，建有向图，然后跑匈牙利/网络流,如下。然而...

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=2000+5;
int q[MAXN],hd1[MAXN],hd2[MAXN];
int lnk[MAXN];
bool vis[MAXN],bw[MAXN];
int n,ft,rr,cnt1,cnt2;
struct Edge
{
	int t,n;
}e1[MAXN<<1],e2[MAXN<<1];

inline void build(int f,int t)
{
	e1[++cnt1]=(Edge){t,hd1[f]};
	hd1[f]=cnt1;
}

inline void build2(int f,int t)
{
	e2[++cnt2]=(Edge){t,hd2[f]};
	hd2[f]=cnt2;
}

void bfs()
{
	ft=rr=0;
	memset(bw,0,sizeof bw);
	memset(vis,0,sizeof vis);
	q[rr++]=0;
	vis[0]=1;
	bw[0]=1;
	while(ft<rr)
	{
		int u=q[ft++];
		for(int i=hd1[u];i;i=e1[i].n)
		{
			int v=e1[i].t;
			if(!vis[v])
			{
				vis[v]=1;
				bw[v]=bw[u]^1;
				q[rr++]=v;
			}
		}
	}
}

bool match(int u)
{
	for(int i=hd2[u];i;i=e2[i].n)
	{
		int v=e2[i].t;
		if(!vis[v])
		{
			vis[v]=1;
			if(lnk[v]==-1||match(lnk[v]))
			{
				lnk[v]=u;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	while(~scanf("%d",&n))
	{
		cnt1=cnt2=0;
		memset(hd1,0,sizeof hd1);
		memset(e1,0,sizeof e1);
		memset(e2,0,sizeof e2);
		memset(hd2,0,sizeof hd2);
		memset(lnk,-1,sizeof lnk);
		
		int from,m,to;
		for(int i=0;i<n;++i)
		{
			scanf("%d:(%d)",&from,&m);
			for(int i=1;i<=m;++i)
				scanf("%d",&to),build(from,to),build(to,from);
		}
		bfs();
		for(int k=0;k<n;++k)
		{
			if(bw[k])
			{
				for(int i=hd1[k];i;i=e1[i].n)
					build2(k,e1[i].t);
			}
		}
		int ans=0;
		for(int i=0;i<n;++i)
		{
			if(bw[i])
			{
				memset(vis,0,sizeof vis);
				if(match(i))
					++ans;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

然而我看网络上流传的都是另一种做法，直接输出在原无向图的最大匹配除以2，却很少有人证明（~~可能是各位大佬都认为这太显然了不用证~~）。仔细思考这个结论还是比较显然的（~~虽然我还想了一会~~），这里给出简单的证明，原来匹配一次的边被分别从从左右两个方向匹配了一次，这样每天匹配边就被记录了两次，又因为是求得的是最大匹配数，所以左右两边的匹配都应是最大匹配，故求给定无向图求最大匹配可以直接在原图求最大匹配，答案为该数值除以2。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int MAXN=2000+5;
int hd[MAXN],lnk[MAXN];
bool vis[MAXN];
int n,cnt;
struct Edge
{
	int t,n;
}e[MAXN<<1];

inline void build(int f,int t)
{
	e[++cnt]=(Edge){t,hd[f]};
	hd[f]=cnt;
}

bool match(int u)
{
	for(int i=hd[u];i;i=e[i].n)
	{
		int v=e[i].t;
		if(!vis[v])
		{
			vis[v]=1;
			if(lnk[v]==-1||match(lnk[v]))
			{
				lnk[v]=u;
				return 1;
			}
		}
	}
	return 0;
}

int main()
{
	while(~scanf("%d",&n))
	{
		cnt=0;
		memset(hd,0,sizeof hd);
		memset(e,0,sizeof e);
		memset(lnk,-1,sizeof lnk);
		int from,m,to;
		for(int i=0;i<n;++i)
		{
			scanf("%d:(%d)",&from,&m);
			for(int i=1;i<=m;++i)
				scanf("%d",&to),build(from,to),build(to,from);
		}
		int ans=0;
		for(int i=0;i<n;++i)
		{
			memset(vis,0,sizeof vis);
			if(match(i))
				++ans;
		}
		printf("%d\n",ans>>1);
	}
	return 0;
}

还有DP解法，待填。
11.02UPD 树形DP解法

NOIP2012 疫情控制题解（LuoguP1084）

发表于 2017-10-24 更新于 2021-04-29

NOIP2012 疫情控制题解（LuoguP1084）

不难发现，如果一个点向上移动一定能控制更多的点，所以可以二分时间，判断是否可行。
但根节点不能不能控制，存在以当前时间可以走到根节点的点，可使向下走到深度为2的节点控制其他点，此时又可以进行另一个贪心，优先选择走到根节点还能再走的时间小的去控制深度一到二之间边权较小的。
某大佬有更加详尽的讲解，参见这里

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

typedef long long ll;
const int MAXN=50000+5;
int anc[21][MAXN];
ll tab[21][MAXN];
struct Edge
{
	int t,v,n;
}e[MAXN<<1];
int cnt,n,m,scnt;
int rsn[MAXN],siz[MAXN],army[MAXN],hd[MAXN],frm[MAXN];
bool cvef[MAXN],cover[MAXN];
typedef pair<int,int> pii;
pii a[MAXN],c[MAXN];

inline void build(int f,int t,int v)
{
	e[++cnt]=(Edge){t,v,hd[f]};
	hd[f]=cnt;
}

void dfs1(int u)
{
	if(anc[0][u]==1)
		frm[u]=u;
	else frm[u]=frm[anc[0][u]];
	for(int i=hd[u];i;i=e[i].n)
	{
		int v=e[i].t;
		if(v==anc[0][u])
			continue;
		++siz[u];
		anc[0][v]=u;
		tab[0][v]=e[i].v;
		for(int i=1;anc[i-1][v];++i)
		{
			anc[i][v]=anc[i-1][anc[i-1][v]];
			tab[i][v]=tab[i-1][v]+tab[i-1][anc[i-1][v]];
		}
		dfs1(v);
	}
}

void dfs2(int u)
{
	cvef[u]=1;
	if(siz[u]>1)
		return;
	for(int i=hd[u];i;i=e[i].n)
		if(e[i].t!=anc[0][u])
			dfs2(e[i].t);
}
void initrt()
{
	for(int i=hd[1];i;i=e[i].n)
	{
		int v=e[i].t;
		rsn[++scnt]=v;
		dfs2(v);
	}
}

bool check(ll mid)
{
	memset(cover,0,sizeof cover);
	int cntc=0,cnta=0;
	for(int i=1;i<=m;++i)
	{
		ll tmp=mid;
		int pos=army[i];
		for(int j=20;j>=0;--j)
		{
			if(anc[j][pos]&&tmp>=tab[j][pos])
			{
				tmp-=tab[j][pos];
				pos=anc[j][pos];
			}
		}
		if(pos!=1)
		{
			if(cvef[pos])
				cover[frm[pos]]=1;
		}
		else
			a[++cnta]=pii(tmp,frm[army[i]]);
	}
	for(int i=1;i<=scnt;++i)
	{
		if(!cover[rsn[i]])
			c[++cntc]=pii(tab[0][rsn[i]],rsn[i]);
	}
	if(cntc>cnta)
		return 0;
	sort(a+1,a+cnta+1);
	sort(c+1,c+cntc+1);
	int j=1;
	int t=cntc;
	for(int i=1;i<=cnta;++i)
	{
		if(!cover[a[i].second])
			cover[a[i].second]=1,--t;
		else
		{
			while(j<=cntc&&cover[c[j].second])
				++j;
			if(a[i].first>=c[j].first)
				cover[c[j].second]=1,++j,--t;
		}
	}
	if(t>0)
		return 0;
	return 1;
}

int main()
{
	scanf("%d",&n);
	int x,y,z;
	ll l=0,r=0;
	for(int i=1;i<n;++i)
	{
		scanf("%d%d%d",&x,&y,&z);
		build(x,y,z);
		build(y,x,z);
		r+=z;
	}
	scanf("%d",&m);
	for(int i=1;i<=m;++i)
		scanf("%d",&army[i]);
	dfs1(1);
	initrt();
	if(m<scnt)
	{
		puts("-1");
		return 0;
	}
	while(r-l>1)
	{
		ll mid=l+r>>1;
		if(check(mid))
			r=mid;
		else
			l=mid;
	}
	printf("%lld",r);
	return 0;	
}

~~看来是只是贪心二分等基础算法我也不会QAQ~~

1

2

NOIP2012 疫情控制 题解（LuoguP1084）

NOIP2012 疫情控制题解（LuoguP1084）