AtCoder Beginner Contest 346 (ABCDEF)

标签：AtCoder cnt int 346 cost sm ans input ABCDEF

AtCoder Beginner Contest 346

A - Adjacent Product

题意

给你一个数组 a 1 , a 2 , . . . , a n a_1,a_2,...,a_n a1,a2,...,an ，现在有 b i = a i ∗ a i + 1 b_i = a_i * a_{i+1} bi=ai∗ai+1 输出 b 1 , b 2 , . . . , b n − 1 b_1,b_2,...,b_{n-1} b1,b2,...,bn−1

思路

照着题意写就行

代码

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 ≤ W , B ≤ 100 ) (1\le W,B \le 100 ) (1≤W,B≤100) 问是否存在某个子串满足：包含 W W W个w以及 B B B 个b

思路

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

代码

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,k n,k 以及一个长度为n的数组A ，问所有 [ 1 , k ] [1,k] [1,k] 中不属于A的数的总和是多少。

( 1 ≤ n ≤ 2 ∗ 1 0 5 , 1 ≤ k , A i ≤ 2 ∗ 1 0 9 ) (1 \le n \le 2*10^5 , 1\le k,A_i \le 2 * 10^9) (1≤n≤2∗105,1≤k,Ai≤2∗109)

思路

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

代码

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 a_i ai表示将 S i S_i Si 进行01翻转所需要的花费。

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

思路

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

S1 = 1010101...

S2 = 0101010...

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

我们可以计算出将前 i i i个字符替换为S1形式的花销 c o s t 1 i cost1_i cost1i 以及将前 i i i个字符替换为S2形式的花销 c o s t 2 i cost2_i cost2i 。

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

选择左半部分为S1，右半部分为S2
选择左半部分为S2，右半部分为S1

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

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

代码

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 H H行 W W W 列的表格，起初全部涂满了0 。下面要进行M次操作，每次操作有三个参数 t , a , x t,a,x t,a,x

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

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

思路

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

我们用变量 r o w row row记录已经染了几行，用 c o l col col表示已经染了几列。

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

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

代码

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 ) f(X,k) f(X,k)表示将X这个字符串整体重复k次。 g ( X , k ) g(X,k) g(X,k)表示将X的每一个字符重复k次后拼接起来。

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

现在给你一个整数n和两个字符串 S , T S,T S,T ,求出k最大是多少，能使得 g ( T , k ) g(T,k) g(T,k)是 f ( S , n ) f(S,n) 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是已知的。

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

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

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

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

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

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

代码

#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;
}

标签：AtCoder,cnt,int,346,cost,sm,ans,input,ABCDEF
From： https://blog.csdn.net/qq_66608435/article/details/137021314