跳转至

abc458

AtCoder Beginner Contest 457

A

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
#include<iostream>
using namespace std;
const int N = 150;
int a[N];
int main(){
    int n;
    cin >> n;
    for(int i = 1;i<=n;i++){
        cin >> a[i];
    }
    int x;
    cin >> x ;
    cout << a[x] << endl;
    return 0;
}

B

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
using namespace std;
const int N = 2e5+10;
int a[N][N];
int n;
int main(){
    cin >> n;
    int idx = 1;
    while(n-->0){
        int t;
        cin >> t;
        for(int i=1;i<=t;i++)
            cin >> a[idx][i];
        idx++;
    }
    int x,y;
    cin >> x >> y;
    cout << a[x][y] << endl;
    return 0;
}

1

C

1

D

题目描述

黑板上最初写着一个整数 $ X $ 。

接下来会有 $ Q $ 个查询，请你依次处理。第 $ i $ 个查询（\(1\le i\le Q\)）内容如下：

给出两个整数 $ A_i,B_i $，将这两个数写到黑板上。

然后，输出黑板上目前所有 $ 2i+1 $ 个整数的中位数。

输入格式

输入从标准输入给出，格式如下：

$ X $
$ Q $
$ A_1 $ $ B_1 $
$ A_2 $ $ B_2 $
...
$ A_Q $ $ B_Q $

输出格式

输出 $ Q $ 行。

第 $ i $ 行输出第 $ i $ 个查询的答案，也就是当前黑板上所有数的中位数。

输入输出样例 #1

输入 #1

1
2
3
4
5
5
3
2 3
1 2
8 9

输出 #1

1
2
3
3
2
3

说明/提示

样例解释 1

第 $ 1 $ 个查询后，黑板上的数是 $ 5,2,3 $，中位数是 $ 3 $。

第 $ 2 $ 个查询后，黑板上的数是 $ 5,2,3,1,2 $，中位数是 $ 2 $。

第 $ 3 $ 个查询后，黑板上的数是 $ 5,2,3,1,2,8,9 $，中位数是 $ 3 $。

约束条件

  • $ 1\le X\le 10^9 $
  • $ 1\le Q\le 2\times 10^5 $
  • $ 1\le A_i,B_i\le 10^9 $
  • 输入的所有数均为整数
 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
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<iostream>
#include<queue>
#include<iomanip>
#include<cmath>
using namespace std;
using ll = long long;
const ll N=1e5+5,M=2e6+5,mod=998244353,inf=1LL<<60;
const long double pi=acos(-1);

void solve(){
    int x,q;
    cin >> x >> q;
    priority_queue<int,vector<int>,greater<int>> mi;
    priority_queue<int> ma;
    ma.push(x);
    while(q--){
        int a,b;
        cin >> a >> b;
        // int tm = ma.top();
        if(a>=ma.top()){
            mi.push(a);
        }else {
            ma.push(a);
        }
        if(b>=ma.top()){
            mi.push(b);
        }else {
            ma.push(b);
        }
        ll t = (ll)ma.size()-(ll)mi.size();
        if(t==1){
            cout << ma.top() << endl;
        }else if(t==3){
            int tt = ma.top();
            ma.pop();
            mi.push(tt);
            cout << ma.top() << endl;
        }else if(t==-1){
            int t2 = mi.top();
            mi.pop();
            ma.push(t2);
            cout << ma.top() << endl;
        }
    }
}

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

E

问题陈述

求长度为 \(X _ 1+X _ 2+X _ 3\) 的序列 \(A = (a _ 1, \cdots, a _ {X _ 1 + X _ 2 + X _ 3})\) 中，满足以下所有条件的模数 \(998244353\) 的个数。

  • \(A\) 恰好包含 \(X _ 1\) 份 \(1\) ，恰好包含 \(X _ 2\) 份 \(2\) 和恰好包含 \(X _ 3\) 份 \(3\) 。
  • 相邻元素之间的绝对差最多为 \(1\) 。也就是说，对于满足 \(1 \leq i \leq X _ 1+X _ 2+X _ 3-1\) 的每一个整数 \(i\) ，我们都有 \(|a _ {i+1} - a _ i| \leq 1\) 。

思路

显然这是一个排列组合问题

1

F

问题陈述

给你一个由小写英文字母组成的 \(K\) 字符串 \(S _ i\) 。
求长度为 \(N\) 的由小写英文字母组成的字符串中，子串（连续子序列）不包含 \(S _ 1, S _ 2, \dots, S _ K\) 的个数，取模为 \(998244353\) 。

1

G

1