Codeforces补题 (持续更新，还没补完，呜呜呜)

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

题目大意：

你有两种类型的硬币，分别是1元，2元的硬币，现在你有a枚1元硬币，b枚2元硬币，请问你最小不能凑出的钱数是多少？

思路:

我们按照先考虑用1元硬币来凑，我们可以凑出[1,a]这个区间的所有钱，然后我们考虑用2元硬币来凑,我们可以凑出[2,2b]区间的钱，然后我们再考虑两种硬币一起用:我们考虑两种硬币最大能凑出多少钱:2b+a,那我们是否可以证明从[1,2b+a]的所有数都能凑出来呢，首先如果a=0，那么答案显然是1，因为我们没有1元的硬币，那我们再考虑再a!=0的情况下证明一下 是不是通过两种硬币的组合都可以可以凑出[1,2b+a] 的钱数,这样我们最小不能凑出的钱数就是2b+a+1

1+1*2,1+2*2,......1+2*b
2+1*2,2+2*2.......2+2*b
..... 
......
a+1*2...................a+2*b

我们发现对于任意a枚硬币我们都可以选择任意b枚硬币和它组合，上诉区间全部求并集之后，一定是[1,2b+a]，尽管里面区
间可能有重复，但这个区间的所有数都可以凑出来,故最小凑不出来的钱数就是2b+a+1

代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int tt;
    cin>>tt;
    while(tt--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        //凑不出来最小的数
        if(!a)printf("1\n");
        else printf("%d\n",a+b*2+1);
    }
    return 0;
}

B

题目大意：

思路:

代码:

C

题目大意：

思路:

代码:

D

题目大意：

思路:

代码:

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

题目大意：

给你一个01矩阵，你可以任意循环移动一行一列，使得矩阵发生变换，然后你可以对矩阵中的元素进行异或操作，就是可以把0变1，1变0，现在问你要把这个矩阵变成一个主对角线上都是1，其余地方都是0的矩阵，最少操作次数是多少

思路:

我们发现对于任意循环移动行和列，我们所有可以变换的矩阵种类其实相当于把原矩阵复制三次，然后拼成一个(2n2n) 的大矩阵,然后从这个大矩阵中选一个(nn)的矩阵都是经过变换得到的矩阵，如图所示

然后我们来看看如何计算我们的操作次数，首先我们设矩阵大小是n*n,
其中矩阵中1的个数是ans,矩阵中主对角线中1的个数是res，
由于我们最后要让对角线上的元素全变成0,那我们对角线上的元素是n,
主对角线中1的个数是res,故在对角线需要操作的次数是n-res,
然后我们考虑主对角线外的元素,由于矩阵中1的个数是ans, ans-res就是不在对角线上的1， 所以我们在主对角线外要修改的1的个数就是ans-res,因为矩阵是01矩阵，所以我们只要把对角线外的1改成0，对角线上的0改成1就可以了

所以我们的操作次数就是: n+ans-2*res ,所以要结果最小，n,ans是不变，唯一变的是对角线上1的个数，即res,，所以我们只要通过变换使得对角线上1的个数最多即可

那么关键是怎么找到矩阵变换过程中对角线上元素的变换，通过模拟我们发现，这些所有的变换过程，对角线上的元素都是取自不同行不同列的元素，具体看图:

代码:

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef pair<int,int>PII;
typedef long long LL;
const int N=2e5+10;
const int mod=1e9+7;
const int inf=1e9;  //正无穷 
const int fnf=-1e9;  //负无穷
int g[2010][2010];
int main()
{
    int tt;
    cin>>tt;
    while(tt--)
    {
        int n;
        int ans=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)scanf("%1d",&g[i][j]),ans+=g[i][j]; //记录1的个数

        int res=0;
        for(int i=0;i<n;i++)  //枚举所有变换可能出现的对角线情况，统计其中1的个数
        {
            int cnt=0;
            for(int j=0;j<n;j++)
            {
                cnt+=g[j][(i+j)%n];
            }
            res=max(res,cnt);
        }
        cout<<n+ans-2*res<<endl;
    }
    return 0;
}