AtCoder Beginner Contest 250 A - E 题解
传送门
闲来无事，突然想 vp 一场之前忙的来不及做的
A - Adjacent Squares
这题没想到居然还会卡了一下
给出一个图，给出当前位置，看看有多少个格子相邻
行和列分别判断就好
#include
using namespace std;
int main()
{
int n, m;
cin >> n >> m;
int x, y;
cin >> x >> y;
int cnt = 0;
if(n == 1) cnt += 2;
else if(x == 1 || x == n) cnt++;
if(m == 1) cnt += 2;
else if(y == 1 || y == m) cnt++;
cout << 4 - cnt << endl;
return 0;
}
B - Enlarged Checker Board
一个模拟，算了一下并不会爆空间，就直接写好再打印了
#include
using namespace std;
const int maxn = 110;
char s[maxn][maxn];
int main()
{
int n, a, b;
cin >> n >> a >> b;
for(int i=0; i C - Adjacent Swaps
这个用桶来处理一下位置，然后每次询问的时候桶和数组同时维护
#include
#include
#include
using namespace std;
const int maxn = 2e5 + 10;
int num[maxn], alp[maxn];
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++) num[i] = alp[i] = i;
while(m--)
{
int x;
scanf("%d", &x);
if(alp[x] == n) x = num[n-1];
int way = alp[x];
int a = num[way];
int b = num[way + 1];
swap(num[way], num[way+1]);
swap(alp[a], alp[b]);
}
for(int i=1; i<=n; i++)
{
if(i != 1) printf(" ");
printf("%d", num[i]);
}
printf("\n");
return 0;
}
D - 250-like Number
这个题比较有趣
首先素数的话先用一个欧拉筛预处理一下
接着要寻找合理的情况，本来是想用 \(O(n^2)\) 强行莽一下，但是一直死活写不对，就突然想到二分，一下就过了
因为 \(k = p * q ^ 3\) 且有 \(p < q\)，所以可以枚举 \(q\)，然后再找有多少个符合的 \(p\)
而找 \(p\) 的数量，可以直接用二分去寻找第一个大到不符合要求的 \(p\) 的位置，然后知道有多少个 \(p\) 符合条件
这题比较友好的一点是，因为查询的是素数乘积，所以不会出现说相同一个数字有多种分解的情况，就不用查重，不然还得用一个 set 去维护
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e6 + 10;
int prime[maxn], tp = 0;
long long p[maxn];
void init()
{
int n = 1e6 + 1;
for(int i=2; i> n;
for(int i=0; i E - Prefix Equality
这题也很有趣，大概就是问 \(a\) 数组前 \(x_i\) 个 和 \(b\) 数组前 \(y_i\) 个，这两组各自形成的集合是否相等
尺取
我用的是尺取过的，但是看了别人的题解，好像都是用哈希来预处理 \(a\) 的前缀集合 还有 \(b\) 的前缀集合，然后直接判断是否相等
我认为，如果选定了 \(a\) 数组的前 \(i\) 个，则在 \(b\) 数组中，一定有一个范围 \([l, r]\) 使得答案成立
并且对于这个范围，有 \(l_{i} \leq l_{i+1}\) 和 \(r_{i} \leq r_{i+1}\)，因此可以判断他是单调的，所以直接尺取区间就行，尺取复杂度为 \(O(n)\)
因为要维护一个桶，所以用了 \(map\)
总的时间复杂度为 \(O(nlogn)\)
#include
#include
#include