放假后的第一场个人训练赛，今天状态实属不好，加上这次的题有点绕，明明有思路了但是在代码实现的时候经常会打到一半就大脑空白，逻辑转换能力不行，说白了还是得多练。这次题目偏思维的较多，水题少，还是很有价值的一套题，下面是部分题目的题解。
A – Abandoned Animal（思维+贪心）
题意：
有n个超市，有k条信息（i，s），表示物品s在编号为i的超市可以买到。有m个物品要买，给出m件物品的名称，要求按输入的顺序购买所有物品，且访问的超市的编号必须是非严格递增的，若找不到这样的方案输出impossible，若有多种方案输出ambiguous，否则输出unique。
题目分析：
此题可以将购买清单里的物品按照顺序编号，用一个二维vector分别存入每个超市里所含有的购物清单里物品的编号。然后用一个变量表示当前需要购买的物品，从第一个超市开始遍历每个超市，若当前超市有当前需要购买的物品，则购买物品并将变量+1表示完成购买。最后只要判断这个变量是否大于m，大于m说明买完了，方案存在，至于是否唯一价格flag就行，具体看代码。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5+10;
const double PI = acos(-1.0);
unordered_map<string, int> mp;
vector<int> way[maxn];
string a[maxn];
pair<int, string> thing[maxn];
int main(int argc, char const *argv[]) {
int n, k, m;
cin >> n >> k;
for(int i = 0; i < k; i++) {
int id;
string s;
s.resize(20);
scanf("%d %s",&id,&s[0]);
thing[i].first = id;
thing[i].second = s;
}
cin >> m;
for(int i = 1; i <= m; i++) {
string s;
s.resize(20);
scanf("%s", &s[0]);
mp[s] = i;
}
for(int i = 0; i < k; i++) {//将每件物品的编号分别压给所属的超市
if(mp.find(thing[i].second) == mp.end()) continue;
way[thing[i].first].push_back(mp[thing[i].second]);
}
int now = 1;
int flag = 0;
for(int i = 0; i < n; i++) {
sort(way[i].begin(),way[i].end());//需要保证有序才行
for(int j = 0; j < way[i].size(); j++) {
if(way[i][j] == now - 1) flag = 1;//有多种方案可以购买now-1这个物品
if(way[i][j] == now && now <= m) now++;
}
}
if(now > m) {
if(flag) puts("ambiguous");
else puts("unique");
}
else puts("impossible");
return 0;
}
C – Crowd Control（二分答案）
题意：
给你一张n个点m条边的带权图，找到一条从起点0到终点n-1的路径，使得路径中的最小边权尽可能大。最后输出不在这条路径上但有一个端点属于这条路径的所有边的编号（编号从0-m-1，按照边的输入顺序编号）。
题目分析：
关键信息：找一条路径中的最小边权的最大值，最小值的最大值问题可以朝二分答案去思考。粗略思考可以感觉出，这题的答案具有单调性，所以是可以二分的。首先通过二分每次进行一次dfs可以很快的找到最优的答案，但还有个难点就是怎么输出题目要求的边。
首先，根据二分得到的值再进行一遍dfs，找到路径并标记路径中每个节点的前驱和后继，然后遍历一遍路径的每个点，每次遍历每个节点的所有边，将不属于路径中的边加入到set（去重）中，再输出set即可。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
int head[10000], to[10000], e[10000], ne[10000], tot, id[10000];//链式前向星存图
int nextt[10000],fa[10000];//后继和前驱
bool vis[10000];//是否被访问过
int n, m;
bool flag;
void add(int u, int v, int val, int x) {//链式前向星加边
id[tot] = x;
e[tot] = val;
to[tot] = v;
ne[tot] = head[u];
head[u] = tot++;
}
void dfs1(int now, int val) {//dfs找是否存在边权都大于等于val的从0 - n-1的路径
if (now == n - 1) {
flag = 1;
return;
}
vis[now] = 1;
for (int i = head[now]; i != -1; i = ne[i]) {
int j = to[i];
if (!vis[j] && e[i] >= val) {
dfs1(j, val);
}
}
}
bool check(int val) {//二分的check函数
flag = 0;
dfs1(0, val);
if (flag) return true;
return false;
}
void dfs(int now, int val) {//再次dfs找路径
if (now == n - 1) {
flag = 1;//找到路径了，不用继续递归查找了，回溯这条路径
return;
}
for (int i = head[now]; i != -1; i = ne[i]) {
int j = to[i];
if (!vis[j] && e[i] >= val) {
vis[j] = 1;
dfs(j, val);
if (flag == 1) {//这里很重要，记得return结束，用于回溯确定路径上每个节点的前驱后继
nextt[now] = j;
fa[j] = now;
return;
}
}
}
}
int main(int argc, char const *argv[]) {
cin >> n >> m;
memset(head, -1, sizeof(head));
for (int i = 0; i < m; i++) {
int x, y, val;
cin >> x >> y >> val;
add(x, y, val, i);
add(y, x, val, i);
}
int l = 1, r = 500000;//二分模板
while (l < r) {
memset(vis, 0, sizeof(vis));
int mid = l + r + 1 >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
flag = 0;
memset(vis, 0, sizeof vis);
vis[0] = 1;
dfs(0, l);
set<int> s;
int now = 0;
//找边，自行体会一下，主要是if的条件
while (now != n - 1) {
for (int i = head[now]; i != -1; i = ne[i]) {
if (fa[now] != to[i] && nextt[now] != to[i]) s.insert(id[i]);
}
now = nextt[now];
}
for (int i = head[n - 1]; i != -1; i = ne[i]) {
if (fa[n - 1] != to[i]) s.insert(id[i]);
}
if (s.size() == 0)
puts("none");
else {
for (auto it : s) cout << it << ' ';
}
return 0;
}
D – Disastrous Doubling（思维/暴力）
题意：
实验室中初始细菌数为1，每小时细菌会增长到当前数量的两倍，有 $N$ 小时，每小时会消耗 $b_i$ 个细菌用于实验，问最后会剩多少细菌，$1 \leq N \leq 10^5 $ ，$0 \leq b_i \leq 2^{60}$。
题目分析：
这题有两个做法，一个就是大数模拟直接暴力循环模拟一遍，见代码1（队友Python暴力过的）
还有一种思路：由于细菌复制是加倍复制的，我们找出所有试验中细菌需求最大的一次，如果存在某一时刻，细菌的数量大于细菌最大需求的两倍，那么后面无论怎么试验，细菌数都是稳步上升的，这时我们可以直接在运算的过程中进行取模处理，保证数据不会超longlong。若细菌数小于需求的两倍，由于$0 \leq b_i \leq 2^{60}$，那么细菌数最多只有$2^{61}$个，所以不会超longlong可以不用取模直接暴力，实现见代码2。
代码
代码1
n = int(input())
b = input().split(" ")
flag = True
num = 1
for i in range(n):
num *= 2
if flag == False:
continue
if num >= int(b[i]):
num -= int(b[i])
else:
flag = False
if flag == False:
print("error")
else:
print(num % int(1e9 + 7))
代码2
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e5 + 10;
const double PI = acos(-1.0);
const LL mod = 1e9 + 7;
LL a[maxn];
int main(int argc, char const *argv[]) {
int n;
cin >> n;
LL Max = -1;
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
Max = max(Max, a[i]);
}
LL now = 1;
bool f = 0;//标记当前细菌数是否大于需求最大值的两倍
Max *= 2;
for (int i = 0; i < n; i++) {
if (!f) {//这里可以保证now不会超longlong 直接暴力处理即可
now *= 2;
if (now >= Max) f = 1;//大于两倍需求，f为1
if (now - a[i] < 0) {//细菌不够了，输出error直接结束
puts("error");
return 0;
}
now -= a[i];
} else
now = (now * 2 % mod - a[i] % mod + mod) % mod;//可能超longlong 取模处理
}
cout << now % mod << endl;
return 0;
}
E – Envious Exponents（贪心）
题意：
给你 $N$ 和 $k$，让你找出大于 $N$ 的最小整数，使得可以用 $k$ 个2的不同次幂的和来表示,$1 \le N \le 10^{18}$ and $1 \le k \le 60$。
题目分析：
先将N用二进制表示出来，用贪心的思想：从最低位开始遍历N的所有二进制位，如果遇到一个位是0，将它改成1，然后判断从这个点到最高位有几个1，如果小于等于k个，那就把这个位到最低位的所有1改为0，然后再从最低位开始将0改1直到全部1的个数等于k个（因此前面的判断还要加一个条件：这个位置前面全改为1可以使得1的总数是大于等于k的），这样一定是最优的。
代码：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e3 + 10;
const double PI = acos(-1.0);
LL n, k;
LL a[maxn], cnt;
int main(int argc, char const *argv[]) {
cin >> n >> k;
while (n) {
a[++cnt] = n % 2;
n /= 2;
}
for (int i = 1; i <= 61; i++) {
if (a[i] == 0) {
a[i] = 1;
int tot = 1;
for (int j = i + 1; j <= 61; j++) {
if (a[j] == 1) tot++;
}
if (tot > k || i + tot - 1 < k)
continue;
else {
for (int j = 1; j < i; j++) a[j] = 0;
int j = 1;
while (tot < k) {
a[j++] = 1;
tot++;
}
break;
}
}
}
LL ans = 0, now = 1;
for (int i = 1; i <= 61; i++) {
if (a[i] == 1) ans += now;
now *= 2;
}
cout << ans << endl;
return 0;
}
H – Horror Film Night（贪心）
题意：
两人每人有一个喜爱节目的清单，要你找到尽可能多的节目，使得节目单中不存在连续两个节目都是同一个人不喜欢的，
题目分析：
一共最多有1000000个节目，假设A是第一个人喜欢的，B是第二个人喜欢的，o是两个人都喜欢的，那么节目单大致是ABABOBABAOABAB形式（随便举的例子），如果遇到两个人都喜欢的节目，贪心的思想，下一个节目无论是谁喜欢的都要选，画个图就知道了，代码实现也简单。
代码：
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn = 1e6 + 10;
const double PI = acos(-1.0);
int fi[maxn], se[maxn];
int main(int argc, char const *argv[]) {
int n, m;
cin >> n;
for (int i = 0; i < n; i++) {
int x;
scanf("%d", &x);
fi[x] = 1;
}
cin >> m;
for (int i = 0; i < m; i++) {
int x;
scanf("%d", &x);
se[x] = 1;
}
int f1 = 0, f2 = 0;
int ans = 0;
for (int i = 0; i < 1000000; i++) {
if (fi[i] && se[i]) {
f1 = f2 = 0;
ans++;
} else if (fi[i] && !f1) {
f1 = 1;
f2 = 0;
ans++;
} else if (se[i] && !f2) {
f2 = 1;
f1 = 0;
ans++;
}
}
cout << ans << endl;
return 0;
}
