这次测试在比打暴力…

T1

此题体现了SPFA的性能很差…

30分

题解表示随便什么暴力…

60分

暴力连边+堆优化dijkstra，使用SPFA就233了…

100分

考虑建边，此题建边简直就是建网络流的图跑最短路…
对于每个板块，我们建一个超级源 $s$，板块中每个点向 $s$ 连代价为 $0$ 的边，$s$ 向板块中每个点连代价为 $c_i$ 的边。

T1

直接贪心，对输入数据排序，每次选价格最高的三本书进行购买即可，因为只有这样才能取到能免费的书中最贵的。

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

#include <cctype>
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;
char ch;
bool iosig;
inline void read(int &x) {
    x = 0, iosig = 0;
    do {
        ch = getchar();
        if (ch == '-') iosig = true;
    } while (!isdigit(ch));
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
    if (iosig) x = -x;
}
int n, w[100005];
long long ans;
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(w[i]);
    sort(w + 1, w + n + 1);
    int res = n % 3;
    for (int i = 1 + res; i <= n; i += 3) ans += w[i + 1] + w[i + 2];
    if (res == 1) ans += w[1];
    else if (res == 2) ans += w[1] + w[2];
    cout << ans;
    return 0;
}

字符串Hash学习总结

定义

字符串Hash简单来说就是：把字符串有效地转换为一个整数。

Hash函数

就是使得每一个字符串都能够映射到某一个整数上的函数

T1

此题说好的linux评测，然后在windows评测机上就2333了…

注意读入，注意windows上的读入

一看这题不就是矩阵乘法，$O(n^3)$ T掉,应该先预处理 $sum A_j = \sum limits_{i = 0}^{N - 1} A_{i,j}$ 和 $sum B_j = \sum\limits_{k = 0}^{N - 1} B_{j,k}$ ，那么 $sum = \sum_\limits{i=0}^{N-1}\sum\limits_{j=0}^{N-1}A_{i,j}sumB_j = \sum\limits_{j=0}^{N-1}\sum\limits_{k=0}^{N-1}B_{j,k}sumA_j$。

因此，我们只需要$O(n^2)$计算出一开始的 $sum$ 值，每次修改$O(1)$更新$sumA,sumB,sum$。

时间复杂度为$O(n^2+q)$。

A*算法学习总结

引入

假设有人想从A点移动到一墙之隔的B点，如下图，绿色的是起点A，红色是终点B，蓝色方块是中间的墙。

简化搜索区域

如上图，搜索区域已经划分成了方格，像这样简化搜索区域，是寻路的第一步。这一方法将搜索区域简化成了二位数组(基本的图论模型)，数组的每一个元素是是网格的一个方块，方块被标记为可通过的和不可通过的。路径被描述为从s到t我们经过的方块的集合。一旦路径被找到，我们的人就从一个方格的中心走向另一个，直到到达目的地。

链接

来源：NOIP2015提高组 Day1 T3
bzoj4325
数据加强版：uoj151

暴搜

以每种点数的牌的数量为状态，状态可压缩进一个 64 位整数中，搜索。
我们可以建一个HashMap存储，直接暴搜就能过(vijos上的加强数据会T，uoj的加强数据上被zz gyr给卡了)…

分析

求出每条路径两个端点的最近公共祖先，进而求出每条路径的长度。二分一个答案$x$，所有长度$>x$的路径上都至少需要删去一条边。对这些路径求交，最优方案一定是删去路径交中长度最大的边，如果删去最大的边后，最长的路径仍不满足$ \leq x$，则答案$x$不合法。

分析

令$f(x) = a_0 + a_1 x + a_2x^2 + \cdot \cdot \cdot + a_nx^n = 0$，那么对于一个质数$p$取模，如果有$f(x) = 0$，则一定有$f(x)% p = 0$。
我们只需要求出所有满足$f(x)%p = 0$的$x$，然后模另一个质数检验。
时间复杂度为$O(np + n \frac{nm}{p})$。

博弈论学习总结

Nim游戏

Nim游戏就是经典的取石子游戏，规则如下：
桌子上有 N 堆石子，游戏者轮流取石子。每次只能从一堆中取出任意数目的石子，但不能不取。 取走最后一个石子者胜。

结论：对于一个nim游戏局面($a_1,a_2, \cdots ,a_n$)，若$a_1$ ^ $a_2$ ^ \cdots ^ $a_n = 0$ 则先手必败。

这次测试三道题都是贪心233…

T1

30分

暴力枚举每个排列，暴力算值。

100分

贪心，肯定先考虑一大一小地放，打个暴力对拍一下，可以发现答案为以下两种情况的最大值:

• 最大的放中间，然后左边和右边依次放最小和次小的。
• 最小的放中间，然后左边和右边依次放最大和次大的。

T1

80分贪心

毫无正确性的贪心，直接统计小写变大写后的小写字母数。

正解

递推一下就行了，lsum表示小写字母的个数，usum表示大写字母的个数，$lsum = max(lsum, usum)$，那么 $ans = len - max(lsum, usum)$

T1

T2、T3 AC的我T1爆0…
string.substr注意长度的判断，以免RE…
此题可以直接暴力计数，也可以用HashMap优化

感谢出题人送我的生日礼物，人生第一次AK，23333…

T1

一维水dp，为什么某些人要作死写二维
f[0] 表示1的长度，f[1]表示符合题意的18的最大长度，f[2]表示符合题意的190最大长度，f[3]表示符合题意的1807最大长度。

T1

此题推了一个小时的网络流，然后拆点写挂…

100分

最大流，将所有点 u 都拆分成 u1 和 u2，s 向 u1 连容量为 F 的边，u2 向 t 连容量为 F 的边。对于原图的边 (u, v)，建立边 (u1, v2)，容量为 w(u, v)。
这样答案为 $\sum F_{i} - MaxFlow$

T1

80分算法

写了一个最水的贪心(毫无正确性)，每次取最大得数给 Bob，取完后其他的给 Alice，用 max_element 很短就能实现…

数位dp模板，记忆化搜索，dp[pos][pre][status]。
以不要62【hdu】为例