CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)

A. Two 0-1 Sequences

void solve(){
    int n=read(),m=read(),ans=1;
    string s,t;
    cin>>s>>t;
    // cout<<s<<t<<endl;
    for(int i=t.size()-1,j=s.size()-1;i>=1&&j>=1;i--,j--){
        if(s[j]!=t[i]){
            ans=0;
            // cout<<j<<" "<<i<<endl;
            break;
        }
    }
    int fl=0;
    for(int i=0;i<=s.size()-t.size();i++){
        if(s[i]==t[0])fl=1;
    }
    if(!fl)ans=0;
    puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

B. Luke is a Foodie

int a[N];
void solve(){
    int n=read(),x=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
    }
    int maxx=a[1],minn=a[1],ans=0;
    for(int i=2;i<=n;i++){
        maxx=max(a[i],maxx);
        minn=min(a[i],minn);
        if(maxx-minn>2*x){
            ans++;
            maxx=a[i];
            minn=a[i];
        }
    }
    cout<<ans<<endl;
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

C. Virus

#define int long long
map<int,int>mp;
int a[N];
void solve(){
    int n=read(),m=read();
    mp.clear();
    for(int i=1;i<=m;i++){
        int x=read();
        mp[x]=1;
    }
    int last=0,cnt=0;
    for(auto [x,y]:mp){
        cnt++;
        a[cnt]=x-last-1;
        last=x;
    }
    if(last!=n){
        a[1]+=n+1-last-1;
    }
    sort(a+1,a+1+cnt);
    int day=0,live=0;
    for(int i=cnt;i>=1;i--){
        a[i]-=day*2;
        if(a[i]<=0)break;
        if(a[i]>2){
            live+=a[i]-1;
            day+=2;
        }else {
            live++;
            day++;
        }
    }
    cout<<n-live<<endl;
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

D. Magical Array

计算每个数组a[i]*i的和

对于进行任意次operation1的数组 和不变

对于进行k次operation2的数组 和增加k

#define int long long
void solve(){
    int m=read(),n=read();
    vector<int>a(n),sum(m);
    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++){
            a[j]=read();
            sum[i]+=a[j]*j;
        }
    }
    int ans=-1;
    int maxx=*max_element(sum.begin(),sum.end()),minn=*min_element(sum.begin(),sum.end());
    for(int i=0;i<m;i++){
        if(sum[i]==maxx)ans=i;
    }
    cout<<ans+1<<" "<<(maxx-minn)<<"\n";
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}

E. Count Seconds

首先这是一个DAG 想到拓扑排序

计算每一点对答案的贡献 各点贡献*点数的和就是答案 此处贡献就是汇点到这个的点的路径数

但是 对于有点权为0的点 上述结论不适用 因为若该点祖先有值 则该点会在几秒之后工作 也就是说 上面的结论只适用于与汇点已经相连的不含0点权的路径

如何排除0点权的麻烦呢 DAG的最长路径一定小于等于n 模拟n轮的情况后 该图上所有点权不为0的点与汇点相连的路径都是不为0的点

所以先模拟 后拓扑序dp求贡献和

#define int long long
int h[N], e[N], ne[N], idx, d[N], dp[N], bk[N], q[N], w[N];
int n,m;
void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void topsort(){
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        if (!d[i])
            q[ ++ tt] = i;
    while (hh <= tt){
        int t = q[hh ++ ];
        for (int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if (-- d[j] == 0)
                q[ ++ tt] = j;
        }
    }
    bool az=1;
    for(int i=1;i<=n;i++){
        if(w[i]){
            az=0;
            break;
        }
    }
    if(az){ 
        cout<<"0\n";
        return ;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)bk[j]=w[j];
        for(int j=1;j<=n;j++){
            if(w[j]){
                bk[j]--;
                for(int k=h[j];k!=-1;k=ne[k]){
                    int t=e[k];
                    bk[t]++;
                }
            }
        }
        az=1;
        for(int j=1;j<=n;j++){
            w[j]=bk[j];
            if(w[j]){
                az=0;
            }
        }
        if(az){
            cout<<i<<"\n";
            return ;
        }
    }
    int ans=n;
    for(int i=n-1;i>=0;i--){
        int x=q[i];
        if(i==n-1)dp[x]=1;
        else dp[x]=0;
        for(int j=h[x];j!=-1;j=ne[j]){
            int k=e[j];
            dp[x]=(dp[x]+dp[k])%mod;
        }
        ans+=w[x]*dp[x];
        ans%=mod;
    }
    cout<<ans<<endl;
}


void solve(){
    n=read(),m=read();
    idx = 0;
    memset(h, -1, sizeof h);
    for(int i=1;i<=n;i++){
        w[i]=read();
        d[i]=0;
    }
    for(int i=1;i<=m;i++){
        int x=read(),y=read();
        add(x,y);
        d[y]++;
    }
    topsort();
    //puts(ans>0?"YES":"NO");
    //puts(ans>0?"Yes":"No");
}