AtCoder Beginner Contest 230

知识点分析

题解

A - AtCoder Quiz 3

给一个整数 $n$，要求输出 AGC + n，不足三位补前导零，且如果 $n \geq 42$时需要 $+1$

思路
没什么坑点，直接模式输出即可

B - Triple Metre

一个长度为字符串 T 由 $10^5$ 个相同的 oxx 组成，给一个字符串 S，问 S 是否是 T 的子串

由于字符串 S 的长度很小，所以可以构造 T 为长度为 $30$ 的字符串 oxxoxxoxxoxx...，之后枚举判断即可

C - X drawing

有一个 $N \times N$ 的网格：
1.对于所有 $k \in [\max\{1-A, 1-B\}, \min\{N-A, N-B\}]$ 网格 $(A + k, B + k)$ 为黑色格
2. 对于所有 $k \in [\max\{1-A, B-N\}, \min\{N-A, B-1\}]$ 网格 $(A + k, B - k)$ 为黑色格
现在要求输出所有网格 $(i, j)$ ，其中 $i \in [P, Q], j \in [R, S]$，黑色格用 #表示，其他用 . 表示

由于 $N$ 很大，但要求输出的网格很小，所以直接枚举需要输出的网格 $(i, j)$，其中 $i \in [P, Q], j \in [R, S]$，然后求取 $k$ ，如果两个 $k$ 相等且合法则输出 #，否则输出 .

D - Destroyer Takahashi

高桥可以使用拳击摧毁最多长度为 $D$ 的墙，现在给出 $N$ 排墙，问最少多少次拳击可将全部的墙摧毁

首先考虑一个贪心：对于所有的墙，选取的摧毁范围的起点为墙的右端点
因为此时可以将所有包含当前端点的墙摧毁，同时向右覆盖最大的范围
所以对所有的墙先按右端点从小到大排序，如果右端点相同则按左端点从小到大排序，之后枚举所有的墙，判断是否更新答案即可

E - Fraction Floor Sum

非常板的整除分块
首先可以知道由一段区间 $\dfrac{N}{i}$ 是相同的
假设 $i$ 是最小的使得 $\dfrac{N}{I} = x$ 的数，则最大的使得$\dfrac{N}{I} = x$ 的数为 $\lfloor \dfrac{N}{\lfloor \dfrac{N}{i} \rfloor} \rfloor$
所以直接枚举所有的区间，累计答案即可，时间复杂度为 $O(\sqrt{N})$

代码

A

#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#define INF 0x3f3f3f3f
using namespace std;
#define MAX_SIZE 1 << 20
inline void debug() { puts("Work"); exit(0);}
char buf[MAX_SIZE], *_p, *__p;
#define gc() (_p == __p && (__p = (_p = buf) + fread(buf, 1, MAX_SIZE, stdin), _p == __p) ? EOF : *_p++)
template<class T>
inline void read(T & x){
 bool sign = false;
 x = 0;
 char c = gc();
 for(;!isdigit(c);c = gc()) if(c == '-')sign = true;
 for(;isdigit(c);c = gc())x = (x << 3) + (x << 1) + (c ^ 48);
 if(sign)x = -x;
}
template<class T, class ...S>
inline void read(T& a, S&...b){
 read(a); read(b...);
}
//======================================

//=====================================

int32_t main() {
#ifdef LOCAL
 freopen("in.in", "r", stdin);
#endif
//======================================
     int n;
     read(n);
     if (n >= 42) n ++;
     printf("AGC%03d", n);
//======================================
}

B

#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#define INF 0x3f3f3f3f
using namespace std;
#define MAX_SIZE 1 << 20
inline void debug() { puts("Work"); exit(0);}
char buf[MAX_SIZE], *_p, *__p;
#define gc() (_p == __p && (__p = (_p = buf) + fread(buf, 1, MAX_SIZE, stdin), _p == __p) ? EOF : *_p++)
template<class T>
inline void read(T & x){
 bool sign = false;
 x = 0;
 char c = gc();
 for(;!isdigit(c);c = gc()) if(c == '-')sign = true;
 for(;isdigit(c);c = gc())x = (x << 3) + (x << 1) + (c ^ 48);
 if(sign)x = -x;
}
template<class T, class ...S>
inline void read(T& a, S&...b){
 read(a); read(b...);
}
//======================================
string mod = "oxxoxxoxxoxxoxxoxxoxxoxxoxxoxxoxxoxxoxxoxxoxxoxx";
//=====================================

int32_t main() {
#ifdef LOCAL
 freopen("in.in", "r", stdin);
#endif
//======================================
     string s;
     cin >> s;
     int len = mod.length();
     int n = s.length();
     for (int i = 0; i < len - n; ++ i) {
         bool flag = true;
         for (int j = i; j < i + n; ++ j) {
             char k = mod[j];
             char w = s[j - i];
             if (k != w) {
                 flag = false;
                 break;
             }
         }
         if (flag) {
             puts("Yes");
             return 0;
         }
     }
 puts("No");
//======================================
}

C

#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#define INF 0x3f3f3f3f
using namespace std;
#define MAX_SIZE 1 << 20
inline void debug() { puts("Work"); exit(0);}
char buf[MAX_SIZE], *_p, *__p;
#define gc() (_p == __p && (__p = (_p = buf) + fread(buf, 1, MAX_SIZE, stdin), _p == __p) ? EOF : *_p++)
template<class T>
inline void read(T & x){
 bool sign = false;
 x = 0;
 char c = gc();
 for(;!isdigit(c);c = gc()) if(c == '-')sign = true;
 for(;isdigit(c);c = gc())x = (x << 3) + (x << 1) + (c ^ 48);
 if(sign)x = -x;
}
template<class T, class ...S>
inline void read(T& a, S&...b){
 read(a); read(b...);
}
//======================================

#define int long long

//=====================================

int32_t main() {
#ifdef LOCAL
 freopen("in.in", "r", stdin);
#endif
//======================================
     int N, A, B;
     int P, Q, R, S;
     read(N, A, B);
     read(P, Q, R, S);
     auto fi = [](int k, int a, int b, int n) -> bool {
        return k >= min(1-a, 1-b) && k <= max(n-a, n-b);
     };
     auto se = [](int k, int a, int b, int n) -> bool {
        return k >= max(1-a, b-n) && k <= min(n-a, b-1);
     };
     for (int i = P; i <= Q; i ++)
     {
         for (int j = R; j <= S; j ++) {
             if (i - A == j - B) {
                 if (fi(i - A, A, B, N)) printf("#");
                 else printf(".");
             }
             else if (i - A == B - j) {
                 if (se(i - A, A, B, N)) printf("#");
                 else printf(".");
             }else printf(".");
        }
        puts("");
     }
//======================================
}

D

#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#define INF 0x3f3f3f3f
using namespace std;
#define MAX_SIZE 1 << 20
inline void debug() { puts("Work"); exit(0);}
char buf[MAX_SIZE], *_p, *__p;
#define gc() (_p == __p && (__p = (_p = buf) + fread(buf, 1, MAX_SIZE, stdin), _p == __p) ? EOF : *_p++)
template<class T>
inline void read(T & x){
 bool sign = false;
 x = 0;
 char c = gc();
 for(;!isdigit(c);c = gc()) if(c == '-')sign = true;
 for(;isdigit(c);c = gc())x = (x << 3) + (x << 1) + (c ^ 48);
 if(sign)x = -x;
}
template<class T, class ...S>
inline void read(T& a, S&...b){
 read(a); read(b...);
}
//======================================
#include <vector>
using pll = pair<int, int>;
int n, d;
//=====================================

int32_t main() {
#ifdef LOCAL
 freopen("in.in", "r", stdin);
#endif
//======================================
     read(n, d);
     vector<pll> v(n);
     for (auto& [x, y] : v) read(x, y);
     sort(v.begin(), v.end(), [](pll& a, pll& b) {
         if (a.second == b.second) return a.first < b.first;
         return a.second < b.second;
     });
     int last = -INF;
     int ans = 0;
     for (auto [x, y] : v) {
         if (x > last) {
             ans ++;
             last = y + d - 1;
         }
     } 
     cout << ans << endl;
//======================================
}

E

#include <iostream>
#include <cstring>
#include <algorithm>
#include <numeric>
#define INF 0x3f3f3f3f
using namespace std;
#define MAX_SIZE 1 << 20
inline void debug() { puts("Work"); exit(0);}
char buf[MAX_SIZE], *_p, *__p;
#define gc() (_p == __p && (__p = (_p = buf) + fread(buf, 1, MAX_SIZE, stdin), _p == __p) ? EOF : *_p++)
template<class T>
inline void read(T & x){
 bool sign = false;
 x = 0;
 char c = gc();
 for(;!isdigit(c);c = gc()) if(c == '-')sign = true;
 for(;isdigit(c);c = gc())x = (x << 3) + (x << 1) + (c ^ 48);
 if(sign)x = -x;
}
template<class T, class ...S>
inline void read(T& a, S&...b){
 read(a); read(b...);
}
//======================================
#define int long long
//=====================================

int32_t main() {
#ifdef LOCAL
 freopen("in.in", "r", stdin);
#endif
//======================================
     int x;
     read(x);
     int ans = 0;
     for (int i = 1; i <= x; i = x / (x / i) + 1) {
         int len = (x / (x / i)) - i + 1;
         ans += len * (x / i);
     }
     cout << ans << endl;
//======================================
}