学校周赛（3）
A:
题目：
解题：
本道题木只需要找到一个*的位置，并且查看这个*是否满足四种情况即可，对与判断的体哦见是四周不出现任何的*,由于每次搜索我们首先搜索到的的最左上角的*,因此我们以左上角的为中心进行讨论分析，分析见下图所示（橙红色表示第一个*的位置，绿色框表示我对应L的位置，紫色X表示不能有*的位置）
代码：
#include<iostream>
#include<vector>
using namespace std;
void bu(vector<vector<int>>& a,int i, int j) {
if (a[i + 1][j] && a[i + 1][j + 1] && !a[i - 1][j - 1] && !a[i - 1][j] && !a[i - 1][j + 1] &&
!a[i][j - 1] && !a[i][j + 1] && !a[i][j + 2] && !a[i + 1][j - 1] && !a[i + 1][j + 2] &&
!a[i + 2][j - 1] && !a[i + 2][j] && !a[i + 2][j + 1] && !a[i + 2][j + 2]) {
a[i][j] = a[i + 1][j] = a[i + 1][j + 1] = 0;
return;
}
if (a[i + 1][j - 1] && a[i + 1][j] && !a[i - 1][j - 1] && !a[i - 1][j] && !a[i - 1][j + 1] &&
!a[i][j - 2] && !a[i][j - 1] && !a[i][j + 1] && !a[i + 1][j - 2] && !a[i + 1][j + 1] &&
!a[i + 2][j - 2] && !a[i + 2][j - 1] && !a[i + 2][j] && !a[i + 2][j + 1]) {
a[i][j] = a[i + 1][j - 1] = a[i + 1][j] = 0;
return;
}
if (a[i][j + 1] && a[i + 1][j + 1] && !a[i - 1][j - 1] && !a[i - 1][j] && !a[i - 1][j + 1] &&
!a[i - 1][j + 2] && !a[i][j - 1] && !a[i][j + 2] && !a[i + 1][j - 1] && !a[i + 1][j] &&
!a[i + 1][j + 2] && !a[i + 2][j] && !a[i + 2][j + 1] && !a[i + 2][j + 2]) {
a[i][j] = a[i][j + 1] = a[i + 1][j + 1] = 0;
return;
}
if (a[i][j + 1] && a[i + 1][j] && !a[i - 1][j - 1] && !a[i - 1][j] && !a[i - 1][j + 1] &&
!a[i - 1][j + 2] && !a[i][j - 1] && !a[i][j + 2] && !a[i + 1][j - 1] && !a[i + 1][j + 1] &&
!a[i + 1][j + 2] && !a[i + 2][j - 1] && !a[i + 2][j] && !a[i + 2][j + 1]) {
a[i][j] = a[i][j + 1] = a[i + 1][j] = 0;
return;
}
}
void to_do() {
int n, m; cin >> n >> m;
//给予一个边界防止益处
vector<vector<int>> cnt(n+2, vector<int>(m+2));
//用1表示*，0表示.
char c;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> c;
if (c == '*') cnt[i][j] = 1;
}
}
//第一次遍历，将满足要求的进行填补
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (cnt[i][j]==1) bu(cnt, i, j);
}
}
//第二次遍历，查找是否有未填补的地方
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (cnt[i][j] == 1) {
cout << "NO" << endl;
return;//提前返回，减少时间
}
}
}
cout << "YES" << endl;
}
int main() {
int T; cin >> T;
while (T--) to_do();
return 0;
}
B:
题目：
解题：
本道题目要求我们求最长路径，但我们所遇到的问题都是最短路径问题，因此我们可以反过来思考，将所有的距离变为负数，那么我们的问题就变成了最基础的最短路径问题。
代码：
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], w[N], e[N], ne[N], idx;
int dist[N];
bool st[N];
void add(int a, int b, int c)//加入边，链接矩阵
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int zui_duan()
{
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
queue<int> q;
q.push(1);
st[1] = true;
while (q.size())
{
int t = q.front();
q.pop();
st[t] = false;
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j] > dist[t] + w[i])
{
dist[j] = dist[t] + w[i];
if (!st[j])
{
q.push(j);
st[j] = true;
}
}
}
}
return dist[n];
}
int main()
{
cin >> n >> m;
memset(h, -1, sizeof h);
while (m--)
{
int a, b, c;
cin >> a >> b >> c;
add(a, b, -c);
}
int t = zui_duan();
if (t == 0x3f3f3f3f) cout << "-1";
else cout << -t;
return 0;
}
C:解析和答案见周赛（1）的 F
题目：
D:
题目：
解题：
数学的组合问题，我们可以将两个位置用二位数组取记录其数量，利用组合数的思想直接计算答案
代码：
#include<iostream>
using namespace std;
int main()
{
int t; cin >> t;
while (t--)
{
int n; cin >> n;
int cnt[11][11] = { 0 };
long long ans = 0;
for (int i = 0; i < n; i++)
{
char x, y;
cin >> x >> y;
cnt[x - 'a'][y - 'a']++;
for (int k = 0; k < 11; k++)
{
if (cnt[x - 'a'][k] && k != y - 'a')
ans += cnt[x - 'a'][k];
if (cnt[k][y - 'a'] && k != x - 'a')
ans += cnt[k][y - 'a'];
}
}
cout << ans << endl;
}
return 0;
}
E:
题目：
解题：
本题要求你最多执行k次操作使得整个数组&操作得到最大值.关于每次操作 你可以改变数组中某个数的某个二进制位变为1。我们可以先统计每个位上&的结果（注：&的结果只有是1&1时才为1，因此只需要和1进行比较），然后我们由高位向低位进行逐位分析（因为要是结果最大，那么我们就必须保证高位尽可能为1），那么此时我们需要考虑第j位是否可以通过need次操作达到效果（要想使此位为1，则要求每个数的此位都为1，即need=此位置上的0的个数），当我need<=k时表示我能够进行此操作，同时k-=need表示我已经操作了need次数了
代码：
#include<iostream>
#include<vector>
using namespace std;
void to_do() {
int n, k;
cin >> n >> k;
vector<int> a(n),cnt(31,0);
//给一个数组，允许改变任意一个元素最多k次（将二进制的k位变成1）
for (int i = 0; i < n; i++) {
cin >> a[i];
for (int j = 30; j >= 0; j--) {
if (a[i] & (1 << j)) {
//记录按位与的过程
cnt[j]++;
}
}
}
int ans = 0;
//遍历按位与的记录值，要想结果最大，优先给最高位1
for (int j = 30; j >= 0; j--) {
//cnt记录的值为1的个数
//n-cnt的个数为0的个数
int need = n - cnt[j];
//如果此为0的个数小于k，那么说明我可以通过need次操作使其变为1
if (need <= k) {
//k减去need的次数
k -= need;
ans += (1 << j);
}
}
cout << ans << endl;
}
int main()
{
int t; cin >> t;
while (t--) to_do();
return 0;
}
原文地址：https://blog.csdn.net/qq_60624992/article/details/142701577
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！