错题报告

得分情况

T1：100/100

T2：100/100

T3：100/100

T4：0/100

T5：0/100

T1

100分

T2

100分

T3

100分

T4

正确代码：

#include<iostream>
using namespace std;
const int N = 100010;
int a[N];
int sum[N];
int n,k;
int res[N];
int main()
{
    cin>>n>>k;
    long long ans = 0;
    res[0]=1;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
        sum[i]%=k;
        ans += res[sum[i]];
        res[sum[i]]++;
    }
    cout<<ans<<endl;

    return 0;
}

简析：前缀和，每次都需要找在模k的意义下，前面前缀和与当前前缀和相等的个数。所以 sum[b]-sum[a] 时 每次需要找在模k的意义下0- b-1 与当前相等的，由于计算
的时候是从sum[1]开始的，所以sum[0]也需要先添加进去。

T5

正确代码：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 15;
char map[N][N];
bool line[N][N],col[N][N],cell[3][3][N];
bool dfs (int x, int y) {
    if (y == 9) x++,y = 0;
    if (x == 9) {
        for (int i = 0;i < 9;i++)   cout << map[i] << endl;
        return true;
    }
    if (map[x][y] != '.')   return dfs(x,y + 1);
    for (int i = 1;i <= 9;i++) {
        if (!line[x][i] && !col[y][i] && !cell[x / 3][y / 3][i]) {
            map[x][y] = i + '0';
            line[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
            if (dfs(x,y + 1))   return true;
            line[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            map[x][y] = '.';
        }
    }
    return false;
}
int main () {
    for (int i = 0;i < 9;i++)  {
        cin >> map[i];
        for (int j = 0;j < 9;j++) {
            if (map[i][j] != '.') {
                int num = map[i][j] - '0';
                line[i][num] = col[j][num] = cell[i / 3][j / 3][num] = true;
            }
        }
    }
    dfs(0,0);
}

简析：line[i][num]表示第i行是否出现数字num;
col[j][num]表示第j列是否出现数字num;
cell[i][j][num]表示第i行j列小格子内是否出现数字num;
这样写可以避免繁杂的检查。dfs返回值设为bool类型可以在找到结果后快速退出

T6

正确代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

typedef long long LL;//防止爆掉int
const int N=1000010;

LL a[N],c[N];

int main()
{
    int n;
    cin>>n;

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

    LL sum=0;
    for(int i=0;i<n;i++) sum+=a[i];

    LL ave=sum/n;//求平均值

    for(int i=n-1;i>0;i--)
    {
        c[i]=c[i+1]+ave-a[i];//求每个坐标所对应的常数c
    }

    sort(c,c+n);//对常数c排序

    LL res=0;
    for(int i=0;i<n;i++) 
       res+=abs(c[i]-c[n/2]);//求数轴上每个点到中点的距离

    printf("%lld\n",res);

    return 0;
}