BITSS 2018 寒假集训算法总结赛题解（Unofficial）

Author： xzm2019
发布时间：March 3, 2019
3787views
No comments
7711字数
Categories：算法

| Solved |  A   |  B   |  C   |  D   |  E   |  F   |  G   |  H   |  I   |  J   |  K   |  L   |
| :----: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: | :--: |
|  5/12  |  !   |  !   |  .   |  O   |  O   |  Ø   |  .   |  O   |  .   |  O   |  O   |  Ø   |

- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet

## Problem A Lancern 与数字序列

长文预警！！！（以下内容来自原官方题解）如想跳过建议点击右侧目录

> 首先我们要意识到（无论是通过计算复杂度还是一发 TLE），枚举区间求最大值和最小值进行累加会超时。那么我们可以从每个数对答案的贡献的角度来考虑这个问题，下面我们以每个数对最小值的贡献为例，来解释如何求这个贡献。
>
> 如何算一个数对最小值的贡献呢？我们只要知道这个数在多少个区间里是最小值即可。我们以第二个样例$𝐴 = \{1, 2, 3, 2,1\}$这个序列为例，对于$𝐴_3 = 3$来说，它只在$[3, 3]$这个区间里是最小值；对于$𝐴_2 = 2$来说，它在$[2, 2],[2, 3],[2, 4]$这三个区间里是最小值；对于$𝐴_4 = 2$来说，它在$[2,4],[3, 4],[4, 4]$这三个区间里是最小值。所以整个序列每个区间的最小值之和就等于$\sum_1^nA_i *$这个数作为最小值的区间个数。
>
> 那么我们就有了两个问题，一个是如何求$𝐴_𝑖$在多少个区间中是最小的，另一个是如何去掉重复区间（比如$𝐴_2 = 2$和$𝐴_4 = 2$都是区间$[2, 4]$的最小值）。
>
> 对于第一个问题，因为包含$𝐴_𝑖$的区间左端点一定在$𝑖$左边，右端点一定在$𝑖$右边，所以我们可以利用乘法原理，通过计算有多少个左端点的可选位置，多少个右端点的可选位置，乘起来就是$𝐴_𝑖$作为最小值的区间个数。我们可以发现，直到左边第一个小于$𝐴_𝑖$的数之间的位置都可以作为区间的左端点，直到右边第一个小于$𝐴_𝑖$的数之间的位置都可以作为区间的右端点。
>
> 对于第二个问题，我们可以对于相同的数，认为规定一个大小关系，比如下标小的更小，这样做就可以不重不漏了，大家可以结合用例来理解这种想法。
>
> 那么我们如何找到$𝐴_𝑖$左边第一个小于它的位置呢？我们总结了 5 种方法，下面将分别介绍这 5 种方法：
>
> \1. 双链表
>
> 我们首先对$𝐴$序列按照大小排序（还要带着下标一起排序），因为每个数的大小都不超过$10^5$，所以我们可以通过桶排序在$𝑂(𝑁)$的时间内完成排序，如果不会桶排序的话直接$𝑠𝑜𝑟𝑡$即可，效率也差不多。我们还要建立一个长度为$𝑁$的双向链表，双链表的节点要开在一段连续内存中，以便随机访问（如果不理解可以结合标程理解），假设双链表的每个节点为$𝑝_𝑖$，左指针𝑙指向上一个节点的下标，即$𝑖 −1$，右指针$𝑟$指向下一个节点的下标，即$𝑖 + 1$。然后从排好序的序列中，从权值大的一端开始遍历，假设这个数在原序列$𝐴$中的下标为$𝑖$，我们访问$𝑝_𝑖$，那么$𝑝_𝑖.𝑙$就是这个数在原序列中左边第一个小于它的位置，$𝑝_𝑖.𝑟$就是右边第一个小于它的位置。统计答案之后将这个节点从双链表中删除。因为每次遍历到一个数的时候，比它大的数都在之前的操作中被从双链表中删除了，所以保证了每次$𝑝𝑖. 𝑙$和$𝑝𝑖. 𝑟$位置的数一定比它小。因为每个元素只被访问一次，双链表的删除是$𝑂(1)$的，所以这一部分的时间复杂度也是$𝑂(𝑁)$的。计算最大值的部分和计算最小值的部分类似，只是变成了从小到大遍历。
>
> 整个算法的时间复杂度为$𝑂(𝑁)$的。
>
> 这个解法是出题人最开始期望的解法，主要考察想大家对链表的应用。
>
> ```cpp
> #include <bits/stdc++.h>
> using namespace std;
> typedef long long LL;
> const int MAXN = 100005;
> struct Node
> {
>     int l, r;
> }node[MAXN];
> void init(int n)
> {
>     node[0].r = 1, node[n + 1].l = n;
>     for (int i = 1; i <= n; i ++)
>     {
>         node[i].l = i - 1;
>         node[i].r = i + 1;
>     }
> }
> void erase(int x)
> {
>     node[node[x].l].r = node[x].r;
>     node[node[x].r].l = node[x].l;
> }
> int n;
> struct Record
> {
>     int idx, value;
>     Record() {}
>     Record(int idx, int value) : idx(idx), value(value) {}
> }rec[MAXN];
> vector<int> cnt[MAXN];
> LL get_max()
> {
>     init(n);
>     LL ret = 0;
>     for (int i = 1; i <= n; i ++)
>     {
>         ret += (LL)rec[i].value * (rec[i].idx - node[rec[i].idx].l) *
>             (node[rec[i].idx].r - rec[i].idx);
>         erase(rec[i].idx);
>     }
>     return ret;
> }
> LL get_min()
> {
>     init(n);
>     LL ret = 0;
>     for (int i = n; i > 0; i --)
>     {
>         ret += (LL)rec[i].value * (rec[i].idx - node[rec[i].idx].l) *
>             (node[rec[i].idx].r - rec[i].idx);
>         erase(rec[i].idx);
>     }
>     return ret;
> }
> int main()
> {
>     int t;
>     scanf("%d", &t);
>     while (t--)
>     {
>         scanf("%d", &n);
>         for (int i = 1; i <= 100000; i ++)
>             cnt[i].clear();
>         for (int i = 1; i <= n; i ++)
>         {
>             int a;
>             scanf("%d", &a);
>             cnt[a].push_back(i);
>         }
>         for (int i = 1, j = 1; i <= 100000; i ++)
>             for (auto k : cnt[i])
>                 rec[j++] = Record(k, i);
>         LL ans = get_max() - get_min();
>         printf("%lld\n", ans);
>     }
>     return 0;
> }
> ```
>
> 
>
> \2. 并查集
>
> 大体思路和双链表类似，只不过这个并查集不光要维护联通关系，还要维护集合大小。先按上面说的方法进行排序，每次选出最大的数，看这个数左边一个数所在集合大小，就是区间左端点可选位置的数量，右边同理，然后将这个数左右集合合并。因为每次查询一个数的时候，它左右两边的集合一定是比它大的元素，所以可以保证正确性。
>
> 复杂度$𝑂(𝑁)$。如果理解有困难可以结合标程理解。
>
> 这个解法想考察大家对并查集维护集合大小的应用。
>
> ```cpp
> #include <bits/stdc++.h>
> using namespace std;
> typedef long long LL;
> const int MAXN = 100005;
> int parent[MAXN], siz[MAXN];
> void init(int n)
> {
>     for (int i = 1; i <= n; i++)
>     {
>         parent[i] = i;
>         siz[i] = 1;
>     }
> }
> int find(int x)
> {
>     if (x == parent[x]) return x;
>     else return parent[x] = find(parent[x]);
> }
> void merge(int x, int y)
> {
>     int z = find(x), w = find(y);
>     parent[z] = w;
>     siz[w] += siz[z];
> }
> int size(int x)
> {
>     return siz[find(x)];
> }
> int n;
> bool vis[MAXN];
> struct Node
> {
>     int idx, value;
> }p[MAXN];
> LL get_max()
> {
>     init(n);
>     memset(vis, false, sizeof vis);
>     LL ret = 0;
>     for (int i = 1; i <= n; i ++)
>     {
>         vis[p[i].idx] = true;
>         int l = 1, r = 1;
>         if (p[i].idx > 1 && vis[p[i].idx - 1])
>         {
>             l += size(p[i].idx - 1);
>             merge(p[i].idx, p[i].idx - 1);
>         }
>         if (p[i].idx < n && vis[p[i].idx + 1])
>         {
>             r += size(p[i].idx + 1);
>             merge(p[i].idx, p[i].idx + 1);
>         }
>         ret += p[i].value * l * r;
>     }
>     return ret;
> }
> LL get_min()
> {
>     init(n);
>     memset(vis, false, sizeof vis);
>     LL ret = 0;
>     for (int i = n; i > 0; i --)
>     {
>         vis[p[i].idx] = true;
>         int l = 1, r = 1;
>         if (p[i].idx > 1 && vis[p[i].idx - 1])
>         {
>             l += size(p[i].idx - 1);
>             merge(p[i].idx, p[i].idx - 1);
>         }
>         if (p[i].idx < n && vis[p[i].idx + 1])
>         {
>             r += size(p[i].idx + 1);
>             merge(p[i].idx, p[i].idx + 1);
>         }
>         ret += p[i].value * l * r;
>     }
>     return ret;
> }
> int main()
> {
>     int t;
>     scanf("%d", &t);
>     while (t--)
>     {
>         scanf("%d", &n);
>         for (int i = 1; i <= n; i ++)
>         {
>             scanf("%d", &p[i].value);
>             p[i].idx = i;
>         }
>         sort(p + 1, p + n + 1,[](const Node& a, const Node& b)->bool
>         {
>             if (a.value != b.value) return a.value < b.value;
>             else return a.idx < b.idx;
>         });
>         LL ans = get_max() - get_min();
>         printf("%lld\n", ans);
>     }
>     return 0;
> }
> ```
>
> \3. 树状数组
>
> 我们想要求$𝐴_𝑖$左边第一个小于它的位置，我们可以按照权值建立一颗树状数组，树状数组中维护最大值。从左到右扫过$𝐴$序列，当扫到$𝐴_𝑖$时，查询树状数组下标$1 \sim 𝐴_𝑖$范围内的最大值，即为𝐴𝑖左边第一个小于它的位置。右边同理，扫完左边清空一下树状数组从右边开始再扫一遍即可。我们还要求最大值，所以一共要扫 4 遍$𝐴$序列。
>
> 整个算法的时间复杂度为$𝑂(𝑁𝑙𝑜𝑔𝑁)$的。
>
> 这个解法主要想考察大家对树状数组以不同方式建立，维护不同内容的应用。
>
> \4. 线段树
>
> 思路和树状数组一样，毕竟树状数组能解决的问题，线段树都能解决。
>
> 复杂度也是$𝑂(𝑁𝑙𝑜𝑔𝑁)$的，但是常数比树状数组大，验题人的程序跑了 3s 多，所以这题才开了 5s 的时间限制~~（可是重现是在cf上的比hdu的快啊）~~。
>
> \5. ST表+二分
>
> 这个解法只是随口一说，有兴趣的同学可以研究一下。
>
> 这道题想考察大家对时间复杂度的估计，以及从不同角度想问题的思维。算贡献是计数问题的常见套路，大家不妨记住这种思想。~~其实出这个题本来也没希望大家能做出来，但是~~这个题的解法多样，并且覆盖了最近大部分的知识点，希望大家看了题解之后能用自己喜欢的方法补一下这个题。

------

## Problem B bibibibi 与苹果

其实题目就是给了一堆不等式$a_{L_i}+a_{L_i+1}+\cdots+a_{R_i} \geq X_i$，同时有约束条件$a_i \leq s_i$。如果把这个式子做前缀和做差分形式，则有$sum_{R_i}-sum_{L_i-1} \geq X_i\ (1)\ ,sum_i-sum_{i-1} \leq s_i\ (2)$。形成了一个不等式组。题目的要求就是解出$sum_n$的最大值。

把$(1)$式取反得，$sum_{L_i-1}-sum_{R_i} \leq L_i$，这样形成了一个全部都是小于等于的不等式组，以此建边，跑最长路即可。

如果最后出现正环，则说明无解，则给出全部苹果。

建议参考这个博文：https://www.cnblogs.com/songorz/p/9386509.html

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
struct Edge
{
	int v;
	int cost;
	Edge(int _v = 0, int _cost = 0) :v(_v), cost(_cost) {}
};
vector<Edge>E[MAXN];

void addedge(int u, int v, int w)
{
	E[u].push_back(Edge(v, w));
}
bool vis[MAXN];
int cnt[MAXN];
int dist[MAXN];
bool SPFA(int start, int n)
{
	memset(vis, false, sizeof(vis));
	for (int i = 1; i <= n; i++)dist[i] = -1;
	vis[start] = true;
	dist[start] = 0;
	queue<int>que;
	while (!que.empty())que.pop();
	que.push(start);
	memset(cnt, 0, sizeof(cnt));
	cnt[start] = 1;
	while (!que.empty())
	{
		int u = que.front();
		que.pop();
		vis[u] = false;
		int lenn = E[u].size();
		for (int i = 0; i<lenn; i++)
		{
			int v = E[u][i].v;
			if (dist[v]<dist[u] + E[u][i].cost)
			{
				dist[v] = dist[u] + E[u][i].cost;
				if (!vis[v])
				{
					vis[v] = true;
					que.push(v);
					if (++cnt[v]>n)return false;
				}
			}
		}
	}
	return true;
}
int n, m;
int num[100010];

int main()
{
	// freopen("data.in", "r", stdin);
	// freopen("data.out", "w", stdout);
	int i, j;
	while (scanf("%d%d", &n, &m) != EOF)
	{
		int le = 1e9 + 7, ri = -1e9 + 7;
		for (i = 0; i <= n; i++) E[i].clear();
		long long sum = 0;
		for (i = 1; i <= n; i++)
		{
			scanf("%d", &num[i]);
			sum += num[i];
		}
		for (i = 1; i <= m; i++)
		{
			int L, R, w;
			scanf("%d %d %d", &L, &R, &w);
			le = min(le, L), ri = max(ri, R);
			addedge(L - 1, R, w);
		}
		for (i = le; i <= ri; i++)
		{
			addedge(i - 1, i, 0);
			addedge(i, i - 1, 0 - num[i]);
		}
		bool flag = SPFA(le - 1, n);
		if (flag == 0) printf("%lld\n", sum);
		else printf("%d\n", dist[ri]);
	}
	return 0;
}
```

------

## Problem C 命令行与文件系统

题解略……QAQ

```cpp
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <stack>

using namespace std;

struct node {
    string name;
    node* parent;
    map<string, node *> children;

node() : name(), parent(NULL), children() { }
    node(const string& _name) : name(_name), parent(NULL), children() { }
    node(const string& _name, node* _parent) : name(_name), parent(_parent), children() { }
};

node *root, *now;
string cmd;

void clear(node** pnode) {
    if (!(*pnode))
        return;

for (auto& child : (*pnode)->children)
        clear(&child.second);

delete *pnode;
    *pnode = NULL;
}

void init() {
    root = new node();
    now = root;
}

void analyze_path(vector<string>& names, const string& path) {
    for (int i = 0; i < (int)path.length(); ) {
        int j = i;
        while (j < (int)path.length() && path[j] != '/')
            ++j;

// cout << "TRACE: analyze_path: i = " << i << ", j = " << j << endl;
        names.push_back(path.substr(i, j - i));

i = j + 1;
    }
}

node* fetch_fsnode(node* start, const vector<string>& names) {
    node* fsnode = start;
    for (const string& item : names) {
        if (item.empty())
            continue;
        if (item == ".")
            continue;
        else if (item == "..") {
            fsnode = fsnode->parent;
            if (fsnode == NULL)
                return NULL;
        } else {
            auto ptr = fsnode->children.find(item);
            if (ptr == fsnode->children.end())
                return NULL;
            else
                fsnode = ptr->second;
        }
    }
    return fsnode;
}

void print_path(const node* fsnode) {
    stack<const node *> path;
    while (fsnode != root) {
        path.push(fsnode);
        fsnode = fsnode->parent;
    }
    if (path.empty())
        cout << "/" << endl;
    else {
        while (!path.empty()) {
            cout << "/" << path.top()->name;
            path.pop();
        }
        cout << endl;
    }
}

void cd() {
    string path;
    cin >> path;

vector<string> names;
    analyze_path(names, path);

// for (const string& item : names)
    //     cout << "TRACE: item = " << item << endl;

bool absolute = true;
    if (names[0].length() != 0)
        absolute = false;

node* fsnode = NULL;
    if (absolute) {
        fsnode = fetch_fsnode(root, names);
        if (fsnode != NULL) {
            now = fsnode;
            cout << "cd: ";
            print_path(fsnode);
            return;
        }
    }

fsnode = fetch_fsnode(now, names);
    if (fsnode == NULL)
        cout << "cd: no such directory" << endl;
    else {
        now = fsnode;
        cout << "cd: ";
        print_path(fsnode);
    }
}

void mkdir() {
    string name;
    cin >> name;
    if (now->children.count(name))
        cout << "mkdir: directory already exist" << endl;
    else
        now->children[name] = new node(name, now);
}

void ls() {
    if (now->children.size() == 0)
        cout << "ls: (empty directory)" << endl;
    else {
        bool first = true;
        for (const auto& item : now->children) {
            if (first)
                first = false;
            else
                cout << " ";
            cout << item.first;
        }
        cout << endl;
    }
}

void rm() {
    string name;
    cin >> name;

auto ptr = now->children.find(name);
    if (ptr == now->children.end())
        cout << "rm: no such directory" << endl;
    else {
        clear(&ptr->second);
        now->children.erase(ptr);
    }
}

int main(int argc, char* argv[]) {
    root = NULL;

int q;
    while (cin >> q) {
        clear(&root);
        init();

while (q--) {
            cin >> cmd;
            if (cmd[0] == 'c')
                cd();
            else if (cmd[0] == 'm')
                mkdir();
            else if (cmd[0] == 'l')
                ls();
            else
                rm();
        }
    }

return 0;
}
```

------

## Problem D 关灯

先考虑每个问题的求解，很显然，我们只要对第一行进行枚举即可，第一行一共$2^4=16$种状态，枚举每种情况以后，从第二行的格子开始考虑，只要他上面的打开的，就一定要进行翻转。

再考虑整体情况，一共$2^{16}=32768$种情况，而数据共$200\,000$个，因此对数据进行存储，如果有重复的直接输出答案或者从全关状态开始，bfs去遍历到每种状况的最少次数。

然后就有了我的惨案：

~~然而由于cf的评测机较快，我把我第一发的提交扔上去就直接AC了！！！（然而我想了想没有改时限）~~

```cpp
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int inf = 0x3F3F3F3F;

int steps[100005];

int flip(int mask, int i, int j) {
    if (i < 0 || i >= 4 || j < 0 || j >= 4)
        return mask;
    else
        return mask ^ (1 << (i * 4 + j));
}

int make_step(int now, int i, int j) {
    now = flip(now, i, j);
    now = flip(now, i - 1, j);
    now = flip(now, i + 1, j);
    now = flip(now, i, j - 1);
    now = flip(now, i, j + 1);
    return now;
}

void bfs() {
    memset(steps, 0x3F, sizeof(steps));
    queue<int> q;

q.push(0);
    steps[0] = 0;

while (!q.empty()) {
        int now = q.front();
        q.pop();

for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                int next = make_step(now, i, j);
                if (steps[next] == inf) {
                    steps[next] = steps[now] + 1;
                    q.push(next);
                }
            }
        }
    }
}

char grid[4][5];

int main(int argc, char* argv[]) {
    bfs();

int t;
    scanf("%d", &t);

while (t--) {
        for (int i = 0; i < 4; ++i)
            scanf("%s", grid[i]);

int mask = 0;
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                if (grid[i][j] == '#')
                    mask |= (1 << (i * 4 + j));
            }
        }

if (steps[mask] == inf)
            puts("-1");
        else
            printf("%d\n", steps[mask]);
    }

return 0;
}
```

------

## Problem E 一起去划船

签到题，贪心，把所有人按照时间从小到大排序，如果她开心就让她划，不开心就让她最后再划。

```cpp
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
typedef long long ll;

using namespace std;
const int maxn = 1e5 + 10;
ll t[maxn], temp;
int cas, ans, n;

int main()
{
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	scanf("%d", &cas);
	while (cas--)
	{
		scanf("%d", &n);
		temp = 0;
		ans = 0;
		for (int i = 1; i <= n; i++)
			scanf("%lld", &t[i]);
		sort(t + 1, t + 1 + n);

for (int i = 1; i <= n; i++)
			if (t[i] >= temp)
				ans++, temp += t[i];
		printf("%d\n", ans);
	}
}
```

------

## Problem F Teammates and Red Envelopes

根据容斥原理，在总数为$N$的情况下，Lchen不要的数量是$\lfloor \frac{N}{P_1} \rfloor$，Lytning不要的数量是$\lfloor \frac{N}{P_2} \rfloor$，两者都不要的数量是$\lfloor \frac{N}{P_1P_2} \rfloor$。优先把Lchen不要的给Lytning，把Lytning不要的给Lchen，剩下的按顺序给即可。

因此显然这题可以通过二分答案完成。注意起始的右界为$10^9$是不够的，要开为$2*10^9$。同此同时注意$l+r$可能会超过`int`的范围。

```cpp
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int cnt1, cnt2, x, y;

bool can(int v){
	int a = v - v / x;
	int b = v - v / y;
	int c = v - v / (x * y) ;
	return (c >= cnt1 + cnt2) && cnt1 <= a && cnt2 <= b;
}

int main(void){
	while(~scanf("%d%d%d%d",&cnt1,&cnt2,&x,&y)) {
		LL l = 1, r = 2e9;
	while (l < r){
		int mid = ((LL)l + (LL)r) >> 1;
		if (can(mid))
			r = mid;
		else
			l = mid + 1;
	}
	cout << l << endl;
	}	
}
```

------

## Problem G 小清河取景记

由于大家同时去集合，所以移动是同时的，因此只需要枚举每个人去哪个地方取景即可。同样采用二分答案的方式即可。

```cpp
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stack> 
#include <math.h>
#include <queue>
using namespace std;

int n,k;
long long p,a[2002],b[2005],vis[2005];

int solve(long long x){
	int i,j;
	int cnt=0;

memset(vis,0,sizeof(vis));
	for(i=0;i<n;i++)
	    for(j=0;j<k;j++){
	    	if(!vis[j]&&abs(a[i]-b[j])+abs(p-b[j])<=x){
	    		vis[j]=1;
	    		cnt++;
	    		break;
			}
		}
	if(cnt==n)
	    return 1;
	return 0;
}

long long bsearch(long long left,long long right){
	long long mid,ret=-1;

while(left<=right){
		mid=left+(right-left)/2;
		if(solve(mid)){
			ret=mid;
			right=mid-1;
		}
		else
		    left=mid+1;
	}
	return ret;
}

int main(){
	int i;
	long long ans;

while(~scanf("%d%d%lld",&n,&k,&p)){
		for(i=0;i<n;i++)
		    scanf("%lld",&a[i]);
		for(i=0;i<k;i++)
		    scanf("%lld",&b[i]);
		sort(a,a+n);
		sort(b,b+k);
		ans=bsearch(0,1e10);
		printf("%lld\n",ans);
	}

return 0;
}
```

------

## Problem H bibibibi 的超级异或计算器

我们注意前两个要求，就是单点修改，区间查询异或和，显然只需要把我们学过的线段树的加号改成异或即可。

对于第三个条件，显然并不能真正实现位移，我们可以区间位移从而得到，只需要记录位移量，对于修改和查询，进行下标的修改即可。同时要注意区间查询的时候可能会让区间一分为二，分两段求异或和然后再异或即可。

```cpp
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cstdio>
#include <stack>
#include <map>
#include <string> 
#include <set>
#define eps 1e-5
using namespace std;

int tree[400001];
int val[100001];
void push(int rt)     //合并区间答案操作 
{
	tree[rt]=tree[rt << 1]^tree[rt << 1 | 1];   //求最大值用max函数代替就好 
}

void build(int L,int R,int rt)    //递归建树 
{
	int m=(L+R)/2;
	if (L==R)
	{
		tree[rt]=val[L];
		return;
	}
	build(L,m,rt<<1);     //建左子树 
	build(m+1,R,rt<<1|1);  //建右子树 
	push(rt);
}
int Query(int L,int R,int l,int r,int rt)   //[l,r]区间查询 
{
	int m =(l+r)/2;
	int ans=0;
	if (L<=l&&r<=R)
	{
		return tree[rt];
	}
	if (L<=m)
	{
		ans^=Query(L,R,l,m,rt<<1);
	}
	if (R>m)
	{
		ans^=Query(L,R,m+1,r,rt<<1|1);
	}
	return ans;
}
void updata(int n,int add,int l,int r,int rt)   //单点更新 ，n这个位置的值加add 
{
	int m=(l+ r)/2;
	if (l==r)
	{
		tree[rt]=add;
		return;
	}
	if (n<=m)           //更新点在左区间 
	{
		updata(n,add,l,m,rt<<1);
	}
	else    //更新点在右区间 
	{
		updata(n,add,m+1,r,rt<<1|1);
	}
	push(rt);
}
int main()
{
	int n,m;
	while (scanf("%d%d",&n,&m)==2)
	{
		memset(tree,0,sizeof(tree));
		for (int i=1;i<=n;i++) scanf("%d",&val[i]);
		build(1,n,1);
		int op,py=0,a,b;
		for (int i=1;i<=m;i++)
		{
			scanf("%d",&op);
			switch (op)
			{
				case 1:{
					scanf("%d%d",&a,&b);
					a+=py; b+=py;
					if (a>n)
					{
						a%=n; b%=n;
					}
					if (b<=n)
					{
						printf("%d\n",Query(a,b,1,n,1));
					}
					else
					{
						printf("%d\n",Query(a,n,1,n,1)^Query(1,b%n,1,n,1));
					}
					break;
				}
				case 2:{
					scanf("%d%d",&a,&b);
					a+=py;
					if (a>n) a%=n;
					updata(a,b,1,n,1);
					break;
				}
				case 3:{
					py++;
					if (py>n) py=1;
					break;
				}
			}
		}
	}
    return 0;
}
```

------

## Problem I Lylist 与魔法卡牌 Episode. 1

我们每次把两张牌进行合并，获得积分，然后保留一张。仔细一想，$n$张牌进行$n-1$次合并，相当于是一棵树。对于两张卡牌之间连一条边，边权就是$max(R_i\ xor\ B_j,R_j\ xor\ B_i)$。然后跑最大生成树即可。

最大生成树相对于最小生成树的变化就是把边权排序顺序进行改变即可。

```cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 505;
int parent[MAXN];
int find(int x)
{
    if (x == parent[x]) return x;
    else return parent[x] = find(parent[x]);
}
void merge(int x, int y)
{
    parent[find(x)] = find(y);
}
struct Edge
{
    int from, to, value;
    Edge() {}
    Edge(int from, int to, int value) :
        from(from), to(to), value(value) {}
};
int n;
int r[MAXN], b[MAXN];
vector<Edge> edges;
void init(int n)
{
    edges.clear();
    for (int i = 1; i <= n; i ++)
        parent[i] = i;
}
LL Kruskal()
{
    sort(edges.begin(), edges.end(),
    [](const Edge& a, const Edge& b)->bool
    {
        return a.value > b.value;
    });
    LL ret = 0;
    for (auto& i : edges)
    {
        if (find(i.from) == find(i.to)) continue;
        ret += i.value;
        merge(i.from, i.to);
    }
    return ret;
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d", &n);
        init(n);
        for (int i = 1; i <= n; i ++)
            scanf("%d%d", r + i, b + i);
        for (int i = 1; i < n; i ++)
            for (int j = i + 1; j <= n; j ++)
                edges.emplace_back(i, j, max(r[i] ^ b[j], r[j] ^ b[i]));
        LL ans = Kruskal();
        printf("%lld\n", ans);
    }
    return 0;
}
```

------

## Problem J Lylist 与魔法卡牌 Episode. 2

题目要求不下降子序列的个数，我们可以把它进行一个转化。在每个数位置上的答案就等于比他小的答案+他本身。使用树状数组进行维护即可。

```cpp
#include <cstdio>
#include <algorithm>

using namespace std;

const int mod = 1000000007;

class binary_indexed_tree {
    #define LSB(x)      ((x) & -(x))

int tree[100005];
    int n;

public:
    void init(int n) {
        this->n = n;
        for (int i = 0; i <= n; ++i)
            tree[i] = 0;
    }

void update(int pos, int delta) {
        while (pos <= n) {
            tree[pos] = ((long long int)tree[pos] + delta) % mod;
            pos += LSB(pos);
        }
    }

int query(int pos) {
        int ans = 0;
        while (pos > 0) {
            ans = ((long long int)ans + tree[pos]) % mod;
            pos -= LSB(pos);
        }
        return ans;
    }
};

int a[100005];
binary_indexed_tree tree;
int n;

int main(int argc, char* argv[]) {
    int t;
    scanf("%d", &t);

int kase = 0;
    while (t--) {
        scanf("%d", &n);

int maxa = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            maxa = max(maxa, a[i]);
        }

int ans = 0;
        tree.init(maxa);

for (int i = 1; i <= n; ++i) {
            int now = (1 + tree.query(a[i])) % mod;
            ans = ((long long int)ans + now) % mod;
            tree.update(a[i], now);
        }

printf("Case %d: %d\n", ++kase, ans);
    }

return 0;
}
```

------

## Problem K coachyang1000 的传说

签到题，用map+priority_queue即可，取出每个题的前五大即可。当然，sort之类的也可以了。

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
map<string,int>ma;
map<int,string>sma;
priority_queue<int>q[1010];
int n;
void init()
{
	ma.clear();
	sma.clear();
	int i;
	for(i=0;i<=1000;i++)
	{
		while(!q[i].empty()) q[i].pop();
	}
}

int main()
{
	int i,j;
	while(scanf("%d",&n)!=EOF)
	{
		init();
		string str;
		int cnt=0;
		for(i=1;i<=n;i++)
		{
			int now;
			cin>>str>>now;
			if(ma.count(str)==0)
			{
				ma[str]=cnt++;
				sma[cnt-1]=str;
			}
			q[ma[str]].push(now); 
		}
		int ans=0;
		for(i=0;i<cnt;i++)
		{
			int now;
			for(j=1;j<=5;j++)
			{
				if(q[i].empty()) break; 
				now=q[i].top();
				q[i].pop();
				ans+=now;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
} 
```

------

## Problem L LC与脱发

题目描述说的很玄学，但是自己看看，`图G中所有的生成树（如果有的话）都被 LC 选过一次以上`，那如果整个图是连通图，则所有非自环的边都会被染色。否则所有边都不会被染色。

```cpp
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 100000+10;

int n, m;
bool used[N];
vector<int>G[N];

queue<int>Q;
void bfs(int x)
{
	memset(used, 0, sizeof(used));
	used[x] = true;
	Q.push(x);
	while(!Q.empty())
	{
		int x = Q.front(); Q.pop();
		for(int v : G[x])
			if(!used[v])
			{
				used[v] = true;
				Q.push(v);
			}
	}
}

int main()
{
	while(scanf("%d%d", &n, &m) != EOF)
	{
		for(int i = 1; i <= n; i++)
			G[i].clear();

int ans = 0;
		for(int i = 1; i <= m; i++)
		{
			int u, v;
			scanf("%d%d", &u, &v);
			if(u==v)
				ans++;
			G[u].push_back(v);
			G[v].push_back(u);
		}
		bfs(1);
		bool safe = true;
		for(int i = 1; i <= n; i++)
			if(!used[i])	
				safe = false;
		if(!safe)
			ans = m;
		printf("%d\n", ans);
		fflush(stdout);
	}
}
```

Last modification：May 14th, 2019 at 08:28 am

If you think my article is useful to you, please feel free to appreciate

Comment *

私密评论

Name *

Email *

Site

BITSS 2018 寒假集训算法总结赛题解（Unofficial）

xzm2019 • 2019 年 03 月 03 日

- O for passing during the contest
- Ø for passing after the contest
- ! for attempted but failed
- · for having not attempted yet

## Problem A Lancern 与数字序列

长文预警！！！（以下内容来自原官方题解）如想跳过建议点击右侧目录

------

## Problem B bibibibi 与苹果

把$(1)$式取反得，$sum_{L_i-1}-sum_{R_i} \leq L_i$，这样形成了一个全部都是小于等于的不等式组，以此建边，跑最长路即可。

如果最后出现正环，则说明无解，则给出全部苹果。

建议参考这个博文：https://www.cnblogs.com/songorz/p/9386509.html

------

## Problem C 命令行与文件系统

题解略……QAQ

```cpp
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <stack>

using namespace std;

struct node {
    string name;
    node* parent;
    map<string, node *> children;

node *root, *now;
string cmd;

void clear(node** pnode) {
    if (!(*pnode))
        return;

for (auto& child : (*pnode)->children)
        clear(&child.second);

delete *pnode;
    *pnode = NULL;
}

void init() {
    root = new node();
    now = root;
}

// cout << "TRACE: analyze_path: i = " << i << ", j = " << j << endl;
        names.push_back(path.substr(i, j - i));

i = j + 1;
    }
}

void cd() {
    string path;
    cin >> path;

vector<string> names;
    analyze_path(names, path);

// for (const string& item : names)
    //     cout << "TRACE: item = " << item << endl;

bool absolute = true;
    if (names[0].length() != 0)
        absolute = false;

void rm() {
    string name;
    cin >> name;

int main(int argc, char* argv[]) {
    root = NULL;

int q;
    while (cin >> q) {
        clear(&root);
        init();

return 0;
}
```

------

## Problem D 关灯

然后就有了我的惨案：

~~然而由于cf的评测机较快，我把我第一发的提交扔上去就直接AC了！！！（然而我想了想没有改时限）~~

```cpp
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int inf = 0x3F3F3F3F;

int steps[100005];

int flip(int mask, int i, int j) {
    if (i < 0 || i >= 4 || j < 0 || j >= 4)
        return mask;
    else
        return mask ^ (1 << (i * 4 + j));
}

void bfs() {
    memset(steps, 0x3F, sizeof(steps));
    queue<int> q;

q.push(0);
    steps[0] = 0;

while (!q.empty()) {
        int now = q.front();
        q.pop();

char grid[4][5];

int main(int argc, char* argv[]) {
    bfs();

int t;
    scanf("%d", &t);

while (t--) {
        for (int i = 0; i < 4; ++i)
            scanf("%s", grid[i]);

if (steps[mask] == inf)
            puts("-1");
        else
            printf("%d\n", steps[mask]);
    }

return 0;
}
```

------

## Problem E 一起去划船

签到题，贪心，把所有人按照时间从小到大排序，如果她开心就让她划，不开心就让她最后再划。

```cpp
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<stack>
typedef long long ll;

using namespace std;
const int maxn = 1e5 + 10;
ll t[maxn], temp;
int cas, ans, n;

for (int i = 1; i <= n; i++)
			if (t[i] >= temp)
				ans++, temp += t[i];
		printf("%d\n", ans);
	}
}
```

------

## Problem F Teammates and Red Envelopes

因此显然这题可以通过二分答案完成。注意起始的右界为$10^9$是不够的，要开为$2*10^9$。同此同时注意$l+r$可能会超过`int`的范围。

```cpp
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
int cnt1, cnt2, x, y;

bool can(int v){
	int a = v - v / x;
	int b = v - v / y;
	int c = v - v / (x * y) ;
	return (c >= cnt1 + cnt2) && cnt1 <= a && cnt2 <= b;
}

------

## Problem G 小清河取景记

由于大家同时去集合，所以移动是同时的，因此只需要枚举每个人去哪个地方取景即可。同样采用二分答案的方式即可。

```cpp
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <stack> 
#include <math.h>
#include <queue>
using namespace std;

int n,k;
long long p,a[2002],b[2005],vis[2005];

int solve(long long x){
	int i,j;
	int cnt=0;

long long bsearch(long long left,long long right){
	long long mid,ret=-1;

while(left<=right){
		mid=left+(right-left)/2;
		if(solve(mid)){
			ret=mid;
			right=mid-1;
		}
		else
		    left=mid+1;
	}
	return ret;
}

int main(){
	int i;
	long long ans;

return 0;
}
```

------

## Problem H bibibibi 的超级异或计算器

我们注意前两个要求，就是单点修改，区间查询异或和，显然只需要把我们学过的线段树的加号改成异或即可。

int tree[400001];
int val[100001];
void push(int rt)     //合并区间答案操作 
{
	tree[rt]=tree[rt << 1]^tree[rt << 1 | 1];   //求最大值用max函数代替就好 
}

------

## Problem I Lylist 与魔法卡牌 Episode. 1

最大生成树相对于最小生成树的变化就是把边权排序顺序进行改变即可。

------

## Problem J Lylist 与魔法卡牌 Episode. 2

题目要求不下降子序列的个数，我们可以把它进行一个转化。在每个数位置上的答案就等于比他小的答案+他本身。使用树状数组进行维护即可。

```cpp
#include <cstdio>
#include <algorithm>

using namespace std;

const int mod = 1000000007;

class binary_indexed_tree {
    #define LSB(x)      ((x) & -(x))

int tree[100005];
    int n;

public:
    void init(int n) {
        this->n = n;
        for (int i = 0; i <= n; ++i)
            tree[i] = 0;
    }

void update(int pos, int delta) {
        while (pos <= n) {
            tree[pos] = ((long long int)tree[pos] + delta) % mod;
            pos += LSB(pos);
        }
    }

int query(int pos) {
        int ans = 0;
        while (pos > 0) {
            ans = ((long long int)ans + tree[pos]) % mod;
            pos -= LSB(pos);
        }
        return ans;
    }
};

int a[100005];
binary_indexed_tree tree;
int n;

int main(int argc, char* argv[]) {
    int t;
    scanf("%d", &t);

int kase = 0;
    while (t--) {
        scanf("%d", &n);

int maxa = 0;
        for (int i = 1; i <= n; ++i) {
            scanf("%d", &a[i]);
            maxa = max(maxa, a[i]);
        }

int ans = 0;
        tree.init(maxa);

for (int i = 1; i <= n; ++i) {
            int now = (1 + tree.query(a[i])) % mod;
            ans = ((long long int)ans + now) % mod;
            tree.update(a[i], now);
        }

printf("Case %d: %d\n", ++kase, ans);
    }

return 0;
}
```

------

## Problem K coachyang1000 的传说

签到题，用map+priority_queue即可，取出每个题的前五大即可。当然，sort之类的也可以了。

```cpp
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
map<string,int>ma;
map<int,string>sma;
priority_queue<int>q[1010];
int n;
void init()
{
	ma.clear();
	sma.clear();
	int i;
	for(i=0;i<=1000;i++)
	{
		while(!q[i].empty()) q[i].pop();
	}
}

------

## Problem L LC与脱发

```cpp
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

const int N = 100000+10;

int n, m;
bool used[N];
vector<int>G[N];

int main()
{
	while(scanf("%d%d", &n, &m) != EOF)
	{
		for(int i = 1; i <= n; i++)
			G[i].clear();

BITSS 2018 寒假集训算法总结赛题解（Unofficial）

Leave a Comment

2019南昌邀请赛网络赛个人记录（附官方题解）

北京理工大学第七届程序设计新生赛题解（unofficial）

第 43 届 ACM/ICPC 亚洲区域赛（南京）总结

北京理工大学第八届程序设计新生赛题解

Beijing Institute of Technology 2019.6 Monthly Contest 题解

Beijing Institute of Technology 2019.6 Monthly Contest 题解

第43届ACM-ICPC亚洲区域赛（青岛）个人总结

lintcode 384. 最长无重复字符的子串

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 现场赛题解

BITSS 2018 寒假集训算法总结赛题解（Unofficial）

BITSS 2018 寒假集训算法总结赛题解（Unofficial）

Leave a Comment

BITSS 2018 寒假集训算法总结赛 题解 （Unofficial）

BITSS 2018 寒假集训算法总结赛题解（Unofficial）