算法练习专栏——牛客练习——牛客小白月赛93

A:生不逢七:cn:

链接

题目描述

睡前游戏中最简单又最好玩的游戏就是这个啦！

​ 该游戏规则为：多名玩家轮流报数，当要报的数字中含有 7 或者是 7 的倍数时（例如 37，49），不能将该数报出来，要换一种提前规定好的方式报数，当一个人报错或者报慢了这个人就输了。

​ 我们认为玩家是围成一圈进行游戏的，第 n 个人报完数之后，会轮到第 1 个人报数。

现在告诉你玩家的总人数以及你上一个人报的数（用数字表示，即便这个数含有 7 或者是 7 的倍数），你需要预测接下来 k 轮你要报的数字，当你需要报的数字含有 7 或者是 7 的倍数时，你需要输出字符 p。

输入描述:

1
2
3
4
5
第一行一个整数 T，表示输入数据的组数。

接下来每组数据中均只有一行数据，每行三个整数 n，a，k，分别表示玩家数量，你的上一位玩家报的数，你需要模拟的游戏轮数。

数据保证 1≤T,n,k,a≤100。

输出描述:

1
共 T 行，每行输出 k 个整数或者字符 p。

示例1

输入

复制

1
2
3
4
3
2 16 3
3 69 3
2 1 10

输出

复制

1
2
3
p 19 p
p p p
2 4 6 8 10 12 p 16 18 20

代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i+=2)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 1e5 + 10;

bool check(int x) {
    if (x % 7 == 0) return false;
    string s = to_string(x);
    for(int i = 0; i < s.length(); i++) {
        int k = s[i] - '0';
        if (k == 7) return false;
    }
    return true;
}
void solve() {
    int n, a, k;
    cin >> n >> a >> k;
    ++a;
    if (check(a)) cout << a << " ";
    else cout << 'p' << " ";
    for (int i = 1; i <=k - 1; i++) {
        a += n;
        if (check(a)) cout << a << " "; 
        else cout << 'p' << " "; 
    }
    
    cout << ed;
}
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

B:交换数字:cn:

链接

题目描述

Baijiaohu有两个长度均为 n 且不包含前导零的数字 a,b ，现在他可以对这两个数字进行任意次操作：

  1. 选择一个整数 1≤i≤n ,并交换 a,b 的第 i 位 。

请输出任意次操作后 a×b 的最小值，由于答案可能很大，请对 998244353 取模。

输入描述:

1
2
3
第一行输入一个数字 n 代表两个数字的长度 
第二到三行输入两个字符串 a,b
1≤n≤2×105

输出描述:

1
2
输出一个 ans 表示最后的答案 
请对 998244353 取模

示例1

输入

复制

1
2
3
3
159
586

输出

复制

1
91884

示例2

输入

复制

1
2
3
10
1578959751
1786548221

输出

复制

1
410002876

思路

​

代码(python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
a = input()
b = input()
aa = list(a)
bb = list(b)
mod = 998244353
for i in range(n):
    if aa[i] > bb[i]:
        tmp = aa[i]
        aa[i] = bb[i]
        bb[i] = tmp
        
a = ''.join(aa)
b = ''.join(bb)
print(int(a) * int(b) % mod)

代码(C++)

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
#include <bits/stdc++.h>
typedef unsigned long long ll;
using namespace std;
const int N=2e5+10,mod=998244353;
int n;
int ma[N],mi[N];
string a,b;
ll A,B;
int main()
{
    cin>>n;
    cin>>a>>b;
    for(int i=0;i<n;i++)
    {
        if(a[i]<=b[i])
        {
            mi[i]=a[i]-'0',ma[i]=b[i]-'0';
        }
        else
        {
            mi[i]=b[i]-'0',ma[i]=a[i]-'0';
        }
    }
    for(int i=0;i<n;i++)
    {
        A=A*10+mi[i];
        B=B*10+ma[i];
        A=A%mod;
        B=B%mod;
    }
    cout<<A*B%mod;
    return 0;
}

C:老虎机:cn::cn:

链接

题目描述

老虎机游玩规则：共有三个窗口，每个窗口在每轮游玩过程中会等概率从图案库里选择一个图案，根据最后三个窗口中图案的情况获得相应的奖励。

你有一个老虎机，你可以设定这个老虎机图案的数量和收益规则。

现在你设定了图案的数量为 m，没有相同的图案得 a 元，一对相同的图案 b 元，三个相同的图案 c元。

​ 你想知道在你设定的规则下，单次游玩期望收益是多少？答案对 998244353 取模。

​ 根据 逆元 的定义，如果你最后得到的答案是形如 $\frac{a}{b}$ 的分数，之后你需要对 p 取模的话，你需要输出 $(a\times b^{mod - 2}) \bmod p$ 来保证你的答案是正确的。

输入描述:

1
2
第一行一个整数 T(1≤T≤104)。
接下来 T 行，每行四个整数 m,a,b,c(1≤m,a,b,c≤106)。

输出描述:

1
一个整数表示答案，答案对 998244353 取模。

示例1

输入

复制

1
2
1
2 2 3 4

输出

复制

1
748683268

说明

1
1/4 的概率出现三个相同的图案，收益为 4，3/4 的概率出现两个相同的图案，收益为 3，不可能出现没有相同图案的情况，期望收益为 13/4。
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define debug(x) cout << "#x = " << x << ed;

#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 1e5 + 10;
const LL mod = 998244353;

long long quick_sort(long long a, long long b) {
    long long ret = 1;
    while (b) {
        if ((b & 1) == 1) ret = ret*a%mod;
        a = a * a % mod;
        b >>= 1;
    }
         
    return ret;
} 
void solve(){
    long long m, a, b, c; cin >> m >> a >> b >> c;
     
    long long sum1=(c+(3*m-3)*b+(m*m-3*m+2)*a)%mod;
    long long sum2=m*m%mod;
    long long ret = sum1*quick_sort(sum2,mod-2)%mod;
    cout << ret << endl;
     
    return;
}
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}

D:幻兽帕鲁:cn::cn:

链接

题目描述

在幻兽帕鲁中，不同的帕鲁能干不同的工作，现在我们要对帕鲁进行分类以便他们能够更好的进行压榨。

你有 2n 只帕鲁，初始给每只帕鲁一个工号，并让帕鲁按 [0,2n−1] 工号的顺序排成一队。

当我们对区间 [l,r][l,r][l,r] 的帕鲁进行操作时，我们会对该区间的帕鲁按顺序进行临时编号 [0,r−l]，记 $mid = \lfloor\frac{l + r}{2}\rfloor$，我们将临时编号为偶数和奇数的帕鲁，分别按顺序置于区间 [l,mid] 和 [mid+1,r] ，并递归对这两个区间进行上述操作，直到区间长度为 1 。

现在我们对[0,2n−1] 的幻兽进行一次操作，然后给你 m 次询问，每次询问 x 位置的帕鲁工号是多少？

输入描述:

1
2
3
4
第一行两个整数 n,m(0≤n≤60,1≤m≤105) 。


接下来 m 行，每行一个整数 x 表示询问第 x 个位置的帕鲁的工号，位置从 0 开始计数。

输出描述:

1
输出每次询问的帕鲁的工号。

示例1

输入

复制

1
2
3
4
5
2 4
0
1
2
3

输出

复制

1
2
3
4
0
2
1
3

示例2

输入

复制

1
2
3
4
5
3 4
0
2
5
7

输出

复制

1
2
3
4
0
2
5
7

思路

​

代码

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <bitset>
#include <cstdio>
#include <iomanip>

// #define int long long
#define ull unsigned long long
#define ed '\n'
#define fi first
#define se second
#define fore(i, l, r) for(int i = (int)(l); i <=(int)r; i++)
#define reforce(i, l, r) for(int i = int(r); i >= (int)r; i--)
#define debug(x) cout << "#x = " << x << ed;
#define PI acos(-1)
#define E exp(1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define me0(st) memset(st, 0, sizeof st)
#define me3f(st) memset(st, 0x3f, sizeof st)
#define pdf(x) printf("%lf", double(x))
#define pif(x) printf("%d ",  int(x))
#define scf(x) printf("%d",  int(x))
#define re return 0
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define out(x, k) cout << fixed << setprecision(k) << x << ed

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
typedef double db;


const int INF = 1e9;
const int N = 2e5 + 10;
const LL mod = 998244353;

LL ans;

void solve() {
    int n, m;
    cin >> n >> m;
    while(m --)
    {
        LL x;
        cin >> x;
        LL res = 0 , cnt = 0;
        LL l = 0 , r = (1LL << n) - 1;
        while(l < r)
        {
            LL mid = (l + r) >> 1;
            if(x <= mid) 
            {
                r = mid;
                cnt ++;
            }
            else
            {
                res += 1LL << cnt;
                cnt ++;
                l = mid + 1;
            }
        }
        cout << res << ed;
    }
}
int main()
{
    IOS;
    int _ = 1;
//     cin >> _;
    
    while(_--) {
        solve();
    }
    
    re;
}