Atcoder beginer contest 233 (a~d) solution

AtCoder Beginner Contest 233 Answer key

A - 10yen Stamp

【 Topic link 】A - 10yen Stamp (atcoder.jp)

The question ： The current number can be added each time 10, Ask at least several times before sending a letter

• x > y： The instructions are enough to send
• x < y： Can't send , Then add 10, know x > y until , Count .

【 Code implementation 】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <string.h>
#include <unordered_set>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;



int main() 
{
    
    int x, y;
    cin >> x >> y;

    if(x >= y) cout << 0;
    else 
    {
    
        int ans = 0;
        while(x < y)
        {
    

            x += 10;
            ans ++;
        }
        cout << ans;
    }
    
    return 0;
}

B - A Revers

【 Topic link 】B - A Reverse (atcoder.jp)

The question ： The string s stay [l,r] After the string of is flipped , Output s

Knowledge point ： String emulation

【 Code implementation 】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <string.h>
#include <unordered_set>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10;
char s[N];

int main() 
{
    

    int l, r;
    scanf("%d%d", &l, &r);
    scanf("%s", s + 1);
    int len = strlen(s + 1);

    // Double pointer to flip 
    int i = l, j = r;
    while(i < j) swap(s[i ++], s[j --]);
    
    printf("%s", s + 1);
    
    return 0;
}

C - Product

【 Topic link 】C - Product (atcoder.jp)

The question ： Yes n A package , There are several balls with numbers in each bag , Let you choose a ball in each bag so that the number product is x, Finally, let you be satisfied equal to x Number of alternatives .

notes ：

• The range of data
• prune

Knowledge point ：DFS

【 Code implementation 】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <string.h>
#include <unordered_set>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 1e5 + 10;

int n, res = 0;
LL target;
vector<LL> a[N];//  Two dimensional array 

void dfs(int u, LL val)// Choose the number of backpacks   What is the weight of the backpack now 
{
    
    if(u == n)
    {
    
        if(val == target) res ++;
        return ;
    }
    for(int j = 0; j < a[u].size(); j ++)//  use vector Make a two-dimensional array , Each layer calls .size(), You can get the number of backpacks in the current layer 
    {
    
        if(a[u][j] * val > target) continue;//  prune 
        dfs(u + 1, val * a[u][j]);
    }
}

int main() 
{
    
    scanf("%d%lld", &n, &target);
    for(int i = 0; i < n; i ++)
    {
    
        int cnt;
        scanf("%d", &cnt);
        for(int j = 0; j < cnt; j ++)
        {
    
            LL value;
            scanf("%lld", &value);
            a[i].push_back(value);
        }
    }
    dfs(0, 1);
    printf("%d", res);
    return 0;
}

D - Count Interval

【 Topic link 】D - Count Interval (atcoder.jp)

The question ： Statistics s[r]-s[l - 1] == k Number of occurrences

Ideas ： If enumerating intervals , Time complexity will explode , Statistics s[r]-s[l - 1] == k Equivalent to statistics s[r]-k == s[l - 1]. And then for each r Just ask s[r]-k The number of , That is to say s[l-1] The number of .s[l-1] It's also a prefix and , Therefore, the number of prefixes and the number of prefixes are increased by the way when looping .（ Enumerate the right endpoint to find s[r]-k == s[l - 1] The number of times , It's just that we preprocessed it when counting prefixes and s[l-1] Value , Because it is also the value of prefix and ！）

Knowledge point ： The prefix and + Hashtable

【 Code implementation 】

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <vector>
#include <string.h>
#include <unordered_set>
#include <unordered_map>

#define x first
#define y second

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;

const int N = 2e5 + 10;
LL s[N];

int main() 
{
    

    LL n, k, res = 0;
    scanf("%lld%lld", &n, &k);

    unordered_map<LL, LL> hasp;
    for(int i = 1; i <= n; i ++)
    {
    
        scanf("%lld", &s[i]);
        s[i] = s[i] + s[i - 1];
        hasp[s[i - 1]] ++;
        res += hasp[s[i] - k];

    }
    printf("%lld", res);
    
    return 0;
}