比赛记录

比赛传送门

A

没什么好说的,打表根据 n 输出就行

Code

1
2
3
4
5
6
7
void solve() {
    vector<char> a{'A','B','C','D','E','F','G','H','I','J','K','L','M'};
    int n;
    cin >> n;
    for(int i=0;i<n;i++) cout << a[i] << " ";
    cout << el;
}

B

观察数据,肯定不能模拟象的路径,只能人算
大概猜一下(1,1)点为起点是最优的
分别计算奇数行能到的位置有多少和有多少奇数行,偶数同理
注意特判

Code

1
2
3
4
5
6
7
8
9
10
11
12
void solve() {
    int n,m;
    cin>>n>>m;
    if (n<3 || m<3) {
        cout<<1 <<el;
        return;
    }
    int jin=n/4+(n%4==0 ? 0 : 1),jim=m/4+(m%4==0 ? 0 :1);
    n-=2; m-=2;
    int oun=n/4+(n%4==0 ? 0 : 1),oum=m/4+(m%4==0 ? 0 :1);
    cout << jin*jim+oun*oum<<el;
}

C

直觉就是只能全选或者全部选才有最小花费
cf打多了天天在这猜
就比较原数组的和与 数组全修改为最小值的和加上最大值 的大小即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void solve() {
    int n;
    cin>>n;
    vector<int> a(n);
    int sum=0;
    for(int i=0;i<n;i++) {
        cin>>a[i];
        sum+=a[i];
    }
    int mx =*max_element(all(a));
    int mn =*min_element(all(a));
    int t=mx+n*mn;
    cout << min(t,sum) << el;
}

D

一眼看出没有 1 那么数组子序列之和构成序列 S 的mex为 1
接下来讨论有 1 怎么办
将数组 a 升序排序,记当前能达到的最大连续数字为mx(说的有点难懂,就是当前mex-1的值)
从左向右扫描,如果满足 $a[i]≦mx+1$ ,则将mx加上a[i]
为什么这样可以有效更新?
因为mx意味着之前数组可以取出任何小于等于mx的数[1…mx],也就可以让mx更新到 mx+a[i]
不满足说明这个数对于S的mex的贡献为0,可以删掉

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve() {
    int n;
    cin>>n;
    vector<int> a(n);
    bool found=false;
    for(int i=0;i<n;i++) {
        cin>>a[i];
        if (a[i]==1) found=true;
    }
    if(found==false) cout<<n<<el;
    else {
        sort(all(a));
        int mx=0;
        int ans=0;
        for(int i=0;i<n;i++) {
            if (a[i]<=mx+1) mx+=a[i];
            else ans++;
        }
        cout<<ans<<el;
    }
}

补题传送门

说些什么吧！

waline