不知道什么的复习题

P4408 [NOI2003] 逃学的小孩，一眼就看出要化简题面：不就是找三个点使得AB+BC最大嘛，不妨想起直径的性质，最长，而且其他点到它的距离最长。那么直接拿直径来做就行。推导出结论为ans=max(min(dis[A][k],dis[B][k])+dis[A][B]);那么直接求直径算就行，我们尝试贪心的选择路径就行了。

#include
#define int long long 
using namespace std;
int n,m,len=0,last[250001],dis[3][250001],A,B;
struct pp
{
	int x,y,c,next;
};pp p[250001];
void ins(int x,int y,int c)
{
	int now=++len;
	p[now]={x,y,c,last[x]};last[x]=now;
	return ;
}
void dfs1(int x,int fa)
{
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;if(y==fa) continue ;
		dis[0][y]=dis[0][x]+p[i].c;dfs1(y,x);
	}
	if(dis[0][x]>dis[0][A]) A=x;
	return ;
} 
void dfs2(int x,int fa)
{
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;if(y==fa) continue ;
		dis[0][y]=dis[0][x]+p[i].c;dfs2(y,x);
	}
	if(dis[0][x]>dis[0][B]) B=x;
	return ;
}
void dfs3(int x,int fa,int k)
{
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;if(y==fa) continue ;
		dis[k][y]=dis[k][x]+p[i].c;dfs3(y,x,k);
	}
	return ;
}
signed main()
{
	memset(last,-1,sizeof(last));
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++) 
	{
		int x,y,c;scanf("%lld%lld%lld",&x,&y,&c);
		ins(x,y,c);ins(y,x,c);
	}
	dfs1(1,1);memset(dis[0],0,sizeof(dis[0]));dfs2(A,A);
	dfs3(A,A,1);dfs3(B,B,2);int ans=0;
	for(int i=1;i<=n;i++) ans=max(min(dis[1][i],dis[2][i])+dis[0][B],ans);
	printf("%lld\n",ans); 
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

P3225 [HNOI2012]矿场搭建呃复习一下割点以及不知道什么东西的做法。讨论一下就行,发现一定能在缩完之后得到一颗树，那么不妨推敲一下每种情况的不同。

#include
#define int long long 
using namespace std;
int n,m,len=0,last[100001],dfsx[100001],low[100001],dfs_x=0,id[100001],point=0,sum,num;
bool v[100001];
struct pp
{
	int x,y,next;
};pp p[100001];
void ins(int x,int y)
{
	int now=++len;
	p[now]={x,y,last[x]};last[x]=now;
	return ;
}
void CNT(int x,int dd) 
{
	int ch=0;dfsx[x]=low[x]=++dfs_x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y])
		{
			CNT(y,dd);low[x]=min(low[x],low[y]);//考虑从最上面的点过来	 
			if(low[y]>=dfsx[x]&&dd!=x) v[x]=true;//如果有一个点能被断掉 
			if(x==dd) ch++;//根的情况 
		}
		low[x]=min(low[x],dfsx[y]);//取一手最小值 
	}
	if(ch>=2) v[x]=true;//如果是根的话 
	return ;
}
void dfs(int x)
{
    id[x]=point;//标记 
    if(v[x]) return;
    sum++;//	printf("*");
    for(int i=last[x];i!=-1;i=p[i].next)
    {
        int y=p[i].y;
        if(v[y]&&id[y]!=point) num++,id[y]=point;//统计割点数目。 
        //如果是割点且标记不与遍历的的连通块相同就修改标记。 
        if(!id[y]) dfs(y);
    }
}
signed main()
{
	int tot=0;
	while(scanf("%lld",&n))
	{
		if(!n) break ;int ans1=0,ans2=1,maxx=0 ;
		memset(low,0,sizeof(low));memset(last,-1,sizeof(last));memset(id,0,sizeof(id));
		memset(dfsx,0,sizeof(dfsx));memset(p,0,sizeof(p));memset(v,false,sizeof(v));len=0;dfs_x=0;point=0;
		for(int i=1;i<=n;i++)
		{
			int x,y;scanf("%lld%lld",&x,&y);
			ins(x,y);ins(y,x);maxx=max(max(x,y),maxx);
		}
		for(int i=1;i<=maxx;i++) if(!dfsx[i]) CNT(i,i);
		for(int i=1;i<=maxx;i++)
		{
			if(!v[i]&&!id[i]) 
			{
				point++;num=sum=0;dfs(i);//printf(">>%d\n",point);
				if(!num) ans1+=2,ans2*=sum*(sum-1)/2;
				if(num==1) ans1++,ans2*=sum;
			}
		}
		printf("Case %lld: %lld %lld\n",++tot,ans1,ans2);
	}
	return 0;	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

P1273 有线电视网，烦人的树形背包，差点没搞出来。一般看到不能直接从上一个点转移的东西，直接状压或者背包好了。气死！注意有一个小细节，每次u合并儿子son的背包时，两层循环中，外层只循环到u在遍历到son之前的叶节点总数，son只循环到son自己子树内的叶节点总数 。那么你的时间是n^2，要是你枚举上当前节点的，那时间就是n ^ 3了。这样复杂度就假了。那么不妨枚举选取了多少个节点，明显可以转移钱。最后再枚举一下就好。https://blog.csdn.net/no1_terminator/article/details/77824790推荐

#include
using namespace std;
int n,m,len=0,last[100001],siz[100001],f[4000][4000],tmp[4000],val[4000];
struct pp
{
	int x,y,c,next;
};pp p[100001];
void ins(int x,int y,int c)
{
	int now=++len;
	p[now]={x,y,c,last[x]};last[x]=now;
	return ;
}
void dfs(int x,int fa)
{
	if(x>=n-m+1)
	{
		siz[x]=1;f[x][1]=val[x];
		return ;
	}
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;if(y==fa) continue ;dfs(y,x);
		for(int j=0;j<=siz[x];j++) tmp[j]=f[x][j];
		for(int j=0;j<=siz[x];j++)
		{
			for(int k=0;k<=siz[y];k++) f[x][j+k]=max(f[x][j+k],tmp[j]+f[y][k]-p[i].c);//printf("%d\n",f[x][j+k]);
		}
		siz[x]+=siz[y];
	}
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));memset(f,~0x3f,sizeof(f));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-m;i++)
	{
		int x;scanf("%d",&x);
		for(int j=1;j<=x;j++) 
		{
			int y,c;scanf("%d%d",&y,&c);
			ins(i,y,c);
		}
	}
	for(int i=n-m+1;i<=n;i++) scanf("%d",&val[i]);
	for(int i=1;i<=n;i++) f[i][0]=0;
	dfs(1,1);int ans=0;
	for(int i=m;i>=1;i--)
	{//printf("%d  ",f[1][i]);
		if(f[1][i]>=0) 
		{
			printf("%d",i);
			return 0;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

P2656 采蘑菇

#include
using namespace std;
int n,m,len=0,last[100001],dfsx[100001],low[100001],dfs_x=0,id[100001],point=0;
int q[100001],top=0,siz[100001],f[100001],ans=0;bool v[100001];
struct pp
{
	int x,y,c,next,val,re;
};pp p[400001],L[400001];
int getval(int x,int k)
{
	int tot=0;
	while(x) tot+=x,x=x*k/10;
	return tot;
}
void ins(int x,int y,int c)
{
	int now=++len;
	p[now]={x,y,c,last[x]};last[x]=now;
	return ;
}
void SH(int x)
{
	dfsx[x]=low[x]=++dfs_x;
	v[x]=true;q[++top]=x;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		if(!dfsx[y]) SH(y),low[x]=min(low[x],low[y]);
		else if(v[y]) low[x]=min(low[x],dfsx[y]);
	}
	if(dfsx[x]==low[x])
	{
		point++;
		while(dfsx[x]<=dfsx[q[top]])
		{
			id[q[top]]=point;v[q[top]]=false;
			top--,dfs_x--;
		}
	}
	return ;
} 
bool cmp(const pp &x,const pp &y)
{
	if(x.x!=y.x) return x.x<y.x;
	return x.y<y.y;
}
void remake()
{
	memset(last,-1,sizeof(last));len=0;memset(p,0,sizeof(p));
	for(int i=1;i<=m;i++) L[i].x=id[L[i].x],L[i].y=id[L[i].y];
	sort(L+1,L+m+1,cmp);
	for(int i=1;i<=m;i++)
	{
		if(L[i].x==L[i].y) siz[L[i].x]+=getval(L[i].val,L[i].re);
		else ins(L[i].x,L[i].y,L[i].val);
	}
	return ;
}
void dfs(int x)
{
	if(f[x]) return ;
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;
		dfs(y);f[x]=max(f[x],f[y]+p[i].c);
	}
	f[x]+=siz[x];
	return ;
}
int main()
{
	memset(last,-1,sizeof(last));memset(f,0,sizeof(f));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int x,y,val,re;double k;scanf("%d%d%d%lf",&x,&y,&val,&k);
		re=k*10;ins(x,y,0);L[i].x=x,L[i].y=y,L[i].val=val,L[i].re=re;
	}
	int ST;scanf("%d",&ST);
	for(int i=1;i<=n;i++) if(!dfsx[i]) SH(i);
	remake();dfs(id[ST]);printf("%d",f[id[ST]]);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

P2619 [国家集训队]Tree I，奇怪的二分，但是看得出来在限定范围内求最小，那么考虑从选择的边的边权入手，考虑贪心的选择但是这样是错误的，具体的可以自己举一个反例。如果，在当前情况下，如若白点的边数不够的话，说明它的白的整体边权过大了。那么我们让所有的白边减去一个(x)， 就会导致，顺序变换，那么就会改变选择的边。刚刚在想，要是选择的白边多了怎么办，完全没问题，因为可以继续减。

#include
using namespace std;
int n,m,need,fa[100001];
struct pp
{
	int x,y,c,color;
};pp p[1000001];
int findfa(int x)
{
	if(fa[x]==x) return x;
	return fa[x]=findfa(fa[x]);
}
int check()
{
	int tot=0,num=0,rt=0;
	for(int i=1;i<=m;i++)
	{
		int x=p[i].x,y=p[i].y,fx=findfa(x),fy=findfa(y);
		if(fx!=fy) rt+=p[i].c,tot+=(p[i].color^1),fa[fx]=fy,num++;
		if(num==n-1)break;
	}
	if(tot>=need) return rt;
	return 0;
}
bool cmp(const pp &x,const pp &y)
{
	if(x.c==y.c) return x.color<y.color;
	return x.c<y.c;	
}
void remake(int val)
{
	for(int i=0;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) if(!p[i].color) p[i].c+=val;
	sort(p+1,p+m+1,cmp);
	return ;
}
int main()
{
	scanf("%d%d%d",&n,&m,&need);
	int l=-111,r=111,ans;
	for(int i=1;i<=m;i++) scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].c,&p[i].color);//l-=min(p[i].c,0),r+=max(0,p[i].c);
	while(l<=r)
	{
		int mid=(l+r)/2;
		remake(mid);
		if(check()) ans=mid,l=mid+1;
		else r=mid-1;
		remake(-mid);
	}
	remake(ans);
	printf("%d",check()-ans*need);
	return 0;
}	
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

要不我们去做国集的题目吧虽然看起来很难：P3918 [国家集训队]特技飞行。这个比较简单不难发现无论怎么摆放动作，一个动作的贡献都是c*abs（第一次做-最后一次做），那么我们直接排列就行。

#include
using namespace std;
int n,m,a[100001],ans=0,tot=0;
bool cmp(const int &x,const int &y)
{
	return x>y;
}
int main()
{
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+n+1,cmp);
	for(int i=1;i<=min(m/2,n);i++) tot++,ans+=(a[i]*(m-tot*2+1));
	printf("%d",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

P1499 [CTSC2000]公路巡逻呃这个算了。
P1792 [国家集训队]种树一眼dp发现会爆炸，那么直接看题解，大佬说：可反悔贪心！我哈哈大笑，根本不会。问题不大，不妨维护一个大根堆，对于每一个选取的节点，将其的左右两个节点的val-它的val的和插入进去，那么就可以做到反悔了。

#include 
using namespace std;
int n,m,a[220000],pre[220000],net[220000],ans=0;bool v[220000];
struct node
{
	int id,val;
	friend bool operator <(const node &x,const node &y)
	{
		return x.val < y.val;	
	};
};priority_queue<node > q;
void dl(int now)
{
	pre[now]=pre[pre[now]];net[now]=net[net[now]];
	net[pre[now]]=now;pre[net[now]]=now;
	return ;
}
int main()
{
	memset(v,false,sizeof(v));
	scanf("%d%d",&n,&m);
	if(n/2<m) 
	{
		printf("Error!");return 0;
	}
	for(int i=1;i<=n;i++) 
	{
		scanf("%d",&a[i]),pre[i]=i-1,net[i]=i+1;
		node e;e.id=i,e.val=a[i],q.push(e);
	}
	pre[1]=n;net[n]=1;
	for(int i=1;i<=m;i++)
	{
		while(v[q.top().id]) q.pop();
		node now=q.top();q.pop();
		a[now.id]=a[pre[now.id]]+a[net[now.id]]-a[now.id];v[pre[now.id]]=v[net[now.id]]=true;
		node e;e.val=a[now.id];e.id=now.id;q.push(e);
		ans+=now.val;dl(now.id);
	}
	printf("%d",ans);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

明天需要做点：dp+数据结构+字符串。

P2634 [国家集训队]聪聪可可,树形dp，明显的性质，一个合法情况中肯定可以由两个情况组成，比如说3%3=(1+2)%3，那么直接转移上去%3意义下权值的就行了。注意了，要计算上自己与子树中匹配的点的次数，还有！因为点对有序，所以要*2。

#include
using namespace std;
int n,m,len=0,last[1000001],f[100001][4],ans=-0;
struct pp
{
	int x,y,c,next;
};pp p[1000001];
void ins(int x,int y,int c)
{
	int now=++len;
	p[now]={x,y,c,last[x]};last[x]=now;
	return ;
}
void dp(int x,int fa)
{
	f[x][0]=1;//printf("*");
	for(int i=last[x];i!=-1;i=p[i].next)
	{
		int y=p[i].y;if(y==fa) continue ;
		dp(y,x);
		for(int j=0;j<=2;j++) ans+=f[y][j]*f[x][(3-((j+p[i].c)%3+3)%3)%3]*2;
		for(int j=0;j<=2;j++) f[x][(p[i].c+j+3)%3]+=f[y][j];
	}
	return ;
}

int main()
{
	memset(last,-1,sizeof(last));
	scanf("%d",&n);
	for(int i=1;i<=n-1;i++)
	{
		int x,y,c;scanf("%d%d%d",&x,&y,&c);
		ins(x,y,c);ins(y,x,c);
	}
	dp(1,1);ans+=n; 
	int k=__gcd(ans,n*n);
	printf("%d/%d",ans/k,n*n/k);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

P1412 经营与开发这种dp有后效性，那么不妨考虑倒着做，就是从后往前做。遇到有后效性的dp多考虑考虑正难则反，那么反着做就很简单了就是简单的从后往前，如果会取一个点，那么就会对后面造成影响，那么f[i+1]*(…)如果不，那么就直接继承即可。
这个思路想想就懂，但不懂。

#include
using namespace std;
double n,m,f[100001],a[100001],k,c,w,p[100001];
int main()
{
	scanf("%lf%lf%lf%lf",&n,&k,&c,&w);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i],&a[i]);
	for(int i=n;i>=1;i--)
	{
		if(p[i]==1) f[i]=max(f[i+1],f[i+1]*(1-0.01*k)+a[i]);
		else f[i]=max(f[i+1],f[i+1]*(1+0.01*c)-a[i]);
	}
	printf("%.2lf",f[1]*w);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15