Atcoder Beginner Contest 300

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;
int h,w;
char s[N][N];
map<int,int>mp;
int main()
{
	cin>>h>>w;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			cin>>s[i][j];
		}
	}
	for(int i=1;i<h-1;i++){
		for(int j=1;j<w-1;j++){
			int cnt=0;
			while(i-cnt>=0&&i+cnt<h&&j-cnt>=0&&j+cnt<w&&s[i-cnt][j-cnt]=='#'&&s[i-cnt][j+cnt]=='#'&&s[i+cnt][j-cnt]=='#'&&s[i+cnt][j-cnt]=='#') 
             cnt++;
             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;
}