首页 > 其他分享 >Acwing.第123场周赛

Acwing.第123场周赛

时间:2023-10-06 09:01:28浏览次数:44  
标签:语句 周赛 测试点 int 整数 123 long dp Acwing

Acwing.第123场周赛

比赛链接

回家休息了五天调整好状态继续出发!!!!

A.队列

一共有三个队列,当前分别已有 a,b,c个人。
现在有 n个人尚未进队,每个人都需要被安排到一个队列当中。
为了队形整齐,我们希望所有人被安排进队后,三个队列包含的人数均相等。
请你判断,是否可能做到。
输入格式
第一行包含整数 T,表示共有 T 组测试数据。
每组数据占一行,包含四个整数 a,b,c,n。
输出格式
每组数据输出一行结果,如果能做到,则输出 YES,否则输出 NO。
数据范围
前 3个测试点满足 1≤T≤5。
所有测试点满足 1≤T≤104,1≤a,b,c,n≤108。

思路

一开始思路有点误区,以为求个总和能被3整除就行,事实上之前分好的人是不允许再进入其他队列当中的!

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve(){
    int a,b,c,n;
    cin>>a>>b>>c>>n;
    int ans=0;
    ans+=a+b+c+n;
    if(ans%3){
        cout<<"NO"<<endl;

    }
    else{
        int maxn=max(max(a,b),c);
        int cha=maxn-a+maxn-b+maxn-c;
        if(cha>n){
            cout<<"NO"<<endl;
        }
        else{
            if((n-cha)%3){
                cout<<"NO"<<endl;
            }
            else{
                cout<<"YES"<<endl;
                
            }
        }

    }
    return ;
    
}
int main(){
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;

}

B.合格数

给定 n个整数区间,其中第 i个区间为 [li,ri]。
如果一个整数被至少 k个给定区间所包含,就称这个整数为合格数。
你需要回答 q个问题。
第 i个问题给定两个整数 a,b,请你计算 [a,b]范围内有多少个合格数。
输入格式
第一行包含三个整数 n,k,q。
接下来 n行,每行包含两个整数 li,ri,表示一个给定区间。
接下来 q行,每行包含两个整数 a,b,用来描述一个问题。
输出格式
每个问题输出一行结果,一个整数,表示 [a,b]范围内合格数的数量。
数据范围
前 4个测试点满足 1≤k≤n≤5,1≤q≤5。
所有测试点满足 1≤k≤n≤2×105,1≤q≤2×105,1≤li≤ri≤2×105。

思路

是一个比较简单的差分与前缀和的综合,倒是也不难,看到区间应该就可以想到。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;
int a[N];
int c[N];
int ans[N];

void solve(){
    int n,k,q;
    cin>>n>>k>>q;
    while(n--){
        int l,r;
        cin>>l>>r;
        a[l]+=1;
        a[r+1]-=1;

    }
    for(int i=1;i<=N;i++){
        c[i]=c[i-1]+a[i];
    }
    for(int i=1;i<=N;i++){
        if(c[i]<k){
            c[i]=0;
        }
        else{
            c[i]=1;

        }
    }
    for(int i=1;i<=N;i++){
        ans[i]=ans[i-1]+c[i];
    }
    while(q--){
        int l,r;
        cin>>l>>r;
        cout<<ans[r]-ans[l-1]<<endl;
        ;

    }

}
int main(){
    int t=1;
    while(t--){
        solve();
    }
    return 0;

}

C.Python缩进

在 Python 中,代码块没有显式的开始/结束或大括号来标记代码块的开始和结束。
相反,代码块是通过缩进定义的。
我们考虑一个极其简化的 Python 子集,其只有两种类型的语句:简单语句和 For语句。
简单语句(Simple statements)仅占一行,每行一个。
For语句(For statements)是复合语句:它们包含一个或多个其它语句。For语句由循环头和循环体共同组成。循环头是一个以 for开头的单独行。循环体是比循环头缩进一级的语句块。循环体可以包含两种类型的语句。循环体不能为空。
给定 n个没有缩进的语句,请你计算,通过合理缩进,一共可以形成多少个不同的有效 Python 代码。
输入格式
第一行包含整数 n。
接下来 n行,每行包含一个字符 f(表示 For语句)或 s (表示简单语句),用来描述一行给定语句的类型。
保证最后一行一定是简单语句。
输出格式
一个整数,表示可以形成的不同有效 Python 代码的数量对 109+7取模后的结果。
数据范围
前 3个测试点满足 1≤n≤5
所有测试点满足 1≤n≤5000

思路

读题就会发现这个和明显是一个dp问题,给出的每一条语句都和上一条语句有关系
如果上条语句是f,那么当前语句只能缩进不能出现并列的情况,所以

\[dp[i][j]=dp[i-1][j-1] \]

如果上条语句是s,那么他既可以与上条语句并列出现,也可以比任意级语句并列

\[dp[i][j]=dp[i-1][j]+dp[i][j+1] \]

最后求和取模就好了

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+7;
const int N=5010;
char a[N];
int dp[N][N];
void solve(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }  
    dp[1][0]=1;
    for(int i=2;i<=n;i++){
        for(int j=i-1;j>=0;j--){
            if(a[i-1]=='f'){
                if(j){
                    dp[i][j]=dp[i-1][j-1];
                }
            }
            else dp[i][j]=(dp[i-1][j]+dp[i][j+1])%mod;
        }
    }
    int ans=0;
    for(int i=0;i<n;i++){
        ans=(ans+dp[n][i])%mod;
    }
    cout<<ans<<endl;
    
}
int main(){
    int t=1;
    while(t--){
        solve();
    }
    return 0;

}

标签:语句,周赛,测试点,int,整数,123,long,dp,Acwing
From: https://www.cnblogs.com/du463/p/17744228.html

相关文章

  • 123木头人
    html+css入门:html入门教程_html教程-CSDN博客HTML+CSS小白入门与进阶教程-CSDN博客......
  • AcWing_1_1_785_快速排序
    一、题目描述给定你一个长度为n的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。输入格式输入共两行,第一行包含整数n。第二行包含n个整数(所有整数均在\(1∼10^9\)范围内),表示整个数列。输出格式输出共一行,包含n个整数,......
  • 1113123131
    //#include<bits/stdc++.h>//usingnamespacestd;//intmain(){// inta,b,c;// scanf("%d%d%d",&a,&b,&c);// cout<<setw(8)<<a<<""<<setw(8)<<b<<""<<setw(8)<<......
  • CF1234(Div. 3) 题解(A to E)
    AEqualizePricesAgain题解题目大意\(n\)个商品,每个商品价格为\(a_i\),求一个最小的价格\(x\),使得不亏本(即\(\sum\limits_{i=1}^n{(a_i-x)}\ge0\))。解题思路输出平均数向上取整(即\(\left\lceil(\sum\limits_{i=1}^n{a_i})\divn\right\rceil\))即可。代码#include<bit......
  • 以下是一个比较复杂的R语言代码示例: ```R # 生成随机数 set.seed(123) data <- rnorm
    以下是一个比较复杂的R语言代码示例:#生成随机数set.seed(123)data<-rnorm(1000)#数据处理和分析data_mean<-mean(data)data_sd<-sd(data)data_median<-median(data)#创建一个绘图窗口par(mfrow=c(2,2))#绘制直方图hist(data,main="HistogramofDat......
  • LeetCode 周赛上分之旅 #49 再探内向基环树
    ⭐️本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]和BaguTreePro知识星球提问。学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场LeetCode周赛的解题报告,一......
  • AtCoder Regular Contest 123 F Insert Addition
    洛谷传送门AtCoder传送门用\((x,y)\)表示\(Ax+By\),那么这个等价于SB树。那么直接在SB树上二分,遍历一遍找到\(n\)个点就好了。可以采用类似线段树查询的方式。于是现在还剩下一个子问题:给定\(a,b\),求\(ax+by\len\)且\(\gcd(x,y)=1\)的正整数\((x,y......
  • AcWing 431. 守望者的逃离
    \(AcWing\)\(431\).守望者的逃离一、题目描述恶魔猎手尤迪安野心勃勃,他背叛了暗夜精灵,率领深藏在海底的娜迦族企图叛变。守望者在与尤迪安的交锋中遭遇了围杀,被困在一个荒芜的大岛上。为了杀死守望者,尤迪安开始对这个荒岛施咒,这座岛很快就会沉下去。到那时,岛上的所有人都会......
  • AcWing 414. 数字游戏
    \(AcWing\)\(414\).数字游戏一、题目描述丁丁最近沉迷于一个数字游戏之中。这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。游戏是这样的,在你面前有一圈整数(一共\(n\)个),你要按顺序将其分为\(m\)个部分,各部分内的数字......
  • 砝码123456
    法玛三因子模型(Fama-FrenchThree-FactorModel)是一种资本资产定价模型(CapitalAssetPricingModel,CAPM)的扩展,用于解释股票回报的变异性。该模型由尤金·法玛(EugeneFama)和肯尼斯·法rench(KennethFrench)于1992年提出。该模型考虑了三个因子对股票回报的影响:市场风险因子、市值......