学校周赛（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;//遍历按位与的记录值，要想结果最大，优先给最高位1for (int j = 30; j >= 0; j--) {//cnt记录的值为1的个数//n-cnt的个数为0的个数int need = n - cnt[j];//如果此为0的个数小于k，那么说明我可以通过need次操作使其变为1if (need <= k) {//k减去need的次数k -= need;ans += (1 << j);}}cout << ans << endl;
}
int main()
{int t; cin >> t;while (t--) to_do();return 0;
}

​