CF864div2
小的总结
这是我的第一场CF比赛，习惯了中文题面之后确实有一点点不适应，不过还好，在脱离谷歌翻译与百度翻译的情况下还是把题意理解清楚了，虽然虽然一个题没做出来
用四个字来说呢就是到此一游，更简单的说法就是坐牢
我真的真的一直在修改一直在提交...一直在WA
A题
先来看看题目，也是多组数据进行测试，分别给出棋盘的大小，以及对应的两个坐标，问阻断两者之间路径最少所需要放置的障碍物数目
There is a rectangular maze of size n×m. Denote (r,c) as the cell on the r-th row from the top and the c-th column from the left. Two cells are >adjacent if they share an edge. A path is a sequence of adjacent empty cells.
Each cell is initially empty. Li Hua can choose some cells (except (x1,y1)and (x2,y2)) and place an obstacle in each of them. He wants to know >the minimum number of obstacles needed to be placed so that there isn't a path from (x1,y1)to (x2,y2).
Suppose you were Li Hua, please solve this problem.Input
The first line contains the single integer t (1≤t≤500) — the number of test cases.
The first line of each test case contains two integers n,m(4≤n,m≤109) — the size of the maze.
The second line of each test case contains four integers x1,y1,x2,y2(1≤x1,x2≤n,1≤y1,y2≤m) — the coordinates of the start and the end.
It is guaranteed that |x1−x2|+|y1−y2|≥2.Output
For each test case print the minimum number of obstacles you need to put on the field so that there is no path from (x1,y1)to (x2,y2).
算法呢是贪心和模拟。其实不难想，只要不被误导的话。
这个是样例给的图片，于是我认为阻断的话是填满一数列或者一横行。
所以我的代码是
if(n<m)ans=n;
else ans=m;
把样例复制过来测试了一下，发现并非如此
input
3
4 4
2 2 3 3
6 7
1 1 2 3
9 9
5 1 3 6output
4
2
3
于是我仔细发现，第二个数据里面有一个块在角上放着所以直接两个就可以堵上了，第三个样例的话有一个块在边上，所以三个就完全足够
于是我的代码是这个样子
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int T,n,m,a,b,c,d,ans;
scanf("%d",&T);
while(T--){
ans=0;
scanf("%d%d",&n,&m);
scanf("%d%d%d%d",&a,&b,&c,&d);
if((a==1&&b==1)||(c==1&&d==1)){
ans=2;
}
else if(a==1 || b==1 ||c==1||d==1){
ans=3;
}
else{
if(n<m)ans=n;
else ans=m;
}
printf("%d\n",ans);
}
return 0;
}
于是pretest2WA了
于是我再一次看了看我的代码
发现对于边边角角我只考虑了第一行第一列和左上角，于是重新改了一下
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int T;
long long n,m,a,b,c,d,ans;
scanf("%d",&T);
while(T--){
ans=0;
scanf("%lld%lld",&n,&m);
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if(((a==1||a==n)&&(b==1 || b==m))||((c==1||c==n)&&(d==1 || d==m))){
ans=2;
}
else if(a==1 || b==1 ||c==1||d==1||a==n || c==n || b==m || d==m){
ans=3;
}
else{
if(n<m)ans=n;
else ans=m;
}
printf("%lld\n",ans);
}
return 0;
}
发现还是pretest2 WA
于是继续看一看代码
意识到有可能两个块在同一行同一列，那么就不能用随便摆满一行或者一数列进行阻隔
于是更改了一下代码并且提交
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int T;
long long n,m,a,b,c,d,ans;
cin>>T;
while(T--){
ans=0;
cin>>n>>m;
//cout<<n<<endl;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
//cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
if(m==1 || n==1){
ans=1;
}
else if(((a==1||a==m)&&(b==1 || b==n))||((c==1||c==m)&&(d==1 || d==n))){
ans=2;
}
else if(a==1 || b==1 ||c==1||d==1||a==m || c==m || b==n || d==n){
ans=3;
}
else if(a==c){
ans=n;
}
else if(b==d){
ans=m;
}
//cout<<ans<<endl;
if(ans==0){
if(n<m)ans=n;
else ans=m;
}
//cout<<n<<" "<<m<<endl;
cout<<ans<<endl;
}
return 0;
}
结果再一次的WA
突然意识到如果两个块在同一列的话也不一定是横着断开就是最省事儿的，如果横着特别长竖着很短的话可以采用台阶样式的
所以就是比较一下横着块的数目和竖+2的块数目
又一次进行提交
#include<iostream>
#include<cstdio>
using namespace std;
int main(){
int T;
long long n,m,a,b,c,d,ans,q,p;
cin>>T;
while(T--){
ans=0;
cin>>n>>m;
//cout<<n<<endl;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
//cout<<a<<" "<<b<<" "<<c<<" "<<d<<endl;
if(((a==1||a==m)&&(b==1 || b==n))||((c==1||c==m)&&(d==1 || d==n))){
ans=2;
}
else if(a==1 || b==1 ||c==1||d==1||a==m || c==m || b==n || d==n){
ans=3;
}
else if(a==c){
p=m+2;
if(n<p)ans=n;
else ans=p;
}
else if(b==d){
q=n+2;
if(m<q)ans=m;
else ans=q;
}
//cout<<ans<<endl;
if(ans==0){
if(n<m)ans=n;
else ans=m;
}
//cout<<n<<" "<<m<<endl;
cout<<ans<<endl;
}
return 0;
}
这也是我截止到最后提交的代码
仍旧WA
说一下正解吧
角块两个 边块三个 中心块儿四个
我也不知道我是如何做到想到了边块儿用三个，角块儿用两个的情况下中间的块儿需要四个就完全足够
大概真的是因为例图误导叭
不过说白了还是以为自己做的题太少
所以以后还是要多做多记
#include<iostream>
using namespace std;
int main(){
int T;
long long n,m,a,b,c,d,ans;
cin>>T;
while(T--){
ans=0;
cin>>n>>m;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
if(((a==1||a==n)&&(b==1 || b==m))||((c==1||c==n)&&(d==1 || d==m))){
ans=2;
}
else if(a==1 || b==1 ||c==1||d==1||a==n || c==n || b==m || d==m){
ans=3;
}
else{
ans=4;
}
cout<<ans<<endl;
}
return 0;
}
其实刚刚提交的时候还是错了一次
主要是行数和列数判断的不好
不过还是补出来了
呜呜呜果然要想成为ICPCer的第一件事儿就是补题
B题
题目也是看上去没有什么难度，但是我还是愉快的往坑里踩
简单来说就是开一个二维数组，然后看看需要更换多少个颜色，然后和可以更改颜色的数目相比较，输出YES或者NO就好
Li Hua has a pattern of size n×n, each cell is either blue or red. He can perform exactly k operations. In each operation, he chooses a cell and >changes its color from red to blue or from blue to red. Each cell can be chosen as many times as he wants. Is it possible to make the >pattern,that matches its rotation by 180∘
Suppose you were Li Hua, please solve this problem.Input
The first line contains the single integer t(1≤t≤100) — the number of test cases.
The first line of each test case contains two integers n,k (1≤n≤103,0≤k≤109) — the size of the pattern and the number of operations.
Each of next n lines contains n integers ai,j (ai,j∈{0,1}) — the initial color of the cell, 0 for blue and 1 for red.
It's guaranteed that sum of n over all test cases does not exceed 103.Output
For each set of input, print "YES" if it's possible to make the pattern, that matches its rotation by 180∘ after applying exactly k of >operations, and "NO" otherwise.
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
于是我的代码是这个样子滴
#include<iostream>
#include<cstdio>
using namespace std;
int a[1005][1005];
int main(){
int T,n,k,tt;
scanf("%d",&T);
while(T--){
tt=0;
cin>>n>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n/2;i++){
for(int j=1;j<=n/2;j++){
if(a[i][j]!=a[n+1-i][n+1-j])tt++;
}
}
if(tt>k)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}
不负众望的是，pretest2WA了捏
（然而此时两小时结束哩）
He can perform exactly k operations.
必须要走满K步无论当前是否变换完成，所以对于偶数列的表格无法将最后剩下的奇数步用完之后并且保持一个对称的状态
于是最终代码如下
#include<iostream>
#include<cstdio>
using namespace std;
long long map[1005][1005];
int main(){
int T,n,k,tt;
cin>>T;
while(T--){
tt=0;
cin>>n>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>map[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(map[i][j]!=map[n+1-i][n+1-j])tt++;
}
}
tt/=2;
if(tt>k)cout<<"NO"<<endl;
else if((k-tt)%2==1 && n%2==0)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}