网站开发培训课程表,软件定制开发外包,中国能源建设集团有限公司招标网,江西省水文监测中心Codeforces Round 719 Div. 3 除F2题外补题报告 得分情况补题情况错题分析C题题目大意初次思路正解思路正解代码错误原因 D题题目大意初次思路正解思路正解代码错误原因 E题题目大意初次思路正解思路正解代码 F1题题目大意正解思路正解代码 G题题目大意正解思路正解代码 得分情… Codeforces Round 719 Div. 3 除F2题外补题报告 得分情况补题情况错题分析C题题目大意初次思路正解思路正解代码错误原因 D题题目大意初次思路正解思路正解代码错误原因 E题题目大意初次思路正解思路正解代码 F1题题目大意正解思路正解代码 G题题目大意正解思路正解代码 得分情况 A题AC B题AC C题TLE在样例2 题简单脑袋没转过弯来 补题情况 全部AC 错题分析
C题
题目大意 构造一个n∗n的矩阵使得相邻的两个格子填的数不能相邻。 初次思路 暴力枚举。 正解思路 我们可以把奇偶分开填入矩阵可知除了2*2无解别的情况都行。 正解代码
#includeiostream
#includecstdio
#includecstring
using namespace std;
int main(){int t;scanf(%d,t);while(t--){int k1;int n;scanf(%d,n);if(n1){printf(1\n);continue;}if(n2){printf(-1\n);continue;}for(int i1;in;i){for(int j1;jn;j){printf(%d ,k);k2;if(kn*n){k2;}}printf(\n);}}return 0;
}错误原因 题意理解错了。 D题
题目大意 给出T组序列a,长度为N,询问有多少对 ( i , j ) (i,j) (i,j)满足 i j ij ij且 a j − a i j − i a_j −a_i j−i aj−aij−i。 初次思路 暴力枚举。 正解思路 将 a j − a i j − i a_j −a_i j−i aj−aij−i变形为 a j − j a i − i a_j −j a_i−i aj−jai−i,然后统计值与下标的差再用排列组合公式求出数量—— n ∗ ( n − 1 ) / 2 n*(n-1)/2 n∗(n−1)/2,最后求和。 正解代码
#includeiostream
#includecstdio
#includecstring
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 i1;in;i){int x;scanf(%d,x);vis[x-in];}long long ans0;for(int i0;i2*n;i){ans1ll*vis[i]*(vis[i]-1)/2;}printf(%lld\n,ans);}return 0;
}错误原因 没有想到对原式进行变形。 E题
题目大意 一共有 t 组数据每组数据第一行为 n 为字符串长度下一行为一个字符串只有 ’ . ’ 和 ’ * 字符每次可以向右或者向左移动 ‘ * ’ 字符求把所有的 ’ * ’ 字符连起来的最小移动次数。 初次思路 暴力模拟。 正解思路 中间的羊是羊群的中心因此让羊往中心靠拢最优所以统计其它羊靠过来的距离最优。 正解代码
#includeiostream
#includestring
#includealgorithm
using namespace std;
int sheep[1000005];
int main(){int t;cint;while(t--){long long n,cnt0,step0;string s;cinns;for(int i0;in;i){if(s[i]*){sheep[cnt]i;}}int mid(1cnt)/2;int len_left1,len_right1;for(int i1;icnt;i){if(sheep[mid]sheep[i]){stepsheep[mid]-sheep[i]-len_left;}if(sheep[mid]sheep[i]){stepsheep[i]-sheep[mid]-len_right;}}coutstep\n;} return 0;
}F1题
题目大意 交互题。给定 n,t,k由于这里是简单版保证 t1即t没啥用)有一个长度为n的标号为1⋯n 的仅含01的数组你每次可以询问l到r的和需要得出数组中第k个0的下标。最多询问20次。 正解思路 可以用二分枚举位置通过询问结果来判断前面有多少个0如果0的数量大于等于k说明mid要变小lmid1,反之rmid。 正解代码
#includeiostream
#includestring
#includealgorithm
using namespace std;
int sheep[1000005];
int main(){int m,n,t;cinmtn;int l1,rm;while(lr){int mid(lr)/2;cout? 1 mid\n;cout.flush();int x;cinx;if(mid-xn){rmid;}else{lmid1;}}cout! l;return 0;
}G题
题目大意 给定一个n×m的网格每个格子(i,j)都有一个整数参数 a i j ( − 1 a i j 1 0 9 ) a_{ij}(-1a_{ij}10^9) aij(−1aij109), a i j − 1 a_{ij}−1 aij−1表示这个格子不能通过否则这个格子可以通过若 a i j 0 a_{ij}0 aij0则表示这个格子内有一个传送门。现在小D想要从(1,1)移动到(n,m)它可以以如下两种方式移动在任意两个相邻且参数均不为−1的格子间移动花费为w,在有传送门的两个格子 (i,j)和(x,y) 间移动花费为 a i j a x y a_{ij}a_{xy} aijaxy求小D所需的最小花费。 正解思路 分类思考一是不走传送门二是走一次传送门进行两次bfs求出最终结果。 正解代码
#include bits/stdc.h
using namespace std;
int n,m,w;
int a[2010][2010],dis[2010][2010];
long long ans10x3f3f3f3f3f3f3f3f,ans20x3f3f3f3f3f3f3f3f,allans0x3f3f3f3f3f3f3f3f;
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));queuepairint,int que;dis[sx][sy]0;que.push(make_pair(sx,sy));while(!que.empty()){int xque.front().first,yque.front().second;que.pop();for(int i0;i4;i){int nxxdx[i],nyydy[i];if(nx1||ny1||nxn||nym||a[nx][ny]-1||dis[nx][ny]!-1){continue;}dis[nx][ny]dis[x][y]1;que.push(make_pair(nx,ny));}}if(sx1dis[n][m]!-1){allansmin(allans,(long long)dis[n][m]*w);}for(int i1;in;i){for(int j1;jm;j){if(dis[i][j]!-1a[i][j]0){ansmin(ans,(long long)dis[i][j]*wa[i][j]);}} }
}
int main(){scanf(%d%d%d,n,m,w);for(int i1;in;i){for(int j1;jm;j){scanf(%d,a[i][j]);}}bfs(1,1,ans1);bfs(n,m,ans2);allansmin(allans,ans1ans2);printf(%lld,allans0x3f3f3f3f3f3f3f3f?-1:allans);return 0;
}
