img

牛客周赛 Round 30

小红的删字符

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>
 
#define int long long
#define endl '\n'
 
using namespace std;
 
void solve() {
    string s;
    cin >> s;
    cout << s[0] << s[2] << endl;
}
 
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    //cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

小红的正整数

排序后输出即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<bits/stdc++.h>
using namespace std;
string s;
signed main()
{
    cin >> s;
    sort(s.begin(), s.end());
    if(s[0] == '0')
        for(int i = 1; i < s.length(); i ++)
            if(s[i] != '0')
            {
                swap(s[0], s[i]);
                break;
            }

    cout << s << endl;

    return 0;
}

小红的构造回文

由于三个一定不行

其余的都可以，只需要找到不同即可

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>
#define int long long
using namespace std;
 
int a[27];
 
void solve() {
    string s;
    cin >> s;
    int n = s.size();
    int mid = n / 2;
    int f = 0;
    for(int i = 1; i < mid; i++) 
    {
        if(s[i] != s[i - 1]) 
        {
            f = 1;
            swap(s[i], s[i - 1]);
            swap(s[n - i - 1], s[n - i]);
            cout << s << endl;
            break;
        }
    }
    if(!f) cout << -1 << endl;
}
 
signed main() {
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    //cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

小红整数操作

由于是要×到两个数之间

依据题意一定可以

我们完全可以考虑先除到最小，就是除以最大公约数

这样最有操作空间

并在后面我们完全不粗需要忧虑除法的问题，只需要枚举乘法记录答案即可。

题解优质代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll gcd(ll a, ll b){return b ? gcd(b, a % b) : a;}

int main()
{
    ll x, y, l, r, ans = 0;
    cin >> x >> y >> l >> r;
  //计算最大公因数
    ll goncd = gcd(x, y);
      //找到最基础的值
    x /= goncd, y /= goncd;
      //判断范围是否合法，若合法，则计数
    for(ll i = 1; i * x <= r && i * y <= r; i ++)
        if(i * x >= l && i * y >= l)
            ans ++;
  //输出
    cout << ans << '\n';

    return 0;
}

小红树上染色

f[u] [1]表示以u为根节点，且此节点为红色

[0]则为白色

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;
typedef long long ll;
const int N = 1e5+5, Mod = 1e9+7;
int n;
vector<int> tree[N];
ll f[N][2];
void dfs(int u,int father)
{
    f[u][0] = f[u][1] = 1;
  //遍历tree[u]中的相邻节点
    for(int x : tree[u])
      //若不是父节点，再进行下一步操作
        if(x != father)
        {
            dfs(x,u);
          //当根节点为白色时，种类数为自身为白色时的数量 * 子节点为红色时的数量
            f[u][0] = f[u][0] * f[x][1] % Mod;
          //当根节点为红色时，种类数为自身为白色时的数量 * 子节点为（红色或白色）时的数量
            f[u][1] = f[u][1] * (f[x][0] + f[x][1]) % Mod;
        }
}
int main()
{
    cin>>n;
  //建立邻接表
    for(int i = 1; i < n; i ++)
    {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1,-1);
  //输出树的根部时，红色加白色的种类数的总和即使所求值
    cout<<(f[1][0]+f[1][1]) % Mod <<'\n';
    return 0;
}