D - Trophy

题目大意

有一个游戏，由$N$个关卡组成。第$i$个关卡由一个数对$(A_i,B_i)$组成。

要通过一个关卡，你必须先花$A_i$的时间看一次介绍。然后，用$B_i$的时间打通这个关卡。若想多次通过同一个关卡，则第一次需要看介绍，后面无需再看（即如果想打通第$i$关$N$次，则所需时间为$A_i+N\times B_i$）。

开始时，只有第一关被解锁。当你每打通一关，其下一关会自动解锁（最后一关除外）。求总共打通$X$关的最少时间（重复通关也算）。

$1\le N\le 2\times 10^5$
$1\le A_i,B_i\le 10^9$
$1\le X\le N$

输入格式

$NX$
$A_1{B}_1$
$⋮$
$A_N{B}_N$

输出格式

输出答案。

样例

略，请自行前往AtCoder查看。

分析

仔细想想会发现，通过的方式都是先不重复通过某一关前所有关卡，再通过这一关一定次数，最终达到正好$X$次。因此，我们利用前缀和，依次枚举每个关卡，最终时间复杂度可达$\mathcal{O}(n)$。

代码

#include <cstdio>
#define INF 0x7FFFFFFFFFFFFFFFLL
using namespace std;

int main()
{
	int n, x;
	scanf("%d%d", &n, &x);
	if(x < n) n = x;
	long long s = 0LL, ans = INF, cur;
	for(int i=1; i<=n; i++)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		if((cur = (s += a + b) + (long long)(x - i) * b) < ans)
			ans = cur;
	}
	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

---

E - Packing Potatoes

WJ...

---

F - Main Street

WJ...

---

G - Triangle

题目大意

给定一张由$N$个点组成的简单无向图$G$和它的邻接矩阵$A$。

什么是邻接矩阵 ？

• 邻接矩阵，顾名思义，即表示图中每两点之间关系的矩阵。
• 如本题中$A_{i,j}$表示$i,j$两点之间是否有边。$A_{i,j}=0$表示无边，$1$表示有边。
• 一般来说，对于任意简单无向图，$A_{i,i}=0$，$A_{i,j}=A_{j,i}$ ($i\ne j$)。

求数对$(i,j,k)$的个数，使得：

• $1\le i<j<k\le N$
• $(i,j,k)$三个点在图中组成一个三角形，即$i,j,k$中任意两点之间有一条连边。

$3\le N\le 3000$

输入格式

$N$
$A_{1,1}{A}_{1,2}\dots A_{1,N}$
$A_{2,1}{A}_{2,2}\dots A_{2,N}$
$⋮$
$A_{N,1}{A}_{N,2}\dots A_{N,N}$（注意没有空格，如10110）

输出格式

输出一个整数，即符合条件的数对$(i,j,k)$的个数。

样例

略，请自行前往AtCoder查看。

分析

前言

• 个人感觉这题其实是这场比赛中最有意思的题。题目不难，但很具有研究意义。
  这里我将从各个角度分析题目，也期待大家在评论区中分享其他方法。

废话不多说，题解开始！

题目说得太啰嗦，其实不用管什么图论，可以看成是给定$N\times N$的$01$矩阵$A$，求$A_{i,j}=A_{i,k}=A_{j,k}=1$的$(i,j,k)$的个数。

再来看数据范围。$N\le 3000$，则$\mathcal{O}(N^3)$的朴素算法时间可达到$T(2.7\times 10^{10})$，显然无法通过。

然而，事实并非如此。
在仔细研究后发现，时间限制为$3\mathrm{s}$的题目可以使用复杂度稍高的算法。
但是一般来说，极端情况下超过$T(10^{10})$的算法无法通过。
因此，也许是数据不够强吧，使用如下的优化可以恰好通过（#32949139 $37764\mathrm{K}\mathrm{B},2755\mathrm{m}\mathrm{s}$）：

#pragma GCC optimize("Ofast") // -Ofast 预编译优化
#include <cstdio>
#define maxn 3000 // 数组大小设置正好，减少内存占用
using namespace std;

// 题目中正常的邻接矩阵
bool a[maxn][maxn];

// 特殊邻接表存储，减少尝试次数
// 这里不使用vector，会拖慢速度
int G[maxn][maxn], sz[maxn];

inline void print(const long long& x) // 快写-输出优化
{
	if(x > 9LL) print(x / 10);
	putchar(x % 10 ^ 48);
}

int main()
{
	// getchar快读输入优化
	int n = 0; char c;
	while((c = getchar()) != '\n')
		n = (n << 3) + (n << 1) + (c ^ 48);
	for(int i=0; i<n; i++, getchar())
		for(int j=0; j<n; j++)
			if(getchar() == '1' && j > i) // j > i：只存一半，去掉重复
				a[i][j] = 1, G[i][sz[i]++] = j;

	// 注意答案数据类型使用long long
	long long ans = 0LL;
	for(int v=0; v<n; ++v)
		for(int i=0; i<sz[v]; ++i) // 直接调取邻接表，省去不必要判断
		{
			int u = G[v][i];
			for(int j=0; j<sz[u]; ++j)
				if(a[v][G[u][j]])
					ans ++;
		}
	print(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

当然，这种方法并非每道题都能用，因此还是建议大家继续看正解。

正解还是基于上面的朴素算法，可看作：

• 依次遍历$A_{i,j}=1$的$(i,j)$（$i<j$）
• => 将答案加上$A[i]$和$A[j]$对应位置上都是$1$的位置个数
• 输出答案，除以3（去掉每个重复算的三次）

那么别的地方都没办法，只有第二部可以使用bitset进行优化。详见代码。

代码

#include <cstdio>
#include <bitset>
#define maxn 3000
using namespace std;

bitset<maxn> a[maxn];

int main()
{
	int n = 0; char c;
	while((c = getchar()) != '\n')
		n = (n << 3) + (n << 1) + (c ^ 48);
	for(int i=0; i<n; i++, getchar())
		for(int j=0; j<n; j++)
			if(getchar() == '1')
				a[i].set(j); // a[i][j] = 1
	long long ans = 0LL;
	for(int i=0; i+1<n; i++)
		for(int j=i+1; j<n; j++)
			if(a[i][j])
				ans += (a[i] & a[j]).count(); // 取交集，数1的个数
	printf("%lld\n", ans / 3LL);
	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

部分待更……