Codeforces Educational Round46


Last Update: July, 2018

First time post a codeforces contest.

Don’t know how to do the last one.. emm…

Save this for later


 

Since this is only a Div 2, so I won’t include much explanation(took me centuries to finish). Typesetting is to0 hard…

A:

Just do it

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e6 + 10;

int N;
map<string,int> mp1,mp2;

int main(){
    FAST_IO
    cin>>N;
    for(int i = 1; i <= N; i++){
        string s;
        cin>>s;
        mp1[s]++;
    }
    for(int i = 1; i <= N; i++){
        string s;
        cin>>s;
        mp2[s]++;
    }
    int ans = 0;
    ans += abs(mp2["M"] - mp1["M"]);
    string s = "S";
    for(int i = 0; i <= 3; i++){
        ans += abs(mp2[s] - mp1[s]);
        s.insert(s.begin(),'X');
    }
    s = "L";
    for(int i = 0; i <= 3; i++){
        ans += abs(mp2[s] - mp1[s]);
        s.insert(s.begin(),'X');
    }
    cout<<ans / 2<<endl;
    return 0;
}

B:

A problem that requires you to think about the invariants in the sum of lights on and off.

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e6 + 10;
int N,M;
int a[maxn],sum_off,sum_on,rang[maxn];
int main(){
    FAST_IO
    cin>>N>>M;
    for(int i = 1; i <= N; i++) cin>>a[i];
    a[N + 1] = M;
    for(int i = 1; i <= N + 1; i++){
        rang[i] = a[i] - a[i - 1];
    }
    for(int i = 1; i <= N + 1; i++){
        if(i % 2 == 1) sum_on += rang[i];
        else sum_off += rang[i];
    }
    int maxx = sum_on,tmp = 0,sum = 0;
    for(int i = 1; i <= N + 1; i++){
        if(i % 2 == 1) sum += rang[i];
        else sum_off -= rang[i];
        tmp = sum_off + sum - 1;
        maxx = max(maxx,tmp);
    }
    cout<<maxx<<endl;
    return 0;
}

C:

Using BIT or Segment Tree to transform the original problem into another dimension.

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e6 + 10;
int N;
vector<pll> v;
ll cnt[maxn];
int main(){
    FAST_IO
    cin>>N;
    for(int i = 1; i <= N; i++){
        ll a,b;
        cin>>a>>b;
        v.push_back(pll(a,1));
        v.push_back(pll(b + 1,-1));
    }
    sort(v.begin(),v.end());
    ll f = 0;
    for(int i = 0; i < v.size(); i++){
        f += v[i].second;
        if(i < v.size() - 1){
            if(v[i].first != v[i + 1].first){
                cnt[f] += v[i + 1].first - v[i].first;
            }
        }
    }
    for(int i = 1; i <= N; i++) cout<<cnt[i]<<" ";
    cout<<endl;
    return 0;
}

D:

Simple Combinatoric Problem

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e3 + 10;
ll mod = 998244353;
ll C[maxn][maxn],dp[maxn],a[maxn];
int N;


int main(){
    FAST_IO
    cin>>N;
    for(int i = 0; i <= 1000; i++){
        C[i][0] = C[i][i] = 1;
        for(int j = 1; j < i; j++){
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
    for(int i = 1; i <= N; i++) cin>>a[i];
    dp[N + 1] = 1;
    for(int i = N; i ; i--){
        if(a[i] <= 0) continue;
        for(int j = i + a[i] + 1; j <= N + 1; j++){
            dp[i] = (dp[i] + dp[j] * C[j - 1 - i][a[i]]) % mod;
        }
    }
    ll sum = 0;
    for(int i = 1; i <= N; i++) sum = (sum + dp[i]) % mod;
    cout<<sum<<endl;
    return 0;
}

E:

Use Edge Biconnected Component to make the original graph into a tree, and find the diameter of the tree.

#pragma GCC optimize(2)
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e6 + 10;
int head[maxn<<1],ver[maxn<<1],nxt[maxn<<1];
int dfn[maxn],low[maxn],tot,num;
bool bridge[maxn<<1];
int c[maxn],pre[maxn<<1];
int tot_bridge,N,M;
int dcc;
bool instac[maxn];
stack<int> S;
vector<int> G[maxn];
void addedge(int x,int y){
    ver[++tot] = y;
    nxt[tot] = head[x];
    head[x] = tot;
}
void tarjan(int x,int fa){
    dfn[x] = low[x] = ++num;
    S.push(x);
    for(int i = head[x]; i; i = nxt[i]){
        int v = ver[i];
        if(v == fa) continue;
        if(!dfn[v]){
            tarjan(v,x);
            low[x] = min(low[x],low[v]);
        }
        else low[x] = min(low[x],dfn[v]);
    }
    if(low[x] == dfn[x]){
        int tmp;
        dcc++;
        do{
            tmp = S.top();
            S.pop();
            c[tmp] = dcc;
        }
        while(!S.empty() && tmp != x);
    }
}
int ans,dp[maxn][2];
void dfs(int u,int fa){
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(v == fa) continue;
        dfs(v,u);
        if(dp[u][1] < dp[v][1] + 1){
            dp[u][0] = dp[u][1];
            dp[u][1] = dp[v][1] + 1;
        }
        else dp[u][0] = max(dp[u][0],dp[v][1] + 1);
    }
    ans = max(ans,dp[u][1] + dp[u][0]);
}
int main(){

    FAST_IO
    cin>>N>>M;
    for(int i = 1; i <= M; i++){
        int u,v;
        cin>>u>>v;
        addedge(u,v); addedge(v,u);
    }
    for(int i = 1; i <= N; i++) if(!dfn[i]) tarjan(i,0);
    for(int i = 1; i <= N; i++){
        for(int j = head[i]; j; j = nxt[j]){
            int u = ver[j];
            if(c[i] != c[u]){
                G[c[i]].push_back(c[u]);
            }
        }
    }
    dfs(1,0);
    cout<<ans<<endl;
    return 0;
}

F:

The condition of one occurrence is that the previous occurrence of the current number is not in the range l….r. Therefore, we can sort the queries, and use a Segment Tree to query the minimum occurrence index within the range l….r and see if it is less than the left bound l.

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e6 + 10;
#define inf 0x7f7f7f7f
int N,Q;
int a[maxn],pos[maxn];
pii tree[maxn<<2];

void build(int cur,int l,int r){
    if(l == r) {
        tree[cur] = make_pair(inf,l);
        return ;
    }
    int mid = (l + r) >> 1;
    build(cur<<1,l,mid);
    build(cur<<1|1,mid + 1,r);
    tree[cur] = min(tree[cur<<1],tree[cur<<1|1]);
}

void update(int cur,int l,int r,int a,int b,int delta){
    if(a <= l && r <= b){
        tree[cur].first = delta;
        return;
    }
    int mid = (l + r) >> 1;
    if(a <= mid) update(cur<<1,l,mid,a,b,delta);
    if(b > mid) update(cur<<1|1,mid + 1,r,a,b,delta);
    tree[cur] = min(tree[cur<<1],tree[cur<<1|1]);
}

pii query(int cur,int l,int r,int a,int b){
    if(a <= l && r <= b){
        return tree[cur];
    }
    int mid = (l + r) >> 1;
    auto st = make_pair(inf,-1);
    if(a <= mid) st = min(st,query(cur<<1,l,mid,a,b));
    if(b > mid) st = min(st,query(cur<<1|1,mid + 1,r,a,b));
    return st;
}

struct que{
    int l,r,id;
    que(int a = 0,int b = 0,int c = 0):l(a),r(b),id(c){}
};

vector<que> quer;
int ans[maxn];
bool cmp(que a,que b){
    return a.r < b.r;
}

int main(){
    memset(pos,-1,sizeof(pos));
    FAST_IO
    cin>>N;
    for(int i = 1; i <= N; i++) cin>>a[i]; 
    cin>>Q;
    for(int i = 1; i <= Q; i++){
        int l,r;
        cin>>l>>r;
        quer.push_back(que(l,r,i));
    }
    sort(quer.begin(),quer.end(),cmp);
    int lst = 0;
    build(1,1,N);
    for(int i = 0; i < quer.size(); i++){
        int l = quer[i].l;
        int r = quer[i].r;
        for(int j = lst + 1; j <= r; j++){
            if(pos[a[j]] != -1) update(1,1,N,pos[a[j]],pos[a[j]],inf);
            update(1,1,N,j,j,pos[a[j]]);
            pos[a[j]] = j;
        }
        auto it = query(1,1,N,l,r);
        if(it.second == -1 || it.first >= l ) ans[quer[i].id] = 0;
        else ans[quer[i].id] = a[it.second];
        lst = r;
    }
    for(int i = 1; i <= Q; i++) cout<<ans[i]<<endl;
    return 0;
}

G:

Seems like a Tree-DP, don’t know how to do it for now. Save this for later.. 

Leave a Reply

Your email address will not be published. Required fields are marked *