AtCoder Beginner Contest 042 题解

• A - Iroha and Haiku (ABC Edition)
  • 题目大意：
• B - Iroha Loves Strings (ABC Edition)
  • 题目大意：
  • 分析：
• C - Iroha's Obsession
  • 题目大意：
  • 分析：
• D - Iroha and a Grid
  • 题目大意

A - Iroha and Haiku (ABC Edition)

题目大意：

判断输入的三个数字是不是 5，5，7。

#include
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define Equ(a,b) (fabs((a)-(b))(eps))
#define x first
#define y second
using namespace std;
const int N=1e6+7;
const double eps=1e-6;
const int mod=1e9+7;
int a[N];
int main (){
    IOS
    int x, y, z; cin >> x >> y >> z;
    a[x] ++; a[y] ++; a[z] ++;
    if (a[5] == 2 && a[7] == 1){
        cout << "YES" << endl;
    }
    else cout << "NO" << endl;
    
    return 0;
}

B - Iroha Loves Strings (ABC Edition)

题目大意：

给出若干个字符串，如何首位拼接得到字典序最小的字符串。

分析：

利用 c++ string 类型的比较就是按字典序比较，然后排序输出即可

#include
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define Equ(a,b) (fabs((a)-(b))(eps))
#define x first
#define y second
using namespace std;
const int N=1e6+7;
const double eps=1e-6;
const int mod=1e9+7;
string s[N];
int main (){
    IOS
    int n, l; cin >> n >> l;
    for (int i = 1 ; i <= n ; i ++) cin >> s[i];
    sort (s + 1, s + n + 1);
    for (int i = 1 ; i <= n ; i ++) cout << s[i];
    return 0;
}

C - Iroha's Obsession

题目大意：

给出数字的使用限制，用剩下的数字拼成大于等于 \(n\) 的数并输出。

分析：

题给出的 \(n\) 较小，直接从 \(n\) 开始枚举，并 check 构成数字的合法性即可。复杂度 \(O(n)\)

赛中，脑抽尝试去构造。构造细节较多，并不好写，但是复杂度可以达到 \(O(\lg_ n)\)

#include
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define Equ(a,b) (fabs((a)-(b))(eps))
#define x first
#define y second
using namespace std;
const int N=1e6+7;
const double eps=1e-6;
const int mod=1e9+7;
int a[N];
bool check (int n){
    while (n){
        if (a[n % 10]) return 0;
        n /= 10;
    }
    return 1;
}
int main (){
    IOS
    int n, k; cin >> n >> k;
    for (int i = 1, x ; i <= k ; i ++){
        cin >> x;
        a[x] = 1;
    }
    while (!check (n)){
        n ++;
    }
    cout << n << endl;
    return 0;
}

脑子不清楚时候写的构造(可ac)

#include
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define Equ(a,b) (fabs((a)-(b))(eps))
#define x first
#define y second
using namespace std;
const int N=1e6+7;
const double eps=1e-6;
const int mod=1e9+7;
int a[N];
int main (){
    IOS
    string k;int n; cin >> k >> n;
    for (int i = 1, x ; i <= n ; i ++) {
        cin >> x; a[x] = 1;
    }
    char minn, minn2;
    for (int i = 0 ; i <= 9 ; i ++){
        if (!a[i]){
            minn = i + '0';
            break;
        }
    }
    for (int i = 1 ; i <= 9 ; i ++){
        if (!a[i]){
            minn2 = i + '0';
            break;
        }
    }
    string ans;
    bool flag = 1;
    for (int i = k.size () - 1; i >= 0 ; i --){
        bool f = 0;
        bool f1 = 0;
        for (int j = 0 ; j <= 9 ; j ++){
            if (a[j]) continue;
            if (j >= k[i] - '0'){
                if (!flag && j == k[i] - '0') continue; 
                f1 = j != k[i] - '0';
                ans = (char)(j + '0') + ans;
                f = 1;
                break;
            }
        }        
        flag = f;
        if (f1){
            if (ans.size () > 1){
                for (int i = ans.size () - 1; i >= 1 ; i --) ans[i] = minn;
            }
        }
        if (!f) {
            ans += minn;
            for (int i = 0 ; i < ans.size () ; i ++) ans[i] = minn;
        }
    }
    if (!flag)
        cout  << minn2 + ans << endl;
    else {
        cout << ans << endl;
    }
    return 0;
}

D - Iroha and a Grid

题目大意

很经典的问题，从一个表格的左上角走到右下角有几种走法 （只能向下或者向右）。加上一定左下角一块区域不能走的限制。通常会采用 \(dp\), 或者是组合数的方法解决。数据范围 \(1e5\) ,因此不能用 \(dp\) 。因而尝试用组合数分段处理，难度不大。

详情见代码注释部分

#include
#define ll long long
#define INF 0x7f7f7f7f //2139062143
#define llINF 9223372036854775807
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define Equ(a,b) (fabs((a)-(b))(eps))
#define x first
#define y second
using namespace std;
const int N=1e6+7;
const double eps=1e-6;
const int mod=1e9+7;
int a[N], f[N], invf[N];
ll qpow(ll base, ll power) {
    ll result = 1;
    while (power > 0) {
        if (power & 1) {
            result = result * base % mod;
        }
        power >>= 1;
        base = (base * base) % mod;
    }
    return result;
}
void init(){
    f[0] = 1;
    for(int i = 1 ; i < N ; i ++) f[i] = 1ll * f[i - 1] * i % mod;
    invf[N - 1] = qpow(f[N - 1], mod - 2);
    for(int i = N - 2; i >= 0 ; i --) invf[i] = 1ll * invf[i + 1] * (i + 1) % mod;
}
ll c(ll a,ll b){
    if (a < b) return 0;
    return 1ll * f[a] * invf[a - b] % mod * invf[b] % mod;
}
int main (){
    ll h, w, a, b; cin >> h >> w >> a >> b; 
    init();
    // 对区间[b + 1, w] 的 i 先算 (1, 1) 到 (h - a, i)的方案数, 再算 (h - a + 1, i) 到 (h, w)的方案数， 两者相乘即可
    ll ans = 0;
    for (int i = b + 1 ; i <= w ; i ++){
        ll ans1 = c((h - a - 1) + i - 1, i - 1), ans2 = c(a - 1 + w - i, a - 1);
        ans = ans + ans1 * ans2 % mod;
        ans %= mod;
    } 
    cout << ans << endl;
    return 0;
}