AtCoder Beginner Contest 346

A - Adjacent Product

题意

给你一个数组$a1,a_2,…,a_n$ ，现在有$b_i = a_i * a{i+1}$ 输出$b1,b_2,…,b{n-1}$

思路

照着题意写就行

代码

1
2
3
4
5
n = int(input())
lst = [int(x) for x in input().split()]
ans = []
for i in range(len(lst)-1):
    print(lst[i] * lst[i+1],end=' ')

B - Piano

题意

有一个字符串，由无数个wbwbwwbwbwbw 重复得来，现在给出两个数W和B$(1\le W,B \le 100 )$ 问是否存在某个子串满足：包含$W$个w以及$B$ 个b

思路

这个子串一定不会超过200位，所以我们重复wbwbwwbwbwbw 40次(长度$12*40 = 480$)就可以保证所有的子串都在其中，然后我们求所有长度为$W+B$ 的子串，依次判断他们是否满足情况。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
str = "wbwbwwbwbwbw"*100
w,b = [int(x) for x in input().split()]
sm = []
sm.append(0)
cnt = 0
for x in str:
    if x == 'w':
        cnt+=1
    sm.append(cnt)
for l in range(1,len(sm)):
    r = l+w+b-1
    if r >= len(sm):
        break
    if(sm[r] -sm[l-1]==w):
        print("Yes")
        exit(0)
print('No')

C - Σ

题意

给出$n,k$ 以及一个长度为n的数组A ，问所有$[1,k]$ 中不属于A的数的总和是多少。

$(1 \le n \le 210^5 , 1\le k,A_i \le 2 10^9)$

思路

我们遍历整个数组A，取出其中位于$[1,k]$ 中的所有数， 然后去重。对去重后的数组求和 ，令总和为$sum$，那么最终答案就是$\frac{k*(k+1)}{2} - sum$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input())
string = input()
string = ' ' + string
a = [int(x) for x in input().split()]
sm = [0]
for x in a:
    sm.append(sm[-1]+x)
a = [0] + a
cost = [0]*(n+5)
for i in range(1,n+1):
    cost[i]=cost[i-1]
    if (string[i] == '1')^(i%2) :
        cost[i]+=a[i]
ans = int(1e18)
for i in range(1,n):
    ans = min(ans,cost[i]+(sm[n]-sm[i])-(cost[n]-cost[i]))
    ans = min(ans,(sm[i]-cost[i])+(cost[n]-cost[i]))
print(ans)

D - Gomamayo Sequence

题意

给你一个长度为n的01串S，以及一个长度为n的数组a。$a_i$表示将$S_i$ 进行01翻转所需要的花费。

问最少需要多少花费，能够使得S满足：满足$Si = S{i+1}$ 的$i$恰好有一个。

思路

我们先设有如下两个长度同样为n的字符串：

S1 = 1010101...

S2 = 0101010...

对于最终的字符串，他一定是从S1和S2中各取出一边拼接得来。如S = 0101101 则是先取S2的前4个字符，与S1的后3个字符进行拼接。

我们可以计算出将前$i$个字符替换为S1形式的花销$cost1_i$ 以及将前$i$个字符替换为S2形式的花销$cost2_i$ 。

于是我们枚举拼接点$i$($1\le i \le n-1$) 。 对于每个拼接点，有两种拼接方式：

  1. 选择左半部分为S1，右半部分为S2
  2. 选择左半部分为S2，右半部分为S1

利用已经预处理完毕的$cost1,cost2$ 前缀和数组,分别计算出两部分的花费。与答案取MIN。

最终的答案就是这$2*(n-1)$种选择中的最小值

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
n = int(input())
string = input()
string = ' ' + string
a = [int(x) for x in input().split()]
a = [0] + a
cost1 = [0]*(n+5)
cost2 = [0]*(n+5)
for i in range(1,n+1):
    cost1[i]=cost1[i-1]
    cost2[i]=cost2[i-1]
    if (string[i] == '1')^(i%2) :
        cost1[i] += a[i]
    else :
        cost2[i] += a[i]
ans = int(1e18)
for i in range(1,n):
    ans = min(ans,cost1[i]+cost2[n]-cost2[i])
    ans = min(ans,cost2[i]+cost1[n]-cost1[i])
print(ans)

E - Paint

题意

给出一个$H$行$W$ 列的表格，起初全部涂满了0 。下面要进行M次操作，每次操作有三个参数$t,a,x$

  • $t = 1$时，将第$a$​行涂为编号为x的颜色。
  • $t = 2$时，将第$a$列涂为编号为x的颜色。

问你最终都有哪些颜色，每种颜色占有多少个格子。(按照颜色编号从小到大输出，占有格子为0的颜色不输出)

思路

直接暴力染色很显然会超时(复杂度$O(MN)$) 。 我们发现后染色的会覆盖之前已经染好的颜色。因此我们倒序处理每一个染色操作。

我们用变量$row$记录已经染了几行，用$col$表示已经染了几列。

对于一次新的染色，只能选择之前未染色的格子来染色（因为是逆序），若这次染色为行，那么最终会染$m - col$ 个格子。(这一行共m个格子中有col个格子之前就已经被染色) ，若染色为列，同理$n - row$。

我们还需要注意，如果选择的这一行，在之前就已经选择过，那么这次染色是无效的(一整行都被之前染色过了)，应该直接跳过

代码

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
n,m,q = [int(x) for x in input().split()]
ope = []
for _ in range(q):
    t,a,x = [int(x) for x in input().split()]
    ope.append((t,a,x))
sm = n * m
color = [0]*(int(2e5+5))
col = [0]*(int(2e5+5))
colsum,rowsum = 0,0
row = [0]*(int(2e5+5))
for t,a,x in ope[::-1]:
    if t == 1:
        if row[a] == 0:
            rowsum += 1
            color[x] += m - colsum
            sm -= m - colsum
            row[a] = 1
    else:
        if col[a] == 0:
            colsum += 1
            color[x] += n - rowsum
            sm -= n - rowsum
            col[a] = 1
color[0]+=sm
ans = []
for i in range(int(2e5+2)):
    if(color[i] != 0):
        ans.append((i,color[i]))
print(len(ans))
for a,b in ans:
    print(a,b,end=" ")
    print()

F - SSttrriinngg in StringString

题意

定义$f(X,k)$表示将X这个字符串整体重复k次。$g(X,k)$表示将X的每一个字符重复k次后拼接起来。

f("abc",2) = abcabc。g("abc",2) = aabbcc

现在给你一个整数n和两个字符串$S,T$ ,求出k最大是多少，能使得$g(T,k)$是$f(S,n)$的子序列(子序列不连续）。

思路

很明显的二分答案。关键在于check函数的编写。

先预处理出来如下信息：

  • 26个字母的在S中出现次数的前缀和。int cnt[26][maxn]; 。cnt[1][3]表示在S的前三个字符中，有几个b字符。
  • 26个字母的第i次出现在S中的下标位置。vector<int> pos[26]; pos[1][2]表示在S中的第二个b的下标是多少。

我们在check中，k是已知的。

可以使用一个变量$used$ 表示已经使用了几个完整的S字符串。我们遍历T中的每个字符$ch$。他要重复k次，因此就需要进行如下两步操作：

  1. 如果当前这个字符串还有剩余的ch字符，先用这些字符
  2. 如果不够用，就”启封“新的字符串S。直接计算要用多少个成套的字符串S
  3. 如果用完这些成套的字符串S，还差一些，就再启封一个S，使用其中的一部分字符串。

我们用p表示对于当前启封的字符串，用到了哪个位置了(下标） ，这样下一次只能使用从pos往后的字符。

注意在第2步中，不能使用循环来求，应该直接让剩余量整除以cnt[ch-'a'][n] 得到需要的套数。否则会导致超时。

循环结束后，如果我们有一套启封了但没有用完，同样需要对used进行加一操作。

最终我们要判断的是used是否小于等于N

代码

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
#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
#define rep(i,l,r) for(int i = l;i<=r;i++)
#define per(i,r,l) for(int i = r;i>=l;i--)
const int INF = 0x3f3f3f3f3f3f3f3f;
typedef pair<int,int> PII;
int N;
int n;
string S,T;
const int maxn = 1e5+5;
int cnt[26][maxn];
vector<int> pos[26];
bool check(int k){
    int used = 0;//已经用了多少套完整的S
    int p = 0;//目前这一套用到哪了
    for(char ch : T){
        int kk = k;//还需要多少个kk
        int num = ch-'a';
        if(cnt[num][n] == 0){return false;}
        int time = min(cnt[num][n]-cnt[num][p],kk);
        kk -= time;
        p = pos[num][cnt[num][p]+time];
        used += kk/cnt[num][n];
        kk -= kk/cnt[num][n] * cnt[num][n];
        if(kk){
            used++;
            p = pos[num][kk];
        }
        if(used + (p!=0) > N){ //如果p不等于0表示有一套S用了一半。这时候需要让答案加一
            return false;
        }
    }   
    return true;
}
void solve(){
    cin>>N>>S>>T;
    n = S.length();
    S = " "+ S;
    for(int i = 0;i<26;i++) pos[i].push_back(0);
    for(int i =1;i<=n;i++){
        for(int j = 0;j<26;j++){
            cnt[j][i] += cnt[j][i-1];
        }
        cnt[S[i]-'a'][i]++;
        pos[S[i]-'a'].push_back(i);
    }
    int l = 0,r = 1e18;
    while(l < r){
        int mid = (l+r+1)/2;
        if(check(mid)) l = mid;
        else r = mid -1;
    }
    cout<<l;
}
signed main(){
    int T = 1;
    // cin>>T;
    while(T--){
        solve();
    }
    return 0;
}