AcWing周赛35

写在前面

排名：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,\dots,s_n$ 和 $c_1,c_2,\dots,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;
}