ABC135做题记录

Code

创建时间:2019-07-28 00:00

字数:1.3k 阅读:

评论:

ABC135做题记录

A-Harmony

题意：

给你两个整数A，B要求要到一个数K，使得$|A-K|=|B-K|(A!=B)$，不存在时输出“IMPOSSIBLE”（没有引号）

分析：

简单化简得到$2K=A+B$或$A=B$（舍）

所以$ K=\cfrac{A+B}{2}$ 因为$K\in N$所以$ A+B $ 要是偶数，特判一下

复杂度：时间$O(1)$空间$O(1)$

代码：

#include<bits/stdc++.h>

int main()
{
    int a,b;
    cin>>a>>b;
    if ((a&1)!=(b&1))//无解
    {
        cout<<"IMPOSSIBLE";
    }else//有解
    {
        cout<<(0LL+a+b)/2;
    }
    return 0;
}

B-0 or 1 Swap

题意：

给你一个序列，判断是否最多交换任意两个元素一次，使序列变为升序，可以输YES,不可以输出NO

分析：

本题数据范围小$ n<100 $

暴力枚举交换的两个元素，直接交换，判断是否升序，如果一开始就有序，直接输出。

复杂度：时间$O(n^3)$空间$O(n)$

代码：

#include <Header.hpp>

int main()
{
    int n;
    io >> n;
    vector<int> a(n);
    io >> a;
    if (is_sorted(a.begin(), a.end()))//学会使用STL
    {
        io.WL("YES");
        return 0;
    }
    else
    {
        //暴力枚举
        for (int i = 0; i < n; i++)
        {
            for (int j = i + 1; j < n; j++)
            {
                swap(a[ i ], a[ j ]);
                if (is_sorted(a.begin(), a.end()))
                {
                    io.WL("YES");
                    return 0;
                }
                swap(a[ i ], a[ j ]);//别忘了还原
            }
        }
    }
    //无解
    io.WL("NO");
    return 0;
}

C-City Saver

题意：

给你$N+1$座城市，$N$个超级英雄，第$a_i$个超级英雄可以打败第$i$和$i+1$座城市中的怪物，最多$b_i$个

分析：

~~贪心一波走起~~

事实上就是贪心，第$i$个英雄优先打第$i$座城市中的怪物，如果有多余，再去打第$i+1$座的

很容（lan）易（de）证明，略去。

复杂度：时间$O(n)$空间$O(n)$

代码：

#include<Header.hpp>

int main()
{
    int n;
    io>>n;
    vector<int> a(n+1),b(n);
    io>>a>>b;
    int64_t ans=0;//1e9*1e5会爆int,因为这个WA了一次，哭瞎
    for (int i=0;i<n;i++)//显然贪心
    {
        if (b[i]<=a[i]) ans+=b[i];
        else
        {
            ans+=a[i];
            int t = b[i]-a[i];
            ans+=min(a[i+1],t);
            a[i+1]-=min(a[i+1],t);
        }
    }
    io<<ans;
    return 0;
}

D-Digits Parade

题意：

给你一个字符串，包含0~9,和？，在？中填入0~9，使组成的数模13余5(可以有前导零)

分析：

~~显然数位DP~~没有那么显然啦

我们发现13这个数很小，但是n很大，有$10^5$因此从13入手

令$dp_{ij}$表示当前考虑到第$i$位，这一位余$j$的方案数

因为涉及到取模，倒推有点麻烦，因此我们正着推
dp[i+1][(j*10+k)%13]+=dp[i][j]

复杂度：时间$O(n)$空间$O(n)$

代码：

#include<Header.hpp>
const int MAXN=2e5;
const int MOD=1e9+7;
int dp[MAXN][13];
int main()
{
    string s;
    io>>s;
    int n=s.size();
    dp[0][0]=1;\\初始值
    for (int i=0;i<n;i++)
    {
        if (s[i]!='?')\\不是问号
        {
            int t=s[i]-48;
            for (int j=0;j<13;j++)
            {
                dp[i+1][(j*10+t)%13]=(dp[i][j]+dp[i+1][(j*10+t)%13])%MOD;
            }
        }else\\是问号
        {
            for (int j=0;j<13;j++)
            {
                for (int k=0;k<10;k++)\\枚举0~9
                {
                    dp[i+1][(j*10+k)%13]=(dp[i+1][(j*10+k)%13]+dp[i][j])%MOD;
                }
            }
        }
    }
    io<<dp[n][5];\\输出余5
    return 0;
}

E-Golf

不会，咕了

F-Strings of Eternity

给你两个字符串$s$和$t$

问在$s$重复$j$遍时，是否有一个子串，使得$t$重复$i$次能得到这个子串，

求$i$的最大值，如果$i$没有最大值（最大值为无限大），那么输出-1

分析：

一眼看上去，KMP

然而调了好久没调出来

经过一天的认真分析，写了出来

其实还可以Hash，Z-algorithm，但是本蒟蒻不会啊（事实上这个代码比哈希跑的快）

复杂度：时间$O(max(|s|,|t|))$ 空间$O(max(|s|,|t|))$

#include <Header.hpp>
const int MAXN = 1e7;
template <typename ContainerT = string>
struct KMP
{
    int  fail[ MAXN ], pre[ MAXN ];
    void failure(ContainerT s)
    {
        int j     = -1;
        fail[ 0 ] = -1;
        for (int i = 0; i < s.size(); i++)
        {
            while (j >= 0 && s[ i ] != s[ j ]) j = fail[ j ];
            j++;
            fail[ i + 1 ] = j;
        }
    }
    bool match(ContainerT s, ContainerT t)
    {
        int j    = 0;
        pre[ 0 ] = 0;
        for (int i = 0; i < s.size(); i++)
        {
            while (j == t.size() || (j >= 0 && s[ i ] != t[ j ])) j = fail[ j ];
            j++;
            pre[ i + 1 ] = j;
        }
        return 0;
    }
};
KMP<> kmp;
//以上为KMP板子
string expand(string s, const string &t)
{
    string ns = s;
    while (ns.size() < t.size()) ns += s;
    ns += ns;
    ns += ns;
    return ns;
}
int dp[ MAXN ];
int main()
{
    string s, t;
    io >> s >> t;
    s = expand(s, t);//延长串s，使得它至少为t的两倍长。保险起见，我开到了4倍
    kmp.failure(t);/*失配函数*/
    kmp.match(s, t);/*匹配*/
    int n = s.size(), m = t.size();
    /* for (int i=1;i<=n;i++)
    {
        io.WS(kmp.pre[i]);
    }
    io.WL(); */
    for (int i = 0; i <= n; i++)
    {
        //用一个一维DP记录以i为终点的重复次数最大值
        if (kmp.pre[ i ] == m) dp[ i + m ] = dp[ i ] + 1;
    }
    int ans = (*max_element(dp, dp + 1 + n));
    s += s;//再次扩展
    n = s.size();
    kmp.match(s, t);
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= n; i++)
    {
        if (kmp.pre[ i ] == m) dp[ i + m ] = dp[ i ] + 1;
    }
    int tans = (*max_element(dp, dp + 1 + n));
    if (tans > ans)//如果答案变多了，那么说明可以无限延长，因此输出-1
        io.WL(-1);
    else
        io.WL(ans);
    return 0;
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 alphagocc[at]163[dot]com