bef-> NO.24

Veröffentlicht am

[POI2008]BLO-Blockade

题意翻译

在Byteotia有n个城镇。 一些城镇之间由无向边连接。 在城镇外没有十字路口，尽管可能有桥，隧道或者高架公路（反正不考虑这些）。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。 每个城镇都有一个公民，他们被孤独所困扰。事实证明，每个公民都想拜访其他所有公民一次（在主人所在的城镇）。所以，一共会有n*（n-1）次拜访。

不幸的是，一个程序员总罢工正在进行中，那些程序员迫切要求购买某个软件。

作为抗议行动，程序员们计划封锁一些城镇，阻止人们进入，离开或者路过那里。

正如我们所说，他们正在讨论选择哪些城镇会导致最严重的后果。

编写一个程序：

读入Byteotia的道路系统，对于每个被决定的城镇，如果它被封锁，有多少访问不会发生，输出结果。

输入输出格式

第一行读入n，m，分别是城镇数目和道路数目

城镇编号1~n

接下来m行每行两个数字a,b，表示a和b之间有有一条无向边

输出n行，每行一个数字，为第i个城镇被锁时不能发生的访问的数量。

1
2
3
@[chen_zhe](/space/show?uid=8457)

翻译提供者：Park

题目描述

There are exactly nn towns in Byteotia.

Some towns are connected by bidirectional roads.

There are no crossroads outside towns, though there may be bridges, tunnels and flyovers. Each pair of towns may be connected by at most one direct road. One can get from any town to any other-directly or indirectly.

Each town has exactly one citizen.

For that reason the citizens suffer from loneliness.

It turns out that each citizen would like to pay a visit to every other citizen (in his host’s hometown), and do it exactly once. So exactly n\cdot (n-1)n⋅(n−1) visits should take place.

That’s right, should.

Unfortunately, a general strike of programmers, who demand an emergency purchase of software, is under way.

As an act of protest, the programmers plan to block one town of Byteotia, preventing entering it, leaving it, and even passing through.

As we speak, they are debating which town to choose so that the consequences are most severe.

Task Write a programme that:

reads the Byteotian road system’s description from the standard input, for each town determines, how many visits could take place if this town were not blocked by programmers, writes out the outcome to the standard output.

给定一张无向图，求每个点被封锁之后有多少个有序点对(x,y)(x!=y,1<=x,y<=n)满足x无法到达y

输入输出格式

输入格式：

In the first line of the standard input there are two positive integers: nn and mm (1\le n\le 100\ 0001≤n≤100 000, 1\le m\le 500\ 0001≤m≤500 000) denoting the number of towns and roads, respectively.

The towns are numbered from 1 to nn.

The following mm lines contain descriptions of the roads.

Each line contains two integers aa and bb (1\le a<b\le n1≤a<b≤n) and denotes a direct road between towns numbered aaand bb.

输出格式：

Your programme should write out exactly nn integers to the standard output, one number per line. The i^{th}ith line should contain the number of visits that could not take place if the programmers blocked the town no. ii.

输入输出样例

输入样例#1：

1
2
3
4
5
6
5 5
1 2
2 3
1 3
3 4
4 5

输出样例#1：

1
2
3
4
5
8
8
16
14
8

题解

这个题显然上来思路之一就是割点。

显然每个点的答案都是它分成的联通块大小的卷积加上它自己的n-1次访问（当然还要乘二）。

然后我们发现假如每个割点我们都并查集暴力合并，时间复杂度是

会超时。

然后我yy出一种做法。

我们可以在dfs序的这棵树上做dp。。

考虑以x为跟的子树中有多少个不能回溯到x祖先的点（同一颗子树有一个能那么这颗子树都能）。

由割点定义可知割点的的子树中至少存在一颗子树保证子树内所有点都不能回溯到割点的祖先。

因此我们统计的时候可以直接卷积乘。

但是假如数据是菊花图就变成

了。。

因此记录子树节点数相同的个数，这样就有了根号优化。

注意能回溯到当先点的祖先的子树的大小应加到

中，v即是这颗子树的根

代码突然不想写，有时间再补吧。。

数列求和

题目描述

求数列

的前 n 项和

输入输出格式

输入格式：

输入共 1 行，包含 3 个非负整数： n，a，k

输出格式：

输出共 1 行，包含 1 个非负整数：

输入输出样例

输入样例#1：

1
3 4 0

输出样例#1：

1
84

输入样例#2：

1
3 10 1

输出样例#2：

1
3210

输入样例#3：

1
3 9 2

输出样例#3：

1
6894

说明

Luogu

题解

这道题似乎只要想到按照k递推就不难了。递推中没必要带上n，因为n在这个递推式中是很好处理的。

即

又

注意到 j < kj<k 可以

递推

特殊地，

中间无非是二项式定理展开后利用定比a错位相减，最后再错位相减一次即可

最短距离

题目描述

给出一个 {N}N 个点 {N}N 条边的无向连通图。

你需要支持两种操作：

  1. 修改 第 {x}x 条边的长度为 {y}y ；
  2. 查询 点 {x}x 到点 {y}y 的最短距离。

共有 {M}M 次操作。

输入输出格式

输入格式：

输入共 N + M + 1 行：

第 1 行，包含 2 个正整数 N，M，表示点数即边数，操作次数。

第 2 行到第 N + 1 行，每行包含 3 个正整数 x，y，z，表示 x 与 y 间有一条长度 为 z 的边。

第 N + 2 到 N + M + 1 行，每行包含 3 个正整数 opt，x，y，表示操作种类，操作的参数（含义见【题目描述】）。

输出格式：

对于每次操作 2 输出查询的结果。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
9
10
4 5
1 2 11
1 3 12
2 3 13
1 4 15
2 2 3
1 2 1
2 2 3
2 2 4
2 3 4

输出样例#1：

1
2
3
4
13
12
26
16

说明

Luogu

题解：

一开始以为有神器做法。结果发现就是找环后用线段树/树状数组维护环，对每颗以还上点为根的树用HPD（也可以用树状数组实现HPD。。），然后查询修改就好了。。

[USACO5.3]校园网Network of Schools

题目描述

一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 B 在 A 学校的分发列表中， A 也不一定在 B 学校的列表中。

你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。

输入输出格式

输入格式：

输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。

接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。

输出格式：

你的程序应该在输出文件中输出两行。

第一行应该包括一个正整数：子任务 A 的解。

第二行应该包括子任务 B 的解。

输入输出样例

1
2
3
4
5
6
5
2 4 3 0
4 5 0
0
0
1 0

输出样例#1：

1
2
1
2

说明

题目翻译来自NOCOW。

USACO Training Section 5.3

题解

读了半天题才看明白它想让你求什么。。

缩点后入度为0的点数和出度为0与入度为0的点数的较大值

Tarjan缩点

Code:

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
84
85
86
87
88
89
90
91
92
// luogu-judger-enable-o2
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <stack>
#define maxn 205
#define maxm maxn * maxn
std::stack<int> st;
int head[maxn] , cnt , scc[maxn] , n , m , dfn[maxn] , low[maxn] , tot , idx , rbz , ans1 , ans2 ,t[maxn] , d[maxn];
bool vis[maxn][maxn] , ins[maxn];
struct edge{
	int next , to;
}e[maxm*2];
struct use{
	int from , to;
}er[maxm*2];
inline void add(int x, int y)
{
	e[++cnt].next = head[x];
	e[cnt].to  =y;
	head[x] = cnt;
	++t[x];
	++d[y];
}
void Tarjan(int x)
{
	dfn[x] = low[x] = ++idx;
	st.push(x);
	ins[x] = true;
	for(int i = head[x] ; i ; i = e[i].next)
	{
		if(!dfn[e[i].to])
		{
			Tarjan(e[i].to);
			low[x] = std::min(low[x] , low[e[i].to]);
		}
		else if(ins[e[i].to])	low[x] = std::min(low[x] , dfn[e[i].to]);
	}
	if(dfn[x] == low[x])
	{
		++tot;
		while(st.top() != x)
		{
			scc[st.top()] = tot;
			ins[st.top()] = false;
			st.pop();
		}
		scc[st.top()] = tot;
		ins[st.top()] = false;
		st.pop();

	}
}
int main()
{
	scanf("%d",&n);
	int x;
	for(int i = 1 ; i <= n ; ++i)
	{
		while(scanf("%d",&x))
		{
			if(!x) break;
			add(i,x) , er[++rbz].from = i , er[rbz].to = x;
		}
	}
	for(int i = 1 ; i <= n ; ++i)
		if(!dfn[i])	Tarjan(i);
	std::memset(head,0,sizeof(head));
	std::memset(e,0,sizeof(e));
	std::memset(t,0,sizeof(t));
	std::memset(d,0,sizeof(d));
	cnt = 0;
	for(int i = 1 ; i <= rbz ; ++i)
	{
		if(scc[er[i].from] == scc[er[i].to]) continue;
		add(scc[er[i].from]  , scc[er[i].to]);
//		printf("%d : %d %d\n",i,scc[er[i].from] , scc[er[i].to]);
	}
	for(int i = 1 ; i <= tot ; ++i)
	{
		if(!d[i])	++ans1;
		if(!t[i])	++ans2;
	}
	if(tot == 1)
	{
		printf("%d\n",ans1);
		return 0;
	}
	printf("%d\n",ans1);
}

[USACO14FEB]路障Roadblock

题目描述

每天早晨，FJ从家中穿过农场走到牛棚。农场由 N 块农田组成，农田通过 M 条双向道路连接，每条路有一定长度。FJ 的房子在 1 号田，牛棚在 N 号田。没有两块田被多条道路连接，以适当的路径顺序总是能在农场任意一对田间行走。当FJ从一块田走到另一块时，总是以总路长最短的道路顺序来走。

FJ 的牛呢，总是不安好心，决定干扰他每天早晨的计划。它们在 M 条路的某一条上安放一叠稻草堆，使这条路的长度加倍。牛希望选择一条路干扰使得FJ 从家到牛棚的路长增加最多。它们请你设计并告诉它们最大增量是多少。

输入输出格式

输入格式：

第 1 行：两个整数 N, M。

第 2 到 M+1 行：第 i+1 行包含三个整数 A_i, B_i, L_i，A_i 和 B_i 表示道路 i 连接的田的编号，L_i 表示路长。

输出格式：

第 1 行：一个整数，表示通过使某条路加倍而得到的最大增量。

输入输出样例

输入样例#1：

1
2
3
4
5
6
7
8
5 7
2 1 5
1 3 1
3 2 8
3 5 7
3 4 3
2 4 7
4 5 2

输出样例#1：

1
2

说明

【样例说明】

若使 3 和 4 之间的道路长加倍，最短路将由 1-3-4-5 变为 1-3-5。

【数据规模和约定】

对于 30%的数据，N <= 70，M <= 1,500。

对于 100%的数据，1 <= N <= 100，1 <= M <= 5,000，1 <= L_i <= 1,000,000。

题解

这道简单的最短路+路径记录做了不少时间，不过有所收获。

首先对结构体运用的更灵活了，在结构体里的重载运算符终于能写对了。感谢UOJ大佬告诉我括号后面加const就可以了。

显然有个小结论，对于1~n的最短路，设n的前驱为x，则1~n的最短路一定包括了1~x的最短路（可以反证法）。

这样我们就让优先队列的元素多记录个前驱即可。每个点第一次出队时即为最短路，记录前驱。

最后枚举最短路上的每条边处理后最短路。

可以证明一个没有负环的图单源最短路最多有n-1条边。

Code:

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
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <queue>
#define maxn 105
#define maxm 5050
int n , m , head[maxn] , cnt = 1 , d[maxn] , next[maxn] , tot , ans = -0x7fffffff , minn , edge[maxm*2] , way[maxm*2];
bool vis[maxn];
struct Node{
	int val , ver , pre , edge;
	bool operator > (const Node &x)const{
		return val > x.val;
	}
	bool operator < (const Node &x)const{
		return val < x.val;
	}
};
struct edge{
	int next , to , dis;
}e[maxm * 2];
inline void add(int x , int y , int dis)
{
	e[++cnt].next = head[x];
	e[cnt].to = y;
	e[cnt].dis = dis;
	head[x] = cnt;
}
inline void SPDIJ(int s , int rec)
{
	std::memset(d,0x7f,sizeof(d));
	std::memset(vis,false,sizeof(vis));
	d[s] = 0;
	std::priority_queue<Node , std::vector<Node> , std::greater<Node> > q;
	q.push((Node){d[s],s,0,0});
	while(!q.empty())
	{
		int k = q.top().ver , x = q.top().pre , y = q.top().edge;
		q.pop();
		if(vis[k]) continue;
		if(rec){
			next[k] = x;
			edge[k] = y;
		}
		vis[k] = true;
		for(int i = head[k] ; i ; i = e[i].next)
			if(d[k] + e[i].dis < d[e[i].to])
				d[e[i].to] = d[k] + e[i].dis , q.push((Node){d[e[i].to] , e[i].to , k , i});
	}
	if(rec)
	{
		int k = n;
		while(k != s){
			way[++tot] = edge[k];
			k = next[k];
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	int x , y, dis;
	for(int i = 1 ; i <= m ; ++i)
		scanf("%d%d%d",&x,&y,&dis) , add(x,y,dis) , add(y,x,dis);
	SPDIJ(1,1);
	minn = d[n];
	for(int i = 1 ; i <= tot ; ++i)
	{
		if(way[i] == 0) continue;
		e[way[i]].dis = e[way[i]^1].dis = 2 * e[way[i]].dis;
		SPDIJ(1,0);
//		printf("%d\n",d[n]-minn);
		ans = std::max(ans , d[n] - minn);
		e[way[i]].dis = e[way[i]^1].dis = e[way[i]].dis / 2;
	}
	printf("%d",ans);
}

今天感觉到了深深的危机感啊。。

论代码能力，时间复杂度写了1小时最后交上去也就20多分。

论思维能力，POI的题可以说不会几道（联赛过后必刷POI，联赛前复习基础）。

还需要努力啊。

[NOI2001]炮兵阵地

题目描述

司令部的将军们打算在NM的网格地图上部署他们的炮兵部队。一个NM的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：

img

如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。

输入输出格式

输入格式：

第一行包含两个由空格分割开的正整数，分别表示N和M；

接下来的N行，每一行含有连续的M个字符（‘P’或者‘H’），中间没有空格。按顺序表示地图中每一行的数据。N≤100；M≤10。

输出格式：

仅一行，包含一个整数K，表示最多能摆放的炮兵部队的数量。

输入输出样例

输入样例#1：

1
2
3
4
5
6
5 4
PHPP
PPHH
PPPP
PHPP
PHHP

输出样例#1：

1
6

题解

又独立切掉了状态压缩dp，嘤。

感觉不难啊为什么他们都说难写，找回一点自信

首先看一眼数据范围对行压缩

然后由于当前行会被前两行影响，因此状态保存两行

而且要不是最后的check忘了取反就一遍AC啦！

设

表示当前为第i行，当前状态是

上一行是

由上面的转移可以看出这样做的时间复杂度是

但是我们把每行的最基本的不冲突的合法状态处理出来就大大减少转移状态数，加上此题限制条件多，实际上跑的飞快。

Code：

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#define maxn 105
#define maxm 12
int f[3][1<<maxm][1<<maxm] , n , m , g[1<<maxm] , tot , s[maxn];
inline int count(int x)
{
	int ans = 0;
	for(int i = x ; i ; i -= i & -i)
		++ans;
	return ans;
}
inline bool check(int sta , int rst)
{
	return sta & rst;
}
void write(int x)
{
	if(!x)return;
	write(x/2);
	putchar((x&1)+48);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1 ; i <= n ; ++i)
		for(int j = 1 ; j <= m ; ++j)
		{
			char ch ;
			std::cin>>ch;
			s[i] <<= 1;
			s[i] += (ch == 'P') ? 0 : 1;
		}
	
	int S = (1<<m)-1;
	for(int i = 0 ; i <= S ; ++i)
	{
		if((i & (i << 1)) || (i & (i << 2)) || (i & (i >> 1)) || (i & (i >> 2)) )	continue;
		g[++tot] = i;//prepare the basic valid status
	}
	for(int i = 1 ; i <= tot ; ++i)
		f[1][g[i]][0] = count(g[i]);
	for(int i = 2 ; i <= n ; ++i)
		for(int j = 1 ; j <= tot ; ++j)
			for(int k = 1 ; k <= tot ; ++k)
			{
				if(check(g[j] , g[k]))	continue;
				if(check(g[j] , s[i])) continue;
				if(check(g[k] , s[i-1]))	continue;
				for(int p = 1 ; p <= tot ; ++p)
				{
					if(check(g[k] , g[p]) || check(g[j],g[p]))	continue;
					if(check(g[p] , s[i-2]))	continue;
					f[i%3][g[j]][g[k]] = std::max(f[i%3][g[j]][g[k]] , f[(i-1)%3][g[k]][g[p]] + count(g[j]));
				}
			}
	int ans = -0x7fffff;
	for(int i = 1 ; i <= tot ; ++i)
		for(int j = 1 ; j <= tot ; ++j)
			if(!check(g[i],g[j]))
				ans = std::max(ans , f[n%3][g[i]][g[j]]);
	printf("%d",ans);
}