SYUCTACM 双周赛 #3 题解

比赛 赛制 题目数 时长
SYUCTACM 双周赛 #3 ICPC(罚时制) 11 150 分钟
题号 题目 pid 主要考点 难度
A 学姐别骂我了我再也不往周赛塞石了呜呜呜 P0887 字符串 / 去重 入门
B 01 Game P0877 博弈 / 贪心 入门-普及
C 最小行列覆盖 P0878 构造 普及
D 周期字符串检查 P0879 字符串 入门
E 消除相邻重复字符 P0880 贪心 / 字符串 普及
F 成绩统计 P0881 模拟 入门
G Cells Not Under Attack P0883 计数 普及
H Spy-string P0884 枚举 / 暴力
I 机房过载预警 P0885 线段树 / 懒标记 普及+/提高
J Fix You P0876 观察 普及
K Perfect Square P0882 枚举 / 轨道 普及+/提高

A. 学姐别骂我了我再也不往周赛塞石了呜呜呜

  • 题目 ID:P0887 时限 1 s 内存 256 MB

思路

顺序扫描字符串,单开一个数组标记是否第一次出现即可

复杂度:O(|s|)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    string s;
    cin >> s;
    vector<bool> v(26, false);
    for (int i = 0 ; i < s.size() ;i++) 
    {
        int id = s[i] - 'a';
        if (v[id]==false) 
        {
            cout << s[i] ;
            v[id] = true;
        }
    }
    return 0;
}

B. 01 Game

  • 题目 ID:P0877 时限 1 s 内存 256 MB

思路

只要 0 和 1 都还有剩余,两者之间必然存在一处相邻的 "01" ,也就是总能继续操作。所以游戏长度恰好是 min(cnt0, cnt1)。

于是 Alice 获胜当且仅当 min(cnt0, cnt1) 为奇数。

复杂度:O(|s|)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int t;
    cin >> t;
    while (t--) 
    {
        string s;
        cin >> s;
        int c0 = 0, c1 = 0;
        for (int i = 0 ; i < s.size() ;i++) 
        {
            if (s[i] == '0') c0++ ;
            else c1++ ;
        }
        int k = min(c0, c1);
        if (k % 2 == 1) cout << "YES" << endl ;
        else cout << "NO" << endl ;
    }
    return 0;
}

C. 最小行列覆盖

  • 题目 ID:P0878 时限 1 s 内存 256 MB

思路

同时满足行列:构造对角线即可

复杂度:O(n^2)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int n, r, c;
    cin >> n >> r >> c;
    r-- ; c-- ;
    vector<int> p(n);
    for (int i = 0 ; i < n ;i++) p[i] = i;
    swap(p[r], p[c]);
    vector<string> g(n, string(n, '.'));
    for (int i = 0 ; i < n ;i++) g[i][p[i]] = 'X';
    for (int i = 0 ; i < n ;i++) cout << g[i] << endl ;
    return 0;
}

D. 周期字符串检查

  • 题目 ID:P0879 时限 1 s 内存 256 MB

思路

对所有 i ≥ k 检查 s[i] 是否等于 s[i−k],全部相等输出 YES。

复杂度:O(n)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int t;
    cin >> t;
    while (t--) 
    {
        int n, k;
        string s;
        cin >> n >> k >> s;
        bool ok = true;
        for (int i = k ; i < n ;i++) 
        {
            if (s[i] != s[i-k]) ok = false;
        }
        if (ok==false) cout << "NO" << endl ;
        else cout << "YES" << endl ;
    }
    return 0;
}

E. 消除相邻重复字符

  • 题目 ID:P0880 时限 1 s 内存 256 MB

思路

把字符串按「连续的相同字母」切段,比如 aaabbcd 切成 aaa bb c d。

只看每段的长度 L:段内最多只能保住 L - L/2 个字符不动,所以这一段至少要改 L/2 次(向下取整);

所以答案就是:

答案 = Σ ⌊每段长度 / 2⌋

aaabbcd 就是 ⌊3/2⌋ + ⌊2/2⌋ = 1 + 1 = 2。

复杂度:O(|s|)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    for (int i = 0 ; i < n ;i++) 
    {
        int j = i;
        while (j < n && s[j] == s[i]) j++ ;
        ans += (j - i) / 2;
        i = j - 1;
    }
    cout << ans << endl ;
    return 0;
}

F. 成绩统计

  • 题目 ID:P0881 时限 1 s 内存 256 MB

思路

按照题意模拟即可

复杂度:O(n)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int n;
    cin >> n;
    int mx = -1, mn = 101, pass = 0;
    long long sum = 0;
    for (int i = 0 ; i < n ;i++) 
    {
        int x;
        cin >> x;
        sum += x;
        if (x > mx) mx = x;
        if (x < mn) mn = x;
        if (x >= 60) pass++ ;
    }
    cout << fixed << setprecision(2);
    cout << mx << ' ' << mn << ' ' << (double)sum / n << ' ' << pass << endl ;
    return 0;
}

G. Cells Not Under Attack

  • 题目 ID:P0883 时限 1 s 内存 256 MB

思路

格子 (i, j) 不被攻击 ⟺ 第 i 行没有车、第 j 列也没有车。 每放一个车就标记它的行与列。 记已被占用的不同行数为 r、不同列数为 c,则安全格子数 = (n − r) · (n − c)。

复杂度:O(n + m)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int n, m;
    cin >> n >> m;
    vector<bool> row(n + 1, false), col(n + 1, false);
    int r = 0, c = 0;
    for (int i = 0 ; i < m ;i++) 
    {
        int x, y;
        cin >> x >> y;
        if (row[x]==false) 
        {
            row[x] = true;
            r++ ;
        }
        if (col[y]==false) 
        {
            col[y] = true;
            c++ ;
        }
        long long ans = 1LL * (n - r) * (n - c);
        cout << ans << ' ' ;
    }
    cout << endl ;
    return 0;
}

H. Spy-string

  • 题目 ID:P0884 时限 2 s 内存 256 MB

思路

随便挑一个给定字符串当作答案的起点。如果最终答案存在,那它只好是两种情况之一:

不动,直接就用它;或 只改一个字母:枚举改哪一位(m 种),再枚举改成 26 个字母里的哪一个。 所以最多试1 + 26m个候选。每个候选都跟 n 个字符串比一遍,看是否每个都至多差一位;全都不行就输出 -1。

复杂度:O(m · 26 · n · m)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int t;
    cin >> t;
    while (t--) 
    {
        int n, m;
        cin >> n >> m;
        vector<string> v(n);
        for (int i = 0 ; i < n ;i++) cin >> v[i];
        string ans = "";
        for (int pos = -1 ; pos < m && ans == "" ;pos++) 
        {
            for (char ch = 'a' ; ch <= 'z' && ans == "" ;ch++) 
            {
                string s = v[0];
                if (pos >= 0) s[pos] = ch;
                bool ok = true;
                for (int i = 0 ; i < n ;i++) 
                {
                    int d = 0;
                    for (int j = 0 ; j < m ;j++) 
                    {
                        if (s[j] != v[i][j]) d++ ;
                    }
                    if (d > 1) ok = false;
                }
                if (ok==true) ans = s;
            }
        }
        if (ans == "") cout << "-1" << endl ;
        else cout << ans << endl ;
    }
    return 0;
}

I. 机房过载预警

  • 题目 ID:P0885 时限 2 s 内存 512 MB

思路

本题是zkw线段树的模板题,详细请看oiwiki(大一不需要现在就会)

复杂度:O((n + q) log n)

参考代码

#include <bits/stdc++.h>
using namespace std;
const long long NEG = LLONG_MIN / 4;
int M;                          // 叶子数(2 的幂)
vector<long long> mx, lz;

void apply(int p, long long v) 
{
    mx[p] += v;
    if (p < M) lz[p] += v;
}
void pull(int p) 
{
    mx[p] = max(mx[p << 1], mx[p << 1 | 1]) + lz[p];
}
void push(int p)                // 把 p 到根的标记下推
{
    for (int s = __lg(M) ; s >= 1 ;s--) 
    {
        int i = p >> s;
        if (lz[i] != 0) 
        {
            apply(i << 1, lz[i]);
            apply(i << 1 | 1, lz[i]);
            lz[i] = 0;
        }
    }
}
void add(int l, int r, long long v)     // 对 [l, r] 加 v(1-indexed)
{
    l = l + M - 2;
    r = r + M;                  // 1-indexed 闭区间 [l, r] -> 叶子开区间 (l, r)
    int L = l, R = r;
    push(L);
    push(R);
    while ((l ^ r) != 1) 
    {
        if ((l & 1) == 0) apply(l ^ 1, v);
        if ((r & 1) == 1) apply(r ^ 1, v);
        l >>= 1;
        r >>= 1;
    }
    for (int i = L >> 1 ; i ;i >>= 1) pull(i);
    for (int i = R >> 1 ; i ;i >>= 1) pull(i);
}
long long query(int l, int r)           // 求 [l, r] 的最大值(1-indexed)
{
    l = l + M - 2;
    r = r + M;                  // 同上,转成叶子开区间 (l, r)
    int L = l, R = r;
    push(L);
    push(R);
    long long res = NEG;
    while ((l ^ r) != 1) 
    {
        if ((l & 1) == 0) res = max(res, mx[l ^ 1]);
        if ((r & 1) == 1) res = max(res, mx[r ^ 1]);
        l >>= 1;
        r >>= 1;
    }
    return res;
}
int main() 
{
    int n, q;
    cin >> n >> q;
    M = 1;
    while (M < n + 2) M <<= 1;
    mx.assign(M << 1, NEG);
    lz.assign(M << 1, 0);
    for (int i = 1 ; i <= n ;i++) cin >> mx[M + i - 1];
    for (int i = M - 1 ; i >= 1 ;i--) 
    {
        mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
    }
    for (int i = 0 ; i < q ;i++) 
    {
        int op, l, r;
        long long v;
        cin >> op >> l >> r >> v;
        if (op == 1) add(l, r, v);
        else 
        {
            if (query(l, r) >= v) cout << "YES" << endl ;
            else cout << "NO" << endl ;
        }
    }
    return 0;
}

J. Fix You

  • 题目 ID:P0876 时限 1 s 内存 256 MB

思路

会掉出去的格子只有两种:最后一列写了 R、最后一行写了 D。其余方向都还在网格里,最多就是走到边上,然后由边上那一列/一行把你带到右下角。

因此最少修改次数就等于这两类格子的总数:

最后一列里 R 的个数 + 最后一行里 D 的个数(右下角那个 C 不算)

复杂度:O(n·m)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int t;
    cin >> t;
    while (t--) 
    {
        int n, m;
        cin >> n >> m;
        vector<string> g(n);
        for (int i = 0 ; i < n ;i++) cin >> g[i];
        int ans = 0;
        for (int i = 0 ; i < n - 1 ;i++) if (g[i][m - 1] == 'R') ans++ ;
        for (int j = 0 ; j < m - 1 ;j++) if (g[n - 1][j] == 'D') ans++ ;
        cout << ans << endl ;
    }
    return 0;
}

K. Perfect Square

  • 题目 ID:P0882 时限 2 s 内存 256 MB

思路

旋转 90° 不变 ⟺ 每格与它旋转 90°/180°/270° 后的三格字符相同;n 为偶数时这 4 格互不相同,构成一个 4 元轨道。

轨道之间互不影响,分别求最小代价再相加。单个字符 c 变成目标 t 的代价是 (t − c) mod 26。

t 只可能取这四个字符之一,枚举 4 种取最小;遍历左上角四分之一区域即可,每个格子代表一条轨道。

复杂度:O(n^2)

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() 
{
    int t;
    cin >> t;
    while (t--) 
    {
        int n;
        cin >> n;
        vector<string> g(n);
        for (int i = 0 ; i < n ;i++) cin >> g[i];
        long long ans = 0;
        for (int i = 0 ; i < n / 2 ;i++) 
        {
            for (int j = i ; j < n - 1 - i ;j++) 
            {
                int v[4];
                v[0] = g[i][j];
                v[1] = g[j][n - 1 - i];
                v[2] = g[n - 1 - i][n - 1 - j];
                v[3] = g[n - 1 - j][i];
                int best = 1 << 30;
                for (int k = 0 ; k < 4 ;k++) 
                {
                    int cost = 0;
                    for (int x = 0 ; x < 4 ;x++) cost += (v[k] - v[x] + 26) % 26;
                    best = min(best, cost);
                }
                ans += best;
            }
        }
        cout << ans << endl ;
    }
    return 0;
}

0 條評論

目前還沒有評論...