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$
输入格式
$N~X$
$A_1~B_1$
$\vdots$
$A_N~B_N$
输出格式
输出答案。
样例
略，请自行前往AtCoder查看。
分析
仔细想想会发现，通过的方式都是先不重复通过某一关前所有关卡，再通过这一关一定次数，最终达到正好$X$次。因此，我们利用前缀和，依次枚举每个关卡，最终时间复杂度可达$\mathcal O(n)$。
代码
|
|
E - Packing Potatoes
题目大意
$10^{100}$个土豆排成一列。它们的重量分别是$W_0,W_1,\dots,W_{N-1},W_0,\dots$，即第$i$个土豆的重量是$W_{i\bmod N}$（$i=0,1,2,\dots$）。
Takahashi会往一个盒子里依次放入每个土豆，当放入的土豆总重量$~\ge X$的时候他会换一个新盒子。
给定$Q$个询问。第$i$个询问：给定整数$K_i$，求第$K_i$个盒子中土豆的个数。
$1\le N,Q\le 2\times 10^5$
$1\le X,W_i\le 10^9$
$1\le K_i\le 10^{12}$
输入格式
$N~Q~X$
$W_0~\dots~W_{N-1}$
$K_1$
$\vdots$
$K_Q$
输出格式
输出$Q$行，第$i$行是第$i$个询问的答案。
样例
略，请自行前往AtCoder查看。
分析
周期问题。
代码
|
|
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}$
$\vdots$
$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{KB},2755 \mathrm{ms}$）：
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#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; }当然，这种方法并非每道题都能用，因此还是建议大家继续看正解。
正解还是基于上面的朴素算法，可看作：
- 依次遍历$A_{i,j}=1$的$(i,j)$（$i < j$）
- => 将答案加上$A[i]$和$A[j]$对应位置上都是$1$的位置个数
- 输出答案，除以3（去掉每个重复算的三次）
那么别的地方都没办法，只有第二步可以使用bitset的并集(&)操作进行优化。此时时间复杂度为$\mathcal O(\frac{n^3}w)$，其中$w=64$。详见代码。
代码
|
|