A
给出一个数字，例如18292，你可以选定前任意位，将它翻转，问多少次反转可以变为偶数，或者无法变为偶数即输出-1
A比较简单，如果每一位都是奇数，那调换顺序不能出现偶数，输出-1
否则如果本身就是偶数，那么不用调换，输出0
否则如果首位是偶数，那直接反转即可，输出1
否则输出2
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
int t;
signed main()
{
cin >> t;
while(t --)
{
int n; cin >> n;
vector<int> v;
while(n) v.pb(n % 10), n /= 10;
bool odd = true;
for(auto x : v)
odd |= !(x & 1);
if(odd) cout << -1 << endl;
else if(v[0] % 2 == 0) cout << 0 << endl;
else if(v.back() % 2 == 0) cout << 1 << endl;
else cout << 2 << endl;
}
}
B
给你两个数字，如248，200，每次要么分别取1，3，要么分别取2，2，要么分别取3，1
问最多可以取多少次
我写的是，先通过交换保证a < b
因为每次a取1，b取3的时候，差距缩小2，
并且按题目要求，只有取1，3和2，2这两种组合。
那么我分两段取，第一段取1，3让双方差距缩小到1或0
然后每次各取2人即可
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
int t;
signed main()
{
cin >> t;
while(t --)
{
int a, b;
cin >> a >> b;
if(a > b) swap(a, b);
int res = min(a, (b - a) / 2);
a -= res;
b -= res * 3;
res += min(a / 2, b / 2);
cout << res << endl;
}
}
C
给定一个排列，例如[3,1,4,2]
你需要依据它的要求进行操作
每次取端点较小值，如果它在左边，就放在新数列左边，否则放在右边
我来示范一下
[3, 1, 4, 2] []
[3, 1, 4] [2]
[1, 4] [3, 2]
[4] [1, 3, 2]
[] [4, 1, 3, 2] 或 [1, 3, 2, 4]
但题目稍微绕了一下，说它给你结果序列，问你是否存在原来的序列
例如[1, 3, 2, 4]你就可以找到原来的序列是[3, 1, 4, 2]
而[1, 3, 5, 4, 2]就找不到原来的序列了
就简单模拟一下即可，不是给了我们结果序列吗
我们每次取较大的数插回到原序列，因为越大的数肯定是越晚出来的
我们用一个双端队列实现就OK了
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
int t;
cin >> t;
while(t --)
{
for(int i = 1; i <= 10; i ++);
int n;
cin >> n;
vector<int> a(n);
for(int i = 0; i < n; i ++) cin >> a[i];
int i = 0, j = n - 1;
deque<int> q;
if(a[i] < a[j]) q.push_back(a[j --]);
else q.push_back(a[i ++]);
while(i <= j)
{
if(a[i] < q.back()) q.push_front(a[i ++]);
else if(a[j] < q.front()) q.push_back(a[j --]);
else break;
}
if(i > j) for(auto x : q) cout << x << ' ';
else cout << -1;
cout << endl;
}
}
D
我相信每一个母语非英语的人读D都烦死了吧hhhhh
我用平板好像传不了图，不知道怎么用文字表达。。
题意是，先给一个数组，例如[3, 1, 1, 3, 1]
其实意思就是1，4号节点的双亲节点是3号节点，
2，3，5号节点的双亲节点是1号节点，于是你就可以画出一棵树了
这个数组我代码里写的是f，也就意味着f[2] = 1相当于有一条(1, 2)的边
并且如果要从2走向根节点必须往1走
又给了一个数组，例如[3, 1, 2, 5, 4]
这是个排序数组，就是3号节点的距离最小，然后是1号，然后是2号
距离指什么呢？指到根节点的距离
根节点是谁呢？第一个数组中，如果f[i] = i
也就是说自己的爸爸是自己，那它就是根节点了。。（奇怪的比喻
所以现在我们有了一棵树，以及一个排列
我看群里他们好多人用bfs，我写的不是，我写的也不知道叫啥
叫数数吧？？因为就一个cnt变量贯穿始终hhh
我们明确一些东西
它要我们求什么？
要求输出一个数组，我们不是f数组中每个元素对应一条边嘛
现在要求输出每条边对应的权重
给出这样的权重组合，我们可以得到这些点与根节点的距离符合p数组的要求
OK然后就是找找规律
我画了一棵奇丑无比的大树，然后我随便找了一个点作为距离最小的点
我发现，如果不是根节点的话，这种树是不存在的，因为它还有父节点
而它的父节点离根节点一定更近。
由此又推出，如果出现排序中的任何一个点，它的父节点还未出现
意味着这个排列不合理，
因为它与根节点的距离等于它与它爹的距离加上它爹与根节点的距离啊
而如果它爹已经更新了，那么轻易可以证明，这个排列至此为止是合理的
我的做法是
1 找出根节点
2 标记所有节点为未遍历
3 按距离顺序遍历每个节点，如果这个节点不是根节点并且它爹还没出现，那这个排列错误，跳出
4 如果它爹出现了，那它就是合理的，它只要比之前出现的节点与根节点的距离都远，比之后的都近就好了
5 综上，我们让根节点意外第一个点与根节点的距离为1，第i个点的距离为i就好了
6 如何做到，我们可以立刻知道每个节点它爹的距离（因为我们确保它爹更新过了）
然后我们也知道我们想给他安排的距离是多少
题目不是问他到他爹的距离嘛
那不就是它应该有的距离减去它爹的距离
然后我们再记录一下它的距离，这样它儿子问它的时候，它也可以说出来它自己的距离啦
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int f[N], p[N], w[N], d[N], st[N];
signed main()
{
int t;
cin >> t;
while(t --)
{
int n; cin >> n;
for(int i = 1; i <= n; i ++) cin >> f[i];
for(int i = 1; i <= n; i ++) cin >> p[i];
int root, cnt = 0;
for(int i = 1; i <= n; i ++)
{
if(i == f[i]) root = i;
st[i] = 0;
}
bool suc = true;
w[root] = 0;
for(int i = 1; i <= n; i ++)
{
int now = p[i], pa = f[now];
if(now != root && !st[pa])
{
cout << -1 << endl;
suc = false;
break;
}
st[now] = 1;
if(now == root) d[now] = 0;
else
{
w[now] = ++cnt - d[pa];
d[now] = cnt;
}
}
if(suc)
{
for(int i = 1; i <= n; i ++) cout << w[i] << ' ';
cout << endl;
}
}
}
E1
就是一个捣蛋鬼邀请了一群捣蛋鬼来他家里玩咯
这个捣蛋鬼在1号房间，然后给你他家的地图，还告诉你其他捣蛋鬼最初在那些房间，
游戏开始，那些捣蛋鬼就要来抓主人
注意，这是个树图，没有回路
每秒钟所有人可以移动一个房间，问你这个捣蛋鬼能不能保证获胜
能则输出YES，否则输出NO
这个捣蛋鬼赢的条件是它到了终点房间，路上没有遇到别的捣蛋鬼emmm
莫名想到鱿鱼游戏
我用dfs做的
逻辑是 从1号房间出发，例如1号可以通往2，3，4号房间，我枚举这三个房间有没有一条路是活的，如果有，那么我就能活，就赢了
那么怎么判断2，3，4号房间有没有活路呢，有一个标准
首先，我到达1号房间需要走0步，对吧，那么去2，3，4号房间都需要走1步
我就看其他捣蛋鬼到2，3，4号房间的最近距离是否大于1，如果大于，那么我就是安全的，这个房间就可以到达，reach[i] = true
否则reach[i] = false
而怎么算最近捣蛋鬼距离nearest呢？
也是dfs这个房间能通往的房间，如果这个房间有鬼，那就返回0，否则就返回距离鬼最近的孩子跟鬼的距离加1（绕不绕。。
这样我就知道了哪些房间可以到达，哪些房间不可以
我再枚举所有房间，如果这个房间是终点并且可以到达，那么恭喜，赢了。
没有这样的房间，输了
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int N = 2e5 + 10;
vector<int> h[N];
int n, t, k, x, y, ghost[N], st[N], reach[N];
int dfs(int now, int dis)
{
st[now] = true;
if(ghost[now]) return 0;
int nearest = N;
for(auto x : h[now])
if(!st[x])
nearest = min(nearest, dfs(x, dis + 1));
if(nearest + 1 > dis) reach[now] = true;
// cout << now << ' ' << reach[now] << ' ' << dis << ' ' << nearest << endl;
return nearest + 1;
}
bool dfs2(int now)
{
if(h[now].size() == 1 && now != 1) return true;
reach[now] = false;
for(auto & x : h[now]) if(reach[x] && dfs2(x)) return true;
return false;
}
signed main()
{
cin >> t;
while(t --)
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)
{
h[i].clear();
reach[i] = st[i] = ghost[i] = 0;
}
for(int i = 1; i <= k; i ++)
{
cin >> x;
ghost[x] = 1;
}
for(int i = 1; i < n; i ++)
{
cin >> x >> y;
h[x].pb(y);
h[y].pb(x);
}
dfs(1, 0);
// for(int i = 1; i <= n; i ++) cout << reach[i] << ' ';
// cout << endl;
if(dfs2(1)) cout << "YES" << endl;
else cout << "NO" << endl;
}
}
E2
E2其实与E1改动不多，问的是坏孩子的角度，就是被邀请的捣蛋鬼朋友的角度
问题是留下多少捣蛋鬼可以把主人抓住，如果无论如何都抓不住，那就输出-1，否则输出留下的捣蛋鬼的个数，你看，它没有要求你说留下哪些捣蛋鬼，一下子就变得很容易
仍然是dfs，我的dfs思路是，先按原来的得到每个房间是否可以到达
题目转化为，要把1号房间的所有出路堵死需要留下多少人
还是例如1号可以去2，3，4号
假如我们发现2号去不了，那也就是说如果走2号，会有坏人在你之前到达2号，所以2号这条路通往的子树里面留一个捣蛋鬼就够了，对，就留那个可以最快速度来到这个位置的
所以num ++;
而如果走3号，你发现3号是可到达的，那你就去看把三号房间的所有出路堵死需要留下多少人，那就是dfs(3)人嘛
所以输出dfs(1)即可，当然，同时需要判断有没有堵不死的情况，over
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
const int N = 2e5 + 10;
vector<int> h[N];
int n, t, k, x, y, suc, ghost[N], st[N], reach[N];
int dfs(int now, int dis)
{
st[now] = true;
if(ghost[now]) return 0;
int nearest = N;
for(auto x : h[now])
if(!st[x])
nearest = min(nearest, dfs(x, dis + 1));
if(nearest + 1 > dis) reach[now] = true;
return nearest + 1;
}
int dfs2(int now)
{
if(now != 1 && h[now].size() == 1)
suc = false;
st[now] = true;
int num = 0;
reach[now] = false;
for(auto x : h[now])
{
if(st[x]) continue;
if(reach[x]) num += dfs2(x);
else num ++;
}
return num;
}
signed main()
{
cin >> t;
while(t --)
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)
{
h[i].clear();
reach[i] = st[i] = ghost[i] = 0;
}
for(int i = 1; i <= k; i ++)
{
cin >> x;
ghost[x] = 1;
}
for(int i = 1; i < n; i ++)
{
cin >> x >> y;
h[x].pb(y);
h[y].pb(x);
}
dfs(1, 0);
suc = true;
for(int i = 1; i <= n; i ++) st[i] = false;
int res = dfs2(1);
if(suc) cout << res << endl;
else cout << -1 << endl;
}
}
F
F就很简单了，双指针嘛
问题是，小朋友开了一家银行，有很多人来存钱取钱，给你一个序列，比如
[-16, 2, -6, 8]，并且告诉你小朋友最开始有10块钱
他很坏，他可以不那么早开门，第一个人取16块，他给不起，他就等他走了再开门
假如他在时间为1的时候开门，那他可以服务的客人是0嘛，但是如果在2时刻开门
他可以先服务第一个人，存了2块，他就有12块了，服务第二个人，取了6块，他还有6块，服务第三个人，存了8块，他又有14块了
问你，他想要服务最多的人，可以什么时候开门，什么时候关门
注意他只能开关门一次
不知道这个是不是叫滑动窗口来着
这个问题有一定单调性
比如这个数列的最优解是2，4，
如果2开门，4关门可以满足的话，意味着2，3一定可以满足，2，2，也一定可以满足
所以当我们左端点固定时，虽说要枚举右端点，但是有单调性，一直往右就行
如果2，4满足，第5个人要取100000块，那么就不行了，我们就只能从左边缩
意思是如果2，5不可以，那么2，6一定不可以，但是3，5可能可以
如果3，5不可以，3，6肯定不可以，但是4，5可能可以
如果还是不行，那看看5，5
还不行，那左端点再移动，就把这个5排出去了，就相当于看看6以后的情况了
其实想想也很合理，你取那么多钱，我这个点我不开了，诶，就是玩儿
所以我们将枚举所有左右端点的$(O(n*n))$的复杂度缩减到了线性的$O(n)$
(20w个点，你暴力肯定过不去的)
注意，题目想问最多的连续，那么它会在什么时候出现？当然是右端点扩张的时候可能更新最大值，左端点萎缩的时候是不可能更新记录的
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int a[N];
signed main()
{
int t;
cin >> t;
while(t --)
{
int l = 1, r = 1;
int resl, resr, M = 0;
int n, s; cin >> n >> s;
for(int i = 1; i <= n; i ++) cin >> a[i];
while(r <= n)
{
if(s + a[r] >= 0)
{
s += a[r ++];
if(r - l > M)
{
M = r - l;
resr = r - 1;
resl = l;
}
}
else if(l == r) l ++, r ++;
else s -= a[l ++];
}
if(M) cout << resl << ' ' << resr << endl;
else cout << -1 << endl;
}
}
G
G比赛没写出来，现在也懒得写了2333，反正也许大概应该是二分吧，下班！
tql吧
ucl佬orz
我也补完6题打卡下班了明天写E2，大佬是真的强，向大佬学习orz~
orz
插眼
还在写？
对hhh
一会就写完了