AtCoder Beginner Contest 173 题解

目录
AtCoder Beginner Contest 173 题解
A - Payment
B - Judge Status Summary
C - H and V
D - Chat in a Circle
E - Multiplication 4
F - Intervals on Tree

A - Payment

首先我们可以把所有不用找零的部分都付掉，这样就只剩下了\(A \mod 1000\)这样一个“\(A\)除以\(1000\)的余数部分”。

然后我们再来用\(1000\)减去它，就是要找的零钱，但是假如刚好余数为\(0\)就会出锅，所以再要特判一下，程序这里直接写进公式里了：

#include<bits/stdc++.h>

using namespace std;

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    int n;

    cin>>n;

    cout<<(1000-n%1000)%1000<<endl;

    return 0;

}

B - Judge Status Summary

这波啊，这波是小学数数（雾）。这就是普通的计数啊，我们可以使用C++的STL中的一位：map。

这里讲了map的使用方法：OI-wiki

然后你建立一个字符串对应到整数的map，然后每次读入一个字符串都把对应值加一就行。然后输出每个状态对应的值就好。

#include<bits/stdc++.h>

using namespace std;

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    map<string,int> mp;

    string s;

    int n;

    cin>>n;

    while(n--){

        cin>>s;

        mp[s]++;

    }

    cout<<"AC x "<<mp["AC"]<<'\n';

    cout<<"WA x "<<mp["WA"]<<'\n';

    cout<<"TLE x "<<mp["TLE"]<<'\n';

    cout<<"RE x "<<mp["RE"]<<'\n';

    return 0;

}

C - H and V

很显然数据这么小，我们可以枚举哪些列需要涂色，然后再计算没有涂过的黑色块就好了。

这里你需要学习状态压缩来更好地枚举涂色的列的集合，你可以把集合压缩成一个整数，当中对应的位为\(1\)表示这一行/列涂色了，否则没有涂。这里来学习位运算和状态压缩（状压DP顺便也看看吧，会有用的）。

我这里设置了第\(1\)到\(H\)的二进制位表示对应的行的状态，同理第\(H+1\)到\(W\)位表示对应的列的状态。

#include<bits/stdc++.h>

using namespace std;

int h,w,k;

char g[10][10];

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    cin>>h>>w>>k;

    for(int i=0;i<h;i++){

        cin>>g[i];

    }

    int ans=0;

    for(int s=0;s<1<<h+w;s++){//先执行+再执行<<，A<<B表示A*2^B

        int c=0;

        for(int i=0;i<h;i++){

            for(int j=0;j<w;j++){

                c+=!(s>>i&1)&&!(s>>h>>j&1)&&g[i][j]=='#';//先执行>>再执行&，A>>B&1表示A的第B位，值是1或0

            }

        }

        ans+=c==k;

    }

    cout<<ans<<endl;

    return 0;

}

D - Chat in a Circle

首先我们先把\(A\)从大到小排列一下，并从前往后地让对应位置的人进圈。感性地想，让权值高的人先进，就可以影响旁边人的心情更好，可以证明是对的，但我不会qaq。

然后容易看出，除了第一个人只能影响第二个之外，其余的人都有两个可以影响的空位（废话，左右两边各一个，写题解的人脑子有病吧）。然后就好了可以写程序了（

#include<bits/stdc++.h>

using namespace std;

int n;

int a[200005];

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    cin>>n;

    for(int i=0;i<n;i++)cin>>a[i];

    sort(a,a+n,[](const int &a,const int &b){

        return a>b;

    });

    int tot=n-1;

    long long ans=0;

    for(int i=0;i<n;i++){

        if(tot){

            ans+=a[i];

            tot--;

        }

        if(tot&&i){

            ans+=a[i];

            tot--;

        }

    }

    cout<<ans<<endl;

    return 0;

}

E - Multiplication 4

我们先判断一下能不能弄出一个正的乘积啊，然后退而求其次看能不能弄出\(0\)来，最后再尽量弄一个绝对值小的负数乘积啊。

假如负数两两一对，加上一部分正数能够凑到\(K\)个，就可以弄出正的乘积了。

先看正的乘积，我们把正数负数绝对值从大到小排序，然后两两一对乘起来。然后尽量取大的一对乘起来，最后假如\(K\)是奇数就添上一个单独的正数就好了啊。

UPD: 这边正的乘积需要先考虑\(K\)是奇数的情况并先添上一个正数，否则会被叉。

乘积为\(0\)的话坠简单，输出零就好了。

负数的乘积其实也很简单，由于你已经通过先前的判断证明了不能有正数或者零的乘积，那么只要贪心地取绝对值最小的那些正/负数乘起来就好了。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod=1e9+7;

ll n,k,zero;

ll a[200005];

vector<ll> pos,neg;

void find_pos(){

    sort(pos.begin(),pos.end(),[](const ll &a,const ll &b){

        return a>b;

    });

    sort(neg.begin(),neg.end(),[](const ll &a,const ll &b){

        return a<b;

    });

    ll res=k&1?pos.front():1;

    ll pi=k&1,ni=0;

    while(pi+1<pos.size()&&ni+1<neg.size()&&pi+ni+2<=k){

        if(pos[pi]*pos[pi+1]>neg[ni]*neg[ni+1]){

            res=res*pos[pi]%mod*pos[pi+1]%mod;

            pi+=2;

        }else{

            res=res*neg[ni]%mod*neg[ni+1]%mod;

            ni+=2;

        }

    }

    while(pi+1<pos.size()&&pi+ni+2<=k){

        res=res*pos[pi]%mod*pos[pi+1]%mod;

        pi+=2;

    }

    while(ni+1<neg.size()&&pi+ni+2<=k){

        res=res*neg[ni]%mod*neg[ni+1]%mod;

        ni+=2;

    }

    cout<<(res+mod)%mod<<endl;

}

void find_neg(){

    sort(a,a+n,[](const ll &a,const ll &b){

        return abs(a)<abs(b);

    });

    ll res=1;

    for(ll i=0;i<k;i++){

        res=res*a[i]%mod;

    }

    cout<<(res+mod)%mod<<endl;

}

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    cin>>n>>k;

    for(ll i=0;i<n;i++){

        cin>>a[i];

        if(a[i]>0)pos.emplace_back(a[i]);

        if(a[i]==0)zero++;

        if(a[i]<0)neg.emplace_back(a[i]);

    }

    if(neg.size()-(neg.size()&1)+pos.size()>=k&&(k&1)<=pos.size()){

        find_pos();

    }else if(zero){

        cout<<"0\n";

    }else find_neg();

    return 0;

}

F - Intervals on Tree

首先这是一棵树，所以每一条边都会合并左右结点从属的两个连通块为一个。那么对于一条边，对于所有包含它的\(S\)（定义同题目），它就会减少一个连通块。

那么答案一开始就设成假如每个\(S\)中的点都是独立的一个连通块，一共有多少个连通块，然后对于每一条边，答案减去包含它的\(S\)的个数即可。

#include<bits/stdc++.h>

using namespace std;

int n;

int main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    cin>>n;

    long long ans=0;

    for(int i=1;i<=n;i++){

        ans+=(long long)(n-i+1)*i;

    }

    for(int i=1;i<n;i++){

        int a,b;

        cin>>a>>b;

        if(a>b)swap(a,b);

        ans-=(long long)a*(n-b+1);

    }

    cout<<ans<<endl;

    return 0;

}

AtCoder Beginner Contest 173 题解的相关教程结束。