A - N-choice question

AC代码： 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1010;
int n;
int a[N];
int main()
{cin >> n;int a, b;cin >> a >> b;for (int i = 1; i <= n; i++) {int c;cin >> c;if (a + b == c) {cout << i << endl;break;}}return 0;
}

B - Same Map in the RPG World 

两个地图，每个地图都是由h个字符串组成，每个字符串w个字符

共两种操作：

垂直偏移指的是对于所有行，每一行都往上移动一行，最上面一行移到最下面

水平偏移指的是对于所有列，每一列都往左移动一列，最左边一列移到最右边

问可不可以通过s次垂直偏移和t次水平偏移使得两个地图完全相同

数据比较小，感觉这题需要将所有情况枚举出来，可以用dfs枚举出所有情况，同时判断是否可行，试了一会发现不太会用dfs，那直接就模拟，暴力枚举吧

那么如何实现垂直和水平偏移呢?垂直偏移容易实现，不过就是字符串的上下移动，但是水平偏移的话估计得每一行每个字符都得移动，全部移动完之后又得判断字符串是否相等，感觉太麻烦

于是，我去看Virtual standings，看到了一个很好的代码

该代码并没有实现真正意义上的偏移，只不过直接将b的每一个字符和偏移后的a的每一个字符比较

枚举s次垂直偏移和t次水平偏移，然后看是否两个地图相等

AC代码： 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 50;
char a[N][N], b[N][N];
int h, w;
int main()
{cin >> h >> w;for (int i = 0; i < h; i++) cin >> a[i];for (int i = 0; i < h; i++) cin >> b[i];for (int s = 0; s < h; s++) {for (int t = 0; t < w; t++) {bool flag = true;for (int i = 0; i < h; i++) {for (int j = 0; j < w; j++) {flag &= (b[i][j] == a[(i - s + h) % h][(j - t + w) % w]);}}if (flag) {puts("Yes");return 0;}}}puts("No");return 0;
}

C - Cross

这题题目都看不懂呜呜呜，参考阿史大杯茶

大致题意是找由#组成的X型图形，从中心往外扩展，分别输出往外扩展1层,2层一直到n层的X型图形的个数(其中n=min(h,w))

数据比较小，所以可以枚举每一个#，来判断以它为中心的X型图形往外拓展了几层

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
using namespace std;
const int N = 110;
char s[N][N];
map<int, int>mp;
int h, w;
int main()
{cin >> h >> w;for (int i = 1; i <= h; i++) {for (int j = 1; j <= w; j++) {cin >> s[i][j];}}for (int i = 2; i < h; i++) {for (int j = 2; j < w; j++) {if (s[i][j] == '#') {int cnt = 0;//拓展的层数从0开始，一层一层上去，如果每满足一层的条件，cnt就++while (i + cnt + 1 <= h && i - cnt + 1 >= 1 && j - cnt + 1 >= 1 && j + cnt + 1 <= w && s[i + cnt + 1][j - cnt - 1] == '#' && s[i + cnt + 1][j + cnt + 1] == '#' && s[i - cnt - 1][j - cnt - 1] == '#' && s[i - cnt - 1][j + cnt + 1] == '#') cnt++;mp[cnt]++;}}}int n = min(h, w);for (int i = 1; i <= n; i++) cout << mp[i] << " ";return 0;
}

D - AABCC

看到题目想到质数筛,把质数从小到大依次存到数组中，需要筛到sqrt(1e12/2/2/3)==3e5

然后从中选三个数，一个最小的数用2次，一个最大的数用2次，中间的数用1次

就从小到大枚举三个数，注意中间可以剪枝，减小时间复杂度

参考houthe

AC代码：

#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long 
using namespace std;
const int N = 3e5 + 10;
int prime[N];
int cnt;
int n;
bool st[N];
//欧拉筛
void get_prime() {for (int i = 2; i <= N; i++) {if (!st[i]) prime[cnt++] = i;for (int j = 0; prime[j] <=  N/ i; j++) {st[prime[j] * i] = true;if (i % prime[j] == 0) break;}}
}
signed main()
{cin >> n; get_prime();int res = 0;for (int i = 0; i < cnt; i++) {if (prime[i] * prime[i] > n) break;for (int j = i + 1; j < cnt; j++) {if (prime[i] * prime[i] * prime[j] > n) break;for (int k = j + 1; k < cnt; k++) {int x = prime[i] * prime[i] * prime[j] * prime[k];if (x > n) break;x *= prime[k];if (x <= n) res++;else break;}}}cout << res << endl;
}