2020 计蒜之道 预赛 第一场

 A. 五子棋

思路：模拟题（考虑全面即可）

第一步：判断先手和后手，两棋子相差一定是≤1，当相等时，黑子x先走。

第二步：暴力判断每个空白处，填充相应棋子，能不能凑齐五子连珠。（横，竖，撇，捺）

说明：黑子先走，棋盘上只会出现黑子>=白子的情况（当时只考虑黑子先走，一首凉凉送给自己）

代码：

#include<stdio.h>
char Map[26][26];
bool dfs(int i,int j,char tmp){
    bool flag=false;
    int num=0;  //列
    for(int ii=i+1;ii<=25;ii++){
        if (Map[ii][j]==tmp) num+=1;
        else break;
        if (num==4) return true;
    }
    for(int ii=i-1;ii>=1;ii--){
        if (Map[ii][j]==tmp) num+=1;
        else break;
        if (num==4) return true;
    }
    num=0;  //行
    for(int jj=j+1;jj<=25;jj++){
        if (Map[i][jj]==tmp) num+=1;
        else break;
        if (num==4) return true;
    }
    for(int jj=j-1;jj>=1;jj--){
        if (Map[i][jj]==tmp) num+=1;
        else break;
        if (num==4) return true;
    }
    num=0;  //撇
    for(int ii=i-1,jj=j+1;ii>=1&&jj<=25;ii--,jj++){
        if (Map[ii][jj]==tmp) num+=1;
        else break;
        if (num==4) return true;
    }
    for(int ii=i+1,jj=j-1;ii<=25&&jj>=1;ii++,jj--){
        if (Map[ii][jj]==tmp) num+=1;
        else break;
        if (num==4) return true;
    }
    num=0;  //捺
    for(int ii=i-1,jj=j-1;ii>=1&&jj>=1;ii--,jj--){
        if (Map[ii][jj]==tmp) num+=1;
        else break;
        if (num==4) return true;
    }
    for(int ii=i+1,jj=j+1;ii<=25&&jj<=25;ii++,jj++){
        if (Map[ii][jj]==tmp) num+=1;
        else break;
        if (num==4) return true;
    }
    return false;
}
int main(){
    int x_num=0,o_num=0;
    for(int i=1;i<=25;i++){
        for(int j=1;j<=25;j++){
            scanf("%c",&Map[i][j]);
            if(Map[i][j]=='x') x_num+=1;
            if(Map[i][j]=='o') o_num+=1;
        }
        getchar();
    }
    char tmp=(x_num<=o_num)?'x':'o';//当前不可能出现已经胜利的一方,如果棋盘上的棋子一样，则x先，否则的话谁少谁先。
    int flag=1;
    for(int i=1;i<=25;i++){
        for(int j=1;j<=25;j++){
            if (Map[i][j]=='.'){  //这个点开始能不能五个
                if(dfs(i,j,tmp)){
                    printf("%d %d\n",i-1,j-1);
                    flag=0;
                }
            }
        }
    }
    if(flag==1) printf("tie\n");
}
           

B. 染色（简单）

思路：

第一步：首先很明确，修改的区间不会出现交叉，难度大大降低

第二步：在不替换的情况下，每个点肯定涂黑和白最大值，并计算出前缀和（Max_sum）

第三步：全涂黑色，需要计算一个前缀和，全图白色需要计算一个前缀和（能快速求出某一段的值）（aa和bb）

第四步：根据m组替换规则，计算要不要替换。

不替换的某一段的值为：Max_sum[e]-Max_sum[s-1]

替换的某一段的值为：xx[e]-xx[s-1]+t  (xx为aa或bb)

注意哈：[s,e]区间=（前e项和）-（前s-1项和）

代码：

#include<stdio.h>
long long int aa[300005];
long long int bb[300005];
long long int Max[300005];
long long int Max_sum[300005];
int main()
{
    long long int n,m,tmp;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&tmp);
        aa[i]=aa[i-1]+tmp;
        Max[i]=tmp;
    }
    for(int i=1;i<=n;i++){
        scanf("%lld",&tmp);
        bb[i]=bb[i-1]+tmp;
        if (tmp>Max[i]) Max[i]=tmp;
        Max_sum[i]=Max_sum[i-1]+Max[i];
    }
    long long int ans=Max_sum[n];
    for(int i=1;i<=m;i++){
        long long int x,s,e,t;
        scanf("%lld%lld%lld%lld",&x,&s,&e,&t);
        if (x==2){
            if(bb[e]-bb[s-1]+t>Max_sum[e]-Max_sum[s-1])
                ans=ans-(Max_sum[e]-Max_sum[s-1])+bb[e]-bb[s-1]+t;
        }else{
            if(aa[e]-aa[s-1]+t>Max_sum[e]-Max_sum[s-1])
                ans=ans-(Max_sum[e]-Max_sum[s-1])+aa[e]-aa[s-1]+t;
        }
    }
    printf("%lld\n",ans);
}