AtCoder Beginner Contest 276「A」「B」「C」「D 思维」「E 联通块」「F 树状数组维护期望」

AtCoder Beginner Contest 276

A - Rightmost

题目描述：

给定一个字符串S，找出字符a出现的最后一个位置，没找到就输出-1

思路：

for一遍

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    string s;
    cin >> s;
    for(int i = (int)s.size() - 1; i >= 0; --i){
        if(s[i] == 'a'){
            cout << i + 1 << endl;
            return;
        }
    }
    cout << -1 << endl;
}


int main(){
    io;
    work();
    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

B - Adjacency List

题目描述：

n个点，m条边，对于每个点i，输出与i相邻的点的个数以及所有与他相邻的点

思路：

vector建图

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
vector<int>v[MAX];
void work(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        int x, y;
        cin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    for(int i = 1; i <= n; ++i){
        cout << v[i].size();
        sort(v[i].begin(), v[i].end());
        for(auto x : v[i])cout << " " << x;
        cout << endl;
    }
}

int main(){
    io;
    work();
    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
36
37

C - Previous Permutation

题目描述：

给你一个长度为n的全排列，你需要输出他的上一个全排列

思路：

直接prev_permutation

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
int tr[MAX];

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i];
    prev_permutation(tr+1, tr+1+n);
    for(int i = 1; i <= n; ++i)cout << tr[i] << ' ';
    cout << endl;
}


int main(){
    io;
    work();
    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

D - Divide by 2 or 3

题目描述：

给你一个数组，你有两种操作：

• 选择一个是2的倍数的数字，让它除以2
• 选择一个是3的倍数的数字，让它除以3

问最少能通过多少次操作使得所有数字相等

思路：

显然最后的数字是g=gcd(a1, a2, ... , an)

判断a[i]能不能变成g的条件是：

• a[i]%g==0
• 看a[i]/g能不能通过除2除3变成1

答案就是对每个a[i]/g变成1的操作次数求和

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k, x;
ll tr[MAX];

ll gcd(ll a, ll b){
    if(b) return gcd(b, a % b);
    else return a;
}

ll fuck(ll x){
    int ans = 0;
    while(x % 2 == 0){
        x /= 2;
        ++ans;
    }
    while(x % 3 == 0){
        x /= 3;
        ++ans;
    }
    if(x == 1)return ans;
    else return -1;
}

void work(){
    cin >> n;
    ll g = 0;
    for(int i = 1; i <= n; ++i){
        cin >> tr[i];
        g = gcd(g, tr[i]);
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        ll p = fuck(tr[i] / g);
        if(p == -1){
            cout << -1 << endl;
            return;
        }
        ans += p;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    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
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

E - Round Trip

题目描述：

给你一个n*m的字符矩阵，.可以走，#不可以走，S是起点，问能不能找到一条回路，满足起点和终点都是S点，且中间不会经过重复的点

思路：

可以发现S最多只有四个方向可以到达，所以如果能从一个点出，从另一个点进，则就可以满足要求，所以我们只需要跑出四个方向的点是否存在联通即可，我们可以用dfs暴力跑出整个图每个点的联通块，然后进行判断

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 1000000 + 50
int n, m, k, x;
int sx, sy;
string tr[MAX];
map<pii, int>mp;

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};

bool judge(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >= m)return false;
    else if(mp.count(m_p(x, y)))return false;
    else if(tr[x][y] == '#')return false;
    return true;
}
bool cao(int x, int y){
    if(x < 0 || x >= n || y < 0 || y >= m)return false;
    else if(tr[x][y] == '#')return false;
    return true;
}

int col;
void dfs(int x, int y){
    mp[m_p(x, y)] = col;
    for(int i = 0; i < 4; ++i){
        int xx = x + dx[i];
        int yy = y + dy[i];
        if(!judge(xx, yy))continue;
        dfs(xx, yy);
    }
}

void work(){
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        cin >> tr[i];
    }
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(tr[i][j] == 'S'){
                tr[i][j] = '#';
                sx = i;sy = j;
            }
        }
    }
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            if(!mp.count(m_p(i, j)) && tr[i][j] != '#'){
                ++col;
                dfs(i, j);
            }
        }
    }
    vector<int>a;
    for(int i = 0; i < 4; ++i){
        int xx = sx + dx[i];
        int yy = sy + dy[i];
        if(cao(xx, yy))a.push_back(mp[m_p(xx, yy)]);
    }
    
    for(int i = 0; i < a.size(); ++i){
        for(int j = i + 1; j < a.size(); ++j){
            if(a[i] == a[j]){
                cout << "Yes\n";
                return;
            }
        }
    }
    cout << "No\n";
}


int main(){
    io;
    work();
    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
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
91

F - Double Chance

题目描述：

n个卡片，每个卡片的值为a[i]

对于前K个卡片，我们连续取两次卡片，每次取完都会放回去，计两张卡片的最大值为此次的ans，求ans的期望是多少

K是从1到n的

思路：

我们要知道从K张卡片中抽出的所有情况的数量是K*K，这就是期望的分母，分子应该是每种情况的答案的求和

对于K=i的答案其实可以从K=i-1推过来，因为只多了a[K]这一个卡片，也就是只多了2*K-1种抽法，而这2*K-1种抽法贡献的答案可以分成两部分来计算，第一部分是x<=a[K]的数，假设x<=a[K]的x的数量是num，这些数字对分子的贡献是数量2*num+1乘以a[K],第二部分是x>a[K]的数，这些数字的对答案的贡献是这些数字的和(即前k-1个数字中出现的严格大于a[k]的所有的数字的和)

我们可以用两个树状数组来维护分子，对于每个答案，我们只需要再乘以i*i的逆元即可得到期望

#include 
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;
#define lowbit(x) (x&(-x))
#define int long long
#define MAX 500000 + 50
int n, m, k, x;
int ar[MAX];

int rk[MAX];
void update(int i, int c){
    while (i <= 400050) {
        (rk[i] += c)%=mod9;
        i += lowbit(i);
    }
}
int getnum(int i){//1到i的和
    int ans = 0;
    while (i > 0) {
        (ans += rk[i])%=mod9;
        i -= lowbit(i);
    }
    return ans;
}

int sum[MAX];
inline void update2(int i, int c){
    while (i <= 400050) {
        (sum[i] += c)%=mod9;
        i += lowbit(i);
    }
}

inline int getnum2(int i){//1到i的和
    int ans = 0;
    while (i > 0) {
        (ans += sum[i])%=mod9;
        i -= lowbit(i);
    }
    return ans;
}

ll q_pow(ll a, ll b, ll MOD){
    a%=MOD;
    ll ans = 1;
    while(b > 0){
        if(b & 1)ans = ans * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return ans;
}

inline ll getniyuan(ll a, ll p){
    return q_pow(a, p - 2, p);
}

void work(){
    cin >> n;
    for(int i = 1; i <= n; ++i){
        cin >> ar[i];
    }
    ll ans = 0;
    for(int i = 1; i <= n; ++i){
        int num = getnum(ar[i]);
        update(ar[i], 1ll);
        (ans = ans + ((2ll * num + 1) * ar[i])%mod9)%=mod9;
        int cnt = ((getnum2(400000) - getnum2(ar[i])) + mod9) % mod9;
        update2(ar[i], ar[i]);
        (ans += 2ll*cnt)%=mod9;
        int cao = (getniyuan((i*i)%mod9, mod9))%mod9;
        cout << (ans * cao) % mod9 << endl;
    }
}

signed main(){
    io;
    work();
    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
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