Post 41

Veröffentlicht am

WANNAFLY DIV1 A. Treepath

链接：

https://ac.nowcoder.com/acm/contest/15/A

题目描述

给定一棵n个点的树，问其中有多少条长度为偶数的路径。路径的长度为经过的边的条数。x到y与y到x被视为同一条路径。路径的起点与终点不能相同。

输入描述:

1
2
3
4
第一行一个数n表示点的个数；
接下来n-1行，每行两个整数x，y表示边；
保证输入数据形成一棵树；
1<=n<=100000

输出描述:

1
一行一个整数表示答案。

示例1

输入

1
2
3
3
1 2
1 3

输出

1
1

题解

题意简洁明了。我喜欢。

怎么统计长度为偶数的路径呢？不难想到奇数和奇数，偶数和偶数组成长度为偶数的路径，当然我们还得计算长度为奇数的路径。

但是考虑以任意点为根时，树上两点的路径不管过不过根，我们都只需要看他们到根的距离相加是不是偶数就可以了，这是因为LCA到根的距离是两倍，在模2意义下为0，所以两点间距离在模2意义下（也就是只看奇偶性）就是两点到根路径的和，这样这道题就很好统计了。

我是不会说一开始一想到要么过根要么不过根我差点写了点分治。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#define maxn 100005
int n , o , e;
long long ans;
std::vector<int> g[maxn];
 
void dfs(int x , int fx , int dep)
{
    if(dep & 1) ans += o , ++o;
    else ans += e , ++e;
    for(int i = 0 ; i < (int)g[x].size() ; ++i)
    {
        int v = g[x][i];
        if(v == fx) continue;
        dfs(v , x , dep + 1);
    }
}
 
int main()
{
    scanf("%d",&n);
    int x , y;
    for(int i = 1 ; i < n ; ++i)
    {
        scanf("%d%d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,1,0);
    printf("%lld\n",ans);
}

WANNAFLY DIV1 B. Xorto

链接：

https://ac.nowcoder.com/acm/contest/15/B

题目描述

给定一个长度为n的整数数组，问有多少对互不重叠的非空区间，使得两个区间内的数的异或和为0。

输入描述:

1
2
3
第一行一个数n表示数组长度；
第二行n个整数表示数组；
1<=n<=1000,0<=数组元素<100000。

输出描述:

1
一行一个整数表示答案。

示例1

输入

1
2
3
0 0 0

输出

1
5

说明

1
([1,1],[2,2]),([1,1],[3,3]),([1,1],[2,3]),([1,2],[3,3]),([2,2],[3,3])

题解

本场比赛的第二道送分题。

显然关于异或连续区间我们常用的方法是前缀异或，这时问题等价为选择四个数升序异或和为0。

关于这个统计，如果我们枚举所有$O(n^4)$4元组，恭喜你TLE.

然后我们改进一下枚举，从大到小枚举右端点，然后在这个右端点的基础上枚举左端点，同时确保右端点右边的所有区间异或值已经被加入一个桶，然后统计即可。

也就是说我们通过更改枚举顺序，避免右边的区间被重复加入，通过桶优化了时间复杂度。

时间复杂度$\Theta(n^2)$

Code：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <map>
#define maxn 1024
int s[maxn] , n , c[maxn<<8];
long long ans;
int main()
{
	scanf("%d",&n);
	for(int i = 1 ; i <= n ; ++i)
		scanf("%d",&s[i]) , s[i] ^= s[i-1];
	for(int r = n ; r >= 1 ; --r)
	{
		for(int l = 0 ; l < r ; ++l)
			ans += c[s[r]^s[l]];
		for(int nr = r ; nr <= n ; ++nr)
			++c[s[nr]^s[r-1]];
	}
	printf("%lld\n",ans);
}

luoguP1736 创意吃鱼法

题目背景

感谢@throusea 贡献的两组数据

题目描述

回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。

在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。

猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？

输入输出格式

输入格式：

有多组输入数据，每组数据：

第一行有两个整数n和m（n,m≥1），描述池塘规模。接下来的n行，每行有m个数字（非“0”即“1”）。每两个数字之间用空格隔开。

对于30%的数据，有n,m≤100

对于60%的数据，有n,m≤1000

对于100%的数据，有n,m≤2500

输出格式：

只有一个整数——猫猫一口下去可以吃掉的鱼的数量，占一行，行末有回车。

输入输出样例

输入样例#1：

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

输出样例#1：

1
3

说明

右上角的

1
2
3
1 0 0
0 1 0
0 0 1

题解

我好像又做了一道水题。。。看了看有思路就写了。

首先我们能想到二分答案，因为对于一个大正方形它里面的小正方形也合法。

然后对于每个答案，预处理每个点向左上方和右上方的最大连续长度以及二维前缀和，可以在$O(n^2)$的时间里递推完成。对于枚举的每个点，我们都能通过预处理的信息$O(1)$判断其合法性（左上或右上长度大于等于当前答案，并且通过前缀和容斥得到的这个正方形区间的1的个数等于答案）

最后时间复杂度$\Theta(Tn^2logn)$

好像还有什么悬线法之类可以优化到平方，不过感觉没什么区别。。

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
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <cstring>
#define maxn 2505
int f[maxn][maxn] , g[maxn][maxn] , h[maxn][maxn] , s[maxn][maxn] , ss[maxn] , n , m;

inline bool solve(int cur)
{
//	printf("CUR:%d\n",cur);
	for(int i = cur ; i <= n ; ++i)
		for(int j = cur ; j <= m ; ++j)
		{
//			printf("THE SQUARE%d %d %d %d\n",i,j,g[i][j] - g[i-cur][j] - g[i][j-cur] + g[i-cur][j-cur],f[i][j]);
			if(f[i][j] < cur && h[i][j-cur+1] < cur) continue;
			if(g[i][j] - g[i-cur][j] - g[i][j-cur] + g[i-cur][j-cur] != cur) continue;
			return true;
		}
	return false;
}

int main()
{
	while(scanf("%d%d",&n,&m) != EOF)
	{
		std::memset(f,0,sizeof(f));
		std::memset(g,0,sizeof(g));
		std::memset(h,0,sizeof(h));
		for(int i = 1 ; i <= n ; ++i)
			for(int j = 1 ; j <= m ; ++j)
				scanf("%d",&s[i][j]);
		for(int i = 1 ; i <= n ; ++i)
			for(int j = 1 ; j <= m ; ++j)
			{
				if(!s[i][j]) continue;
				f[i][j] = f[i-1][j-1] + s[i][j];
			}
		for(int i = 1 ; i <= n ; ++i)
			for(int j = m ; j >= 1 ; --j)
			{
				if(!s[i][j]) continue;
				h[i][j] = h[i-1][j+1] + s[i][j];
			}
		for(int i = 1 ; i <= n ; ++i)
		{
			std::memset(ss,0,sizeof(ss));
			for(int j = 1 ; j <= m ; ++j)
				ss[j] = ss[j-1] + s[i][j];
			for(int j = 1 ; j <= m ; ++j)
				g[i][j] = g[i-1][j] + ss[j];
		}
//		puts("THE INFO");
//		for(int i = 1 ; i <= n ; ++i)
//			for(int j = 1 ; j <= m ; ++j)
//				printf("%d %d %c",f[i][j],g[i][j],(j==m)?10:32);
		int l = 1 , r = std::min(n,m) , ans = 0;
		while(l <= r)
		{
			int mid = l + r >> 1;
			if(solve(mid)) ans = mid , l = mid + 1;
			else r = mid - 1;
		}
		printf("%d\n",ans);
	}
}