Educational Codeforces Round 85 (Rated for Div. 2)

\(Educational\ Codeforces\ Round\ 85\ (Rated\ for\ Div.2)\)

\(A. Level Statistics\)

每天都可能会有人玩游戏，同时一部分人会过关，玩游戏的人数和过关的人数会每天更新，问记录的数据是否没有矛盾

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

void solve(){

    int n, x = 0, y = 0;

    cin >> n;

    bool ok = true;

    for(int i = 1; i <= n; i++){

        int a, b;

        cin >> a >> b;

        if(a<x or b<y or b>a) ok = false;

        if(b-y>a-x) ok = false;

        x = a, y = b;

    }

    if(ok) cout << "YES" << endl;

    else cout << "NO" << endl;

}

int main(){

    ____();

    int T;

    for(cin >> T; T; T--) solve();

    return 0;

}

\(B - Middle Class\)

每次可以选几个人把钱均摊，问经过若干次操作之后最多有多少人的钱可以大于\(x\)

从大到小排序，然后判断前\(i\)个人均摊之后能否都大于\(x\)，找最大的\(i\)即可

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 1e5+7;

using LL = int_fast64_t;

int n,x,A[MAXN];

void solve(){

    cin >> n >> x;

    for(int i = 1; i <= n; i++) cin >> A[i];

    sort(A+1,A+1+n,greater<int>());

    LL tot = 0, pr = 0;

    for(int i = 1; i <= n; i++){

        pr += x;

        tot += A[i];

        if(tot<pr){

            cout << i-1 << endl;

            return;

        }

    }

    cout << n << endl;

}

int main(){

    ____();

    int T;

    for(cin >> T; T; T--) solve();

    return 0;

}

\(C. Circle of Monsters\)

怪物站成一圈，每个怪物有血量\(A_i\)，和爆炸伤害\(B_i\)，每次打一颗子弹，可以扣除怪物\(1\)滴血，怪物血量\(\le0\)时死亡，死亡之后会对\(i+1\)个怪物造成相应的爆炸伤害，问最少多少子弹可以消灭所有怪物。

\(1~n\)复制一遍到\(n+1~2n\)，然后算上一个怪物爆炸的情况下这个怪物还需要多少子弹，求前缀和，然后枚举第一个打的怪物即可

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 6e5+7;

using LL = int_fast64_t;

int n;

LL A[MAXN],B[MAXN],cost[MAXN],sum[MAXN];

void solve(){

    cin >> n;

    for(int i = 1; i <= n; i++){

        cin >> A[i] >> B[i];

        A[i+n] = A[i]; B[i+n] = B[i];

    }

    for(int i = 2; i <= n * 2; i++){

        cost[i] = max(0ll,A[i]-B[i-1]);

        sum[i] = sum[i-1] + cost[i];

    }

    LL ret = 0x3f3f3f3f3f3f3f3f;

    for(int i = 1; i <= n; i++) ret = min(ret,A[i]+sum[i+n-1]-sum[i]);

    cout << ret << endl;

}

int main(){

    ____();

    int T;

    for(cin >> T; T; T--) solve();

    return 0;

}

\(D. Minimum Euler Cycle\)

给一张完全图，任意两个点\(u,v\)之间有\(u \rightarrow v, v \rightarrow u\)两条边，要求走完所有边并且走的点的标号的字典序最小，要求输出一段区间内的顶点标号。

假设为顶点数为\(n\)的完全图，则方案为：

\((1, 2, 1, 3, 1, 4 \cdots 1, n)(\ 2, 3, 2, 4 \cdots 2, n)(\ 3, 4, 3, 5 \cdots 3, n) \cdots (n-3, n-2, n-3, n-1, n-3, n)(\ n-2, n-1, n-2, n)(\ n-1, n)\ 1\)

用括号括出来的可以找出来规律

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

using LL = int_fast64_t;

LL n, l, r;

void solve(){

    scanf("%I64d %I64d %I64d",&n,&l,&r);

    if(l==n*(n-1)+1){

        puts("1");

        return;

    }

    int stpos = 1;

    LL tot = 0;

    LL L = 0, R = n - 1;

    while(L<=R){

        LL mid = (L+R)>>1;

        if((n-1+n-mid)*mid<l) L = mid + 1;

        else R = mid - 1;

    }

    stpos = L;

    tot = (n-1+n-R)*R;

    int cur = stpos + (l-tot) / 2;

    bool tg = (((l-tot)&1)?true:false);

    for(LL i = l; i <= r; i++){

        if(stpos==n){

            printf("1 ");

            break;

        }

        if(tg){

            printf("%d ",stpos);

            cur++;

        }

        else{

            printf("%d ",cur);

            if(cur==n){

                stpos++;

                cur = stpos;

            }

        }

        tg = !tg;

    }

    puts("");

}

int main(){

    int T;

    for(scanf("%d",&T); T; T--) solve();

    return 0;

}

\(E. Divisor Paths\)

给出数\(D\)，以这个数建图，建图规则为：所有\(D\)的因子为顶点，\(u,v(u>v)\)两点之间连边的条件为：\(u%v==0 and u/v is prime\)，且边权为\(f(u)-f(v)\)，其中\(f(x)\)为\(x\)的因子数量，现在有\(Q\)次询问，每次询问\(u,v\)间的最短路条数。

首先我们假设要从\(u\)到\(v\)且\(u\%v==0\)，那么走的边必然是\(u\)比\(v\)分解之后多的质因子，略证：

首先假设命题成立

现在从\(a \rightarrow b\)，我们走多余质因子边：\(path(a,b)=a \rightarrow c \rightarrow b\)，则路径长度为：\(f(a)-f(c)+f(c)-f(b)=f(a)-f(b)\)，现在假设不走多余质因子边则：\(path(a,b)=a\rightarrow c \rightarrow d \rightarrow \cdots \rightarrow b\)，路径长度为\(f(a)-f(c)+f(d)-f(c)+dist(d,b)=f(a)-f(c)+f(d)-f(c)+f(d)-f(x)+dist(x,b)=dist(a,b)+2f(d)-2f(c)>dist(a,b)\)

如果\(u\%v\ne 0\)，则必然是先从\(u\)到\(gcd(u,v)\)，再从\(gcd(u,v)到v\)是最优的

如果两个数不互质的话可以先取\(gcd\)，然后必然能经过点\(1\)，然后只要找出\(1\)到各个点最短路的方案数即可。

假设\(x\)各个素因子的数量分别为\(P_1,P_2,\cdots,P_m\)，则最短路数量就是\(\frac{(\sum_{i=1}^{m}P_i)!}{\prod_{i=1}^{m}(P_i!)}\)

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

using LL = int_fast64_t;

const LL MOD = 998244353;

const int MAXN = 1e5+7;

LL D, q, fact[MAXN], invf[MAXN];

map<LL,LL> ret;

LL qpow(LL a, LL b){

    LL res = 1;

    while(b){

        if(b&1) res = res * a % MOD;

        b >>= 1;

        a = a * a % MOD;

    }

    return res;

}

void ikun(LL x){

    LL v = x;

    vector<int> vec;

    int tot = 0;

    for(LL i = 2; i * i <= x; i++){

        if(x%i!=0) continue;

        int cnt = 0;

        while(x%i==0) cnt++, x /= i;

        tot += cnt;

        vec.emplace_back(cnt);

        if(x==1) break;

    }

    if(x!=1) tot++;

    LL res = fact[tot];

    for(int p : vec) res = res * invf[p] % MOD;

    ret.insert(make_pair(v,res));

}

void solve(){

    fact[0] = 1;

    for(int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;

    invf[MAXN-1] = qpow(fact[MAXN-1],MOD-2);

    for(int i = MAXN - 2; i >= 0; i--) invf[i] = invf[i+1] * (i+1) % MOD;

    cin >> D >> q;

    for(LL i = 1; i * i <= D; i++){

        if(D%i!=0) continue;

        ikun(i);

        if(i*i!=D) ikun(D/i);

    }

    while(q--){

        LL u, v;

        cin >> u >> v;

        LL g = __gcd(u,v);

        u /= g; v /= g;

        cout << ret.at(u) * ret.at(v) % MOD << endl;

    }

}

int main(){

    ____();

    solve();

    return 0;

}

\(F. Strange Function\)

给出一个序列，\(f(A)\)操作就是取序列\(A\)的前缀递增序列，序列中每个数有一个价值，现在要求你删除序列\(a\)中的一些元素，使得\(f(A)=B\)

考虑朴素的\(DP\)，\(dp[i][j]\)表示现在\(A\)串的\(i\)位置和\(B\)串的\(j\)位置匹配，最小的花费，转移如下：

①如果不删除

\(\begin{cases} dp[i+1][j] = dp[i][j] & if\ A[i+1]\le B[j] \\ dp[i+1][j+1] = dp[i][j] & if\ A[i+1]=B[j+1]
\\ 不合法 & if\ A[i+1]>B[j]\ and\ A[i+1]\ne B[j+1] \end{cases}\)

②如果删除

\(dp[i+1][j] = dp[i][j] + cost[i+1]\)

现在整理一下：

\(\begin{cases}dp[i+1][j] = dp[i][j]+min(cost[i+1],0) & if\ A[i+1]\le B[j] \\ dp[i+1][j+1] = min(dp[i][j],dp[i][j+1]) & if\ A[i+1]=B[j+1] \\ dp[i+1][j] = dp[i][j]+cost[i+1] & if\ A[i+1]>B[j] \end{cases}\)

可以发现\(i+1\)的状态都是从\(i\)的状态转移过来的，所以可以把第一维给去掉，然后用线段树或者树状数组维护一下

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 5e5+7;

using LL = int_fast64_t;

const LL INF = 0x3f3f3f3f3f3f3f3f;

int n,m,A[MAXN],B[MAXN],p[MAXN];

template<typename T>

struct SegmentTree{

    T lazy[MAXN<<2];

    int l[MAXN<<2],r[MAXN<<2];

    #define ls(rt) rt << 1

    #define rs(rt) rt << 1 | 1

    void build(int L, int R, int rt){

        l[rt] = L; r[rt] = R;

        lazy[rt] = 0;

        if(L+1==R) return;

        int mid = (L + R) >> 1;

        build(L,mid,ls(rt)); build(mid,R,rs(rt));

    }

    void pushdown(int rt){

        if(!lazy[rt]) return;

        lazy[ls(rt)] += lazy[rt];

        lazy[rs(rt)] += lazy[rt];

        lazy[rt] = 0;

    }

    void update(int L, int R, int rt, T x){

        if(L>=r[rt] || l[rt]>=R) return;

        if(L<=l[rt] && r[rt]<=R){

            lazy[rt] += x;

            return;

        }

        pushdown(rt);

        update(L,R,ls(rt),x); update(L,R,rs(rt),x);

    }

    T query(int L, int R, int rt){

        if(L>=r[rt] || l[rt]>=R) return 0;

        if(L<=l[rt] && r[rt]<=R) return lazy[rt];

        pushdown(rt);

        return query(L,R,ls(rt))+query(L,R,rs(rt));

    }

};

SegmentTree<LL> ST;

int main(){

    ____();

    cin >> n;

    for(int i = 1; i <= n; i++) cin >> A[i];

    for(int i = 1; i <= n; i++) cin >> p[i];

    cin >> m;

    for(int i = 1; i <= m; i++) cin >> B[i];

    ST.build(0,m+1,1);

    ST.update(1,m+1,1,INF);

    for(int i = 1; i <= n; i++){

        int pos = lower_bound(B+1,B+1+m,A[i]) - B;

        if(A[i]==B[pos]){

            ST.update(pos,m+1,1,min(0,p[i]));

            ST.update(pos,pos+1,1,min(0ll,ST.query(pos-1,pos,1)-ST.query(pos,pos+1,1)));

            ST.update(0,pos,1,p[i]);

        }

        else{

            ST.update(pos,m+1,1,min(0,p[i]));

            ST.update(0,pos,1,p[i]);

        }

    }

    LL ret = ST.query(m,m+1,1);

    if(ret>INF/2) cout << "NO" << endl;

    else cout << "YES" << endl << ret << endl;

    return 0;

}

\(G. Substring Search\)

给出两个串\(s,t\)要求找到在\(t\)串中所有能和\(s\)串匹配的位置，其中字符匹配的条件是\(s_j==t_{i+j} or P_{s_j}=t_{i+j}\)，其中\(P\)为\(0-25\)的一个排列。

如果用朴素的想法，\(26\)个字符每个都匹配一遍，最后找每个位置的匹配数量的话，一共要进行\(78\)遍\(FFT\)，但是题目只给了\(1.25s\)，显然是行不通的

如果转化成方程的形式，那么如果两个串匹配，则每个相应字符都能匹配上，可以写成：

\[\sum_{j=0}^{m-1}(t_{i+j}-s_j)^2\cdot (t_{i+j}-P_{s_j})^2==0
\]

把\(s\)串翻转后得到：

\[\sum_{j=0}^{m-1}(t_{i+j}-s_{m-1-j})^2\cdot (t_{i+j}-P_{s_{m-1-j}})^2
\]

转换成卷积形式：

\[\sum_{x+y=i+m-1}(t_x-s_y)^2\cdot (t_x-P_{s_y})^2
\]

每个位置的值即为：

\[\sum_{i=0}^{n-1}\sum_{x+y=i+m-1}(t_x-s_y)^2\cdot (t_x-P_{s_y})^2
\]

展开：

\[\sum_{i=0}^{n-1}\sum_{x+y=i+m-1}t_x^4-2(s_y+P_{s_y})t_x^3+(s_y^2+P{s_y}^2+4s_yP{s_y})t_x^2-2s_yP_{s_y}(s_y+P_{s_y})t_x+s_y^2P_{s_y}^2
\]

对于第一项和最后一项可以用前缀和来求，这样可以只做\(7\)次\(FFT\)

hack数据有点恶心，把NTT的998244353模数卡了，用1004535809能过

好像bitset可以水过，而且耗时还很优秀

//#pragma GCC optimize("O3")

//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<bits/stdc++.h>

using namespace std;

function<void(void)> ____ = [](){ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);};

const int MAXN = 1e6+7;

using LL = int_fast64_t;

//const LL MOD = 998244353;

const LL MOD = 1004535809;

const LL g = 3;

int n,P[30],l,limit,r[MAXN],lens,lent;

LL A[MAXN],B[MAXN],C[MAXN];

char s[MAXN],t[MAXN];

LL qpow(LL a, LL b){

    if(!a) return 0;

    LL ret = 1;

    while(b){

        if(b&1) ret = ret * a % MOD;

        b >>= 1;

        a = a * a % MOD;

    }

    return ret;

}

void NTT(LL arr[], int rev){

    for(int i = 0; i < limit; i++) if(i<r[i]) swap(arr[i],arr[r[i]]);

    for(int len = 1; len < limit; len <<= 1){

        LL wn = qpow(g,(MOD-1)/(len<<1));

        if(rev==-1) wn = qpow(wn,MOD-2);

        for(int R = 0; R < limit; R += (len<<1)){

            LL w = 1;

            for(int i = R; i < R + len; i++){

                LL x = arr[i], y = w * arr[i+len] % MOD;

                arr[i] = (x+y)%MOD;

                arr[i+len] = (x-y+MOD)%MOD;

                w = w * wn % MOD;

            }

        }

    }

}

int main(){

    for(int i = 0; i < 26; i++){

        scanf("%d",&P[i]);

        P[i]--;

    }

    scanf("%s %s",s,t);

    lens = strlen(s); lent = strlen(t);

    reverse(s,s+lens);

    limit = 1; l = 0;

    while(limit<=(lens+lent-2)) limit <<= 1, l++;

    for(int i = 0; i < limit; i++) r[i] = (r[i>>1]>>1) | ((i&1)<<(l-1));

    for(int i = lent; i < limit; i++) B[i] = 0;

    for(int i = lens; i < limit; i++) C[i] = 0;

    for(int i = 0; i < lent; i++){

        LL x = t[i] - 'a';

        B[i] = x * x * x;

    }

    for(int i = 0; i < lens; i++) C[i] = (-2*(s[i]-'a'+P[s[i]-'a'])+MOD)%MOD;

    NTT(B,1); NTT(C,1);

    for(int i = 0; i < limit; i++) A[i] = (A[i] + B[i] * C[i]) % MOD;

    for(int i = lent; i < limit; i++) B[i] = 0;

    for(int i = lens; i < limit; i++) C[i] = 0;

    for(int i = 0; i < lent; i++){

        LL x = t[i] - 'a';

        B[i] = x * x;

    }

    for(int i = 0; i < lens; i++) C[i] = qpow(s[i]-'a',2)+qpow(P[s[i]-'a'],2)+4*(s[i]-'a')*P[s[i]-'a'];

    NTT(B,1); NTT(C,1);

    for(int i = 0; i < limit; i++) A[i] = (A[i] + B[i] * C[i]) % MOD;

    for(int i = lent; i < limit; i++) B[i] = 0;

    for(int i = lens; i < limit; i++) C[i] = 0;

    for(int i = 0; i < lent; i++) B[i] = t[i] - 'a';

    for(int i = 0; i < lens; i++) C[i] = (-2*(s[i]-'a')*P[s[i]-'a']*(s[i]-'a'+P[s[i]-'a'])+MOD)%MOD;

    NTT(B,1); NTT(C,1);

    for(int i = 0; i < limit; i++) A[i] = (A[i] + B[i] * C[i]) % MOD;

    NTT(A,-1);

    LL inv = qpow(limit,MOD-2);

    LL sum = 0;

    vector<LL> pre(lent);

    for(int i = 0; i < lens; i++) sum += (s[i]-'a')*(s[i]-'a')*P[s[i]-'a']*P[s[i]-'a'];

    pre[0] = qpow(t[0]-'a',4);

    for(int i = 1; i < lent; i++) pre[i] = pre[i-1] + qpow(t[i]-'a',4);

    for(int i = lens - 1; i < lent; i++) A[i] = (A[i] * inv + sum + pre[i] - ((i-lens>=0)?pre[i-lens]:0)) % MOD;

    for(int i = lens - 1; i < lent; i++) putchar(A[i]?'0':'1'); puts("");

    return 0;

}

巴特西

Educational Codeforces Round 85 (Rated for Div. 2)

最新文章

热门文章