电子商务网站建设的核心多选,品牌vi形象设计公司,茶山做网站,家具电商网站建设A. Li Hua and Maze 给出两个不相邻的点#xff0c;最少需要堵上几个方格#xff0c;才能使得两个方格之间不能互相到达。
思路#xff1a;显然#xff0c;对于不邻任何边界的方格来说#xff0c;最少需要的是4#xff0c;即上下左右都堵上#xff1b;邻一个边界就-1最少需要堵上几个方格才能使得两个方格之间不能互相到达。
思路显然对于不邻任何边界的方格来说最少需要的是4即上下左右都堵上邻一个边界就-1两个方格取一下最小值即可。
AC Code
#include bits/stdc.htypedef long long ll;
const int N 2e5 5;
int t, n, m, x1, y1, x2, y2;int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n m;std::cin x1 y1 x2 y2;int ans1 4, ans2 4;if(x1 1 || x1 n) ans1 --;if(y1 1 || y1 m) ans1 --;if(x2 1 || x2 n) ans2 --;if(y2 1 || y2 m) ans2 --;std::cout std::min(ans1, ans2) \n;}return 0;
}
B. Li Hua and Pattern 给出一个n*n的矩阵操作k次判断能否使得当前矩形和旋转180°后的图形完全相同。每次操作是将格子的颜色翻转。
思路显然将格子分为四部分对角的两两都应该中心对称。对于两两方格的两个坐标有相加等于n1的关系判断一下即可。注意对于奇数时的中心那一条应该等于同一条线上的另一部分。对于操作次数k如果小于不同的方格数则一定不满足条件若是大于kn是偶数时k-cnt必须是偶数。
AC Code
#include bits/stdc.htypedef long long ll;
const int N 1e3 5;
int t, n, k;
int a[N][N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin t;while(t --) {std::cin n k;for(int i 1; i n; i ) {for(int j 1; j n; j ) {std::cin a[i][j];}}int m (n 1) / 2;int cnt 0;for(int i 1; i m; i ) {for(int j 1; j m; j ) {if(a[i][j] ! a[1 n - i][1 n - j])cnt ;}}for(int i m 1; i n; i ) {for(int j 1; j n / 2; j ) {if(a[i][j] ! a[1 n - i][1 n - j])cnt ;}}if(k cnt || (k - cnt) % 2 n % 2 0)std::cout NO \n;elsestd::cout YES \n;}return 0;
}
C. Li Hua and Chess 在n*m的方格中猜一个确定位置。每次可以询问目标位置和询问位置的距离注意距离是指经过八个方向移动的最小距离在三次询问之内找到答案。
思路观察移动方式我们可以发现对于一个位置来说向外扩展x圈上的点到中心点的距离都是x。那么我们可以先询问(1, 1)点然后再问(1 len, 1 len)点当然注意和边界的判断。那么答案位置必然在第二次询问的点的正上方或者正左方。
AC Code
#include bits/stdc.htypedef long long ll;
const int N 1e3 5;
int t, n, m;int ask(int x, int y) {std::cout ? x y \n;std::cout.flush();int dis;std::cin dis;return dis;
}void work() {int a 1, b 1;int len ask(a, b);if(!len) {std::cout ! a b \n;return;}a std::min(a len, n), b std::min(b len, m);len ask(a, b);if(!len) {std::cout ! a b \n;return;}if(len a len b) {std::cout ! a b - len \n;return;}else if(len b len a) {std::cout ! a - len b \n;return;}int aa a, bb b, ll len;a - len;len ask(a, b);if(!len) {std::cout ! a b \n;return;}std::cout ! aa bb - ll \n;
}int main() {// std::ios::sync_with_stdio(false);// std::cin.tie(0);// std::cout.tie(0);std::cin t;while(t --) {std::cin n m;work();std::cout.flush();}return 0;
} D. Li Hua and Tree 给出一棵树进行k次操作操作1是计算x的子树权值的和操作2是交换x和x的重子即断开x和x的父节点之间的边链接x的重子和x的父节点之间的边。定义重子是x中具有最大子树的子节点若有多个点满足条件则重子是索引最小的那个点。
思路模拟整个过程即可注意细节。
AC Code
#include bits/stdc.htypedef long long ll;
#define int long long
const int N 1e5 5;
int n, m;
std::vectorint vec[N];
int a[N], w[N], fa[N], val[N];struct node{int w, id;bool operator(const node a) const{if (w ! a.w) return w a.w;return id a.id;}
};
std::setnode s[N];void DFS(int u, int f){val[u] a[u];w[u] 1;for(auto v : vec[u]){if (v f) continue;fa[v] u;DFS(v, u);val[u] val[v];w[u] w[v];s[u].insert({w[v], v});}
}signed main(){std::cin.tie(0);std::cout.tie(0);std::ios::sync_with_stdio(0);std::cin n m;for(int i 1; i n; i ) {std::cin a[i];}for(int i 1; i n; i ) {int u, v;std::cin u v;vec[u].push_back(v);vec[v].push_back(u);}DFS(1, -1);while(m --){int op, x;std::cin op x;if(op 1) std::cout val[x] \n;else {if (s[x].empty()) continue;int son s[x].begin() - id;s[fa[x]].erase({w[x], x});s[x].erase(s[x].begin());int big w[son];int value val[son];w[son] w[x];w[x] - big;val[son] val[x];val[x] - value;s[fa[x]].insert({w[son], son});s[son].insert({w[x], x});fa[son] fa[x];fa[x] son;}}return 0;
}
