首页 > 其他分享 >AtCoder Beginner Contest 359

AtCoder Beginner Contest 359

时间:2024-06-23 20:03:35浏览次数:23  
标签:AtCoder Beginner int 0.5 x2 leq Ai 字符串 359

AtCoder Beginner Contest 359 (3/6)

A - Count Takahashi

Problem Statement

You are given N N N strings.

The i i i-th string S i S_i Si​ ( 1 ≤ i ≤ N ) (1 \leq i \leq N) (1≤i≤N) is either Takahashi or Aoki.

How many i i i are there such that S i S_i Si​ is equal to Takahashi?

Constraints

  • 1 ≤ N ≤ 100 1 \leq N \leq 100 1≤N≤100
  • N N N is an integer.
  • Each S i S_i Si​ is Takahashi or Aoki. ( 1 ≤ i ≤ N ) (1 \leq i \leq N) (1≤i≤N)

Output

Print the count of i i i such that S i S_i Si​ is equal to Takahashi as an integer in a single line.

Solution

字符串判断

Code
#include<bits/stdc++.h>
#define int long long

using namespace std;


int n;
string s;
int cnt;

void solve()
{
    cin >> n;
    for (int i = 0; i < n; i ++ )
    {
        cin >> s;
        if (s == "Takahashi") cnt ++ ;
    }
    cout << cnt << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    solve();

    return 0;
}

B - Couples

Problem Statement

There are 2 N 2N 2N people standing in a row, and the person at the i i i-th position from the left is wearing clothes of color A i A_i Ai​. Here, the clothes have N N N colors from 1 1 1 to N N N, and exactly two people are wearing clothes of each color.

Find how many of the integers i = 1 , 2 , … , N i=1,2,\ldots,N i=1,2,…,N satisfy the following condition:

  • There is exactly one person between the two people wearing clothes of color i i i.

Constraints

  • 2 ≤ N ≤ 100 2 \leq N \leq 100 2≤N≤100
  • 1 ≤ A i ≤ N 1 \leq A_i \leq N 1≤Ai​≤N
  • Each integer from 1 1 1 through N N N appears exactly twice in A A A.
  • All input values are integers.

Sample Input 1

3
1 2 1 3 2 3

Sample Output 1

2

There are two values of i i i that satisfy the condition: 1 1 1 and 3 3 3.

In fact, the people wearing clothes of color 1 1 1 are at the 1st and 3rd positions from the left, with exactly one person in between.

Solution

题目保证了一种衣服最多有两个人穿,那么其实如果要满足题目的要求,和当前第i个人穿同样衣服的人只会在第i+2个位置出现才会满足要求,从小到大枚举a[i]是否等于a[i + 2]即可

Code
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 210;

int n;
int a[N];
int cnt;

void solve()
{
    cin >> n;
    for (int i = 0; i < 2 * n; i ++ )
    {
        cin >> a[i];
    }

    for (int i = 0; i < 2 * n - 2; i ++ )
    {
        if (a[i] == a[i + 2]) cnt ++ ;
    }
    cout << cnt << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    solve();

    return 0;
}

C - Tile Distance 2

Problem Statement

The coordinate plane is covered with 2 × 1 2\times1 2×1 tiles. The tiles are laid out according to the following rules:

  • For an integer pair ( i , j ) (i,j) (i,j), the square A i , j = { ( x , y ) ∣ i ≤ x ≤ i + 1 ∧ j ≤ y ≤ j + 1 } A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace Ai,j​={(x,y)∣i≤x≤i+1∧j≤y≤j+1} is contained in one tile.
  • When i + j i+j i+j is even, A i , j A _ {i,j} Ai,j​ and A i + 1 , j A _ {i + 1,j} Ai+1,j​ are contained in the same tile.

Tiles include their boundaries, and no two different tiles share a positive area.

Near the origin, the tiles are laid out as follows:

Takahashi starts at the point ( S x + 0.5 , S y + 0.5 ) (S _ x+0.5,S _ y+0.5) (Sx​+0.5,Sy​+0.5) on the coordinate plane.

He can repeat the following move as many times as he likes:

  • Choose a direction (up, down, left, or right) and a positive integer n n n. Move n n n units in that direction.

Each time he enters a tile, he pays a toll of 1 1 1.

Find the minimum toll he must pay to reach the point ( T x + 0.5 , T y + 0.5 ) (T _ x+0.5,T _ y+0.5) (Tx​+0.5,Ty​+0.5)​.

问题陈述

坐标平面上铺有 2 × 1 2\times1 2×1 块瓷砖。瓷砖的摆放规则如下:

  • 对于整数对 ( i , j ) (i,j) (i,j) ,正方形 A i , j = { ( x , y ) ∣ i ≤ x ≤ i + 1 ∧ j ≤ y ≤ j + 1 } A _ {i,j}=\lbrace(x,y)\mid i\leq x\leq i+1\wedge j\leq y\leq j+1\rbrace Ai,j​={(x,y)∣i≤x≤i+1∧j≤y≤j+1} 包含在一个图块中。
  • 当 i + j i+j i+j 为偶数时, A i , j A _ {i,j} Ai,j​ 和 A i + 1 , j A _ {i + 1,j} Ai+1,j​ 包含在同一块方砖中。

瓦块包括其边界,没有两个不同的瓦块共享一个正面积。

在原点附近,瓦片的布局如下:

高桥从坐标平面上的点 ( S x + 0.5 , S y + 0.5 ) (S _ x+0.5,S _ y+0.5) (Sx​+0.5,Sy​+0.5) 开始。

他可以任意重复下面的移动:

  • 选择一个方向(上、下、左或右)和一个正整数 n n n 。向该方向移动 n n n 个单位。

每次他进入一块牌时,都要支付 1 1 1 的过路费。

求他到达 ( T x + 0.5 , T y + 0.5 ) (T _ x+0.5,T _ y+0.5) (Tx​+0.5,Ty​+0.5) 点所需支付的最小通行费。

Constraints

  • 0 ≤ S x ≤ 2 × 1 0 16 0\leq S _ x\leq2\times10 ^ {16} 0≤Sx​≤2×1016
  • 0 ≤ S y ≤ 2 × 1 0 16 0\leq S _ y\leq2\times10 ^ {16} 0≤Sy​≤2×1016
  • 0 ≤ T x ≤ 2 × 1 0 16 0\leq T _ x\leq2\times10 ^ {16} 0≤Tx​≤2×1016
  • 0 ≤ T y ≤ 2 × 1 0 16 0\leq T _ y\leq2\times10 ^ {16} 0≤Ty​≤2×1016
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

S x S _ x Sx​ S y S _ y Sy​
T x T _ x Tx​ T y T _ y Ty​

Output

Print the minimum toll Takahashi must pay.

Sample Output 1

5

For example, Takahashi can pay a toll of 5 5 5 by moving as follows:

  • Move left by 1 1 1. Pay a toll of 0 0 0.
  • Move up by 1 1 1. Pay a toll of 1 1 1.
  • Move left by 1 1 1. Pay a toll of 0 0 0.
  • Move up by 3 3 3. Pay a toll of 3 3 3.
  • Move left by 1 1 1. Pay a toll of 0 0 0.
  • Move up by 1 1 1. Pay a toll of 1 1 1.

It is impossible to reduce the toll to 4 4 4 or less, so print 5.

Solution

太坑了,数据点里的9/40一直通不过,差点给我整急眼了,其实还是推导不够缜密,如果以后遇到这种大部分数据点都能过,证明思路是没有问题的,问题一定发生在细节上,试着注意边界情况特判、举一些刁钻的样例带入等等

观察题目,我们只有在块间通行时需要付费,块内通行无需付费,这时候我们就可以发现一个关键点,先让起点和终点在自己的块内都移到距离彼此最近的地方,这样是无需通行费的,如图,位于这两个位置的起点和终点都需要移动。

那怎么判断起点和终点是否需要移动? 分为以下几种情况

  • 起点

    • 起点在终点的左边,且位于块内的0号位置
    • 起点在终点的右边,且位于块内的1号位置
  • 终点

    • 起点在终点的左边,且位于块内的1号位置
    • 起点在终点的右边,且位于块内的0号位置

实质就是把他俩挨近些,由题知,对一个块,其0号位置坐标 x i + y i x_i+y_i xi​+yi​是偶数,其1号位置坐标 x i + y i x_i+y_i xi​+yi​是奇数,这样我们就可以先将起点和终点坐标预处理了

当预处理完成后,要移动的方向必然不会再经过当前块内所以先+1移动到下一个块,且横向移动给一次通行费可以移动两个单位,则横向移动所需通行费(llabs(x2 - x1) + 1) / 2

竖向移动一个单位必然消耗1个通行费

我们发现横向移动一个单位时也可以顺便上升一个单位,同样只消耗一个通行费,这样横向移动之后到终点的正下方之后,我们就可以直接向上移动到达终点。

分情况讨论

  • 如果 l l a b s ( x 2 − x 1 ) < = l l a b s ( y 2 − y y 1 ) llabs(x2 - x1) <= llabs(y2- yy1) llabs(x2−x1)<=llabs(y2−yy1),也就是高差更大,则在竖向移动的时候顺便覆盖所需的横向移动,最终通行费就是向上移动所需的通行费 l l a b s ( y 2 − y y 1 ) llabs(y2- yy1) llabs(y2−yy1)​
  • 如果 l l a b s ( x 2 − x 1 ) > l l a b s ( y 2 − y y 1 ) llabs(x2 - x1) > llabs(y2- yy1) llabs(x2−x1)>llabs(y2−yy1),也就是高差更小,到达指定高度之后我们还需要继续横向移动,所需通行费$llabs(y2- yy1) + (llabs(x2 - x1) - llabs(y2 - yy1) + 1) / 2 $,也就是先上到终点的高度,剩余的距离通过横向移动来补充。

tips:用了万能头全局变量不能设y1,debug半天

Code
#include<bits/stdc++.h>
#define int long long

using namespace std;

int x1, yy1, x2, y2;

void solve()
{
    cin >> x1 >> yy1 >> x2 >> y2;

    //预处理坐标
    if ((x2 - x1 > 0) && (llabs(x1 + yy1) % 2 == 0))
    {
        x1 ++ ;
    }
    else if ((x2 - x1 < 0) && (llabs(x1 + yy1) % 2 != 0))
    {
        x1 -- ;
    }

    if (((x2 - x1) > 0) && (llabs(x2 + y2) % 2 != 0))
    {
        x2 -- ;
    }
    else if (((x2 - x1) < 0) && (llabs(x2 + y2) % 2 == 0))
    {
        x2 ++ ;
    }

    //处理只用横向移动的情况
    if (yy1 == y2)
    {
        cout << (llabs(x2 - x1) + 1) / 2 << endl;
        return;
    }

    
    int res = llabs(x2 - x1);
    int high = llabs(y2- yy1);
    if (res - high > 0)
        cout << (res - high + 1) / 2 + high << endl;
    else cout << high << endl;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    solve();

    return 0;
}

D - Avoid K Palindrome

Problem Statement

You are given a string S S S of length N N N consisting of characters A, B, and ?.

You are also given a positive integer K K K. A string T T T consisting of A and B is considered a good string if it satisfies the following condition:

  • No contiguous substring of length K K K in T T T is a palindrome.

Let q q q be the number of ? characters in S S S. There are 2 q 2^q 2q strings that can be obtained by replacing each ? in S S S with either A or B. Find how many of these strings are good strings.

The count can be very large, so find it modulo 998244353 998244353 998244353.

问题陈述

给你一个长度为 N N N 的字符串 S S S ,由字符 AB?组成。

同时给你一个正整数 K K K 。如果满足以下条件,由AB组成的字符串 T T T 将被视为好字符串

  • 在 T T T 中,没有长度为 K K K 的连续子串是回文字符串。

设 q q q 是 S S S 中的 ?,用 AB 替换 S S S 中的每个?,可以得到 2 q 2^q 2q 个字符串。请找出其中有多少个字符串是好字符串。

这个数目可能非常大,因此求出它的模数 998244353 998244353 998244353 。

Constraints

  • 2 ≤ K ≤ N ≤ 1000 2 \leq K \leq N \leq 1000 2≤K≤N≤1000
  • K ≤ 10 K \leq 10 K≤10
  • S S S is a string consisting of A, B, and ?.
  • The length of S S S is N N N.
  • N N N and K K K are integers.

Input

The input is given from Standard Input in the following format:

N N N K K K
S S S

Output

Print the answer.

Sample Input 1

7 4
AB?A?BA

Sample Output 1

1

The given string has two ?s. There are four strings obtained by replacing each ? with A or B:

  • ABAAABA
  • ABAABBA
  • ABBAABA
  • ABBABBA

Among these, the last three contain the contiguous substring ABBA of length 4, which is a palindrome, and thus are not good strings.

Therefore, you should print 1.

Solution

题意是将长度为N的字符串中的替换为AB,更改后的字符串T满足T中没有长度为 K 的连续子串是回文字符串,则视为一种合法情况,由题知,字符串中?的个数cnt决定了N可以变换出多少种T字符串,所以合法情况最多有 2 c n t 2^{cnt} 2cnt种,假设A为0,B为1,我们可以遍历每一位?,更改他为0或1,很容易想到状压dp的做法,将其改为二进制字符串的状态

d p [ i ] [ j ] dp[i][j] dp[i][j]​表示前i位字符中满足[i - k + 1, i]这个长度为k的二进制字符串j是合法字符串(非回文)的方案数

当前这个 [ i − k + 1 , i ] [i - k + 1, i] [i−k+1,i]长度为k的字符串,是从长度为k的区间 [ i − k + 1 − 1 , i − 1 ] [i - k + 1 - 1, i - 1] [i−k+1−1,i−1]演变而来的(也就是以第i-1位为终点),利用了他的 [ i − k + 1 , i − 1 ] [i-k+1, i-1] [i−k+1,i−1]位,我们只更改第i位的状态,若第i位是?,我们就选A或B填入,若为合法方案数就记录,而且在第i-1位的基础上增加能保证前i-1位是满足所有大小为k的子字符串是非回文的。

状态转移方程: d p [ i ] [ 前 i − 1 位构成的长度为 k − 1 的字符串加上第 i 位的字符状态 ] = d p [ i ] [ j ] + d p [ i − 1 ] [ 前 i − 1 位构成的长度为 k 的字符串 ] dp[i][前i-1位构成的长度为k-1的字符串加上第i位的字符状态] = dp[i][j] + dp[i - 1][前i-1位构成的长度为k的字符串] dp[i][前i−1位构成的长度为k−1的字符串加上第i位的字符状态]=dp[i][j]+dp[i−1][前i−1位构成的长度为k的字符串]

Code
#include<bits/stdc++.h>
#define int long long

using namespace std;

const int mod = 998244353;

int n, k;
char s[1010];
int dp[1010][1 << 11]; //k最大为10,则字符串状态最大为10位

//检查当前区间[i-k+1,i]长度为k的字符串是否为回文字符串
bool check(int x)
{
    //双指针头和尾比较
    for (int i = 0, j = k - 1; i < j; i ++ , j -- )
    {
        if (((x >> i) & 1) != ((x >> j) & 1))
            return true; //找到不同就为非回文字符串
    }
    return false;
}

void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> s[i];
    // cout << check(128) << endl; 检查check()
    // cout << check(129) << endl;
    //for (int i = 1; i <= n; i ++ ) cout << s[i];
    //cout << n << k;
    dp[0][0] = 1;
    for (int i = 1; i <= n; i ++ ) //枚举位置i,从第1位枚举到第n位可以保证枚举第i位时前面的字符串没有长度为k的回文子串
    {
        for (int st = 0; st < (1 << k); st ++ ) //枚举字符串状态
        {
            for (int j = 0; j < 2; j ++ ) //枚举当前位置i放A还是B
            {
                if (s[i] != '?' && s[i] != 'A' + j) //这个限制条件是保证当前位置如果 不是? 或者 当前位置与j的值不相匹配就跳过 因为字符串上的A和B不可更改 我们设定A对应j=0 B对应1
                    continue;
                //若当前枚举到的字符串满足实际字符串情况(A的位置放A B的位置放B ?位置进行枚举)
                int now = (st >> 1) | ((1 << (k - 1)) * j); //当前区间[i - k + 1, i]的k位字符串由前原字符串的前k-1位和当前位的状态组合而成,前k-1位就是st >> 1,当前位也就是字符串的第k位就是将1右移到第k位乘上当前位的状态j,取|将其组合
                if (i < k || check(now)) //当不足k位时让其预处理,达到k位后当前字符串需要满足题目要求取check()一下
                {
                    dp[i][now] = (dp[i][now] + dp[i - 1][st]) % mod;
                }
            }
        }
    }
    int ans = 0;
    //cout << dp[1][0];

    //将前n位字符中所有状态中的合法方案数i加起来
    for (int i = 0; i < (1 << k); i ++ ) ans = (ans + dp[n][i]) % mod;
    cout << ans << endl;
    return;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    solve();

    return 0;
}

E - Water Tank

Story

There is a long water tank with boards of different heights placed at equal intervals. Takahashi wants to know the time at which water reaches each section separated by the boards when water is poured from one end of the tank.

Problem Statement

You are given a sequence of positive integers of length N N N: H = ( H 1 , H 2 , … , H N ) H=(H _ 1,H _ 2,\dotsc,H _ N) H=(H1​,H2​,…,HN​).

There is a sequence of non-negative integers of length N + 1 N+1 N+1: A = ( A 0 , A 1 , … , A N ) A=(A _ 0,A _ 1,\dotsc,A _ N) A=(A0​,A1​,…,AN​). Initially, A 0 = A 1 = ⋯ = A N = 0 A _ 0=A _ 1=\dotsb=A _ N=0 A0​=A1​=⋯=AN​=0.

Perform the following operations repeatedly on A A A:

  1. Increase the value of A 0 A _ 0 A0​ by 1 1 1.
  2. For i = 1 , 2 , … , N i=1,2,\ldots,N i=1,2,…,N in this order, perform the following operation:
    • If A i − 1 > A i A _ {i-1}\gt A _ i Ai−1​>Ai​ and A i − 1 > H i A _ {i-1}\gt H _ i Ai−1​>Hi​, decrease the value of A i − 1 A _ {i-1} Ai−1​ by 1 and increase the value of A i A _ i Ai​ by 1 1 1.

For each i = 1 , 2 , … , N i=1,2,\ldots,N i=1,2,…,N, find the number of operations before A i > 0 A _ i \gt0 Ai​>0 holds for the first time.

问题陈述

给你一个长度为 N N N 的正整数序列: H = ( H 1 , H 2 , … , H N ) H=(H _ 1,H _ 2,\dotsc,H _ N) H=(H1​,H2​,…,HN​) .

有一个长度为 N + 1 N+1 N+1 的非负整数序列: A = ( A 0 , A 1 , … , A N ) A=(A _ 0,A _ 1,\dotsc,A _ N) A=(A0​,A1​,…,AN​) .最初有 A 0 = A 1 = ⋯ = A N = 0 A _ 0=A _ 1=\dotsb=A _ N=0 A0​=A1​=⋯=AN​=0 .

对 A A A 重复进行以下运算:

  1. 将 A 0 A _ 0 A0​ 的值增加 1 1 1 。
  2. 依次对 i = 1 , 2 , … , N i=1,2,\ldots,N i=1,2,…,N 进行以下操作:
    • 如果 A i − 1 > A i A _ {i-1}\gt A _ i Ai−1​>Ai​ 和 A i − 1 > H i A _ {i-1}\gt H _ i Ai−1​>Hi​ ,则将 A i − 1 A _ {i-1} Ai−1​ 的值减少 1,并将 A i A _ i Ai​ 的值增加 1 1 1 。

求每个 i = 1 , 2 , … , N i=1,2,\ldots,N i=1,2,…,N 在 A i > 0 A _ i\gt0 Ai​>0 首次成立之前的运算次数。

Constraints

  • 1 ≤ N ≤ 2 × 1 0 5 1\leq N\leq2\times10 ^ 5 1≤N≤2×105
  • 1 ≤ H i ≤ 1 0 9   ( 1 ≤ i ≤ N ) 1\leq H _ i\leq10 ^ 9\ (1\leq i\leq N) 1≤Hi​≤109 (1≤i≤N)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N N N
H 1 H _ 1 H1​ H 2 H _ 2 H2​ … \dotsc … H N H _ N HN​

Output

Print the answers for i = 1 , 2 , … , N i=1,2,\ldots,N i=1,2,…,N in a single line, separated by spaces.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

4 5 13 14 26

The first five operations go as follows.

Here, each row corresponds to one operation, with the leftmost column representing step 1 and the others representing step 2.

From this diagram, A 1 > 0 A _ 1\gt0 A1​>0 holds for the first time after the 4th operation, and A 2 > 0 A _ 2\gt0 A2​>0 holds for the first time after the 5th operation.

Similarly, the answers for A 3 , A 4 , A 5 A _ 3, A _ 4, A _ 5 A3​,A4​,A5​ are 13 , 14 , 26 13, 14, 26 13,14,26, respectively.

Therefore, you should print 4 5 13 14 26.

Solution

Code

标签:AtCoder,Beginner,int,0.5,x2,leq,Ai,字符串,359
From: https://blog.csdn.net/m0_75081311/article/details/139898088

相关文章

  • AtCoder Beginner Contest 359
    A-CountTakahashi(abc359A)题目大意给定\(n\)个字符串,问有多少个字符串是Takahashi解题思路注意判断比较即可。神奇的代码#include<bits/stdc++.h>usingnamespacestd;usingLL=longlong;intmain(void){ios::sync_with_stdio(false);cin.tie(0);......
  • UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359)
    A-CountTakahashi(abc359A)解题思路遍历判断即可神奇的代码#include<iostream>#include<algorithm>#include<vector>#include<queue>#include<map>#include<set>#include<cstring>usingnamespacestd;#defineendl'\n......
  • ABC359 G - Sum of Tree Distance
    题目链接题目大意给出一棵树,树上每个节点都有一种颜色,求所有颜色相同的节点两两之间距离的总和。 题解想来写题解主要是看了一下官方解法都写的需要“重心分解”,应该是对应中文语境下的树的点分治。实际上点分治写起来很费事,可以用启发式合并替代。具体来说,dfs时每个节点......
  • UNIQUE VISION Programming Contest 2024 Summer (AtCoder Beginner Contest 359) 题
    点我看题A-CountTakahashi没啥好说的点击查看代码#include<bits/stdc++.h>#definerep(i,n)for(inti=0;i<n;++i)#definerepn(i,n)for(inti=1;i<=n;++i)#defineLLlonglong#definefifirst#definesesecond#definepbpush_back#definemprmake_pair......
  • abc359_G Sum of Tree Distance 题解
    题目链接:Atcoder或者洛谷先考虑暴力,显然是枚举整棵树的路径,这个枚举复杂度显示是\(O(n^2)\),还不考虑计算\(f(i,j)\),考虑使用点分治优化枚举复杂度:\(O(n\log{n})\)。接下来考虑如何计算每条路径的\(f(i,j)\),注意到\(f(i,j)\):当且仅当\(a[i]=a[j]\)时,答案加上\(dis(i,j......
  • AtCoder Beginner Contest 359 解题报告
    AtCoderBeginnerContest359吐槽:A-F还算正常,G题你tm给我放了个出过的板子(ABC340G)是几个意思啊???ASimulate.#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#defineendl'\n'#definePBemplace_back#definePPBpop_back#defineMPmake_pai......
  • AtCoder ABC 358
    比赛链接A-WelcometoAtCoderLandAC_Code#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongsignedmain(){strings,t;cin>>s>>t;if(s=="AtCoder"&&t=="Land")co......
  • AtCoder Beginner Contest 357-F
    Problem同步于博客ProblemYouaregivensequencesoflength\(N\),\(A=(A_1,A_2,\ldots,A_N)\)and\(B=(B_1,B_2,\ldots,B_N)\).Youarealsogiven\(Q\)queriestoprocessinorder.Therearethreetypesofqueries:1lrx:Add\(x\)toeachof......
  • AtCoder Beginner Contest 358
    A-WelcometoAtCoderLandvoidsolve(){strings,t;cin>>s>>t;if(s=="AtCoder"&&t=="Land"){cout<<"Yes\n";return;}cout<<"No\n&qu......
  • [atcoder 358] 【动态规划】
    dp[i][j]表示前i个和为j的个数。那么就有递推式dp[i][j]+=dp[i][j-x]*c(j,j-x);其中x满足从0到c[i],并且x满足<=j组合数递推公式c(n,k)=c(n,k-1)+c(n,k);importjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;impor......