#780 dIV3

题目：

https://codeforces.com/contest/1660

A：

存在两种硬币，1费和2费；

给你1费，2费硬币的数量，让你求不能支付得起，或者不能找零的最小正整数

思路：

1费为a个，2费为b个

可分为三种情况：

1.只有2费硬币，没有1费硬币，那么1是不能找零的最小正整数

2.只有1费，没有2费，那么a+1是最小支付不起

3.都有，那么a+2*b+1 就是最小支付不起的

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=10010;

int t;

int main()
{
      cin>>t;

      while(t--)
      {
          int a,b;
          cin>>a>>b;

          if(a==0)
          {
              cout<<1<<endl;
              continue;
          }
          if(b==0)
          {
              cout<<a+1<<endl;
              continue;
          }

          cout<<a+b*2+1<<endl;

      }

    return 0;
}

B：

题目：

存在一组数字，每次我们让最大的数字减一，如果存在相同的最大数字，那么可以任意一个减一，如果不得不连续相同的数字减一，那么为NO

否则YES

思路：

排序 ，如果第一大和第二大的数字的差大于2 说明在刚开始只能连续减两次最大的数，不符合题意

如果第一次符合题意，那么之后我们每次都会选择最大的减一，那么最终我们都会将这一组数据都减为1。因为不存在会再次使相同的数字连续减1，如果都为1，那么无论是偶数个还是奇数个，都满足题意。

代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1000010;

int t;
int a[N];

bool bmp(int x,int y)
{
    return x>y;
}
int main()
{
      cin>>t;

      while(t--)
      {
          int n;
          cin>>n;

          for(int i=0;i<n;i++)
            cin>>a[i];

          sort(a,a+n,bmp);

          /*我们需要特判n==1的情况，因为此时，我们无法比较他和下面那个数字的大小，如果直接不特判我们想的是后面那个数字为0可以直接判断，但是因为每次a数组都会有上次的值，如果选择清空a数组会超时*/
          if(n==1&&a[0]>1)
          {
              cout<<"NO"<<endl;
              continue;
          }
          if(n==1&&a[0]<=1)
          {
              cout<<"YES"<<endl;
              continue;
          }

          if(a[0]-a[1]>=2)
          {
              cout<<"NO"<<endl;
              continue;
          }

          cout<<"YES"<<endl;

      }
    return 0;
}

C：

题目：给定一个字符串，让你把它变成由任意一个字母连续出现偶数次的情况下，删掉最少字母个数的值 变成aaccffbb这种

思路

直接考虑删掉最小字母的值不好计算，那么考虑留下最多字母，即是删掉最少字母

我们认为，两个相同的字符中间的值删除，是最优解

从前往后枚举字符串，如果这是一个字母出现两次，那么说明这俩字母可以留在我们想构造的字符串里面，那么两个字母中间的我们不考虑留在字符串里。然后n-我们字符串里面的值即是删除的值

代码:

#include<bits/stdc++.h>
using namespace std;

const int N=10010;

int n,t;
string str;
int tong[27];

int main()
{
    cin>>t;

    while(t--)
    {
        memset(tong,0,sizeof tong);

        cin>>str;
        int res=0;

        int n=str.size();

        for(int i=0;i<str.size();i++)
        {
            int num=str[i]-'a';
            tong[num]++;

            if(tong[num]==2)
            {
                res+=2;
                memset(tong,0,sizeof tong);

            }
        }

        cout<<n-res<<endl;

    }

    return 0;
}

D：

题目：

给你一个数组a, 所有a[i] 的绝对值都<=2 ，你可以从前缀删去a个数字，从后缀删去b个数字，问你删去之后乘积最大的情况时a和b的值，答案不唯一

思路：

如果使得剩下的数字最大，我们只考虑 0 和 负数 个数的情况

如果存在0那么如果留下一个0那么结果肯定是0

对于负数，如果他的个数是偶数，那么乘积肯定大于0，

如果是奇数，我们考虑删去一个数，使得变为偶数

所以我们不考虑数组留下0，然后记录0的位置，考虑把0当作数组的分割线，将数组分成一段段，

计算每一段的值，然后比较值

然后只需要考虑每段内的负数，偶数直接计算，

奇数分两种，从前往后删去第一个负数，从后往前删去第一个负数

然后比较

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int long long
const int N=200010;

int n,t;
int g0[N];
int a[N];
int mainn=-1e15-10; //这个一定要确保是最小的
int ans_l,ans_r;


//计算负数的数量
int fu_jo(int l,int r)
{
    int num=0;

    for(int i=l;i<=r;i++)
        if(a[i]<0)num++;

    return num;
}

//计算范围内的结果
void cj(int l,int r)
{
    int num=1;

    //因为n的值很大，所以最终结果可能很大甚至超过Long long
    for(int i=l;i<=r;i++)
    {
        if(num*a[i]>1e15)break; // 超过了我们都记为1e15
        num*=a[i];
    }
    if(num>=mainn)
    {
        mainn=num;
        ans_l=l,ans_r=r;       //每次计算数值，可以直接更新答案
    }
}

signed main()
{
      cin>>t;

      while(t--)
      {
          cin>>n;
          int  cnt=1;
          int maxx;

          g0[0]=0;  //我们给最后和最前都加上一个0，将数组变为 0....0...0  不用考虑边界问题

          for(int i=1;i<=n;i++)
          {
                cin>>a[i];
                if(a[i]==0)
                    g0[cnt++]=i;
          }
          g0[cnt]=n+1;

          for(int i=1;i<=cnt;i++)
          {
              int r=g0[i]-1,l=g0[i-1]+1;

              int fu_num=fu_jo(l,r);

              if(fu_num==0)
              {
                  cj(l,r);
              }else if(fu_num%2==0)
              {
                  cj(l,r);
              }else if(fu_num%2!=0)
              {
                  int wei=l;
                  while(a[wei]>0)wei++;
                  cj(wei+1,r);

                  wei=r;
                  while(a[wei]>0)wei--;

                  cj(l,wei-1);

              }

          }

          cout<<ans_l-1<<" "<<n-ans_r<<endl;

          mainn=-0x3f3f3f3f;  //一定要初始化数值
      }

    return 0;
}

E:

题目：

给定一个n*n的01矩阵，你可以进行四个操作

1.将所有行向上移动一位，第一行移动到最后一行

2向下，同理

3.所有列向左移动一位，第一列移动到最后一列

4.向右同理

与 和一个主对角线都是1的单位矩阵比 最少有多少个不同的地方

1000

0100

0010

0001

思路

假设我们最优构成的矩阵和单位矩阵1的个数最多，那么我们枚举单位矩阵可以从哪几个矩阵移动而来，然后从给出的矩阵中，枚举这几个矩阵的1的位置，找到1的最大值的矩阵

例：

1 0 0     0 1 0    0 0 1
0 1 0  >> 0 0 1  >>1 0 0
0 0 1     1 0 0    0 1 0

发现，每个子矩阵，都是由第一行开始，然后每次偏移i个单位

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
#define int long long
const int N=2010;

int n,t;
char m[N][N];
signed main()
{
      cin>>t;

      while(t--)
      {
          int n;
          cin>>n;

          int res=0;//1的个数
          int ans=0;//对角线上都存在1的个数
          for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
          {
              cin>>m[i][j];
              if(m[i][j]=='1')res++;
          }

          for(int i=0;i<n;i++)
          {//偏移量
              int ji=0;
             for(int j=1;j<=n;j++)  //行
             {
                int h=j;
                int l=j+i;
                l%=n;
                if(l==0)l=n;

                if(m[h][l]=='1')
                    ji++;

             }
             ans=max(ans,ji);

          }

          cout<<n+res-2*ans<<endl;
      }
    return 0;
}

F1:

F2: