hdoj8

3,8,5 -> 6,7,9 -> 1,10,4,2

3. 疯狂的自我搜索者

Ques

题意

Aya 是修车专家，但是有很多彩黑批评她的修车技术还不如劈瓦大师 Amita， Aya 在网上自搜发现有非常多彩黑，她决定将彩黑统统屏蔽。

在接下来 n分钟内，每分钟会出现 条新的彩黑评论， Aya 每分钟至多可以屏蔽 x 条之前未屏蔽过的彩黑评论，在此我们认为，每一分钟都是彩黑评论先出现，然后 Aya 开始屏蔽彩黑评论。

Aya 想知道， n 分钟后还剩余多少条彩黑评论没有被屏蔽。

Input

第一行输入一个正整数 ，表示数据组数。

对于每一组数据：

第一行输入两个正整数 ，表示分钟数，每分钟可以屏蔽的彩黑评论数量。

第二行输入 n 个正整数 ，表示每分钟会出现的彩黑评论数量。

数据保证 。

Output

对于每组数据输出一个整数表示答案。

sample

1
2
3
1
6 3
1 1 4 5 1 4
1
2

Hint

第1分钟出现1条彩黑评论，Aya屏蔽1条彩黑评论，累计剩余0条彩黑评论。

第2分钟出现1条彩黑评论，Aya屏蔽1条彩黑评论，累计剩余0条彩黑评论。

第3分钟出现4条彩黑评论，Aya屏蔽3条彩黑评论，累计剩余1条彩黑评论。

第4分钟出现5条彩黑评论，Aya屏蔽3条彩黑评论，累计剩余3条彩黑评论。

第5分钟出现1条彩黑评论，Aya屏蔽3条彩黑评论，累计剩余1条彩黑评论。

第6分钟出现4条彩黑评论，Aya屏蔽3条彩黑评论，累计剩余2条彩黑评论。

因此答案为2。

Ans

模拟

1
2
3
4
5
6
7
8
9
10
void solve(){
    int n; ll x ; cin >> n >> x;
    ll res = 0;
    for(int i = 0;i < n;++i){
        ll a; cin >> a;
        res = max(0LL,res+a-x);
    }
    cout << res << endl;
    return;
}

8. 石头的领袖魅力

Ques

题意

有三只关系非常好的企鹅，她们的名字分别是Anon、Tomori、Taki。

Anon在和Tomori玩石子游戏，她们都极度聪明，Anon和Tomori轮流操作，Anon先手，初始时有 x 颗石子，每次操作必须恰好拿走 a 颗石子或者 b 颗石子，无法操作的企鹅将输掉这场游戏。

实际上，Taki正在帮Anon和Tomori的石子游戏准备初始石子，Taki喜欢Tomori，想帮助Tomori获得胜利，因此她想知道至少需要多少颗石子（不能为 0 ）可以使得Tomori必定获得胜利？即已知 a,b 的情况下，最小化正整数 x 的值，使得第二位玩家必胜。

Input

第一行输入一个正整数 表示数据组数。

每组数据第一行输入两个正整数 ，表示每次操作的限制。

Output

对于每组数据，在一行中输出一个整数表示答案。

sample

1
2
1
1 2
1
3

Ans

初始思路

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve(){
	ll a,b; cin >> a >>b;
	ll minn = min(a,b);
	ll maxn = max(a,b);
	if(minn*2 < maxn){
		cout << minn*2 << '\n'; 
	}else if(minn == maxn){
		cout << minn*2 << '\n';
	}
	else{
		cout << a+b << '\n';
	}
}

刚开始思维局限了，没意识到其实可以在一开始就卡Anon，并不是一定要过了一轮才开始卡Anon，于是……

题解

1
2
3
4
5
6
7
void solve(){
    ll a,b; cin >> a >> b;
    if(a > b) swap(a,b);
    if(a > 1) cout << "1\n";
    else if(b == 2) cout << "3\n";
    else cout << "2\n";
}

5. 笑容波状攻击

Ques

题意

定义 0101 串的 mex 为：字符串所有字符中最小未出现的非负整数。例如， mex（”0”）=1,mex（”1”）=0,mex（”1010”）=2 。

定义一个 0101 串的快乐值为，这个 0101 串的所有子串的 mex 之和。

Kokoro 有一个 0101 串，不太聪明的她想知道这个 0101 串的快乐值是多少。

Input

第一行输入一个正整数 ，表示数据组数。

对于每一组数据：

第一行输入一个 01 串 s 。

数据保证 。

Output

对于每组数据输出一个整数表示答案。

sample

1
2
3
4
5
4
00
11
10
01
1
2
3
4
3
0
3
3

Ans

对于二进制串，字串的mex只有三种取值：

  • mex = 0 ：子串不含0，即全为1
  • mex = 1 ：子串不含1，即全为0
  • mex = 2 ：子串同时含0和1

相较于同时含0和1的子串，只含1和只含0的子串更加容易处理，故而我们令tot记录总子串数n(n+1)/2，s1记录全1的子串数 初始为0，s0记录全为0的子串数 初始为0。则

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void solve(){
    string s; cin >> s;
    int n = s.size();
    ll tot = n*(n+1)/2;
    ll s1  = 0,s0 = 0;

    ll tmp = 1;
    for(int i = 1;i <= n;++i){
        if(i < n && s[i] == s[i-1]) ++tmp;
        else{
            tmp = tmp*(tmp+1)/2;
            if(s[i-1] == '1') s1 += tmp;
            else s0 += tmp;
            tmp = 1;
        }
    }

    ll res = 2*tot - 2*s1 - s0;
    cout << res << endl;
    return;
}

看到第8行代码，于是有人就会说了，主播主播，你这不是字符串吗，为什么for循环的终止条件是i <= n，是不是敲错了

并非，这是竞赛中常见的”哨兵”技巧，让循环多跑一轮 i = n，这个目的是把最后一段给”冲”出来，避免在循环结束后再写一遍同样的处理逻辑。当然，i = n 时，它是直接进else分支里的。

6. 忠犬PARE公

Ques

题解

PAREO 和 CHU 是一对关系很好的主仆，这天， CHU 有一道非常难的数学题不会做，因此她让 PAREO 把问题交给了你。

有两个长度分别为 n,m 的数组 a,b ，求 $\sum{i=1}^n \sum{j=i}^m \frac{lcm(a_i,b_i)}{gcd(a_i,b_i)}$ 。

其中 分别是求 x 和 y 的最大公约数、最小公倍数。由于最后的答案可能很大，因此你需要输出答案对 取模后的结果。

Input

第一行输入一个整数 表示数据组数。

对于每组数据：

第一行输入两个正整数 ，表示两个数组长度。

第二行输入 n 个正整数 表示数组 a 。

第三行输入 m 个正整数 表示数组 b。

数据保证。

由于输入的数据量非常大，建议使用较快的输入方式，如在C++中关闭同步流。

Output

对于每组数据输出一个整数表示答案对 取模后的结果。

sample

1
2
3
4
5
6
7
2
1 5
1
1 4 5 1 4
3 3
1 1 4
5 1 4
1
2
15
45

Hint

对于第一组样例：

lcm(1, 1) / gcd(1, 1) = 1 / 1 = 1

lcm(1, 4) / gcd(1, 4) = 4 / 1 = 4

lcm(1, 5) / gcd(1, 5) = 5 / 1 = 5

lcm(1, 1) / gcd(1, 1) = 1 / 1 = 1

lcm(1, 4) / gcd(1, 4) = 4 / 1 = 4

1 + 4 + 5 + 1 + 4 = 15

Ans

所需芝士：

gcd/lcm/模运算基础

调和级数枚举

频率数组技巧

线性筛 + 积性函数

狄利克雷卷积/莫比乌斯入门

这边再沉淀沉淀