Educational Codeforces Round 104 (Rated for Div. 2)

2024-01-19 20:42:40

Educational Codeforces Round 104 (Rated for Div. 2)

A.Arena

签到题，对于每个人来说，只要他比任意一个大，就可以成功， O ( n 2 ) O(n^2) O(n2)暴力枚举

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
int t,n,a[105];
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){ 
        cin>>n;
        for(int i=1;i<=n;++i)cin>>a[i];
        int ans=0;
        for(int i=1;i<=n;++i){ 
            for(int j=1;j<=n;++j){ 
                if(i==j)continue;
                else if(a[i]>a[j]){ 
                    ans++;break;
                }
            }
        }
        cout<<ans<<"\n";
    }
    return 0;
}

B.Cat Cycle

n为偶数的时候煞笔题，n为奇数的时候循环节为每n/2向下取整个周期，算下最后取模到哪里就行了

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
int t,n,k;
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){ 
        cin>>n>>k;
        if(n&1){
            int m=(k-1)/((n/2));
            int st=k-1;
            cout<<(1+(st+m)%n)<<"\n";
        }else{ 
            if(k%n==0)
                    cout<<n<<"\n";
            else 
                cout<<k%n<<"\n";
        }
    }
    return 0;
}

C.Minimum Ties

题意：

n个球队,两两球队打一场,胜者加三分,输者不加分,如果平局两边各加一分.问:最少有几次平局,可以使所有球队的最终总得分相同.要求输出具体方案.

思路：

每支队打n-1场，容易想到与n-1的奇偶性有关

当n-1为偶数的时候，胜负对半分，否则就留一场给0，直接画出0/1矩阵，构造上三角即为答案

11-1-1，11-1，11，1或者

10-1,10,1这样很容易就能构造出来

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
int t,n,ans[105];
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){ 
        cin>>n;
        n--;
        if(n&1){ 
            for(int i=1;i<=n/2;++i)ans[i]=1;
            ans[(n+1)/2]=0;
            for(int i=(n+1)/2+1;i<=n;++i)ans[i]=-1;
        }else{ 
            for(int i=1;i<=n/2;++i)ans[i]=1;
            for(int i=n/2+1;i<=n;++i)ans[i]=-1;
        }
        for(int i=n;i>=1;--i){ 
            for(int j=1;j<=i;++j)cout<<ans[j]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}

D.Pythagorean Triples

题意：问三元组 ( a , b , c ) 满 足 1 ≤ a ≤ b ≤ c ≤ n (a,b,c)满足1\leq a\leq b\leq c \leq n (a,b,c)满足1≤a≤b≤c≤n且是直角三角形，满足 c = a 2 − b c=a^2-b c=a2−b的个数

思路：随便推下 c = b + 1 c=b+1 c=b+1,得出 a a a与 b b b的关系，根号 n n n枚举 a a a看看 b b b是否满足条件即可

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
int t,n;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>t;
    while(t--){ 
        ll ans=0;
        cin>>n;
        for(ll i=1;(i*i+1)/2<=n;++i){ 
            ll b=i*i-1;
            if(b%2==0&&b>=i)ans++;
        }
        cout<<ans<<"\n";
    } 
    return 0;
}

E.Cheapo Dinner

思路：

考虑没有限制，就是裸的线段树优化dp， d p [ i ] [ j ] dp[i][j] dp[i][j]表示选完第i个，在第i个中选第j种的最小花费，线段树维护四层的dp值，区间最小值，有限制，还是裸的线段树优化DP，直接在转移的时候，把对应位置的上一层dp值的影响消去，再加上去即可。单点修改，区间最小值

时间复杂度 O ( 4 ( n i l o g n i + m i l o g n i ) ) O(4(n_ilogn_i+m_ilogn_i)) O(4(ni​logni​+mi​logni​)) 四秒2.4e7随便过

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define lson p<<1,l,mid
#define rson p<<1|1,mid+1,r
#define ls p<<1
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int maxn=150005;
const int INF=1e9;
int t,n,ni[5],m[5],a[5][maxn],cnt=0;
vector<int>G[5][maxn];
pair<int,int>pre[maxn];
struct SegmentTree{
    int mx[maxn<<2];
    void pushUp(int p){
        mx[p]=min(mx[ls],mx[rs]);
    }
    void update(int p,int l,int r,int x,int val){
        if(l==r){
            if(val==INF)mx[p]=val;
            else mx[p]=min(mx[p],val);return;
        }
        int mid=l+r>>1;
        if(x<=mid)update(lson,x,val);
        else update(rson,x,val);
        pushUp(p);
    }
    void build(int p,int l,int r){
        if(l==r){
            mx[p]=INF;return;
        }
        int mid=l+r>>1;
        build(lson);
        build(rson);
        pushUp(p);
    }
    int query(int p,int l,int r,int x){
        if(l==r)return mx[p];
        int mid=l+r>>1;
        if(x<=mid)return query(lson,x);
        else return query(rson,x);
    }
}tr[5];
void init(int id){
    int x,y;
    cin>>m[id];
    for(int i=1;i<=m[id];++i){
        cin>>x>>y;
        G[id][y].pb(x);
    }
}
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i=1;i<=4;++i)cin>>ni[i];
    for(int i=1;i<=4;++i)
    	tr[i].build(1,1,ni[i]);
    for(int i=1;i<=ni[1];++i){
        cin>>a[1][i];
        tr[1].update(1,1,ni[1],i,a[1][i]);
    }
    for(int i=2;i<=4;++i)
		for(int j=1;j<=ni[i];++j)cin>>a[i][j]; 
    for(int i=2;i<=4;++i)
        init(i);
    for(int i=2;i<=4;++i){
        for(int j=1;j<=ni[i];++j){
            cnt=0;
            for(int k=0;k<G[i][j].size();++k){
                pre[++cnt]={G[i][j][k],tr[i-1].query(1,1,ni[i-1],G[i][j][k])};
                tr[i-1].update(1,1,ni[i-1],G[i][j][k],INF);
            }
            int now=min(tr[i-1].mx[1]+a[i][j],INF);
            tr[i].update(1,1,ni[i],j,now);
            for(int k=1;k<=cnt;++k)
                tr[i-1].update(1,1,ni[i-1],pre[k].fi,pre[k].se);
        }
    }
    int ans=tr[4].mx[1];
    if(ans==INF)cout<<-1<<"\n";
    else cout<<ans<<"\n";
    return 0;
}

F.Ones （阴间数位DP,题解都看不懂，待补）

G.String Counting

题意：有c1个a，c2个b，…，c26个z。

用这些字母构造出一个长度为n的字符串，使得不存在长度>=3的奇回文子串。

输出方案数

保证对于输入的所有ci来说，ci>n/3都成立。

思路：首先考虑没有个数限制，就是个组合计数问题/dp， d p [ i ] [ j ] [ k ] dp[i][j][k] dp[i][j][k]表示前i个，倒数第二个为j,倒数第一个为k，暴力转移即可，其实就是第一第二个为26，后面*25

现在ci>n/3成立，由鸽巢原理，最多2种字母使用超限，想到容斥，用 a n s = 无 限 制 − ∑ 一 种 超 限 + ∑ 两 种 超 限 ans=无限制-\sum一种超限+\sum两种超限 ans=无限制−∑一种超限+∑两种超限

现在我们只关心最多2种字母的排列，将>=转化为=，在第一种情况下增加dp状态，字母与字母之间是等价的，

d p [ i ] [ j ] [ k ] [ f ] [ d ] dp[i][j][k][f][d] dp[i][j][k][f][d]表示前i个字母，有j个第一种字母，k个第二种字母，倒数两位分别为fd状态，0/1/2分别表示不是第一第二种，是第一种，是第二种，

转移有三种，同样是填0/1/2，但是注意的是填0的时候，前面两个实际上可以填24个，后面当f==0&&大于后面两个的时候，才是填23个

求出dp后，我们需要计算超限的，所以就对dp数组维护一个二维后缀和,将=转为>=

s u m [ i ] [ j ] sum[i][j] sum[i][j]表示第一种字母大于等于i个，第二种大于等于j个方案数

s u m [ i ] [ j ] = s u m [ i + 1 ] [ j ] + s u m [ i ] [ j + 1 ] − s u m [ i + 1 ] [ j + 1 ] sum[i][j]=sum[i+1][j]+sum[i][j+1]-sum[i+1][j+1] sum[i][j]=sum[i+1][j]+sum[i][j+1]−sum[i+1][j+1]

然后容斥一下即可

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
const int mod=998244353;
int t,n,c[27],dp[2][405][405][3][3],sum[405][405];
//最多2个超限制下前i个字母j个第一个k个第二个，倒数第二个和倒数第一个状态分别为0/1/2
void add(int&x,int y){
    x+=y; if(x>=mod)x-=mod;
}
void sub(int&x,int y){
    x-=y;if(x<0)x+=mod;
}
int main(){ 
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=0;i<26;++i)cin>>c[i];
    dp[0][0][0][0][0]=1;
    int now=0;
    for(int i=0;i<n;++i){
        now^=1;
        for(int j=0;j<=i;++j)
            for(int k=0;k+j<=i;++k)
                for(int f=0;f<3;++f)
                    for(int d=0;d<3;++d)
                        dp[now][j][k][f][d]=0;
        for(int j=0;j<=i;++j)
            for(int k=0;k+j<=i;++k){
                for(int f=0;f<3;++f)
                    for(int d=0;d<3;++d){
                        if(!dp[now^1][j][k][f][d])continue;//当前0
                            add(dp[now][j][k][d][0],1ll*dp[now^1][j][k][f][d]*(f==0&&i>=2?23:24)%mod);
                        if(f!=1)//当前1
                            add(dp[now][j+1][k][d][1],dp[now^1][j][k][f][d]);
                        if(f!=2)//当前2
                            add(dp[now][j][k+1][d][2],dp[now^1][j][k][f][d]);
                    }
            }
    }
    for(int j=0;j<=n;++j)
        for(int k=0;k+j<=n;++k)
            for(int f=0;f<3;++f)
                for(int d=0;d<3;++d)
                    add(sum[j][k],dp[now][j][k][f][d]);
    //二维后缀和
    for(int i=n;i>=0;--i)
        for(int j=n;j>=0;--j){
            add(sum[i][j],sum[i+1][j]);
            add(sum[i][j],sum[i][j+1]);
            sub(sum[i][j],sum[i+1][j+1]);
        }
    int ans=1;
    for(int i=0;i<n;++i){
        if(i<2)ans=1ll*ans*26%mod;
        else ans=1ll*ans*25%mod;
    }
    for(int i=0;i<26;++i){//容斥
        sub(ans,sum[c[i]+1][0]);
    }
    for(int i=0;i<26;++i)
        for(int j=i+1;j<26;++j)
            add(ans,sum[c[i]+1][c[j]+1]);
    cout<<ans<<"\n";
    return 0;
}
上一篇：你还在用 Date？建议使用 LocalDateTime 了！


下一篇：mybatis-缓存1