1
思路
令 \(i * j\) 是完全平方数。
那么 \(\sqrt{i * j}\) 是一个整数。令 \(p ( p\) 为 \(i\) 中最大平方因子, \(x = i / (p * p)\), \(q * q\) 为 \(j\) 中的最大平方因子, \(x = j / (q * q)\)
那么 \(\sqrt{i * j}\) 可以写成 \(pq\sqrt{xy}\), 如果 \(\sqrt{i * j}\) 是一个整数, 那么 \(\sqrt{xy}\) 也是一个整数, \(x, y\) 不包含其他完全平方因子, 相等条件只有 \(x = y\), 前缀统计当前数除以最大平方因子的数, 维护答案即可
时间复杂度 \(O(N \log N)\)
空间复杂度 \(O(N)\)
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
long long ans, op, id, dp[N];
int n;
int C(int x){
op = 1;
for(int i = 1; i * i <= x; ++i){
if(x % (i * i) == 0){
op = i * i;
}
}
return op;
}
int main(){
cin >> n;
for(int i = 1; i <= n; ++i){
ans++;
id = C(i);
ans += dp[i / id] * 2;
dp[i / id]++;
}
cout << ans;
return 0;
}
2
思路
可以发现, 可以枚举两次充能的节点。分段DP
状态 \((i, sum)\) 表示解决完前 \(i\) 个打开点并返回 \(sx, sy\) 处是的能量为 \(sum\)
拓扑序 \(i\) 从小到大
最优话属性 \(sum\), \(i\) 一定时, \(sum\) 越小越好
另 \(dis(a, b)\) 表示 \(a \to b\) 打开点的欧几里得距离, \(sx, sy\) 为编号为 \(0\) 的打开点
转移 \(dp_{i} = \min \limits_{j = i - k}^{i - 1} \{dp_{j} + \sum \limits_{k = j + 1}^{i - 2} dis(j, j + 1) + dis(j + 1, 0) + dis(i, 0)\}\)
显然 \(\sum \limits_{k = j + 1}^{i - 2} dis(j, j + 1)\) 可以前缀和优化
时间复杂度 \(O(N^2)\)
空间复杂度 \(O(N)\)
另 \(S_i\) 表示按顺序从 \(1\) 号打卡点到第 \(i\) 号打卡点的距离
优化转移可得 \(dp_{i} = dis(0, i) + S_i + \min \limits_{j = i - k}^{i - 1} \{dp_{j} - S_{j + 1} + dis(0, j + 1)\}\)
单调队列优化。
时间复杂度 \(O(N)\)
空间复杂度 \(O(N)\)
#include<bits/stdc++.h>
using namespace std;
const long long N = 2e5 + 5;
long long n, k, h, t, q[N];
long long x[N], y[N];
long double S(long long i, long long j){
return sqrt(1ll * abs(x[i] - x[j]) * abs(x[i] - x[j]) + 1ll * abs(y[i] - y[j]) * abs(y[i] - y[j]));
}
long double sum[N], dp[N];
int main(){
cin >> n >> k;
for(long long i = 0; i <= n; ++i){
cin >> x[i] >> y[i];
if(i){
sum[i] = sum[i - 1] + S(i, i - 1);
}
}
h = 1, t = 1;
for(long long i = 1; i <= n; ++i){
for(; h <= t && q[h] < i - k; h++){
}
dp[i] = dp[q[h]] + sum[i] - sum[q[h] + 1] + S(q[h] + 1, 0) + S(i, 0);
for(; h <= t && dp[q[t]] - sum[q[t] + 1] + S(q[t] + 1, 0) >= dp[i] - sum[i + 1] + S(i + 1, 0); t--){
}
q[++t] = i;
}
cout << fixed << setprecision(6) << dp[n];
return 0;
}
3
思路
可以发现, 只有\(4 \cdot N+1\)个点可以改变反向, 所以只需要对于每个有效点, 做bfs即可
怎么转移 ?
当前位置可以向四个反向滑行， 只有滑到障碍物才停, 可以set记录每个障碍物的位置, 转移二分即可。
时间复杂度 \(O(4 \cdot N)\)
空间复杂度 \(O(4 \cdot N)\)
#include<bits/stdc++.h>
using namespace std;
const int N = 5e6;
map<int, set<int>>hx, hy;
map<int, map<int, int>>dp, vis;
int x, y, h, w, n, sx, sy, gx, gy, t;
struct O{
int x, y;
}q[N];
void C(int x, int y, int md){
if(vis[x][y]){
return;
}
//cout << x << ' ' << y << '\n';
vis[x][y] = 1;
dp[x][y] = md;
q[++t] = {x, y};
}
int main(){
cin >> h >> w >> n >> sx >> sy >> gx >> gy;
for(int i = 1; i <= n; ++i){
cin >> x >> y;
vis[x][y] = 1;
hx[x].insert(y), hy[y].insert(x);
}
C(sx, sy, 0);
h = 1;
for(; h <= t;){
x = q[h].x, y = q[h++].y;
auto it1 = hx[x].lower_bound(y);
auto it2 = hy[y].lower_bound(x);
if(it1 != hx[x].begin()){
C(x, *prev(it1) + 1, dp[x][y] + 1);
}
if(it1 != hx[x].end()){
C(x, *it1 - 1, dp[x][y] + 1);
}
if(it2 != hy[y].begin()){
C(*prev(it2) + 1, y, dp[x][y] + 1);
}
if(it2 != hy[y].end()){
C(*it2 - 1, y, dp[x][y] + 1);
}
}
cout << (!vis[gx][gy] ? -1 : dp[gx][gy]);
return 0;
}