abc321

오랜만에 망했다.

F 풀이 맞는데 왜 답이 안나오는지 아직도 모르겠다

망했으므로 대충 쓰겠다.

 

A

단순 구현

using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
int main(){
    fast;
    ll n,m,k;
    string s,t;
    cin>>s;
    vector<ll> v,e;
    for(int i = 1 ; i < s.size() ; i++){
        if(s[i-1]-'0' <= s[i]-'0')return cout<<"No",0;
    }
    cout<<"Yes";
}

 

B

0부터 100까지 다 넣어보면 된다

using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
int main(){
    fast;
    ll n,m,k;
    cin>>n>>k;
    vector<ll> v(n-1);
    for(auto &i : v)cin>>i;
    ll ans=1e18;
    for(int i = 0 ; i <= 100 ; i++){
        auto e = v;
        e.push_back(i);
        sort(all(e));
        ll s = accumulate(all(e),0LL)-e[0]-e.back();
        if(s>=k)return cout<<i,0;
    }
    cout<<-1;
}

 

C

백트래킹으로 다 만들면 된다

using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
vector<ll> v;
bool chk[11]={};
void make(ll x){
    if(x==10){
        string s;
        for(int i = 9 ; i >= 0 ; i--){
            if(chk[i])s += char(i+'0');
        }
        if(s=="")return;
        v.push_back(stoll(s));
    }
    else{
        chk[x]=1;
        make(x+1);
        chk[x]=0;
        make(x+1);
    }
}
int main(){
    fast;
    make(0);
    sort(all(v));
    ll k; cin>>k; cout<<v[k];
}

 

D

p 이하인것들만 이분탐색 + 누적합으로 따로 처리하면 된다

using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 1000000007
typedef long long ll;
ll n,m,p;
ll psum[202020];
int main(){
    fast;
    cin>>n>>m>>p;
    vector<ll> v(n), e(m);
    for(auto &i : v)cin>>i;
    for(auto &i : e)cin>>i;
    v.push_back(1e18); e.push_back(1e18);
    sort(all(v)); sort(all(e));
    for(int i = 0 ; i < m ; i++){
        if(!i)psum[i]=e[i];
        else psum[i] = psum[i-1]+e[i];
    }
    ll ans=0;
    for(int i = 0 ; i < n ; i++){
        ll idx = upper_bound(all(e), p-v[i])-e.begin();
        if(idx>0)ans += psum[idx-1]+idx*v[i];
        ans += (m-idx)*p;
    }
    cout<<ans;
}

 

upsolving

E

풀이는 뻔하다. 구현이 귀찮아보이고 무엇보다 F가 안풀려서 구현할 생각도 안했다

 

F

dp[i]에 합이 i인 경우의 수가 다 들어있다고 하자. 배열의 결과만 보면 추가되는 순서에 상관이 없다.

따라서 x를 지울 때 x가 최근에 있었다고 생각하고 지워줘도 된다.

이거 아닌가... 왜 예제도 안나오지

수정) 이유를 찾았다. 반복문 순서 고려 안하면 값이 꼬여서 이상하게 갱신된다......................

using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 998244353
typedef long long ll;
ll dp[5050]={1};
ll q,k;
int main(){
    fast;
    cin>>q>>k;
    while(q--){
        char c; cin>>c;
        ll x; cin>>x;
        if(c=='+'){
            for(int i = k ; i >= x ; i--){
                dp[i] = (dp[i] + dp[i-x])%MOD;
            }
        }
        else{
            for(int i = x ; i <= k ; i++){
                dp[i] = (dp[i] - dp[i-x] + MOD)%MOD;
            }
        }
        cout<<dp[k]<<"\n";
    }
}

 

 

소감

본인이 망했으니 망셋이다.