对于一个非空集合{$a_i$},我们称一个集合是 $magical$ 的,当且仅当它满足以下两个条件。

1:$a_1$ & $a_2$ &…& $a_n$ =0(&表示 $and$)

2:{$a_i$} 的任意一个除它本身外的非空子集不满足1。

小 $A$ 有一个很大很大的集合。很显然这个集合的子集数量是一个天文数字。

小 $A$ 现在想要知道这个集合的 magical 的非空子集数量是多少。

为了防止不必要的麻烦,请将答案 $mod$ $1e9+7$ 后输出。

JPY 精进了生物以后准备再去精进一下通技,于是就向通技竞赛(我也不知道是什么)的同学去请教了各种问题。通技竞赛的同学非常耐心,为他解答了各种问题。过了不久，JPY 感觉自己通技可以虐场了。于是通技竞赛的同学就给他出了一个问题:一个三维空间里有 $n$ 条直线,请找出一个直线的集合,使得这个集合里的直线两两有交点。请告诉他这个集合的最大大小。JPY 又瞬间秒掉了这道题，现在他想来考考你，来确认自己是否能真的虐场。

请计算 $C[k]=\sum(a[i]*b[i-k])$ 其中 $k \leq i < n$ ，并且有 $n \leq 10 ^ 5$。 $a,b$ 中的元素均为小于等于 $100$ 的非负整数。

链接

bzoj2194

输入

第一行一个整数 $N$ ,接下来 $N$ 行，第 $i+2 \cdots i+N-1$ 行，每行两个数，依次表示$a[i],b[i]$ $(0 \leq i < N)$。

输出

输出 $N$ 行，每行一个整数，第 $i$ 行输出 $C[i-1]$。

给出两个 $n$ 位 $10$ 进制整数 $x$ 和 $y$，你需要计算 $x \times y$。

链接

bzoj2179

输入

第一行一个正整数 $n$。 第二行描述一个位数为 $n$ 的正整数 $x$。 第三行描述一个位数为 $n$ 的正整数 $y$。

输出

输出一行，即 $x \times y$ 的结果。

这是一道模板题。
给你两个多项式，请输出乘起来后的多项式。

输入格式

第一行两个整数 $n$ 和 $m$，分别表示两个多项式的次数。
第二行 $n+1$ 个整数，分别表示第一个多项式的 $0$ 到 $n$ 次项前的系数。
第三行 $m+1$ 个整数，分别表示第一个多项式的 $0$ 到 $m$ 次项前的系数。

输出格式

一行 $n+m+1$ 个整数，分别表示乘起来后的多项式的 $0$ 到 $n+m$ 次项前的系数。

给定一个含有 n 个数的序列 a[1],a[2],a[3], … ,a[n]，程序必须回答这样的询问：对于给定的 i,j,k，在 a[i],a[i+1],a[i+2], … ,a[j] 中第 k 小的数是多少 (1≤k≤j-i+1)，并且，你可以改变一些a[i]的值，改变后，程序还能针对改变后的a继续回答上面的问题。你需要编一个这样的程序，从输入文件中读入序列 a，然后读入一系列的指令，包括询问指令和修改指令。对于每一个询问指令，你必须输出正确的回答。 第一行有两个正整数 n(1≤n≤10000)，m(1≤m≤10000)。分别表示序列的长度和指令的个数。第二行有 n 个数，表示 a[1],a[2]……a[n]，这些数都小于 10^9。接下来的 m 行描述每条指令，每行的格式是下面两种格式中的一种。 Q i j k 或者 C i t Q i j k （i,j,k是数字，1≤i≤j≤n, 1≤k≤j-i+1） 表示询问指令，询问 a[i]，a[i+1]……a[j] 中第 k 小的数。C i t (1≤i≤n，0≤t≤10^9) 表示把 a[i] 改变成为 t。

兵库县位于日本列岛的中央位置，北临日本海，南面濑户内海直通太平洋，中央部位是森林和山地，与拥有关西机场的大阪府比邻而居，是关西地区面积最大的县，是集经济和文化于一体的一大地区，是日本西部门户，海陆空交通设施发达。濑户内海沿岸气候温暖，多晴天，有日本少见的贸易良港神户港所在的神户市和曾是豪族城邑“城下町”的姬路市等大城市，还有以疗养地而闻名的六甲山地等。
兵库县官方也大力发展旅游，为了方便，他们在县内的N个旅游景点上建立了n-1条观光道，构成了一棵图论中的树。同时他们推出了M条观光线路，每条线路由两个节点x和y指定，经过的旅游景点就是树上x到y的唯一路径上的点。保证一条路径只出现一次。
你和你的朋友打算前往兵库县旅游，但旅行社还没有告知你们最终选择的观光线路是哪一条（假设是线路A）。这时候你得到了一个消息：在兵库北有一群丧心病狂的香菜蜜，他们已经选定了一条观光线路（假设是线路B），对这条路线上的所有景点都释放了【精神污染】。这个计划还有可能影响其他的线路，比如有四个景点1-2-3-4，而【精神污染】的路径是1-4，那么1-3,2-4,1-2等路径也被视为被完全污染了。
现在你想知道的是，假设随便选择两条不同的路径A和B，存在一条路径使得如果这条路径被污染，另一条路径也被污染的概率。换句话说，一条路径被另一条路径包含的概率。

数集 $S$ 的 $ForbiddenSum$ 定义为无法用 $S$ 的某个子集（可以为空）的和表示的最小的非负整数。
例如，$S={1,1,3,7}$，则它的子集和中包含0(S’= \varnothing)，1(S’={1})，2(S’={1,1})，3(S’={3})，4(S’={1,3})，5(S’ = {1, 1, 3})，但是它无法得到 $6$。因此 $S$ 的 $ForbiddenSum$ 为 $6$。
给定一个序列 $A$，你的任务是回答该数列的一些子区间所形成的数集的$ForbiddenSum$ 是多少。

一个可重复数字集合 $S$ 的神秘数定义为最小的不能被 $S$ 的子集的和表示的正整数。
求由 $a[l]$，$a[l+1]$，… ，$a[r]$ 所构成的可重复数字集合的神秘数。

在 Bytemountains 有 N 座山峰，每座山峰有他的高度 h_i 。有些山峰之间有双向道路相连，共 M 条路径，每条路径有一个困难值，这个值越大表示越难走，现在有 Q 组询问，每组询问询问从点 v 开始只经过困难值小于等于 x 的路径所能到达的山峰中第 k 高的山峰，如果无解输出 -1。

You are working for Macrohard company in data structures department. After failing your previous task about key insertion you were asked to write a new data structure that would be able to return quickly k-th order statistics in the array segment.
That is, given an array $a[1…n]$ of different integer numbers, your program must answer a series of questions $Q(i, j, k)$ in the form: “What would be the k-th number in $a[i…j]$ segment, if this segment was sorted?”
For example, consider the array $a = (1, 5, 2, 6, 3, 7, 4)$. Let the question be $Q(2, 5, 3)$. The segment $a[2…5]$ is $(5, 2, 6, 3)$. If we sort this segment, we get $(2, 3, 5, 6)$, the third number is $5$, and therefore the answer to the question is $5$.
题意：就是求区间第 $k$ 大。

傲娇少女幽香正在玩一个非常有趣的战略类游戏，本来这个游戏的地图其实还不算太大，幽香还能管得过来，但是不知道为什么现在的网游厂商把游戏的地图越做越大，以至于幽香一眼根本看不过来，更别说和别人打仗了。
在打仗之前，幽香现在面临一个非常基本的管理问题需要解决。
整个地图是一个树结构，一共有 $n$ 块空地，这些空地被 $n-1$ 条带权边连接起来，使得每两个点之间有一条唯一的路径将它们连接起来。在游戏中，幽香可能在空地上增加或者减少一些军队。同时，幽香可以在一个空地上放置一个补给站。
如果补给站在点 $u$ 上，并且空地 $v$ 上有 $d_v$ 个单位的军队，那么幽香每天就要花费：$d_v \times dist(u,v)$ 的金钱来补给这些军队。由于幽香需要补给所有的军队，因此幽香总共就要花费为 $\sum_{v=1}^{n}d_v \cdot dist(u, v)$ 的代价。其中 $dist(u,v)$ 表示 $u$ 和 $v$ 在树上的距离（唯一路径的权和）。
因为游戏的规定，幽香只能选择一个空地作为补给站。在游戏的过程中，幽香可能会在某些空地上制造一些军队，也可能会减少某些空地上的军队，进行了这样的操作以后，出于经济上的考虑，幽香往往可以移动她的补给站从而省一些钱。但是由于这个游戏的地图是在太大了，幽香无法轻易的进行最优的安排，你能帮帮她吗？ 你可以假定一开始所有空地上都没有军队。

捉迷藏 $Jiajia$ 和 $Wind$ 是一对恩爱的夫妻，并且他们有很多孩子。某天，$Jiajia$、$Wind$ 和孩子们决定在家里玩捉迷藏游戏。他们的家很大且构造很奇特，由 $N$ 个屋子和 $N-1$ 条双向走廊组成，这 $N-1$ 条走廊的分布使得任意两个屋子都互相可达。游戏是这样进行的，孩子们负责躲藏，$Jiajia$ 负责找，而 $Wind$ 负责操纵这 $N$ 个屋子的灯。在起初的时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，$Jiajia$ 希望知道可能的最远的两个孩子的距离（即最远的两个关灯房间的距离）。 我们将以如下形式定义每一种操作： $C(hange)$ $i$ 改变第 $i$ 个房间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 $G(ame)$ 开始一次游戏，查询最远的两个关灯房间的距离。

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃,两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画 $n$ 个“点”，并用$n-1$条“边”把这 $n$ 个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是 $3$ 的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.
Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.
Write a program that will count how many pairs which are valid for a given tree.
题意：给一棵边带权树，问两点之间的距离小于等于K的点对有多少个。

给定一个长度为 N 的序列，每个序列的元素是一个整数。要支持以下三种操作：

1. 将 [L,R] 这个区间内的所有数加上 V。
2. 将 [L,R] 这个区间翻转，比如 1 2 3 4 变成 4 3 2 1。
3. 求 [L,R] 这个区间中的最大值。 最开始所有元素都是 0。

工资的频繁调整很让员工反感，尤其是集体扣除工资的时候，一旦某位员工发现自己的工资已经低于了合同规定的工资下界，他就会立刻气愤地离开公司，并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司，我就要从电脑中把他的工资档案删去，同样，每当公司招聘了一位新员工，我就得为他新建一个工资档案。老板经常到我这边来询问工资情况，现在工资第 $k$ 多的员工拿多少工资。

Splay Tree（伸展树）是一种自平衡二叉排序树，可以在均摊 $O({\log} n)$ 的时间内完成基于 Splay（伸展）操作的修改与查询。

组合数表示的是从 $n$ 个物品中选出 $m$ 个物品的方案数。举个例子，从 $(1, 2, 3) $ 三个物品中选择两个物品可以有 $(1, 2)$， $(1, 3)$， $(2, 3)$ 这三种选择方法。
根据组合数的定义，我们可以给出计算组合数的一般公式：
$C_n ^ m = \frac{n!}{m!(n - m)!}$
其中 $n! = 1 \times 2 \times \cdots \times n$。
小葱想知道如果给定 $n$， $m$ 和 $k$，对于所有的 $0 \leq i \leq n$， $0 \leq j \leq \min(i, m)$ 有多少对 $(i, j)$ 满足是 $k$ 的倍数。

小南有一套可爱的玩具小人，它们各有不同的职业。

有一天，这些玩具小人把小南的眼镜藏了起来。小南发现玩具小人们围成了一个圈，它们有的面朝圈内，有的面朝圈外。

这时 singer 告诉小南一个谜题：「眼镜藏在我左数第 $3$ 个玩具小人的右数第 $1$ 个玩具小人的左数第 $2$ 个玩具小人那里。」

小南发现，这个谜题中玩具小人的朝向非常关键， 因为朝内和朝外的玩具小人的左右方向是相反的：面朝圈内的玩具小人，它的左边是顺时针方向，右边是逆时针方向；而面向圈外的玩具小人，它的左边是逆时针方向，右边是顺时针方向。

本题中，我们将用符号 $\lfloor c \rfloor$ 表示对 $c$ 向下取整，例如： $\lfloor 3.0 \rfloor = \lfloor 3.1 \rfloor = \lfloor 3.9 \rfloor = 3$。
蛐蛐国最近蚯蚓成灾了！隔壁跳蚤国的跳蚤也拿蚯蚓们没办法，蛐蛐国王只好去请神刀手来帮他们消灭蚯蚓。
蛐蛐国里现在共有 $n$ 只蚯蚓（ $n$ 为正整数）。每只蚯蚓拥有长度，我们设第 $i$ 只蚯蚓的长度为 $a_i$（ $i = 1, 2, \ldots , n$），并保证所有的长度都是非负整数（即：可能存在长度为 $0$ 的蚯蚓）。
每一秒，神刀手会在所有的蚯蚓中，准确地找到最长的那一只（如有多个则任选一个）将其切成两半。神刀手切开蚯蚓的位置由常数 $p$（是满足 $0 < p < 1$ 的有理数）决定，设这只蚯蚓长度为 $x$，神刀手会将其切成两只长度分别为 $\lfloor px \rfloor$ 和 $x - \lfloor px \rfloor$ 的蚯蚓。特殊地，如果这两个数的其中一个等于 $0$，则这个长度为 $0$ 的蚯蚓也会被保留。此外，除了刚刚产生的两只新蚯蚓，其余蚯蚓的长度都会增加 $q$（是一个非负整常数）。
蛐蛐国王知道这样不是长久之计，因为蚯蚓不仅会越来越多，还会越来越长。蛐蛐国王决定求助于一位有着洪荒之力的神秘人物，但是救兵还需要 $m$ 秒才能到来 $\cdots \cdots$ （ $m$ 为非负整数）
蛐蛐国王希望知道这 $m$ 秒内的战况。具体来说，他希望知道：
$m$ 秒内，每一秒被切断的蚯蚓被切断前的长度（有 $m$ 个数）；
$m$ 秒后，所有蚯蚓的长度（有 $n + m$ 个数）。
蛐蛐国王当然知道怎么做啦！但是他想考考你 $\cdots \cdots $

替罪羊树学习总结[模板]

传说中效率极高且较为好写的平衡树(抛开丧心病狂的红黑树和veb树)，替罪羊树写法相当暴力，不用旋转，它只会选择性地重新构树来保证复杂度。

NOIP2016总结【游记】

学$OI$也有半年了，第一次参加$noip$，感觉自己还是太弱了…各种不熟练…总之就是挂掉了…
不过毕竟高一，还有时间努力奋斗…
%%qy神犇 %%高二神犇 %%高三神犇

NOIP赛前总结

算法

基础算法

• 模拟
• 排序(注意合理使用 $sort$ 与 $stable_sort$ 及手写线性排序)
• 贪心(注意对拍验证)
• 分治
• 递推
• 二分答案(注意边界设定)
• 逆序对(树状数组，注意是否需要离散化)
• 中位数($nth_element$)
• 离散化(效率$Hash > sort + unique +$ 指针扫$> sort + unique+lower_bound>set$)
• 倍增法
• 构造法(大胆猜想+写拍)
• 三分答案

T1

文件名打错…
此题应打表找规律，我们可以发现原题就是求$\sum\limits_{k = 0}^{n}m^k=\frac{m^{n + 1}-1}{m-1}$，用费马小定理求逆元，快速幂计算就好了。

树链剖分学习总结

如果要在一棵树上进行路径的修改,求极值,求和，似乎线段树即可完成，实际上只用线段树并不能很好的做到，只有用一种高级的东西——树链剖分。

概念

树链，就是树上的路径。剖分，就是把路径分类为重链和轻链。
记size[v]表示以v为根的子树的节点数，depth[v]表示v的深度(根深度为1)，top[v]表示v所在的链的顶端节点，father[v]表示v的父亲，son[v]表示与v在同一重链上的v的儿子节点（姑且称为重儿子），w[v]表示v与其父亲节点的连边（姑且称为v的父边）在线段树中的位置。只要把这些东西求出来，就能用$O(logn)$的时间完成原问题中的操作。

树上操作学习总结

储存

用邻接表储存。

1
2
3
4
5
6
7
8
9
10

const int MAXN = 10010;
struct Node {
    int v, w;
    Node(int v, int w) : v(v), w(w) {}
};
vector<Node> edge[MAXN];
inline void addEdge(int u, int v, int w) {
    edge[u].push_back(Node(v, w));
    edge[v].push_back(Node(u, v));
}

T1

此题不说正解，我们来说一说玄学乱搞…
考虑贪心，暴力枚举原始盒子里的球，然后找出操作后对应的球的位置，暴力枚举每个区间(注意要按顺序枚举)，扩展区间，看是否能移动到对应位置即可。

T1

先判断负数个数的奇偶性，再处理能直接判断的情况，然后用 double 一乘一除判断就好了。
此题还可以用神奇的数学方法，我们可以把相乘看成 $log$ 相加，处理符号就好了。

T1

此题同codeforces460D
注意各种边界+判断…

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long l, r;
    int k;
    while (cin >> l >> r >> k) {
        if (k >= 4) {
            if (l % 2 && r - l + 1 >= 5) {
                cout << 0 << "\n" << 4 << "\n" << l + 1 << " " << l + 2 << " " << l + 3 << " " << l + 4 << "\n";
                continue;
            }
            else if (l % 2 == 0 && r - l + 1 >= 4) {
                cout << "0\n4\n" << l << " " << l + 1 << " " << l + 2 << " " << l + 3 << "\n";
                continue;
            }
            k = 3;
        }
        if (k == 3) {
            long long c = 3LL, b = 2LL, a = 1LL;
            int flag = 0;
            while (1) {
                if (c <= r && a >= l) {
                    flag = 1;
                    break;
                }
                if (c > r) break;
                a = a << 1 | 1;
                b = b << 1 | 1;
                c = c << 1;
            }
            if (flag) {
                cout << "0\n3\n" << a << " " << b << " " << c << "\n";
                continue;
            }
            k = 2;
        }
        if (k == 2) {
            int flag = 0;
            for (long long i = l; i <= l + 1; i++) {
                if (i % 2LL == 0 && i + 1LL <= r) {
                    flag = 1;
                    cout << "1\n2\n" << i << " " << i + 1LL << "\n";
                }
            }
            if (!flag) {
                if ((l ^ r) < l)  cout << (l ^ r) << "\n" << 2 << "\n" << l << " " << r << "\n";
                else cout << l << "\n1\n" << l << "\n";
            }
        }
        if (k == 1) {
            cout << l << "\n" << 1 << "\n" << l << "\n";;
            continue;
        }
    }
    return 0;
}

T1

此题考语文，注意题意的理解…
贪心，特判偶数串就行。

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

#include <bits/stdc++.h>
using namespace std;
int sum, cnt, k;
int main() {
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        sum = cnt = 0;
        for (int i = 1; i <= n; i++)
            cin >> k, sum += k / 2, cnt += k % 2;
        if (cnt) cout << 1 + (sum / cnt) * 2 << "\n";
        else cout << sum * 2 << "\n";
    }
    return 0;
}

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
30
31
32
33
34
35
36
37
38
39

#include <bits/stdc++.h>
using namespace std;
bool iosig;
char ch;
template<class T>
inline void read(T &x) {
    x = 0, iosig = 0;
    do {
        ch = getchar();
        if (ch == '-') iosig = 1;
    } while (!isdigit(ch));
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ '0'), ch = getchar();
}
int maxh, maxjump, minjump;
int n, deltah;
int h[1000010];
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.in", "r", stdin);
#endif
    read(n), read(deltah);
    for (int i = 1; i <= n; i++)
        read(h[i]);
    sort(h + 1, h + n + 1);
    for (int i = 1; i <= n; i++) {
        if (h[i] - h[i - 1] <= deltah)
            maxh = h[i], maxjump++;
        else break;
    }
    register int cur = 0, pre = 0;
    while (h[pre] < maxh) {
        while (h[cur] - h[pre] <= deltah && cur <= n)
            cur++;
        pre = --cur;
        minjump++;
    }
    cout << maxh << " " << maxjump << " " << minjump;
    return 0;
}

今天的题跟昨天的画风不一样啊…

T1

不要作死手写链表！！！
编号，排序，恢复链表就好…

T1

神奇的平衡三进制…
不懂为什么要转成三进制(好慢)。
直接预处理 $3$ 的幂和幂的前缀和，那么当 $x < 0$ 时，先输出 $T$，当$x>0$时，先输出$1$，当 $x = 0$ 时直接输出 $0$。最高位最多为 $maxDigit = \left \lceil \log_3x \right \rceil$，我们可以与 $3^{maxDigit}-sum[maxDigit-1]$ 比较，然后调整 $maxDigit$，然后向前枚举每一位，确定每一位的值就好了。

KMP算法学习总结

KMP（Knuth-Morris-Pratt）是一种改进的字符串匹配算法，也是算法竞赛中常用的字符串匹配算法之一，它可以有效地利用失配信息来使得匹配全过程中不回溯，从而在线性时间内完成匹配。

T1

一眼看成博弈论…
这是一道数学题，很容易推出可以下棋的格子时固定的，$\gcd(a, b)$ 的倍数格子是可以被下到的，其他的都是下不到的。然后就没了。证明有 $\gcd(a, b) = \gcd(a, a - b) = \gcd(a, a + b)$ 然后题解表示脑补一下就好了…

这次测试在比打暴力…

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$