AtcoderContest315 | Crystal’s Blog

type

Post

status

Published

date

Aug 20, 2023

slug

AtcoderContest315

summary

比赛信息

https://atcoder.jp/contests/abc315

比赛中ac了A、B、C、E。补了D题

赛题解析

A题

c++代码


#include<bits/stdc++.h>
using namespace std;
int main(){
    string s,s1="";
    cin>>s;
    for(int i=0;i<s.length();i++){
        char x=s[i];
        if(x!='a'&&x!='e'&&x!='i'&&x!='o'&&x!='u'){
            s1+=x;
        }
    }
    cout<<s1<<endl;

    return 0;
}

B题

c++代码


#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N];
int main(){
    int m,sum=0;
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        sum+=a[i];
    }
    sum=(sum+1)/2;
    for(int i=1;i<=m;i++){
        if(sum>a[i]){
            sum-=a[i];
        }else{
            cout<<i<<" "<<sum<<endl;
            break;
        }
    }
    return 0;
}

C题

按照deliciousness结构体排序后可以发现，如果最大者和次大者的favour不同，那么答案就是二者deliciousness之和，否则，答案就要在以下两种情况里取较大值：

最大者deliciousness+次大者deliciousness/2

最大者deliciousness+从大往小数第一个favour与最大者不同的deliciousness

c++代码


#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef long long ll;
const int N=3e5+10;
vector<PII>v;
ll max(ll a,ll b){
    return  a>b?a:b;    
}
int main(){
    ll n;
    cin>>n;
    for(int i=0;i<n;i++){
        ll a,b;
        cin>>a>>b;
        v.push_back({b,a});
    }
    sort(v.begin(),v.end());
    ll ans;
    if(v[n-1].second!=v[n-2].second){
        ans=v[n-1].first+v[n-2].first;
    }else{
        ans=v[n-1].first+v[n-2].first/2;
        int i=n-2;
        while(i>=0&&v[i].second==v[n-1].second){
            i--;
        }
        if(i>=0){
            ans=max(ans,v[n-1].first+v[i].first);
        }
    }
    cout<<ans<<endl;
    

    return 0;
}

D题

如果用暴力枚举的话，最多有O（H+W）次procedure，每次procedure中需判断每一行每一列是否全部颜色一样需要O(H*W)。这个办法会超时。

可以看出，主要是判断行/列的颜色是否全部一样这里复杂度较大。可以记录每一行和每一列中26种颜色分别的个数。这样的话，判断每一行是否全部颜色一样时，只用O(H*26)的复杂度，每一列同理。总共复杂度约为O((H+W)*max(H,W)*26)。

c++代码


#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
using namespace std;
int h, w;
int main()
{
    cin >> h >> w;
    vector<vector<char> > colorMatrix(h, vector<char>(w));
    vector<vector<int> > hc(h, vector<int>(26)), wc(w, vector<int>(26));
    rep(i, h)
    {
        rep(j, w)
        {
            char x;
            cin >> x;
            colorMatrix[i][j] = x;
            hc[i][x - 'a']++;
            wc[j][x - 'a']++;
        }
    }
    int cnth = h, cntw = w;        // 当前还没有removed的行和列的个数
    vector<bool> hrmv(h), wrmv(w); // 标记行/列有没有被removed
    // 最多有h+w个行/列
    rep(_, h + w)
    {
        vector<pair<int,int> > hh, ww;
        // 循环判断行里面有没有需要marked的行
        rep(i, h)
        {
            if (hrmv[i] == true)
            {
                continue;
            }
            rep(j, 26)
            {
                // 当前行全部颜色一样
                if (hc[i][j] == cntw&&cntw>=2)
                {
                    hh.push_back({i,j});
                    hrmv[i] = true;
                }
            }
        }
        // 循环判断列里面有没有需要marked的列
        rep(i, w)
        {
            if (wrmv[i] == true)
            {
                continue;
            }
            rep(j, 26)
            {
                if (wc[i][j] == cnth&&cnth>=2)
                {
                    ww.push_back({i,j});
                    wrmv[i] = true;
                }
            }
        }
        if(hh.size()==0&&ww.size()==0){
            break;
        }
        cnth -= hh.size();
        cntw -= ww.size();
        // cout<<cnth<<" "<<cntw<<endl;
        rep(_,hh.size()){
            int i=hh[_].first;//第i行
            int k=hh[_].second;//第k中颜色
            rep(j,w){
                if(colorMatrix[i][j]=='a'+k){
                    wc[j][k]--;
                }
            }
        }
        rep(_,ww.size()){
            int i=ww[_].first;
            int k=ww[_].second;
            rep(j,h){
                if(colorMatrix[j][i]=='a'+k){
                    hc[j][k]--;
                }
            }
        }
    }
    int ans=cnth*cntw;
    cout<<ans<<endl;

    return 0;
}

E题

简单dfs题

c++代码


#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
map<int, bool> mp;
vector<int> v[N];
int n;
void dfs(int x)
{
    for (int i = 1; i <= v[x][0]; i++)
    {
        int y = v[x][i];
        if (mp[y] == true)
        {
            continue;
        }
        else
        {
            dfs(y);
        }
    }
    mp[x] = true;
    if (x != 1)
        cout << x << " ";
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int m;
        cin >> m;
        v[i].push_back(m);
        for (int j = 0; j < m; j++)
        {
            int x;
            cin >> x;
            v[i].push_back(x);
        }
    }
    dfs(1);
    return 0;
}