程序员进阶之算法练习（七十三）
题目1
题目链接 题目大意： 有两种车分别有4个轮子和6个轮子，现在只知道若干个车的轮子总数，想知道最少和最多有几辆车；
输入： 第一行，整数𝑡 表示t个样例 𝑡 (1≤𝑡≤1000) 每个样例一行 整数 𝑛，表示 𝑛个轮子 (1≤𝑛≤10e18)
输出： 每个样例一行，分别输出最少和最多有几辆车，如果没有则输出-1；
Examples input 4 4 7 24 998244353998244352 output 1 1 -1 4 6 166374058999707392 249561088499561088
题目解析： 容易知道，如果n为奇数，则题目无解； n为偶数，如果n=2则无解，其他必然有解； 最少的情况，全部用6轮，剩下的有2个轮子和4个轮子的情况；如果剩2个轮子，则总数+1（将1个6改成4就好）；如果剩4个轮子，则总数+1； 最多的情况，全部用4轮，如果剩2个轮子，则总数不变（将1个4改成6就好）；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
lld n;
cin >> n;
if (n < 4 || n % 2) {
cout << -1 << endl;
}
else {
lld ansMin = (n / 6) + (n % 6 != 0);
lld ansMax = (n / 4);
cout << ansMin << " " << ansMax << endl;
}
}
}
}
ac;题目2
题目链接 题目大意： 给出n个整数的数组a，现在有两个操作： 1、将第i个数字替换为x；（x为输入的整数） 2、将整个数组替换为x；（x为输入的整数） 现在想知道经历q次操作，每次操作完数组的和；
输入： 第一行，整数 𝑛 and 𝑞 (1≤𝑛,𝑞≤2⋅1e5) 第二行n个整数 𝑎1,…,𝑎𝑛 (1≤𝑎𝑖≤1e9) 接下来q行，每行第一个数字是t，表示操作1或者操作2； 如果t=1，则接下来输入数字i和x (1≤𝑖≤𝑛, 1≤𝑥≤1e9) 如果t=2，则接下来输入数字x (1≤𝑥≤1e9)
输出： 每个操作一行，输出操作后的数字和；
Examples input 5 5 1 2 3 4 5 1 1 5 2 10 1 5 11 1 4 1 2 1
output 19 50 51 42 5
题目解析： 朴素的做法，对于数组a，操作1则修改a[i]，时间复杂度O（1）； 操作2则全量修改数组a，时间复杂度O（N）； 计算数字和的复杂度，也是O（N），总的复杂度是（NQ）；
对于操作2，全量修改没必要，用变量记住当前整个数组已经修改即可，数字和也不需要累计，直接x和n的乘积即可； 但是这个变量要如何兼容操作1？ 不用兼容，单独用一个map来记录操作1，当遇到操作2的时候再把map清空；正常往map里面添加一个值的时候，我们就可以实时算出来这个值带来的总和diff，O（1）就可以维护这个数组和； 将这个思路流程化，那么就是记录一个当前和sum； 然后生成一个map，记录每个位置对应的值； 当遇到操作1，则访问当前map，拿到当前值（如果map没有就是操作2的值），生成新的值记录到map，并更新diff到sum； 遇到操作2，则清空map并更新sum； 总的复杂度是O(NlogN)；
class Solution {
static const int N = 201010;
lld a[N];
public:
void solve() {
lld n, q;
cin >> n >> q;
map<lld, lld> h;
lld cur = 0, sum = 0;
for (int i = 1; i <= n; ++i) {
lld x;
cin >> x;
h[i] = x;
sum += x;
}
while (q--) {
int k;
cin >> k;
if (k == 1) {
int i, x;
cin >> i >> x;
if (h[i]) {
sum += x - h[i];
h[i] = x;
}
else {
sum += x - cur;
h[i] = x;
}
}
else {
int x;
cin >> x;
cur = x;
sum = cur * n;
h.clear();
}
cout << sum << endl;
}
}
}
ac;题目3
题目链接 题目大意： 有一个n x n的国际象棋棋盘，现在有3个操作： 操作1，往棋盘（x，y）上面放一个车，车可以攻击同一行或者同一列； 操作2，移除棋盘（x，y）上面的车； 操作3，询问区域(𝑥1,𝑦1)到(𝑥2,𝑦2)内所有位置，是否都可以被车攻击到； 现在有q个操作，想知道每次操作3 之后的结果；
输入： 第一行，整数 𝑛 and 𝑞 (1≤𝑛,𝑞≤2⋅1e5) 接下来q行，每行第一个数字是t，表示操作1、2、3； 如果t=1或者2，则接下来输入数字x和y； (1 ≤ 𝑥,𝑦 ≤ 𝑛) 如果t=3，则接下来输入数字x1、y1、x2和y2； (1 ≤ 𝑥1 ≤ 𝑥2 ≤ 𝑛, 1 ≤ 𝑦1 ≤ 𝑦2 ≤ 𝑛)
输出： 每个操作3一行，输出YES或者NO；
Examples input 8 10 1 2 4 3 6 2 7 2 1 3 2 3 6 2 7 2 1 4 3 3 2 6 4 8 2 4 3 3 2 6 4 8 1 4 8 3 2 6 4 8
output No Yes Yes No Yes
题目解析： 我们用row[N]和column[N]来表示行和列，那么添加(x, y)就可以拆分为row[x]和column[y]的变动； 操作1和操作2比较简单，直接操作数组即可； 操作3，朴素的想法是遍历所有行、列，看看是否满足，所有行或者所有列都被车覆盖；这样的复杂度复杂度是O(N)； 分析这个遍历过程，当我们想知道row[x1]到row[x2]这个区间，是否全部为1，其实可以转化为前n项和之差：只要sum[x2] - sum[x1] = x2 - x1，就满足条件； 于是问题转化为，如何快速维护sum[i]？（row前i个元素的和） 这里偷个懒，用树状数组来支持。（就不展开介绍怎么用树状数组了，可以自己百度，有非常详细介绍）
class TreeArray {
static const int N = 201001;
int tree[N];
int low_bit(int x)
{
return x&-x;
}
public:
void tree_add(int x,int v, int n)
{
while(x<=n)
{
tree[x] += v;
x+=low_bit(x);
}
}
int tree_sum(int x)
{
int sum=0;
while(x)
{
sum += tree[x];
x-=low_bit(x);
}
return sum;
}
};
class Solution {
static const int N = 201001;
TreeArray rowArr, columnArr;
int rowCnt[N], columnCnt[N];
public:
void solve() {
int n, q;
cin >> n >> q;
while (q--) {
int k;
cin >> k;
if (k == 1) {
int x, y;
scanf("%d%d", &x, &y);
int add = 1;
rowCnt[x] += add;
if (rowCnt[x] == 1) {
rowArr.tree_add(x, add, n);
}
columnCnt[y] += add;
if (columnCnt[y] == 1) {
columnArr.tree_add(y, add, n);
}
}
else if (k == 2) {
int x, y;
scanf("%d%d", &x, &y);
int add = -1;
rowCnt[x] += add;
if (rowCnt[x] == 0) {
rowArr.tree_add(x, add, n);
}
columnCnt[y] += add;
if (columnCnt[y] == 0) {
columnArr.tree_add(y, add, n);
}
}
else {
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int rowSum = rowArr.tree_sum(x2) - rowArr.tree_sum(x1 - 1);
int columnSum = columnArr.tree_sum(y2) - columnArr.tree_sum(y1 - 1);
if (rowSum == (x2 - x1 + 1) || columnSum == (y2 - y1 + 1)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
}
}
}
}
ac;题目4
题目链接 题目大意： 有一个n个节点的有向图，每个节点有一个数字a[i]； 现在可以选择某个节点，从这个节点开始沿着有向边走，记录每个访问到的节点，并将这个访问顺序记录下来； 现在想知道，如果需要访问k个节点，访问顺序中的节点数字最大值的最小值是多少；
输入： 整数 𝑛, 𝑚 and 𝑘 (1≤𝑛≤2⋅1e5, 0≤𝑚≤2⋅1e5, 1≤𝑘≤10e18) 接下来n个整数 𝑎𝑖 (1≤𝑎𝑖≤1e9) 接下来是m条行，每行有整数 𝑢 and 𝑣 ，表示u到v的边(1≤𝑢≠𝑣≤𝑛) 题目保证没有指向自己的边，也没有多重边；
输出： 输出k个节点，节点数字最大值的最小值是多少； 如果无法访问到k个节点，则输出-1；
Examples input 6 7 4 1 10 2 3 4 5 1 2 1 3 3 4 4 5 5 6 6 2 2 5
output 4
题目解析： 先用朴素的思维来分析，假如我们需要访问1个节点，那么就是寻找节点的最小值； 如果是需要访问2个节点，那么问题就变得复杂，因为节点2->3的解是比 节点1->4的解更优；那么节点的最小值就失去了意义； 如果是想遍历整个图，并且在遍历过程中去保留这个最大值的最小，无疑是非常复杂的；
那么换一种思想，假如我用二分来处理这个最大值，得到mid，如果a[i]<=mid认为a[i]可以访问，如果a[i]>mid则认为节点不可方案； 题目变成在有向图中，询问遍历步数最多是否能到k；
先不考虑环的情况，在一个有向图中要去判断遍历步数最多情况，可以枚举所有起点出发的情况，然后通过深度优先搜索来记录遍历过程中的步数； 当出现环的时候，我们可以把步数设置为一个很大的值，这样也可以统一逻辑处理。
那么，问题又变成如何在有向图中判断环的存在？ 当我们在深度优先遍历的过程中，假如当前点是u，下一个节点是v，此时有两种情况，v是已经访问过，v还没访问过； 如果v没有访问过，那么就访问v即可； 如果v已经访问过，此时又有两种情况，如果v已经访问过，但是还在当前的递归栈中，则证明v已经可以和u构成环；（step[u]=inf，inf表示一个很大值） 如果是v已经访问过，但是和当前递归栈中没有关系，怎么v只是普通访问过的节点；（此时step[u]=max(step[u], step[v]+1);
class Solution {
static const lld N = 201001;
static const lld inf = 0x7fff7fff3fff7fff;
lld a[N];
int vis[N]; // 0表示没访问，1表示访问中，2表示访问后
lld step[N], n;
vector<lld> g[N];
void dfs(lld u, lld cur, lld mid) {
vis[u] = 1;
step[u] = 1;
for (lld i = 0; i < g[u].size(); ++i) {
lld v = g[u][i];
if (a[v] > mid) {
continue;
}
if (!vis[v]) {
dfs(v, cur + 1, mid);
step[u] = max(step[u], step[v] + 1);
}
else {
if (vis[v] == 1) {
step[u] = inf;
}
else {
step[u] = max(step[u], step[v] + 1);
}
}
}
vis[u] = 2;
}
bool check(lld mid, lld k) {
memset(vis, 0, sizeof(vis));
memset(step, 0, sizeof(step));
dfs(0, 0, mid);
for (lld i = 1; i <= n; ++i) {
if (a[i] > mid) {
continue;;
}
if (step[i] >= k) {
return true;
}
}
return false;
}
public:
void solve() {
lld m, k;
cin >> n >> m >> k;
lld l = 0, r = 0x7fffffff;
for (lld i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
r = max(r, a[i]);
}
for (lld i = 0; i < m; ++i) {
lld u, v;
scanf("%lld%lld", &u, &v);
g[u].push_back(v);
}
for (int i = 1; i <= n; ++i) {
g[0].push_back(i);
}
lld ans = -1;
while (l <= r) {
lld mid = (l + r) / 2;
if (check(mid, k)) {
ans = mid;
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << ans << endl;
}
}
ac;题目5
题目链接 题目大意： 有n个格子排成一行，每个格子有一个灯，灯有两个方向：L和R，分别表示朝左和朝右； 当一个灯朝左时，它能照亮其左边的格子；（不包括灯所在格子） 当一个灯朝右时，它能照亮其右边的格子；（不包括灯所在格子） 现在允许选择某个格子，交换该格子和右边格子的灯，灯的朝向不变；（不能选择最右边的格子） 现在想知道，是否能够让每个格子都能被灯照亮；
输入： 第一行，整数𝑡 表示t个样例𝑡 (1≤𝑡≤10000) 每个样例2行，第一行整数 𝑛 (2≤𝑛≤100000) 第二行n个字符'L' 和 'R'
输出： 每个样例一行，如果无解输出-1，如果不需要交换输出0，如果需要交换则输出交换第x个格子；（1 <= x < n）
Examples input 6 2 LL 2 LR 2 RL 2 RR 7 LLRLLLR 7 RRLRRRL output -1 1 0 -1 3 6
题目解析： 样例给了一个比较关键的数据，当字符串出现RL，题目就必然存在解； 基于此我们继续分析，当字符串只有L或者只有R时，必然无解； 当字符串存在L和R时，必然有解：因为总是能找到L和R相交的位置，如果是R和L，则无需交换；如果是L和R，则进行交换；
class Solution {
static const int N = 201010;
int a[N];
public:
void solve() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
string str;
cin >> str;
int index = -1;
for (int i = 0; i + 1 < n; ++i) {
if (str[i] != str[i + 1]) {
index = str[i] == 'R' ? 0 : (i + 1);
break;
}
}
cout << index << endl;
}
}
}
ac;腾讯云开发者
