AcWing周赛35

2022年2月13日 下午10:28 比赛总结 , , ,

写在前面

排名667/2346
过题数1/3
1.22打的周赛,现在(2.13)才写,鸽了好久了哈哈哈,没事,现在补也为时不晚hh
寒假归来好像第一次认真打周赛,这次当时只做出了一个题,第二题因为初始最大值没有设置好,用了自己的qq号...实际上$1000\times1000\times1000$可比qq号$834290867$大多了...第三题确实妙,甚至值得重开一篇写,我还是写在总结上了吧,降了一个时间复杂度

A.字符串比较(签到)

题意

题目链接:AcWing 4212. 字符串比较 - AcWing

给定两个长度相等的由大小写英文字母构成的字符串 A 和 B。
请你按照字典顺序对这两个字符串进行比较。
注意,在进行比较时,字母的大小写无关紧要,即大写字母被认为等同于相应的小写字母。

思路

签到题,注意解决一下大小写就好了,我还是不怎么习惯用函数,还是数组循环判断吧

代码

inline void Case_Test()
{
    cin>>s1>>s2;
    for (auto &i:s1)
        if (i>='a') i=char(i-32);
    for (auto &i:s2)
        if (i>='a') i=char(i-32);
    if (s1>s2) cout<<1;
    else if (s1==s2) cout<<0;
    else cout<<-1;
}

B.最小结果(搜索)

题意

题目链接:AcWing 4213. 最小结果 - AcWing
给出四个数a,b,c,d和3个符号op1,op2,op3,每次选出两个数依次进行op1,op2,op3操作,然后结果放进去,最后得到的答案最小是多少。
数据范围:$1\leq a,b,c,d\leq 1000$

思路

这个题只有四个数,直接搜索,对于OI选手来说搜索一定打得好,毕竟可以骗分,打暴力,卡时什么的...说远了,这个就直接模拟出所有的情况即可,我是将一个数组开8位,前四位是读入的,然后计算的结果放在后面3位里面
具体的看代码吧

代码

inline void dfs(int x)
{
    if (x==3) 
    {
        ans=Min(ans,a[7]);//ans注意一开始要大,不能是qq号呀!
        return;
    }
    for (int i=1;i<=3+x;i++)//3+x体会一下为什么,第一次x=0的时候,第一个数只能在[1,3]里面选
    {
        if (vis[i]) continue;
        for (int j=i+1;j<=4+x;j++)//同上,第二个数只能在[2,4]里面选
        {
            if (vis[j]) continue;//用过的肯定不能用了
            vis[i]=1;vis[j]=1;
            if (op[x+1]=='*')
                a[4+x+1]=a[i]*a[j];
            else
                a[4+x+1]=a[i]+a[j];
            dfs(x+1);
            vis[i]=0;vis[j]=0;//回溯
        }
    }
}

inline void Case_Test()
{
    for (int i=1;i<=4;i++) cin>>a[i];
    for (int i=1;i<=3;i++) cin>>op[i];
    dfs(0);
    cout<<ans;
}

C.三元组(思维+枚举)

题意

题目链接:AcWing 4214. 三元组 - AcWing

给定两个长度为 $n$ 的整数序列 $s_1,s_2,…,s_n$ 和 $c_1,c_2,…,c_n$。
请你找到一个三元组 $(i,j,k)$,满足以下所有条件:
$i<j<k$
$s_i<s_j<s_k$
$c_i+c_j+c_k$ 尽可能小
输出 $c_i+c_j+c_k$ 的最小可能值。

思路

这样一看这个题,首先来思考一下暴力的想法,首先循环i枚举下标为i的,然后j枚举下标为j的,同理还有k,然后if判断是否满足这三个条件,如果满足的话我们进行对ans的更新,比赛的时候我就不会了,毕竟我的算法是暴力的...时间复杂度是$O(n^3)$的...
正解
我们首先用一个指针来枚举三元组中间的那个j,这样的话i和k就被切成两半了,这个时候再去枚举i和j,这个时候的时间复杂度是$O(n^2)$的,这有什么好处呢?因为我们统计的是$c_i+c_j+c_k$,我们枚举j就已经确定了$c_j$,这个时候要求总体最小的话,我们就要求$c_i$和$c_k$分别是他们的最小就好了,当然了,要满足$s_i<s_j<s_k$这个条件

代码

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++) cin>>s[i];
    for (int i=1;i<=n;i++) cin>>c[i];
    for (int i=2;i<n;i++)//上述的枚举j,三元组中间的那个数
    {
        min1=min2=inf;
        for (int j=1;j<=i;j++) 
            if (s[i]>s[j])
                min1=Min(min1,c[j]);//分别最小
        for (int j=i+1;j<=n;j++) 
            if (s[i]<s[j])
                min2=Min(min2,c[j]);//分别最小
        ans=Min(ans,c[i]+min1+min2);//统计ans
    }
    if (ans==inf) cout<<-1;
    else cout<<ans;
}

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注