Educational Codeforces Round 21

A. Lucky Year

个位数直接输出\(1\)

否则，假设\(n\)十进制最高位的值为\(s\)，答案就是\(s-(n\mod s)\)

view code

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define pb push_back
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x)  cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

void solve(){
    int a, b; sci(a); b = a;
    int t = 0;
    LL s = 1;
    while(a) t++, a/=10, s *= 10;
    s /= 10;
    if(t==1) cout << 1 << endl;
    else cout << s - (b % s) << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("Local.in","r",stdin);
    freopen("ans.out","w",stdout);
    #endif
    solve();
    return 0;
} 

B. Average Sleep Time

滑窗算一下就好了

view code

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define pb push_back
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x)  cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

void solve(){
    int n, k; sci(n); sci(k);
    LL s = 0;
    vl A(n);
    for(auto &x : A) scl(x);
    for(int i = 0; i < k; i++) s += A[i];
    LL tt = s;
    for(int i = k; i < n; i++){
        s += A[i]; s -= A[i-k];
        tt += s;
    }
    cout << fixed << setprecision(10) << 1. * tt / (n - k + 1) << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("Local.in","r",stdin);
    freopen("ans.out","w",stdout);
    #endif
    solve();
    return 0;
} 

C. Tea Party

为了容易处理，先把所有\(a\)从小到大排序

先让所有值都等于\(\lceil a_i\rceil\)，不够用输出\(NO\)

如果有剩下的，从最大的开始把剩下的补进去即可

view code

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define pb push_back
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x)  cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

void solve(){
    int n, m;
    sci(n); sci(m);
    vector<pii> A(n);
    vi B(n);
    for(auto &x : A) sci(x.first);
    for(int i = 0; i < n; i++) A[i].second = i;
    sort(all(A));
    for(int i = 0; i < n; i++){
        B[i] = (A[i].first + 1) / 2;
        m -= B[i];
    }
    if(m<0){
        cout << -1 << endl;
        return;
    }
    int x = min(m,A.back().first - B.back());
    B.back() += x; m -= x;
    for(int i = n - 2; i >= 0; i--){
        x = min(m, min(B[i+1],A[i].first) - B[i]);
        m -= x; B[i] += x;
    }
    vi ret(n);
    for(int i = 0; i < n; i++) ret[A[i].second] = B[i];
    for(int i = 0; i < n; i++) cout << ret[i] << ' ';
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("Local.in","r",stdin);
    freopen("ans.out","w",stdout);
    #endif
    solve();
    return 0;
} 

D. Array Division

维护一个前缀和和后缀和，然后判断是否存在一个数从前缀中放到后缀或者从后缀中放到前缀使得前后缀和相等，用个\(map\)计一下就好了

view code

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define pb push_back
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x)  cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

void solve(){
    int n; sci(n);
    vi A(n);
    for(int &x : A) sci(x);
    LL s = accumulate(all(A),0ll);
    if(s&1){
        cout << "NO" << endl;
        return;
    }
    LL pre = 0;
    map<LL,int> s1,s2;
    for(int x : A) s2[x]++;
    for(int i = 0; i < n; i++){
        pre += A[i];
        s1[A[i]]++; s2[A[i]]--;
        if(s2[A[i]]==0) s2.erase(A[i]);
        LL delta = 2 * pre - s;
        if(delta==0 or (delta<0 and s2.count(-delta/2)) or (delta>0 and s1.count(delta/2))){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("Local.in","r",stdin);
    freopen("ans.out","w",stdout);
    #endif
    solve();
    return 0;
} 

E. Selling Souvenirs

\(w\)比较小，考虑从这里找到解决方法

如果\(w\)只有两种的话直接从大到小排序后枚举一种的数量，然后另一种直接计算就好了

现在\(w\)有三种，那么我们枚举\(w=3\)的，如果暴力枚举\(w=2\)的复杂度会有\(O(n^2)\)

假设我们选完\(w=3\)的之后全选了\(w=1\)的，可以发现我们每次相当于拿一个\(w=2\)的去替换两个\(w=1\)的

考虑最贪心的情况下，肯定是拿值最大的\(w=2\)去替换两个值最小的\(w=1\)的物品

那么我们可以二分这个替换的数量

复杂度\(O(n\log n)\)

view code

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define pb push_back
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x)  cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

void solve(){
    int n, m;
    sci(n); sci(m);
    vl A[3],pre[3];
    for(int i = 0; i < n; i++){
        int x, y; sci(x); sci(y);
        A[x-1].push_back(y);
    }
    for(int i = 0; i < 3; i++){
        sort(all(A[i]),greater<LL>());
        A[i].insert(A[i].begin(),0);
        partial_sum(all(A[i]),back_inserter(pre[i]));
    }
    while(A[0].size()<=m){
        A[0].push_back(0);
        pre[0].push_back(pre[0].back());
    }
    LL ret = 0;
    for(int i = 0; i < A[2].size() and i <= m / 3; i++){
        LL sum = pre[2][i];
        int lft = m - 3 * i;
        if(A[1].size()==1){
            ret = max(ret,sum+pre[0][lft]);
            continue;
        }
        int l = 1, r = min((int)A[1].size()-1,lft/2);
        while(l<=r){
            int mid = (l + r) >> 1;
            if(A[1][mid]>A[0][lft-(mid-1)*2]+A[0][lft-(mid-1)*2-1]) l = mid + 1;
            else r = mid - 1;
        }
        ret = max(ret,sum + pre[1][r] + pre[0][lft-2*r]);
    }
    cout << ret << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("Local.in","r",stdin);
    freopen("ans.out","w",stdout);
    #endif
    solve();
    return 0;
} 

F. Card Game

除了\(2\)以外的所有偶数都不是素数

并且显然我们不会取两张编号为\(1\)的卡

所以我们把所有可以用的卡片按编号的奇偶分成两部分，如果和为素数就连边，可以发现这是一张二分图

源点向所有偶数点连边，容量为价值，所有奇数点向汇点连边，容量为价值，不能同时存在的两个点连容量为\(INF\)的边

那么可以得到的最大价值和就是价值和减去最小割

那么我们二分\(level\)然后网络流判断就好了

view code

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define pb push_back
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x)  cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 222;
#define S 0
#define T MAXN - 1
struct EDGE{
    int to,cap,rev;
    EDGE(){};
    EDGE(int to, int cap, int rev):to(to),cap(cap),rev(rev){};
};
vector<EDGE> G[MAXN];
int iter[MAXN],rk[MAXN];
void ADDEDGE(int u, int v, int cap){
    G[u].push_back(EDGE(v,cap,(int)G[v].size()));
    G[v].push_back(EDGE(u,0,(int)G[u].size()-1));
}
bool bfs(){
    memset(rk,0,sizeof(rk));
    memset(iter,0,sizeof(iter));
    rk[S] = 1;
    queue<int> que;
    que.push(S);
    while(!que.empty()){
        int u = que.front();
        que.pop();
        for(auto e : G[u]){
            if(!e.cap or rk[e.to]) continue;
            rk[e.to] = rk[u] + 1;
            que.push(e.to);
        }
    }
    return rk[T]!=0;
}
int dfs(int u, int flow){
    if(u==T) return flow;
    for(int &i = iter[u]; i < (int)G[u].size(); i++){
        auto &e = G[u][i];
        if(!e.cap or rk[e.to]!=rk[u]+1) continue;
        int d = dfs(e.to,min(e.cap,flow));
        if(d){
            e.cap -= d;
            G[e.to][e.rev].cap += d;
            return d;
        }
    }
    return 0;
}
int Dinic(){
    int flow = 0;
    while(bfs()){
        int d = dfs(S,INF);
        while(d){
            flow += d;
            d = dfs(S,INF);
        }
    }
    return flow;
}
const int MAXM = 2e5+7;
int n, k, prime[MAXM], pri_cnt;
bool npm[MAXM];
vector<pii> card[MAXN];

void sieve(){
    for(int i = 2; i < MAXM; i++){
        if(!npm[i]) prime[++pri_cnt] = i;
        for(int j = 1; i * prime[j] < MAXM; j++){
            npm[i*prime[j]] = true;
            if(i%prime[j]==0) break;
        }
    }
}
void solve(){
    sieve();
    sci(n), sci(k);
    for(int i = 1; i <= n; i++){
        int x, y, z;
        sci(x), sci(y), sci(z);
        card[z].pb({x,y});
    }
    int l = 1, r = n;
    while(l<=r){
        int mid = (l + r) >> 1;
        vector<pii> odd, even;
        int val1 = 0;
        for(int i = 0; i < MAXN; i++) G[i].clear();
        for(int i = 1; i <= mid; i++) for(auto p : card[i]){
            if(p.second==1) cmax(val1,p.first);
            else if(p.second&1) odd.pb(p);
            else even.pb(p);
        }
        if(val1) odd.pb({val1,1});
        int sum = 0;
        for(auto p : odd) sum += p.first;
        for(auto p : even) sum += p.first;
        for(int i = 0; i < (int)even.size(); i++) ADDEDGE(i+1+odd.size(),T,even[i].first);
        for(int i = 0; i < (int)odd.size(); i++){
            ADDEDGE(S,i+1,odd[i].first);
            for(int j = 0; j < (int) even.size(); j++) if(!npm[odd[i].second+even[j].second]) ADDEDGE(i+1,j+1+odd.size(),INF);
        }
        if(sum - Dinic()>=k) r = mid - 1;
        else l = mid + 1;
    }
    cout << (l==n+1?-1:l) << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("Local.in","r",stdin);
    freopen("ans.out","w",stdout);
    #endif
    solve();
    return 0;
} 

G. Anthem of Berland

匹配问题，考虑类似\(KMP\)的做法，先根据\(t\)串得到\(fail\)数组，然后类似\(AC\)自动机，得到每个位置匹配下一个字符到的位置

然后考虑\(dp\)，\(dp[i][j]\)表示现在\(s\)串的\(i\)位置匹配到了\(t\)串的\(j\)位置完美匹配的最多次数，遇到字母直接转移，否则枚举\(26\)个字母转移即可

view code

#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,no-stack-protector")
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LL long long int
#define vi vector<int>
#define vl vector<LL>
#define pb push_back
#define all(V) V.begin(),V.end()
#define sci(x) scanf("%d",&x)
#define scl(x) scanf("%I64d",&x)
#define pii pair<int,int>
#define cmax(a,b) ((a) = (a) > (b) ? (a) : (b))
#define cmin(a,b) ((a) = (a) < (b) ? (a) : (b))
#define debug(x)  cerr << #x << " = " << x << endl
function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};
const int MAXN = 1e5+7;
char s[MAXN], t[MAXN];
int fail[MAXN], ch[MAXN][26], n, m;

void solve(){
    scanf("%s %s",s+1,t+1);
    n = strlen(s+1), m = strlen(t+1);
    for(int i = 2, len = 0; i <= m;){
        if(t[i]==t[len+1]) fail[i++] = ++len;
        else{
            if(len) len = fail[len];
            else fail[i++] = len;
        }
    }
    for(int i = 0; i < m; i++){
        for(int j = 0; j < 26; j++) ch[i][j] = ch[fail[i]][j];
        ch[i][t[i+1]-'a'] = i + 1;
    }
    vector<vi> f(n+1,vi(m+1,-1));
    f[0][0] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(f[i][j]==-1) continue;
            for(int k = (s[i+1]=='?'?0:s[i+1]-'a'); k < (s[i+1]=='?'?26:s[i+1]-'a'+1); k++){
                if(ch[j][k]==m) cmax(f[i+1][fail[m]],f[i][j] + 1);
                else cmax(f[i+1][ch[j][k]],f[i][j]);
            }
        }
    }
    cout << *max_element(all(f[n])) << endl;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("Local.in","r",stdin);
    freopen("ans.out","w",stdout);
    #endif
    solve();
    return 0;
}