Codeforces Round #786 (Div. 3) ABCDE

https://codeforces.com/contest/1674/problem/A

题目大意：给定两个数x和y，问我们能否得出a，b（a表示相乘的次数，b表示和x相乘，如果可以通过x*b相乘a次得到y，那么就可以输出a b,否则输出0 0）

input

3
3 75
100 100
42 13

output

2 5
3 1
0 0

简化思维，x能否被y整除即可，可以的话一次性整除完

不可以的话就是0

特判一下当x>y的时候也是0 

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
using namespace std;
int aa[200200];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        int a,b;
        cin>>a>>b;
 
        int x=0,y=0;
        if(a>b) cout<<x<<" "<<y<<endl;
        else if(a==b) cout<<"1 1"<<endl;
        else
        {
            if(b%a==0)
            {
                cout<<"1 "<<b/a<<endl;
            }
            else cout<<x<<" "<<y<<endl;
        }
    }
    return 0;
}

https://codeforces.com/contest/1674/problem/B

题目大意：伯兰语是由一个字符串两个小写英文字母构成的，两个英文字母不能相同。这些单词是按照他们在字典中的顺序进行排列的，第一个就是ab，第二个ac以此类推。

给定我们若干个伯兰语，问我们他们的索引是啥？也就是指第几个的意思。

input

7
ab
ac
az
ba
bc
zx
zy

out

1
2
25
26
27
649
650

这样想，英文字目一共有26个，不能有重复的，所以s[0]一旦发生变化，前面为25的倍数；

当记录当前s[0]和s[1]的位置的情况时，要考虑一下是s[1]在不在s[0]的前面。

因为受到相等位置的影响。

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
using namespace std;
int aa[200200];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        int sum=(s[0]-'a')*25;
        if(s[1]-'a'>s[0]-'a') sum+=s[1]-'a';
        else sum+=s[1]-'a'+1;
        cout<<sum<<endl;
    }
    return 0;
}

https://codeforces.com/contest/1674/problem/C

题目大意：给定一个字符串s，仅由字母' a '组成，和一个字符串t，由小写字母组成。

在一次移动中，可以用字符串t替换字符串s中的任何字母“a”。（在替换后的字符串s可能包含除“a”以外的字母），可以执行任意次数的移动(包括零次)。问能获得多少不同的字符串？

如果无限数量输出-1

input

3
aaaa
a
aa
abc
a
b

output

1
-1
2

判断c中a的个数

以及思考s中的a可以变换的过程即可 

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
using namespace std;
int aa[200200];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        cin>>s;
        string c;
        cin>>c;
        if(c=="a") cout<<"1"<<endl;
        else
        {
            bool flag=true;
            for(int i=0;i<c.size();i++)
                if(c[i]=='a'&&c.size()>=2) flag=false;
            if(flag==false) cout<<"-1"<<endl;
            else
            {
                long long ti=s.size();
                long long sum=1;
                while(ti--)
                {
                    sum*=2;
                }
                cout<<sum<<endl;
            }
        }
    }
    return 0;
}

https://codeforces.com/contest/1674/problem/D

题目大意：给定3个数组a，b和c，最初，数组a由n个元素组成，数组b和c是空的。

执行两个步骤：

步骤1:当a不为空时，从a中取出最后一个元素，并将其移动到数组b的中间。如果b当前的长度为奇数，您可以选择:将a中的元素放在b中间元素的左侧或右侧。结果，a变为空，b由n个元素组成。
步骤2:当b不为空时，从b中取出中间的元素，并将其移动到数组c的末尾。如果b当前的长度为偶数，则可以选择两个中间元素中的哪一个。结果，b变成空的，c现在由n个元素组成。
问我们能不能让数组c按非降序（升序）排序？

input

3
4
3 1 5 3
3
3 2 1
1
7331

output

YES
NO
YES

 

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
using namespace std;
int a[200200];
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        vector<int> v;
        vector<int> ve;
        for(int i=n;i>=2;i-=2)
        {
            if(a[i]<a[i-1])
            {
                v.push_back(a[i]);
                ve.push_back(a[i-1]);
            }
            else
            {
                ve.push_back(a[i]);
                v.push_back(a[i-1]);
            }
        }
        //if(n%2==1) v.push_back(a[1]);
        reverse(v.begin(),v.end());
        reverse(ve.begin(),ve.end());
        /*
        for(int i=0;i<v.size();i++) cout<<v[i]<<" "; cout<<endl;
        for(int i=0;i<ve.size();i++) cout<<ve[i]<<" "; cout<<endl;
        */
        bool flag=true;
        int maxn=0;
        if(n%2==1) maxn=a[1];
        for(int i=0;i<v.size();i++)
        {
            if(v[i]>=maxn&&v[i]<=ve[i]) maxn=ve[i];
            else flag=false;
        }
        if(flag==true) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

https://codeforces.com/contest/1674/problem/E

题目大意：一堵连续长度为n的墙，第i段初始有耐久性ai。如果某一部分的耐久性变为0或更小，则该部分被视为破损。

要攻击对手，至少需要打破两段墙(任意两段:可能相邻，也可能不相邻)。有一种武器可以用来破坏墙壁的任何部分，这个射击对目标区域造成2点伤害，对邻近区域造成1点伤害。换句话说，如果、向x部分射击，那么x部分的耐久性减少2，而x1和x+1部分(如果存在)的耐久性各减少1。

问我们想要至少打破两个部分所需的最少次数？

 input

5
20 10 30 10 20

output

10

input

3
1 8 1

output

1

input

6
7 6 6 8 5 8

output

4

input

6
14 3 8 10 15 4

output

4

input

4
1 100 100 1

output

2

input

3
40 10 10

output

7 

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<string>
#include<cstdio>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int N=2002000;
int a[N],b[N];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]%2==1) b[i]=(a[i]+1)/2;
        else b[i]=a[i]/2;
    }
    sort(b+1,b+n+1);
    int sum=b[1]+b[2];//这一步是找到最极端情况下的最小步数
 
    for(int i=1;i<=n-1;i++)//两个两个一起找
    {
        int minn=min(a[i],a[i+1]);
        int maxn=a[i]+a[i+1]-minn;
        if(maxn>=minn*2) sum=min(sum,(maxn+1)/2);//如果想要消除这两个，那必须把大的消除了
        else sum=min(sum,(a[i]+a[i+1]+2)/3);
    }
    for(int i=2;i<=n-1;i++)//三个三个一起找
    {
        int maxn=max(a[i-1],a[i+1]);
        sum=min(sum,maxn);
        sum=min(sum,min(a[i+1],a[i-1])+((abs(a[i+1]-a[i-1])+1)/2));
    }
    cout<<sum<<endl;
    return 0;
}

期末考试终于结束了，奖励自己一场cf hh