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);
}