Codeforces Round 913 (Div. 3) | Fructose’s Notion Blog

type

Post

status

Published

date

Dec 7, 2023

slug

summary

CF1907A. Rook

题目大意

将一个国际象棋棋盘的行从下到上表示为1-8，列从左到右表示为a-h，给出国际象棋中Rook（车）的位置，输出它下一步能走的位置，位置由列行表示，先列后行。

大致思路

车能走的位置只能是同行同列，依次枚举即可。

Solution


#include <bits/stdc++.h>
using namespace std;
 
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  int T;
  cin >> T;
  string first = "abcdefgh";
  string second = "12345678";
  while (T--) {
    string s;
    cin >> s;
    for (auto& i: first) {
      for (auto&j : second) {
        if (i == s[0] && j == s[1]) {
 
        } else if (i == s[0] || j == s[1]) {
            cout << i << j << endl;
        }
      }
    }
  }
}

实际上只需要单独枚举行和列即可，不需要用两个循环，但是不影响通过此题。

CF1907B. YetnotherrokenKeoard

题目大意

有一个键盘破损了，B键变成退格键，删除前一个输入的大写字符，b删除前一个输入的小写字符。输出使用该键盘按照正常方式输入字符后得到的字符串。

大致思路

按照双栈进行模拟即可，当然也可以采用其他方式，只要保证能复杂度找到上一个大写或者小写字符即可。

Solution


#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+6;
int vis[maxn];
int up[maxn];
int down[maxn];
 
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
 
  int t;
  cin >> t;
  while (t--) {
    string str;
    cin >> str;
    int n = str.length();
    int last_up = 0, last_down = 0;
    for (int i = 1; i <= n; i++) {
      vis[i] = false;
      up[i] = 0;
      down[i] = 0;
      if (str[i-1] == 'b') {
        vis[i] = true;
        vis[last_down] = true;
        last_down = down[last_down];
      } else if (str[i-1] == 'B') {
        vis[i] = true;
        vis[last_up] = true;
        last_up = up[last_up];
      } else if (str[i-1] >= 'A' && str[i-1] <= 'Z') {
        up[i] = last_up;
        last_up = i;
      } else {
        down[i] = last_down;
        last_down = i;
      }
    }
    for (int i = 1; i <= n; i++) {
      if (!vis[i]) {
        cout << str[i-1];
      }
    }
    cout << "\n";
  }
}

CF1907C. Removal of Unattractive Pairs

题目大意

在一个字符串中，你可以删除两个相邻但不同的字符，求最后剩余字符的个数。

大致思路

考虑最后剩余的字符串，如果这个字符串有不同的字符，那它必然存在一种两个字符可以删除，因此最后剩下的只可能有一种字符，所以统计出现次数最多的字符个数记为，总字符个数记为，则最终剩余字符个数为。

Solution


use std::io::stdin;

fn main() {
    let t: usize = {
        let mut buf = String::new();
        stdin().read_line(&mut buf).unwrap();
        buf.trim().parse().unwrap()
    };
    for _ in 0..t {
        let n: i32 = {
            let mut buf = String::new();
            stdin().read_line(&mut buf).unwrap();
            buf.trim().parse().unwrap()
        };
        let s = {
            let mut buf = String::new();
            stdin().read_line(&mut buf).unwrap();
            buf.trim().to_string()
        };
        let mut mp = std::collections::HashMap::new();
        for c in s.chars() {
            mp.entry(c).and_modify(|x| *x += 1).or_insert(1);
        }
        let &maxn = mp.values().max().unwrap();
        println!("{}", (n&1).max(maxn*2-n));
    }
}

CF1907D. Jumping Through Segments

题目大意

给出若干个区间，你从0开始，每次最多移动k，依次移动到各个区间上，求最小的k。

大致思路

二分答案即可，每次check都按照k和区间依次计算可行区间。

Solution


use std::io::stdin;

fn check(data: &Vec<(i32, i32)>, x: i32) -> bool {
    let mut l = 0;
    let mut r = 0;
    for &(a, b) in data.iter() {
        l -= x;
        r += x;
        if r < a || l > b {
            return false;
        }
        l = l.max(a);
        r = r.min(b);
    }
    true
}

fn main() {
    let t: usize = {
        let mut buf = String::new();
        stdin().read_line(&mut buf).unwrap();
        buf.trim().parse().unwrap()
    };
    for _ in 0..t {
        let n: usize = {
            let mut buf = String::new();
            stdin().read_line(&mut buf).unwrap();
            buf.trim().parse().unwrap()
        };
        let data: Vec<(i32, i32)> = (0..n).map(|_| {
            let mut buf = String::new();
            stdin().read_line(&mut buf).unwrap();
            let mut iter = buf.trim().split_whitespace();
            (iter.next().unwrap().parse().unwrap(),
             iter.next().unwrap().parse().unwrap())
        }).collect();
        let mut l = 0;
        let mut r = 1_000_000_000;
        while l + 1 < r {
            let mid = l + (r - l) / 2;
            if check(&data, mid) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        for i in l..=r {
            if check(&data, i) {
                println!("{}", i);
                break;
            }
        }
    }
}

CF1907E. Good Triples

题目大意

给定，求满足以下条件的的个数：

大致思路

三个数在相加时不能产生进位，否则它们的数位和肯定大于，因此可以按位分配，而按位分配一定满足这两个条件。接下来考虑，可以考虑排列组合中的“插入法”，假设我们要计算的情况，我们可以考虑下面这样一个问题：有根石头排成一行，在其中插入两根木棍分成三个部分，可选的插入位置有个，则最终的可选方案有个。当然，因为范围比较小，这部分不会的话也可以暴力来做。

Solution


use std::io::stdin;

fn main() {
    let t: usize = {
        let mut buf = String::new();
        stdin().read_line(&mut buf).unwrap();
        buf.trim().parse().unwrap()
    };
    for _ in 0..t {
        let n: i64 = {
            let mut buf = String::new();
            stdin().read_line(&mut buf).unwrap();
            buf.trim().parse().unwrap()
        };
        let mut fa = 1;
        let mut ans = 1;
        while fa <= n {
            let m = n / fa % 10;
            ans *= (m + 1) * (m + 2) / 2;
            fa *= 10;
        }
        println!("{ans}");
    }
}

CF1907F. Shift and Reverse

题目大意

给你一个数组，你可以对它进行两种操作：

Shift: 把最后一个数放到最前面；

Reverse: 数组反转

最后让数组变成非递减的，输出操作次数，如果无法完成输出-1。

大致思路

考虑操作序列，有以下两种操作可以简化：

RR === 0 (和没操作一样)；

SRS === R

因此最终的操作序列中不可能有连续的R，连续的S中也不可能出现R，因此最终的操作序列一定是中间有一串连续的S，首尾可能存在R。

Solution


use std::io::stdin;

fn check(arr: &Vec<i32>, n: usize) -> i32 {
    let mut vis = false;
    let mut ans1 = 0;
    for i in 1..n {
        if arr[i] < arr[i - 1] {
            if vis {
                ans1 = -1;
                break;
            }
            vis = true;
            ans1 = (n - i) as i32;
        }
    }
    if vis && arr[n - 1] > arr[0] {
        ans1 = -1;
    }

    let mut vis = false;
    let mut ans2 = 0;
    for i in (0..n - 1).rev() {
        if arr[i] < arr[i + 1] {
            if vis {
                ans2 = -1;
                break;
            }
            vis = true;
            ans2 = (n - i - 1) as i32;
        }
    }
    if vis && arr[0] > arr[n - 1] {
        ans2 = -1;
    }

    if ans1 == -1 && ans2 == -1 {
        return -1;
    }
    if ans1 == -1 {
        return ans2+1;
    }
    if ans2 == -1 {
        return ans1;
    }
    ans1.min(ans2+1)
}

fn main() {
    let t: usize = {
        let mut buf = String::new();
        stdin().read_line(&mut buf).unwrap();
        buf.trim().parse().unwrap()
    };
    for _ in 0..t {
        let n: usize = {
            let mut buf = String::new();
            stdin().read_line(&mut buf).unwrap();
            buf.trim().parse().unwrap()
        };
        let arr = {
            let mut buf = String::new();
            stdin().read_line(&mut buf).unwrap();
            buf.trim()
                .split_whitespace()
                .map(|x| x.parse().unwrap())
                .collect::<Vec<i32>>()
        };
        let ans1 = check(&arr, n);
        let ans2 = check(&arr.iter().rev().map(|&x| x).collect::<Vec<i32>>(), n);
        if ans1 == -1 && ans2 == -1 {
            println!("-1");
        } else if ans1 == -1 {
            println!("{}", ans2 + 1);
        } else if ans2 == -1 {
            println!("{}", ans1);
        } else {
            println!("{}", ans1.min(ans2 + 1));
        }
    }
}

CF1907G. Lights

题目大意

开关有关联效应，比如你使用开关，不仅可以控制灯，还可以控制灯。给定目前所有灯的开关状态，输出最小的控制序列，使所有灯关闭，如果做不到，则输出-1。

大致思路

可以把这个关联控制看成一个有向边，则所有边组成一个图，这个图被称为“基环树森林”，这个图至少有一个环，没有自环。首先可以按照拓扑排序的方式，将除了环上的其他顶点，依次把开着的灯关掉。对于环上的处理，如果某个灯亮着，这有两个可能的方案：

按下这个开关，这个边连接的灯也会影响，依次关闭环上所有开着的灯即可；

不按下这个开关，使用环上其他开关来影响到这个灯，使其关闭；

其中需要特别处理环上亮的灯是奇数的情况，这种情况无法关闭所有灯，同时也需要对所有环都进行上面的操作。

Solution


use std::{collections::VecDeque, io::stdin, vec};

fn main() {
    let t: usize = {
        let mut buf = String::new();
        stdin().read_line(&mut buf).unwrap();
        buf.trim().parse().unwrap()
    };
    'next_case: for _ in 0..t {
        let n: usize = {
            let mut buf = String::new();
            stdin().read_line(&mut buf).unwrap();
            buf.trim().parse().unwrap()
        };
        let s = {
            let mut buf = String::new();
            stdin().read_line(&mut buf).unwrap();
            buf.trim().to_string()
        };
        let mut on: Vec<bool> = vec![false];
        on.extend(s.chars().map(|c| c == '1'));
        let nxt = {
            let mut buf = String::new();
            stdin().read_line(&mut buf).unwrap();
            let mut edges = vec![0];
            edges.extend(
                buf.trim()
                    .split_whitespace()
                    .map(|x| x.parse::<usize>().unwrap()),
            );
            edges
        };
        let mut ind = vec![0; n + 1];
        for i in 1..=n {
            ind[nxt[i]] += 1;
        }
        let mut q = VecDeque::new();
        let mut ans: Vec<usize> = Vec::with_capacity(n);
        for i in 1..=n {
            if ind[i] == 0 {
                q.push_back(i);
            }
        }
        while let Some(u) = q.pop_front() {
            if on[u] {
                ans.push(u);
                on[u] = !on[u];
                on[nxt[u]] = !on[nxt[u]];
            }
            ind[nxt[u]] -= 1;
            if ind[nxt[u]] == 0 {
                q.push_back(nxt[u]);
            }
        }
        let mut q: Vec<usize> = Vec::new();
        for i in 1..=n {
            if on[i] {
                q.push(i);
            }
        }
        if q.len() % 2 == 1 {
            println!("-1");
            continue 'next_case;
        }
        for u in q {
            if on[u] {
                // 按下开关 u
                let mut tmpans1 = Vec::new();
                let mut v = nxt[u];
                let mut blk = true;
                tmpans1.push(u);
                while v != u {
                    if on[v] {
                        blk = !blk;
                    }
                    if blk {
                        tmpans1.push(v);
                    }
                    v = nxt[v];
                }
                if blk {
                    println!("-1");
                    continue 'next_case;
                }
                // 不按下开关 u
                let mut tmpans2 = Vec::new();
                let mut v = nxt[u];
                let mut blk = false;
                while v != u {
                    if on[v] {
                        on[v] = !on[v]; // 同时处理掉状态
                        blk = !blk;
                    }
                    if blk {
                        tmpans2.push(v);
                    }
                    v = nxt[v];
                }
                on[u] = !on[u]; // 同时处理掉状态
                if !blk {
                    println!("-1");
                    continue 'next_case;
                }
                if tmpans1.len() <= tmpans2.len() {
                    ans.extend(tmpans1);
                } else {
                    ans.extend(tmpans2);
                }
            }
        }
        println!("{}", ans.len());
        for i in ans {
            print!("{} ", i);
        }
        println!();
    }
}