shuzhouliu's OI Blog

发表于 分类于 本文字数： 257 阅读时长 ≈ 1 分钟

题意：给定一个 \(10\times 10\) 的矩阵，有一个 B、一个 L 和一个 R，其中 R 那格不能走。现在求 B 和 L 之间的最短路（不包括 B 和 L）。

这题是1权图的最短路，可以用 BFS 求。对于 R 那格特判即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<bits/stdc++.h>
using namespace std;
const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, 1, -1};
char c[10][10];
bool vst[10][10];
int bx, by, rx, ry, lx, ly;
struct state {
  int x, y, t;
  state (int x = 0, int y = 0, int t = 0): x(x), y(y), t(t) {}
};
int main() {
  freopen("buckets.in", "r", stdin);
  freopen("buckets.out", "w", stdout);
  for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
      cin >> c[i][j];
      if (c[i][j] == 'B') bx = i, by = j;
      if (c[i][j] == 'R') rx = i, ry = j;
      if (c[i][j] == 'L') lx = i, ly = j;
    }
  }
  queue<state> q;
  q.push({lx, ly, 0}); // ltob
  while (!q.empty()) {
    auto t = q.front(); q.pop();
    vst[t.x][t.y] = true;
    if (t.x == bx && t.y == by) {
      cout << max(t.t-1, 0) << endl;
      return 0;
    }
    for (int k = 0; k < 4; k++) {
      int nx = t.x + dx[k], ny = t.y + dy[k];
      if (nx >= 0 && nx < 10 && ny >= 0 && ny < 10 && (rx != nx || ry != ny) && !vst[nx][ny])
        q.push({nx, ny, t.t + 1});
    }
  }
  return 0;
}

发表于 分类于 本文字数： 157 阅读时长 ≈ 1 分钟

题意：给定 \(n\) 个单词，每行最多 \(k\) 个字符（不含空格），输出这些单词的排版。

按照题意模拟即可。

因为行末不能有空格，所以要特判一下 curline 的值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include<bits/stdc++.h>
using namespace std;
const int N = 101;
int n, k;
string s[N];
int main() {
  freopen("word.in", "r", stdin);
  freopen("word.out", "w", stdout);
  cin >> n >> k;
  for (int i = 1; i <= n; i++)
    cin >> s[i];
  int curline = 0;
  for (int i = 1; i <= n; i++) {
    if (curline + s[i].length() > k) {
      cout << endl << s[i];
      curline = s[i].length();
    } else if (curline + s[i].length() == k) {
      if (!curline) cout << s[i];
      else cout << " " << s[i];
      curline = k;
    } else {
      if (!curline) cout << s[i];
      else cout << " " << s[i];
      curline += s[i].length();
    }
  }
  cout << endl;
  return 0;
}

发表于 更新于 分类于 本文字数： 143 阅读时长 ≈ 1 分钟

题意：给定七个数，分别是 \(a, b, c, a+b, b+c, a+c, a+b+c\)，求 \(a, b, c\)（已知 \(0 < a \leq b \leq c, a, b, c \in \mathbb{N}^*\)）。

由于 \(a, b, c > 0\)，故而 \(a+b+c\) 一定是这七个数的最大值，\(a\) 一定是这七个数的最小值，\(b\) 一定是这七个数的第二小值。知道了 \(a, b\) 之后，\(c\) 就可以算出来了。

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int a[7];
int main() {
  for (int i = 0; i < 7; i++) cin >> a[i];
  sort(a, a+7);
  cout << a[0] << " " << a[1] << " " << a[6]-a[0]-a[1] << endl;
  return 0;
}

发表于 更新于 分类于 本文字数： 97 阅读时长 ≈ 1 分钟

题意：给定在各组的原先人数和现在人数，求每个级别的人有多少晋升的。

按照题意模拟即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include<bits/stdc++.h>
using namespace std;
int b1, b2, s1, s2, g1, g2, p1, p2;
int main() {
  freopen("promote.in", "r", stdin);
  freopen("promote.out", "w", stdout);
  cin >> b1 >> b2 >> s1 >> s2 >> g1 >> g2 >> p1 >> p2;
  int gtp = p2-p1;
  int stg = g2-g1 + gtp;
  int bts = s2-s1 + stg;
  cout << bts << endl << stg << endl << gtp << endl;
  return 0;
}

发表于 更新于 分类于 本文字数： 91 阅读时长 ≈ 1 分钟

题意：给定 \(k\)，\(n\)，\(w\)，求至少需要多少钱才能买到 \(w\) 个香蕉，其中第 \(i\) 个香蕉需要 \(i \times k\) 钱。

注意不需要借钱的时候就不用借了，直接输出 \(0\) 即可。

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int k,n,w;
int main(){
	cin>>k>>n>>w;
	int _pay=w*(w+1)/2*k;
	cout<<max(_pay-n,0)<<endl;
	return 0;
}

发表于 更新于 分类于 本文字数： 109 阅读时长 ≈ 1 分钟

题意：给定 \(n\) 个题目，三个人对每道题每人都给出是否确定能解决，求至少有两个人确定能解决的题目数。

显然只需判断每道题给定的三个 0/1 之和是否大于等于 \(2\) 即可。

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int n, ans;
int main() {
  cin >> n;
  for (int i = 1, a, b, c; i <= n; i++)
    cin >> a >> b >> c, ans += (a+b+c)>=2;
  cout << ans << endl;
  return 0;
}

发表于 更新于 分类于 本文字数： 131 阅读时长 ≈ 1 分钟

题意：在一条直线上有四个点 \(A, B, X, Y\)，其中 \(X, Y\) 两点可以通过传送门互相传送，求 \(A\) 到 \(B\) 的最短距离。

易得总共只有三种情况：\(A\) 直接到 \(B\)，\(A\) 到 \(X\) 传送到 \(Y\) 再到 \(B\)，\(A\) 到 \(Y\) 传送到 \(X\) 再到 \(B\)。直接计算即可。

1
2
3
4
5
6
7
8
9
10
#include<bits/stdc++.h>
using namespace std;
int a, b, x, y;
int main() {
  freopen("teleport.in", "r", stdin);
  freopen("teleport.out", "w", stdout);
  cin >> a >> b >> x >> y;
  cout<<min({abs(a-b), abs(a-x)+abs(b-y), abs(a-y)+abs(b-x)})<<endl;
  return 0;
}

发表于 更新于 分类于 本文字数： 869 阅读时长 ≈ 3 分钟

A. Sequence Order

题意：输入 \(n\) 个字符串 \(s_1, s_2, \cdots, s_n\)，将他们倒序输出。

输入字符串，将他们压入栈中，然后依次输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
stack<string> st;
int main() {
    cin >> n;
    while (n--) {
        cin >> s;
        st.push(s);
    }
    while (!st.empty()) {
        cout << st.top() << endl;
        st.pop();
    }
    return 0;
}

B. Multi Test Cases

题意：有 \(t\) 组数据，每次给定一个长 \(n\) 的数组，每组求其中奇数的个数。

根据题意，每次判断累加即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<bits/stdc++.h>
using namespace std;
int t, n;
int main() {
    cin >> t;
    while (t--) {
        cin >> n;
        int ans = 0;
        for (int i = 1, x; i <= n; i++)
            cin >> x, ans += (x % 2 == 1);
        cout << ans << endl;
    }
    return 0;
}

C. Count Connected Components

题意：求一个无向图中连通块的个数。

设 \(mark_i\) 表示点已经访问过。遍历 \(i=1\cdots n\)，若 \(mark_i\) 的值为 false，则从 \(i\) 开始进行深度优先搜索，将所有与 \(i\) 相连的点标记为已访问，最后答案加 \(1\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
using namespace std;
const int N = 101;
int n, m, mrk[N];
vector<int> es[N];
void dfs (int x) {
    mrk[x] = 1;
    for (auto v: es[x])
        if (!mrk[v]) dfs(v);
}
int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        es[u].push_back(v), es[v].push_back(u);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (!mrk[i]) ++ans, dfs(i);
    cout << ans << endl;
    return 0;
}

D. Happy New Year 2023

题意：有 \(t\) 组数据，每组给定一个整数 \(n\)（\(1 \leq n \leq 9 \times 10^{18}\)），已知 \(n\) 可以表示为唯一的 \(n=p^2q\)，且 \(p, q\) 是质数，求 \(p\) 和 \(q\) 的值。

设知 \(n=p^2q \sim 10^{18}\)，设 \(q \sim 10^m\)，则 \(p \sim 10^{\frac{18-m}{2}}\)。

则 \(p, q\) 的阶的最大值就是 \(\max(m, \frac{18-m}{2})\)。

若 \(m = \max(m, \frac{18-m}{2})\)，则 \(2m \geq 18-m\)，得 \(m\geq 6\)，则 \(18-m \leq 12\)，得 \(\frac{18-m}{2} \leq 6\)，故而可以先找到 \(q\)，所以只需要找到 \(10^6\) 的素数。

反之，则 \(2m \leq 18-m\)，得 \(m \leq 6\)，所以也只需要找到 \(10^6\) 的素数。但是，\(n\) 的最大值是 \(9\times 10^{18}\)，所以可以筛到 \(10^7\)。

综上所述，只需要找到 \(10^6\) 的素数，然后枚举 \(p\) 或 \(q\) 是否符合条件即可。

筛到一个满足 \(p \equiv 0 \pmod n\) 的素数 \(p\) 时，若 \(p \equiv 0 \pmod{\frac{n}{p}}\)，则这个素数 \(p\) 一定是 \(n=p^2q\) 中的素数 \(p\)，否则这个素数一定是 \(q\)。

知，\(1 \sim x\) 的素数大概是 \(\dfrac{x}{\ln x}\) 个，设筛到的素数为 \(s\)（此处 \(s=10^7\)），则时间复杂度为 \(O(s+\frac{ts}{\ln s})\)，其中 \(t\) 为数据组数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n;
vector<ll> primes;
void sieve (ll x) {
    vector<bool> vst(x+1);
    for (ll i = 2; i <= x; i++) {
        if (!vst[i]) primes.push_back(i);
        for (auto pj: primes) {
            if (i*pj > x) break;
            vst[i*pj] = true;
            if (i % pj == 0) break;
        }
    }
}
int main() {
    cin >> t;
    sieve(10000000);
    while (t--) {
        cin >> n;
        for (auto p: primes) {
            if (n%p == 0) {
                if ((n/p)%p==0) { // then it's the p
                    cout << p << " " << n/p/p << endl;
                    break;
                } else {
                    cout << (ll) sqrtl(n/p) << " " << p << endl;
                  	break;
                }
            }
        }
    }
    return 0;
}

E. Count Simple Paths

题意：求无向图从点 \(1\) 开始的简单路径个数，并对 \(10^6\) 取 \(\min\)。

直接从 \(1\) 开始 DFS，若个数超过 \(10^6\)，则输出 1000000 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
const int N = 200001;
int n, m;
vector<int> es[N];
int cnt = 0;
set<int> st;
void dfs (int x) {
    if (cnt >= 1000000) {
        cout << 1000000 << endl;
        exit(0);
    }
    ++cnt;
    st.insert(x);
    for (auto v: es[x]) {
        if (!st.count(v)) {
            dfs(v);
            st.erase(v);
        }
    }
}
int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        es[u].push_back(v), es[v].push_back(u);
    }
    dfs(1);
    cout << cnt << endl;
    return 0;
}
0%