본문 바로가기
카테고리 없음

abc328

satturn80 2023. 11. 11. 22:49

다시 블루. 이번엔 턱걸이도 아니다.

오늘 ABC는 F까지 웰노운 덮밥이다.

한줄요약하면

D - 이거, E - 이거 비슷하게, F - 이거

D랑 F는 실제로 복붙했다.

 

 

A

문제도 기억안난다.

더보기 
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
int main(){
    fast;
    ll n,m,k=0; string s,t; vector<ll> v,e;
    cin>>n>>m;
    v.resize(n);
    for(auto &i : v){
        cin>>i;
        if(i<=m)k+=i;
    }
    cout<<k;
}

 

 

B

B인걸 감안하면 좀 더럽다.

더보기 
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
int main(){
    fast;
    ll n; cin>>n;
    ll ans=0;
    for(int i = 1 ; i <= n ; i++){
        ll a; cin>>a;
        string s = to_string(i);
        sort(all(s));
        if(s[0]!=s.back())continue;
        for(int j = 1 ; j <= a ; j++){
            string t = to_string(j);
            char c = s[0];
            bool f=0;
            for(auto k : t){
                if(k!=c){
                    f=1;
                    break;
                }
            }
            if(!f)ans++;
        }
    }
    cout<<ans;
}

 

 

C

do you know prefix sum?

더보기 
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
ll psum[303030];
int main(){
    fast;
    ll n,m; cin>>n>>m;
    string s; cin>>s; s = '#'+s+'#';
    for(int i = 1 ; i <= n ; i++){
        psum[i] = psum[i-1] + (s[i]==s[i+1]);
    }
    while(m--){
        ll a,b; cin>>a>>b;
        cout<<psum[b-1]-psum[a-1]<<"\n";
    }
}

 


D

문자열 폭발 문제에서 T = "ABC"로 하면 된다.

더보기 
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
string s,t;
char st[1010101];
ll len;
int main(){
    fast;
    cin>>s; t = "ABC";
    for(int i = 0 ; i < s.size() ; i++){
        st[len++] = s[i];
        ll cnt=t.size();
        if(i>=cnt-1){
            ll j=len;
            bool f=0;
            while(cnt){
                if(st[--j] != t[--cnt]){
                    f=1;
                    break;
                }
            }
            if(!f)len -= t.size();
        }
    }
    
    for(int i = 0 ; i < len ; i++)cout<<st[i];
}

 

 

E

열심히 백트래킹하자.

더보기 
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
#define X first
#define Y second
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
ll n,m,k;
ll p[33];
ll find(ll x){
    if(p[x]<0)return x;
    return p[x] = find(p[x]);
}
bool merge(ll x, ll y){
    x = find(x), y = find(y);
    if(x==y)return 1;
    p[y] = x;
    return 0;
}
ll ans = 1e18;
vector<tuple<ll,ll,ll>> edge, c;
void dfs(ll x, ll y){
    if(y==n-1){
        memset(p,-1,sizeof(p));
        ll cur=0;
        for(auto [a,b,c] : c){
            if(merge(a,b))return;
            cur += c;
            cur %= k;
        }
        ans = min(ans, cur);
        return;
    }
    if(x==m)return;
    c.push_back(edge[x]);
    dfs(x+1,y+1);
    c.pop_back();
    dfs(x+1,y);
}
int main(){
    fast;
    cin>>n>>m>>k;
    edge.resize(m);
    for(auto &[a,b,c] : edge)cin>>a>>b>>c;
    dfs(0,0);
    cout<<ans;
}

 

 

F

문제가 정말 무섭게 생겼다. 핵심은 순차적으로 이루어진다는 것이고, 그래프로 해석했을 때 간선 추가만 이루어진다는 것이다. 문제를 잘 정리해보면 결국 이 문제가 된다.

더보기 
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x << ": " << x << "\n"
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
ll n,m,k;
ll p[202020];
ll dist[202020];
ll f(ll x){
    if(p[x]<0)return x;
    ll P = f(p[x]);
    dist[x] += dist[p[x]];
    return p[x] = P;
}
void merge(ll x, ll y, ll a){
    ll X = f(x), Y = f(y);
    if(X==Y)return;
    dist[Y] = dist[x]-dist[y] + a;
    p[Y]=X;
}
int main(){
    fast;
    memset(p,-1,sizeof(p));
    cin>>n>>m;
    ll ans=0;
    vector<ll> v;
    for(int i = 1 ; i <= m ; i++){
        ll a,b,c; cin>>a>>b>>c;
        if(f(a) == f(b) and dist[a]-dist[b] != c)continue;
        v.push_back(i);
        merge(a,b,-c);
    }
    for(auto i : v)cout<<i<<" ";
}

 

upsolving

G

어려워요

저작자표시 비영리 동일조건

티스토리툴바