得分情況

A題AC
B題AC
C題TLE在樣例2
（題簡單，腦袋沒轉(zhuǎn)過彎來）

補(bǔ)題情況

全部AC

錯題分析

C題

題目大意

構(gòu)造一個n?n的矩陣，使得相鄰的兩個格子填的數(shù)不能相鄰。

初次思路

暴力枚舉。

正解思路

我們可以把奇偶分開填入矩陣，可知，除了2*2無解，別的情況都行。

正解代碼

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main(){int t;scanf("%d",&t);while(t--){int k=1;int n;scanf("%d",&n);if(n==1){printf("1\n");continue;}if(n==2){printf("-1\n");continue;}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){printf("%d ",k);k+=2;if(k>n*n){k=2;}}printf("\n");}}return 0;
}

錯誤原因

題意理解錯了。

D題

題目大意

給出T組序列a,長度為N,詢問有多少對$(i,j)$滿足$i<j$且$a_j?a_i=j?i$。

初次思路

暴力枚舉。

正解思路

將$a_j?a_i=j?i$變形為$a_j?j=a_i?i$,然后統(tǒng)計(jì)值與下標(biāo)的差，再用排列組合公式求出數(shù)量——$n?(n?1)/2$,最后求和。

正解代碼

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int vis[400005];
int main(){int t;scanf("%d",&t);while(t--){memset(vis,0,sizeof vis);int n;scanf("%d",&n);for(int i=1;i<=n;i++){int x;scanf("%d",&x);vis[x-i+n]++;}long long ans=0;for(int i=0;i<=2*n;i++){ans+=1ll*vis[i]*(vis[i]-1)/2;}printf("%lld\n",ans);}return 0;
}

錯誤原因

沒有想到對原式進(jìn)行變形。

E題

題目大意

一共有 t 組數(shù)據(jù)，每組數(shù)據(jù)第一行為 n ，為字符串長度，下一行為一個字符串（只有 ’ . ’ 和 ’ * '字符，每次可以向右或者向左移動 ‘ * ’ 字符，求把所有的 ’ * ’ 字符連起來的最小移動次數(shù)。

初次思路

暴力模擬。

正解思路

中間的羊是羊群的中心，因此讓羊往中心靠攏最優(yōu)，所以統(tǒng)計(jì)其它羊靠過來的距離最優(yōu)。

正解代碼

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int sheep[1000005];
int main(){int t;cin>>t;while(t--){long long n,cnt=0,step=0;string s;cin>>n>>s;for(int i=0;i<n;i++){if(s[i]=='*'){sheep[++cnt]=i;}}int mid=(1+cnt)/2;int len_left=1,len_right=1;for(int i=1;i<=cnt;i++){if(sheep[mid]>sheep[i]){step+=sheep[mid]-sheep[i]-len_left++;}if(sheep[mid]<sheep[i]){step+=sheep[i]-sheep[mid]-len_right++;}}cout<<step<<"\n";} return 0;
}

F1題

題目大意

交互題。給定 n,t,k（由于這里是簡單版，保證 t=1，即t沒啥用)，有一個長度為n的標(biāo)號為1?n 的僅含01的數(shù)組，你每次可以詢問l到r的和，需要得出數(shù)組中第k個0的下標(biāo)。最多詢問20次。

正解思路

可以用二分枚舉位置，通過詢問結(jié)果來判斷前面有多少個0，如果0的數(shù)量大于等于k，說明mid要變小，l=mid+1,反之，r=mid。

正解代碼

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int sheep[1000005];
int main(){int m,n,t;cin>>m>>t>>n;int l=1,r=m;while(l<r){int mid=(l+r)/2;cout<<"? "<<1<<" "<<mid<<"\n";cout.flush();int x;cin>>x;if(mid-x>=n){r=mid;}else{l=mid+1;}}cout<<"! "<<l;return 0;
}

G題

題目大意

給定一個n×m的網(wǎng)格，每個格子(i,j)都有一個整數(shù)參數(shù)$a_{ij}(?1<=a_{ij}<=10^9)$,$a_{ij}=?1$表示這個格子不能通過；否則，這個格子可以通過，若$a_{ij}>0$則表示這個格子內(nèi)有一個傳送門?，F(xiàn)在小D想要從(1,1)移動到(n,m)，它可以以如下兩種方式移動：在任意兩個相鄰且參數(shù)均不為?1的格子間移動，花費(fèi)為w,在有傳送門的兩個格子 (i,j)和(x,y) 間移動，花費(fèi)為$a_{ij}+a_{xy}$求小D所需的最小花費(fèi)。

正解思路

分類思考，一是不走傳送門，二是走一次傳送門，進(jìn)行兩次bfs，求出最終結(jié)果。

正解代碼

#include <bits/stdc++.h>
using namespace std;
int n,m,w;
int a[2010][2010],dis[2010][2010];
long long ans1=0x3f3f3f3f3f3f3f3f,ans2=0x3f3f3f3f3f3f3f3f,allans=0x3f3f3f3f3f3f3f3f;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
void bfs(int sx,int sy,long long &ans){memset(dis,-1,sizeof(dis));queue<pair<int,int> >que;dis[sx][sy]=0;que.push(make_pair(sx,sy));while(!que.empty()){int x=que.front().first,y=que.front().second;que.pop();for(int i=0;i<4;i++){int nx=x+dx[i],ny=y+dy[i];if(nx<1||ny<1||nx>n||ny>m||a[nx][ny]==-1||dis[nx][ny]!=-1){continue;}dis[nx][ny]=dis[x][y]+1;que.push(make_pair(nx,ny));}}if(sx==1&&dis[n][m]!=-1){allans=min(allans,(long long)dis[n][m]*w);}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(dis[i][j]!=-1&&a[i][j]>0){ans=min(ans,(long long)dis[i][j]*w+a[i][j]);}} }
}
int main(){scanf("%d%d%d",&n,&m,&w);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&a[i][j]);}}bfs(1,1,ans1);bfs(n,m,ans2);allans=min(allans,ans1+ans2);printf("%lld",allans==0x3f3f3f3f3f3f3f3f?-1:allans);return 0;
}