AcWing Weekly-80

发布于 2022-12-04  669 次阅读

闫学灿敢于出原题，我敢于一眼看出来是啥题之秒切T3的ranking6

末尾字母

给定一个由大小写字母、空格和问号组成的字符串。

请你判断字符串中的最后一个字母是否是元音字母。

我们认为元音字母共有 6 个，分别为：A、E、I、O、U、Y（当然还有它们的小写）。

输入格式

一个由大小写字母、空格和问号组成的字符串。

保证问号在字符串中恰好出现一次，且一定出现在最后。

字符串中至少包含一个字母。

输出格式

如果字符串中的最后一个字母是元音字母，则输出 YES，否则输出 NO。

注意，我们问的是最后一个字母，而不是最后一个字符，空格和问号不算作字母。

数据范围

所有测试点满足，输入字符串的长度范围 2,100。

输入样例1：

Is it a melon?

输出样例1：

NO

输入样例2：

Is it an apple?

输出样例2：

YES

输入样例3：

  Is     it a banana ?

输出样例3：

YES

输入样例4：

Is   it an apple  and a  banana   simultaneouSLY?

输出样例4：

YES

注意读入的时候要用getline，因为有空格，cin会停掉，然后去掉后面的非字母字符，最后判断一下就OK了

#include <bits/stdc++.h>

using namespace std;
/*
 * author: Paren
 * time:2022/12/03 Sat.
 */
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e8;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int N = 1000;

void solve() {
    string s;
    string t;
    getline(cin, s);
    t = "AEIOUYaeiouy";
    while (!isalpha(s.back())) s.pop_back();
    if (t.find(s.back()) != t.npos) {
        cout << "YES";
    } else {
        cout << "NO";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

寻找数字

给定一个正整数 n，请你找到一个正整数 x，要求：

  1. x≥n
  2. x 的各个数位均不包含 4 和 7 以外的数字，且 x 中包含的4 的数量与 7 的数量恰好相等。
  3. 满足前两个条件的前提下，x 应尽可能小。

输入格式

一个正整数 n。

输出格式

一个正整数，表示 x。

数据范围

前 66 个测试点满足 1≤n≤5000
所有测试点满足 1≤n≤$10^9$

输入样例1：

4500

输出样例1：

4747

输入样例2：

47

输出样例2：

47

事实上呢，由4和7组成的10位以内的数也就1024个，然后可以枚举出来，然后判断一下个数是否相同，最后就lowerbound就拿到答案了

#include <bits/stdc++.h>

using namespace std;
/*
 * author: Paren
 * time:2022/12/03 Sat.
 */
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1e9 + 7;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int N = 1000;

set<ll> S;

void dfs(ll x, int n4, int n7) {
    if (n4 + n7 >= 11) {
        return;
    }
    if (n4 == n7) {
        S.insert(x);
    }
    dfs(1ll * x * 10 + 4, n4 + 1, n7);
    dfs(1ll * x * 10 + 7, n4, n7 + 1);
}

void solve() {
    dfs(0, 0, 0);
    S.erase(0);
    int n;
    cin >> n;
    cout << *S.lower_bound(n);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

摆放棋子

给定 n1 个完全相同的黑色棋子和 n2 个完全相同的白色棋子。

请你将所有棋子摆成一排。

在所有棋子都摆放好后，需满足：

  1. 不得有超过 k1 （即大于 k1）个黑色棋子连续相邻的排在一起。
  2. 不得有超过 k2 （即大于 k2）个白色棋子连续相邻的排在一起。

请问一共有多少种不同的摆放方法。

由于结果可能很大，你只需要输出对 $10^8$ 取模后的结果。

输入格式

共一行，包含 4 个整数 $n1,n2,k1,k2$。

输出格式

输出满足要求的摆放方法数量对 $10^8$ 取模后的结果。

数据范围

前 44 个测试点满足 $1≤n1,n2≤10$。
所有测试点满足 $1≤n1,n2≤100$，$1≤k1,k2≤10$。

输入样例1：

2 1 1 10

输出样例1：

1

输入样例2：

2 3 1 2

输出样例2：

5

输入样例3：

2 4 1 1

输出样例3：

0

定义fiu表示已经摆放了i颗黑色棋子,j颗白色棋子,结尾为连续u颗相同颜色棋子,并且以v颜色结尾(0表示黑色,1表示白色),瞎搞一搞就出来了，是个原题，CF118D

#include <bits/stdc++.h>

using namespace std;
/*
 * author: Paren
 * time:2022/12/03 Sat.
 */
#define all(c) (c).begin(), (c).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define Sum(a) accumulate((a).begin(), (a).end() , 0ll)
#define Min(a) *std::min_element((a).begin(), (a).end())
#define Max(a) *std::max_element((a).begin(), (a).end())
#define rev(a) reverse((a).begin(), (a).end())
#define each(x, a) for(auto& x : a)
#define mst(a, x) memset(a, x, sizeof(a))
#define rep(i, from, to) for(ll i = from;i<to;i++)
#define rrep(i, from, to) for(ll i = from;i>=to;i--)
#define to_uni(a) a.erase(unique(begin(a), end(a)), end(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define endl "\n"
#define ll long long
typedef pair<int, int> pii;
const int mod = 1e8;
const int dx[4]{1, 0, -1, 0}, dy[4]{0, 1, 0, -1};
const int fx[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, fy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int N = 1000;

int N1, N2, K1, K2;
int f[210][110][30];

void solve() {
    cin >> N1 >> N2 >> K1 >> K2;
    f[1][1][1] = f[1][1][K1 + 1] = 1;
    f[1][0][0] = f[1][0][K1 + 2] = 1;
    for (int i = 1; i < N1 + N2; i++) {
        for (int j = 0; j <= min(i, N1); j++) {
            if (j < N1) {
                for (int k = 0; k <= K1 - 1; k++) {
                    if (!f[i][j][k]) continue;
                    f[i + 1][j + 1][k + 1] = ((ll) f[i + 1][j + 1][k + 1] + f[i][j][k]) % mod;
                    f[i + 1][j + 1][K1 + 1] = ((ll) f[i + 1][j + 1][K1 + 1] + f[i][j][k]) % mod;
                }
            }
            if ((i - j) < N2) {
                for (int k = K1 + 1; k <= K1 + 1 + K2 - 1; k++) {
                    if (!f[i][j][k]) continue;
                    f[i + 1][j][k + 1] = ((ll) f[i + 1][j][k + 1] + f[i][j][k]) % mod;
                    f[i + 1][j][0] = ((ll) f[i + 1][j][0] + f[i][j][k]) % mod;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i <= K1; i++) {
        ans = ((ll) ans + f[N1 + N2][N1][i]) % mod;
    }
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int T = 1;
//    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

绝对不是恋爱脑！