Atcoder Brown

这篇博客记录下atcoder上的棕色难度的刷题记录；

ABC190 C - Bowls and Dishes

题解

这里由于\(k\)最大只有\(16\)，因此可以用暴力，这里使用二进制进行枚举，第\(i\)位为0表示，选择将球放在\(C_i\)中，否则放在\(D_i\)中；之后判断\(m\)个\(condition\)满足了多少个，然后更新最大值；

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;

int n, m, k, dish[104];

vector<pair<int, int> > vec;

vector<pair<int, int> > p;

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        vec.push_back({a, b});
    }
    cin >> k;
    for (int i = 1; i <= k; i++) {
        int c, d;
        cin >> c >> d;
        p.push_back({c, d});
    }
    int ans = 0;
    for (int i = 0; i < 1 << k; i++) {
        memset(dish, 0, sizeof(dish));
        for (int j = 0; j < k; j++) {
            if (i >> j & 1) dish[p[j].first]++;
            else
                dish[p[j].second]++;
        }
        int cnt = 0;
        for (auto &x: vec)
            if (dish[x.first] && dish[x.second]) cnt++;
        ans = max(ans, cnt);
    }
    cout << ans << endl;
}

ABC190 D - Staircase Sequences Editorial

题解

题目即让我们求满足\(\frac{(A+B)(B-A+1)}{2}=2N\)的\((B-A+1)\)的种类数乘以\(2\)；并且一个重要的隐含条件是，\(A+B\)与\(B-A+1\)必定是一奇一偶；

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long ll;

ll n;

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n;
    n = n * 2;
    int ans = 0;
    for (int i = 1; 1ll * i * i <= n; i++) {
        if (n % i == 0 && i % 2 != n / i % 2)
            ans++;
    }
    cout << ans * 2<< endl;
}

ABC189 C

题解

题目的意思是这样的，给定一个长度为\(n\)的序列\(a\)，求\(\max((l-r+1)\times \min(a_l\dots a_r))\)

这个题目其实可以暴力，复杂度\(O(n^2)\)，也可以用单调栈；对于\(a[i]\)，分别求除左边和右边比他小的数的位置，\(l_i,r_i\)，那么以\(a[i]\)为最小值的最长区间为\(\left[l_i + 1, r_i - 1\right]\)；然后不断更新答案即可；

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

typedef long long ll;

int n, a[10005];

stack<int> s1, s2;

int l[10005], r[10004];

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        r[i] = l[i] = i;
    }
    a[0] = a[n + 1] = 0;
    for (int i = 0; i <= n + 1; i++) {
        while (!s1.empty() && a[s1.top()] >= a[i]) s1.pop();
        if (!s1.empty()) l[i] = s1.top() + 1;
        s1.push(i);
    }
    for (int i = n + 1; i >= 0; i--) {
        while (!s2.empty() && a[s2.top()] >= a[i]) s2.pop();
        if (!s2.empty()) r[i] = s2.top() - 1;
        s2.push(i);

    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, a[i] * (r[i] - l[i] + 1));
    }
    cout << ans << endl;
}

ABC189 D

题解

题意：给定\(n\)个字符串\(s_1\dots s_n\)，求序列\((x_0\dots x_n)\)的个数，该序列保证\(y_n\)结果为True；其中\(y_0=x_0\)，如果\(s_i\)为AND，那么\(y_i=y_{i-1}\&x_i\)，若\(s_i\)为OR，那么\(y_i = y_{i - 1}|x_i\)；其中\(x_i\)只能为True或False；

令\(dp[i][0/1]\)表示前\(i\)个变量的结果为True或False的情况下的序列的个数；

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

typedef long long ll;

ll n, dp[103][2];

string s[103];
int main() {
    freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> s[i];
    dp[0][0] = dp[0][1] = 1;
    for (int i = 1; i <= n; i++) {
        if(s[i] == "AND") {
            dp[i][1] = dp[i - 1][1];
            dp[i][0] = dp[i - 1][1] + dp[i - 1][0] * 2;
        }else {
            dp[i][1] = dp[i - 1][1] * 2 + dp[i - 1][0];
            dp[i][0] = dp[i - 1][0];
        }
    }
    cout << dp[n][1] << endl;
}

ABC187 D

题解

这题不能\(A_i+B_i\)贪心，因为某一步的贪心并不能保证全局的最优；实际上每次选择都会影响到后序的选择情况；

按\(2A_i+B_i\)贪心的从大到小选是可行的；

比如

//按A+B排
5
2 6 
5 2
1 2
1 2
1 2
//按2*A+B排
5
5 2
2 6
1 2
1 2
1 2

code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = int64_t;

int main(){
    ll N;
    cin >> N;
    ll X = 0;
    vector<ll> x(N);
    for(ll i = 0; i < N; i++){
        ll A, B;
        cin >> A >> B;
        X -= A;
        x[i] = A + A + B;
    }
    sort(x.begin(), x.end());
    ll ans = 0;
    while(X <= 0){
        X += x.back();
        x.pop_back();
        ans++;
    }
    cout << ans << endl;
}

ABC186 D

题解

对于长度为\(n\)的序列\(A\)，求\(\displaystyle{\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} |A_i-A_j|}\)；

即求所有任意两个元素差绝对值的和；

实际上这个结果跟\(A\)的排列顺序无关，因此如果A是升序的；

那么即求，对任意的\(i\)，\(\sum_{j=i+1}^{N}|A_i-A_j|=(\sum_{j=i+1}^{N}A_j)-(N-i)A_i\)

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

typedef long long ll;

int n, a[200005];
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    ll sum = 0, temp = 0;
    for (int i = 1; i <= n; i++) {
        sum += 1ll * (i - 1) * a[i];
        temp += 1ll * (n - i) * a[i];
    }
    cout << sum - temp << endl;
    
}

ABC185 D

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

typedef long long ll;

int n, m, a[200005];
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
        cin >> a[i];
    sort(a + 1, a + 1 + m);
    a[m + 1] = n + 1;
    int step = 0x3f3f3f3f;
    for (int i = 1; i <= m + 1; i++) {
        if (a[i] - a[i - 1] == 1) continue;
        step = min(step, a[i] - a[i - 1] - 1);
    }
    int ans = 0;
    for (int i = 1; i <= m + 1; i++) {
        ans += ceil(1.0 * (a[i] - a[i - 1] - 1) / step);
    }
    cout << ans << endl;
}

ABC183 D

题解

往一个全\(0\)序列进行区间加的操作，最后问是否有某个位置的和大于\(w\)；这里可以使用树状数组，之后查询每个位置的和即可；或者直接差分更简单；小心爆\(int\)

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

typedef long long ll;

ll n, w, bit[200005];

void insert(int x, int val) {
    for (int i = x; i < 200005; i += i & -i)
        bit[i] += val;
}

ll sum(int x) {
    ll ans = 0;
    for (int i = x; i > 0; i -= i & -i)
        ans += 1ll * bit[i];
    return ans;
}

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n >> w;
    int maxm = 0;
    for (int i = 1; i <= n; i++) {
        int s, t, p;
        cin >> s >> t >> p;
        maxm = max(maxm, t + 1);
        insert(s + 1, p);
        insert(t + 1, -p);
    }
    for (int i = 1; i <= maxm; i++)
        if(sum(i) > w) {
            cout << "No" << endl;
            return 0;
        }
    cout << "Yes" << endl;
}

ABC182 D

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

typedef long long ll;

ll n, a[200005], sum[200005];

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n;
    ll ans = 0, sum = 0, maxm = 0, pre = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
        maxm = max(maxm, sum);
        ans = max(ans, pre + maxm);
        pre += sum;
    }
    cout << ans << endl;
}

ABC181 D

题解

因为\(1000=8\times 125\)，因此\(10^3、10^4\dots\)都是\(8\)的倍数，实际上只需要判断最后\(3\)位即可；

\(1000\)以内\(8\)的倍数可以枚举出来，对于每个数，判断\(s\)中是否有字符能够组成它即可；

code

#include <bits/stdc++.h>
using namespace std;
 
bool solve(string s){
    if(s.size() == 1) return s == "8";
    if(s.size() == 2){
        if(stoi(s) % 8 == 0) return 1;
        swap(s[0], s[1]);
        return stoi(s) % 8 == 0;
    }
    vector<int> cnt(10);
    for(char x : s) cnt[x - '0']++;
    for(int i = 112; i < 1000; i += 8){
        auto c = cnt;
        for(char x : to_string(i)) c[x - '0']--;
        if(all_of(c.begin(), c.end(), [](int x){ return x >= 0; })) return 1;
    }
    return 0;
}
int main(){
    string s;
    cin >> s;
    puts(solve(s) ? "Yes" : "No");
}

ABC178 C

题解

容斥原理，直接求包含\(0\)和\(9\)的不好求，分别求出仅不包含\(0\)和仅不包含\(9\)的可能数，在求出不包含\(0\)和\(9\)的可能数；

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;

ll powmod(ll x,ll y){
    ll res=1;
    for(ll i=0;i<y;i++){
        res=res*x%mod;
    }
    return res;
}
int main(){
    ll n;
    cin>>n;
    ll ans=powmod(10,n)-powmod(9,n)-powmod(9,n)+powmod(8,n);
    ans%=mod;
    ans=(ans+mod)%mod;
    cout<<ans<<"\n";
}

ABC177 D

题解

这是一个并查集计数的问题，实际上就是需要我们求所有连通量中，最大的那个包含多少个元素；

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

typedef long long ll;

const int mod = 1e9 + 7;

int n, m;

int cnt[200005], f[200005];

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        f[i] = i, cnt[i] = 1;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        int fu = find(u), fv = find(v);
        if (fu != fv)  {
            f[fu] = f[fv] = fu;
            cnt[fu] = cnt[fu] + cnt[fv];
        }
    }
    int maxm = 0;
    for (int i = 1; i <= n; i++)
        maxm = max(maxm, cnt[find(i)]);
    cout << maxm << endl;
}

ABC175 C

code

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;

int main() {
    ll X, K, D;
    cin >> X >> K >> D;
    X = abs(X);

    ll straight = min(K, X / D);
    K -= straight;
    X -= straight * D;

    if (K % 2 == 0) {
        cout << X << endl;
    } else {
        cout << D - X << endl;
    }

    return 0;
}

ABC173 C

题解

数据非常的小，可以暴力；用二进制枚举行与列的所有的选择的情况，然后统计#的数量为\(k\)的情况；

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

typedef long long ll;

int h, k, w;

string s[10];

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> h >> w >> k;
    for (int i = 0; i < h; i++)
        cin >> s[i];
    int ans = 0;
    for (int i = 0; i < 1 << h; i++)
        for (int j = 0; j < 1 << w; j++) {
            int cnt = 0;
            for (int r = 0; r < h; r++)
                for (int c = 0; c < w; c++)
                    if (s[r][c] == '#' && (i >> r & 1) && (j >> c & 1)) cnt++;
            if (cnt == k) ans++;
        }
    cout << ans << endl;
}

ABC169 C

题解

这点需要注意，\(double\)在内存中都是近似存储的（\(\text{IEEE754}\)），比如\(0.1\)并不能精确的表示； 因此可以想象如果把这个\(double\)再乘上一个很大的数，那么这其中的误差就会被放大；这里可以将\(double\)当作一个字符串，将小数部分按位计算，或者使用std::round；

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

typedef long long ll;

ll a;
double b;

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> a >> b;
    b = round(b * 100);
    cout << a * (ll)b / 100 << endl;
}

ABC165 D

题解

定义\(f(x) = floor(\frac{Ax}{B}) − A × floor(\frac{x}{B})\)，那么有\(f(x + B) = f(x)\)；那么不妨假设\(0\leq x\leq n - 1\)，则\(f(x)=floor(\frac{Ax}{B})\)，此时由于\(f(x)\)是单调不减的，则\(x\)越大越好，那么当\(x\)取\(min(B-1,N)\)时，\(f(x)\)最大；

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

typedef long long ll;

const int maxm = 1000000000;

ll a, b, n;
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> a >> b >> n;
    cout << a * min(b - 1, n) / b;
}  

ABC159 D

题解

首先统计每个数字出现次数，那么从\(N\)个数字中取两个相同的总的方法数也就知道了；对于\(A[i]\)来说，要求从\(A[i]\)外的\(N-1\)个数字中取2个相同的，只需要拿总的方法数减去\(A[i]\)的贡献即可；

code

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
#include <stack>
#include <set>
using namespace std;
typedef long long ll;
ll C(int x) {
    return 1ll * x * (x - 1) / 2;
}
int n, a[200005], cnt[200005];
set<int> s;
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
        s.insert(a[i]);
    }
    ll sum = 0;
    for (set<int>::iterator it = s.begin();it != s.end(); it++)
        sum += C(cnt[*it]);
    for (int i = 1; i <= n; i++)
        cout << sum - (cnt[a[i]] - 1) << endl;
}  

ABC150 C

题解

给了我们长度为\(n\)的两个\(1\)到\(n\)全排列，然后需要我们求它们字典序差的绝对值；一开始的想法是，由于\(n\)最大是\(n\)，那么可以求出\(1\)到\(n\)所有全排列，然后利用\(hash\)记录字典序（\(c++\)的next_permutation是按字典序递增生成排列的），之后求差；

看了题解，不一样的是，题解是把排列看成整数，然后分别求出所有排列中，小于排列\(a、b\)对应整数的排列有多少个，然后相减；

这里又用了一下\(python\)，\(python\)的\(itertools\)提供了很多函数，其中的\(itertools.permutation\)需要一个可迭代对象作为参数（可以是字符串！）；

import itertools
 
st = "ABC"
 
per = itertools.permutations(st)
 
for val in per:
    print(*val)
# A B C
# A C B
# B A C
# B C A
# C A B
# C B A

import itertools
 
values = [1, 2, 3, 4]
 
per = itertools.permutations(values, 2)
 
for val in per:
    print(*val)
# 1 2
# 1 3
# 1 4
# 2 1
# 2 3
# 2 4
# 3 1
# 3 2
# 3 4
# 4 1
# 4 2
# 4 3

code

import itertools

def cal(l):
    ans = 0
    for x in l:
        ans = ans * 10 + x
    return ans

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cal_a = cal(a)
cal_b = cal(b)

val = itertools.permutations(range(1, n + 1))

les_a = 0
les_b = 0

for x in val:
    temp = cal(x)
    if temp < cal_a:
        les_a += 1
    if temp < cal_b:
        les_b += 1
print(abs(les_a - les_b))

ABC149 D

题解

对于给定的\(A、B、X\)，我们需要求满足\(A\times N+B\times d(N)\leq X\)的最大的N，\(d(N)\)是\(N\)有多少位，N的范围是\(1\)到\(10^9\)；

我们可以枚举\(d(N)\)，这样\(N\)的范围就确定了，再枚举\(N\)找到满足条件的\(N\)；

code

def check(n, x):
    cnt = 0
    while n:
        n //= 10
        cnt += 1

    if cnt == x:
        return 1
    else:
        return 0

a, b, x = map(int, input().split())

ans = 0
for i in range(1, 11):
    upp = (x - b * i) // a
    low = pow(10, i - 1)
    upp = min(pow(10, i) - 1, upp, int(1e9))
    for n in range(upp, low - 1, -1):
        if check(n, i):
            ans = max(ans, n)
            break

print(ans)

ABC137 D

题解

一开始是想直接对\(value\)进行贪心，但是会有这样一个问题比如两个工作2 1和1 2，\(M\)是3，如果优先选\(value\)大的，那么1 2就不能第一个，那么如果选它，就只能在第\(2\)天做，那它的报酬只能在第\(4\)天获得（大于\(M\)）；

通过对时间排序（也就是延迟获得报酬的时间尽量小），从最后一天往前，筛选出最迟完成时间在同一天的工作，从中选出价值最大的；

如果在最后一天做，只能做完成后\(1\)天就可以获得报酬的工作，倒数第二天做，只能做完成后\(1\)或\(2\)天就可以获得报酬的工作，\(\dots\)；

code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
const int maxn = 1e5 + 7;
int n, m;
struct job {
    int a, b;
    bool operator<(const job& t) const {
        return t.a > a;
    }
} jo[maxn];
int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> jo[i].a >> jo[i].b;
    sort(jo + 1, jo + 1 + n);
    multiset<int> s;
    int cnt = 1, k = 1, ans = 0;
    while (cnt <= m) {
        while (k <= n && cnt >= jo[k].a) {
            s.insert(jo[k].b);
            k++;
        }
        if (s.size()) {
            multiset<int>::iterator pos = --s.end();
            ans += *pos;
            s.erase(pos);
        }
        cnt++;
    }
    cout << ans << endl;
}

ABC143 D

题解

给定一个序列，需要求能够组成三角形的三元组的个数；考虑三条边从小到大的三条边\(a、b、c\)，如果\(a、b\)确定了，那么我们只需要\(c\lt a + b\)；那么我们枚举\(a、b\)，求满足\(b\le c\lt a + b\)的\(c\)的个数，可以用树状数组，或者直接二分也可以；

code

import bisect
n = int(input())

l = list(map(int, input().split()))
l.sort()
ans = 0
for i in range(n - 2):
    for j in range(i + 1, n - 1):
        pos = bisect.bisect_left(l, l[i] + l[j])
        ans += (pos - j - 1)
print(ans)

#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long ll;
int n, l[2003], c[2003];
void insert(int x) {
    for (int i = x; i < 2001; i += i & -i)
        c[i] += 1;
}
int sum(int x) {
    int res = 0;
    for (int i = x; i; i -= i & -i)
        res += c[i];
    return res;
}
int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> l[i];
    sort(l + 1, l + 1 + n);
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += (sum(2003) - sum(l[i]));
        for (int j = 1; j < i; j++) {
            insert(l[i] + l[j]);
        }
    }
    cout << res << endl;
}