Codeforces Round \ # 579 (Div. 3) 훈련 총화 및 문제 풀이 A - F

이 마음가짐 과 상태 가 별로 좋 지 않 았 습 니 다. Awa 가 한 발 했 습 니 다. B 는 문 제 를 늦게 읽 었 고 C 는 wa 를 2 발 잘못 읽 었 습 니 다. Ewa 는 7 발 이 었 습 니 다. D 는 인내심 을 가지 고 쓰 지 못 했 습 니 다. F 장 후에 배 웠 습 니 다.요약:

와 문제 의 심리 상 태 를 조절 해 야 한다.

A 문 제 는 당황해 서 판단 조건 에 무언 가 를 더 했다

C 문제 the num of 는 민감 해 야 하고, wa 의 다른 한 발 은 if 판단 조건 이다.

D 문 제 는 느 려 져 서 밀어 내 자마자 나 왔 는데 자꾸 서열 을 생각 하지 못 했다.

E 문제 map

문제 풀이: A. 문제 의 뜻: n 개의 수가 1 - n 또는 n - 1 순서에 따라 하나의 고 리 를 구성 하 는 지 판단 합 니 다.사고방식: 폭력 코드:

#include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f;
 
int main(){
    IO;cout.precision(10);cout<<fixed;
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int>a(n);
        forn(i,n) cin>>a[i];
        bool ok1 = 1,ok2 = 1;
        forn(i,n){
            int x = 0;
            if(i) x = a[i-1]+1;
            else x = a[n-1]+1;
            if(x>n) x-=n;
            if(x!=a[i]) ok1 = 0;
        }
        forn(i,n){
            int x = 0;
            if(i) x = a[i-1]-1;
            else x = a[n-1]-1;
            if(x<1) x+=n;
            if(x!=a[i]) ok2 = 0;
        }
        if(ok1||ok2) cout<<"YES"<<'
';
        else cout<<"NO"<<'
';
    }
    return 0;
}

B. 제목: 4 * n 개 수 는 n 개의 사각형 을 구성 할 수 있 고 사각형 면적 이 같 습 니 다.사고방식: stl 코드:

#include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f;

int main(){
    IO;cout.precision(10);cout<<fixed;
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        multiset<int>s;
        map<int,int>mp;
        bool ok = 0;
        forn(i,n<<2){
            int x;cin>>x;
            mp[x]++;s.insert(x);
        }
        int cnt = 0;
        for(auto x:mp) cnt+=x.second/2;
        if(cnt==2*n) ok = 1;
        if(!ok){
            cout<<"NO"<<'
';
            continue;
        }
        set<int>ss;
        forn(i,n){
            int x = *s.rbegin();
            int y = *s.begin();
            int xx,yy;
            xx = x,yy = y;
            s.erase(s.find(xx));
            s.erase(s.find(yy));
            s.erase(s.find(xx));
            s.erase(s.find(yy));
            //cerr<
            ss.insert(xx*yy);
        }
        if(ss.size()==1) cout<<"YES"<<'
';
        else cout<<"NO"<<'
';
    }
    return 0;
}

C. 제목: n 개 수의 공통 인 자 는 몇 가지 사고방식 이 있다. gcd 의 인 자 는 몇 가지 코드 가 있다.

#include 
using namespace std;
#define ll long long
#define forn(i,n) for(ll i=0;i
#define for1(i,n) for(ll i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const ll inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f;
 
int main(){
    IO;cout.precision(10);cout<<fixed;
    ll n;cin>>n;
	ll x = 0;
	forn(i,n){
		ll y;cin>>y;x = __gcd(x,y);
	}
    ll cnt = 0;
    ll m = sqrt(x);
    for1(i,m){
        if(x%i==0) cnt++;
        if(x%i==0&&x/i!=i) cnt++;
    }
    cout<<cnt<<'
';
    return 0;
}

D. 제목: 두 문자열 s, t 는 s 의 하위 문자열 을 삭제 하여 나머지 부분의 하위 서열 을 t 로 구성 할 수 있 습 니 다.가장 긴 길 이 를 삭제 하 십시오.사고: 두 바늘, 가운데 부분 을 삭제 하 는 것 에 주의 하 세 요.코드:

#include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f;
const int maxn = 2e5+5;
int l[maxn],r[maxn];
 
int main(){
    IO;cout.precision(10);cout<<fixed;
    string s,t;cin>>s>>t;
    int len = s.size(),len2 = t.size();
    forn(i,len){
        l[i+1] = l[i];
        if(l[i+1]<len2&&s[i]==t[l[i+1]]) l[i+1]++;
    }   
    r[len] = len2;
    for(int i = len-1;i>=0;i--){
        r[i] = r[i+1];
        if(r[i]>=0&&s[i]==t[r[i]-1]) r[i]--;
    }
    int ans = 0,p = 0;
    // forn(i,len) cerr<
    // cerr<
    // forn(i,len) cerr<
    // cerr<
    forn(i,len){
        while(p<len&&l[i]+1>r[p+1]) p++;
        // cerr<
        ans = max(ans,p-i);
     //   else break;
    }
    cout << ans<<'
';
    return 0;
}

E. 제목: 매번 숫자 + 1, - 1 을 사용 할 수 있 습 니 다.최대 몇 가지 숫자 를 구하 다.사고: 1 - 2 번 의 우선 아래로.코드:

#include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f;
 
int main(){
    IO;cout.precision(10);cout<<fixed;
    int n;cin>>n;
    multiset<int>s;
    map<int,int>mp;
    forn(i,n){
        int x;cin>>x;
        s.insert(x);mp[x]++;
    }    
    for(auto x:s){
        if(x>1&&!mp[x-1]){
            mp[x]--;
            mp[x-1]++;
        }
        if(mp[x]>1){
            mp[x]--;
            mp[x+1]++;
        }if(!mp[x]) mp.erase(x);
    }
    cout << mp.size()<<'
';
   // cout<
   // cout<
    return 0;
}

F. 제목: 100 개 관문 은 진입 문턱 ai 가 있 습 니 다. 통관 하면 bi (가능 - 가능 +) 를 얻 을 수 있 습 니 다. 처음에 r 의 금화 가 있 습 니 다. r > = ai 만 들 어 갈 수 있 습 니 다. 진입 후 r + = b [i], r < 0 이 되면 직접 게임 에 실패 하고 그 밖 에 통관 횟수 + 가 있 습 니 다.사고: bi > 0 시 우선 통관, bi < 0 시 우 리 는 이러한 상황 을 고려 하여 a1a 2b1b 2 만약 에 우리 가 12 의 노선 을 걷는다 면 r > = a1, r + b1 > = a2, 동 리 21r > = a1, r + b2 > = a1 그래서 r > = max (a1, a2 - b1) r > = max (a2, a1 - b2) 현재 첫 번 째 max 가 가장 작다 고 가정 하면 max (a1, a2 - b1) < = max (a2, a1 - b2), 분명히 a1 그래서 a2 - b1 은 a2 + b2 이후 01 가방 을 얻 으 면 된다.코드:

#include 
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i
#define for1(i,n) for(int i=1;i<=n;i++)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f;
const int maxn = 105;

int dp[maxn];

bool cmp(pair<int,int> x,pair<int,int> y){
    return x.first+x.second>y.first+y.second;
}

int main(){
    IO;cout.precision(10);cout<<fixed;
    forn(i,maxn) dp[i] = -inf;
    int n,r;cin>>n>>r;
    vector<pair<int,int> >a,b;
    forn(i,n){
        int x,y;cin>>x>>y;
        if(y>=0) a.push_back({x,y});
        else b.push_back({x,y});
    }
    sort(a.begin(),a.end());
    sort(b.begin(),b.end(),cmp);
    int ans = 0;
    for(auto x:a){
        if(r>=x.first) r+=x.second,ans++;
    }
    n = b.size();
    dp[0] = r;
    forn(i,n){
        int lim = b[i].first,v = b[i].second;
        for(int j=n-1;j>=0;j--){
            if(dp[j]>=max(lim,-v)){
                dp[j+1] = max(dp[j+1],dp[j]+v);
                //cerr<
            }
        }
    }
    for(int i = n;i>=1;i--) if(dp[i]!=-inf){
        ans+=i;
        break;
    }
    cout << ans <<'
';
    return 0;
}