AtCoder Beginner Contest 400（ABCDE）

A - ABC400 Party

翻译：

          在 ABC400 的纪念仪式上，我们想把 400 人排成 A 行 B 列的长方形，且不留任何空隙。

        给你一个正整数 A，请打印可以这样排列的正整数 B 的值。如果没有这样的正整数 B，则打印-1。

思路：

        判断能否整除即可。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int MX = 51000;void solve(){int a;cin>>a;int b = 400/a;if (a*b==400){cout<<b<<endl; } else{cout<<-1<<endl;}
}int main(){// 鍏抽棴杈撳叆杈撳嚭娴佸悓姝?ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 涓嶄娇鐢ㄧ瀛﹁鏁版硶// cout<<fixed;// 鍥涜垗浜斿叆涓棿濉繚鐣欏嚑浣嶅皬鏁帮紝涓嶅～榛樿// cout.precision();solve();	return 0;
}

B - Sum of Geometric Series

翻译：

        给你两个正整数N，M。

        让。如果X<=1e9打印X的值，否则打印inf。

思路：

        暴力求解，当算到X>1e9时直接输出inf。

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MX = 1e9;
ll n,m,ans = 0;
void solve(){cin>>n>>m;ll now_n = 1;for (int i=0;i<=m;i++){ans+=now_n;now_n *= n;if (ans>MX || (now_n>MX && i!=m)){cout<<"inf"<<endl;return;}}cout<<ans<<endl;
}int main(){// 鍏抽棴杈撳叆杈撳嚭娴佸悓姝?ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 涓嶄娇鐢ㄧ瀛﹁鏁版硶// cout<<fixed;// 鍥涜垗浜斿叆涓棿濉繚鐣欏嚑浣嶅皬鏁帮紝涓嶅～榛樿// cout.precision();solve();	return 0;
}

C - 2^a b^2

翻译：

        当且仅当一个正整数 X 满足以下条件时，它才被称为好整数：

• 存在一对整数(a,b)如此

        例如，400 是一个好整数，因为 。

        给定一个正整数 N，求 1 到 N 之间（包括 N）的好整数个数。

思路：

        每个 好整数 的b必定可以是一个奇数，那么先从1开始通过遍历a，结束条件为2^a>N，其间使用二分求出b的最大值，可得到在a_i的情况下有种b是可用的（b要为奇数）。

        注意在二分中可使用的方法避免大数相乘。这题中要注意整数溢出问题。(二分，数论)

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll N, ans = 0;
ll integer_sqrt(ll x) {if (x <= 0) return 0;ll left = 0, right = min(x, (ll)1e9)+1; while (left+1 != right) {ll mid = (right + left) / 2;if (mid <= x / mid) { left = mid ;} else {right = mid ;}}return left;
}void solve() {cin >> N;ll now = 1;for (int a = 1; ; a++) {now *= 2;if (now > N) break;ll x = N / now;ll tmp = integer_sqrt(x);ans += tmp / 2;         if (tmp % 2 == 1) ans++; }cout << ans << "\n";
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);solve();return 0;
}

D - Takahashi the Wall Breaker

翻译：

        高桥正准备去鱼店买鳗鱼。

        他居住的小镇被划分成 H 行 W 列的网格。

        每个单元格要么是一条路，要么是一堵墙。

        我们把从上往下第 i 行（1≤i≤H）和从左往上第 j 列（1≤j≤W）的单元格记为单元格 (i,j)。具体来说，如果 S i 的第 j 个字符（1≤i≤H,1≤j≤W）是 .，则(i,j) 单元是一条路；如果是 #，则 (i,j) 单元是一堵墙。

        他可以按任意顺序重复执行以下两种操作：

• 移动到相邻的单元格（向上、向下、向左或向右），该单元格位于小镇内且是道路。
• 从四个方向（上、下、左或右）中选择一个，然后朝该方向踢一脚。
• 当他踢出前踢腿时，在距离他当前所在的小格最多 2 步远的地方，如果该小格是墙，就会变成路。
• 如果最远 2 步之外的一些单元格在城镇之外，则仍然可以进行前踢，但城镇之外的任何东西都不会改变。

        他从(A,B)单元格开始，想移动到(C,D)单元格的鱼店。他开始所在的单元格和有鱼店的单元格都是道路。

        求他到达鱼店所需的最小前踢数

思路：

     参考最短路的思路，使用堆和广度优先搜索，记录每个点的前踢数，如有更新点的前踢数放入堆中。(数据结构，贪心，广搜)

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MX = 1e9;
ll h,w,x1,yy,x2,y2;
vector<array<int,2>> direct(4);
struct cmp{bool operator()(array<int,3> x,array<int,3> y){return y[0]<x[0];}
};
void solve(){direct[0] = {0,1};direct[1] = {1,0};direct[2] = {0,-1};direct[3] = {-1,0};cin>>h>>w;vector<vector<char>> maze(h+1,vector<char>(w+1));vector<vector<int>> vis(h+3,vector<int>(w+3,INT_MAX));for (int i=1;i<=h;i++){for (int j=1;j<=w;j++){cin>>maze[i][j];}}cin>>x1>>yy>>x2>>y2;vis[x1][yy] = 0;priority_queue<array<int,3>,vector<array<int,3>>,cmp> pq;pq.push({0,x1,yy});while (!pq.empty()){int val = pq.top()[0],x = pq.top()[1],y = pq.top()[2];pq.pop();for (auto& i:direct){int now_x = x+i[0],now_y = y+i[1],tmp_x = x+2*i[0],tmp_y = y+2*i[1];if (now_x<=h && now_x>=1 && now_y<=w && now_y>=1){if (maze[now_x][now_y]=='#'){if (vis[now_x][now_y]>val+1){pq.push({val+1,now_x,now_y});vis[now_x][now_y] = val+1;}if (tmp_x<=h && tmp_x>=1 && tmp_y<=w && tmp_y>=1){if (vis[tmp_x][tmp_y]>val+1){pq.push({val+1,tmp_x,tmp_y});vis[tmp_x][tmp_y] = val+1;}}}else{if (vis[now_x][now_y]>val){pq.push({val,now_x,now_y});vis[now_x][now_y] = val;}if (tmp_x<=h && tmp_x>=1 && tmp_y<=w && tmp_y>=1){if (maze[tmp_x][tmp_y]=='#'){if (vis[tmp_x][tmp_y]>val+1){pq.push({val+1,tmp_x,tmp_y});vis[tmp_x][tmp_y] = val+1;}}else{if (vis[tmp_x][tmp_y]>val){pq.push({val,tmp_x,tmp_y});vis[tmp_x][tmp_y] = val;}	}}}}}}cout<<vis[x2][y2]<<endl;
}int main(){// 鍏抽棴杈撳叆杈撳嚭娴佸悓姝?ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 涓嶄娇鐢ㄧ瀛﹁鏁版硶// cout<<fixed;// 鍥涜垗浜斿叆涓棿濉繚鐣欏嚑浣嶅皬鏁帮紝涓嶅～榛樿// cout.precision();solve();	return 0;
}

E - Ringo's Favorite Numbers 3

翻译：

        当且仅当正整数 N 同时满足以下两个条件时，它是一个 400 数：

• N 恰好有 2 个不同的质因数。
• 对于 N 的每个质因数 p，p 平分 N 的次数是偶数。更正式地说，能使 p k 除以 N 的最大非负整数 k 是偶数。

        处理 Q 个查询。每个查询都会给出一个整数 A，因此请找出不超过 A 的最大 400 个数。在此问题的限制条件下，不超过A 的 400 个数总是存在的。

思路：

        先预处理，先求出1e6内的质数，再求出这些质数能得到的值（<=1e12），在求组合中使用剪枝（两质数相乘>1e6不可行），否则超时。通过去除。

        在每次询问中使用二分求解答案即可。这题也要注意边界条件。（深搜，数论）

实现：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MX = 1e6+10;
const ll MXX = 1e12+10;
ll a;
vector<ll> num(MX,0),prime,ans; 
void init(){for (ll i=2;i<MX;i++){if (!num[i]){prime.push_back(i);for (ll j=i+i;j<MX;j+=i){num[j] = 1;}}}ll n = prime.size();for (ll i=0;i<n;i++){for (ll j=i+1;j<n;j++){ll p = prime[i],q = prime[j];if (p*q>MX) break;p*=p,q*=q;// cnt number based on p,qauto dfs = [&](auto&&dfs,ll x,ll y)->void{if (x*y<=MXX){ans.push_back(x*y);if (x<=MXX/y/p){dfs(dfs,x*p,y);} if (y<=MXX/x/q){dfs(dfs,x,y*q);} }};dfs(dfs,p,q);}}sort(ans.begin(),ans.end());ans.erase(unique(ans.begin(),ans.end()),ans.end());
}
void solve() {cin>>a;cout<<ans[upper_bound(ans.begin(),ans.end(),a)-ans.begin()-1]<<endl;
}int main() {ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);init(); ll q;cin>>q;while (q--) solve();return 0;
}

  有建议可以评论，我会积极改进qwq。