2023ICPC网络赛第二场
M Dirty Work
解题思路:
算出解决每道题的时间的期望，升序排序，前缀和累加即可。
时间复杂度:\(O(nlogn)\)
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi
#define se
int n;
void solve()
{
scanf("%d",&n);
vector<double> v(n + 1);
for(int i = 1;i<=n;i++)
{
double a,b,p;
scanf("%lf %lf %lf",&a,&b,&p);
v[i] = a * (1.0 - p) + ((a + b) * p);
}
sort(v.begin() + 1,v.end());
double ans = 0;
double res = 0;
for(int i = 1;i<=n;i++)
{
res += v[i];
ans += res;
}
printf("%.12lf\n",ans);
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}
D Project Manhattan
解题思路:
如果每行选一个电话亭，那么必定能覆盖所有位置。
如果每列选一个电话亭，同样必定能覆盖所有位置。
如果我们有一列没有选任何一个电话亭，那么必定是每行至少选择了一个电话亭。
如果我们有一行没有选任何一个电话亭，那么必定是每行至少选择了一个电话亭。
所以，要么按每行最少选一个电话亭的方案选，要么按每列最少选一个电话亭的方案选。二者取更优的。
对于\(<0\)的电话亭，必定选上。
这里以每行选一个电话亭为例。
遍历每行，如果最小值\(\geq 0\)，那么选最小的一个。如果最小值\(< 0\)，那么就将小于0的全部选上。
遍历列时同理。
时间复杂度:\(O(n^2)\)
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi
#define se
int n;
void solve()
{
scanf("%d",&n);
vector<vector<ll>> g(n + 10,vector<ll>(n + 10));
ll s1 = 0;
ll s2 = 0;
for(int i = 1;i<=n;i++)
{
for(int j = 1;j<=n;j++)
{
scanf("%lld",&g[i][j]);
}
}
for(int i = 1;i<=n;i++)
{
ll res = 0;
ll ming = 1e18;
for(int j = 1;j<=n;j++)
{
if(g[i][j] < 0)
{
res += g[i][j];
}
ming = min(ming,g[i][j]);
}
if(ming < 0)
{
s1 += res;
}
else
{
s1 += ming;
}
}
for(int i = 1;i<=n;i++)
{
ll res = 0;
ll ming = 1e18;
for(int j = 1;j<=n;j++)
{
if(g[j][i] < 0)
{
res += g[j][i];
}
ming = min(ming,g[j][i]);
}
if(ming < 0)
{
s2 += res;
}
else
{
s2 += ming;
}
}
printf("%lld\n",min(s1,s2));
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}
E Another Bus Route Problem
解题思路:
首先，这是一颗有根树，根节点为\(1\)，我们先将所有结点的父节点处理出来，方便之后从根节点开始的搜索。
村庄中正常的\(n-1\)条正常的路是一颗树。\(m\)条公交路线构成另一幅图。
我们在公交图上从根节点\(1\)开始跑\(bfs\)。
对于当前遍历到的结点\(u\)，如果存在公交路线\(u - v\)，我们从\(v\)结点开始向根节点遍历，更新并加入还未到达过的所有结点。
所有结点都只会被更新一遍，所以时间复杂度:\(O(n)\).
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi
#define se
void solve()
{
int n,m;
scanf("%d %d",&n,&m);
vector<vector<int>> adj(n + 1);
for(int i = 1;i<n;i++)
{
int x;
scanf("%d",&x);
adj[i+1].push_back(x);
adj[x].push_back(i + 1);
}
vector<int> fa(n + 1);
auto dfs = [&](auto self,int u,int p) -> void
{
fa[u] = p;
for(auto v : adj[u])
{
if(v == p)
{
continue;
}
self(self,v,u);
}
};
dfs(dfs,1,-1);
vector<vector<int>> station(n + 1);
for(int i = 1;i<=m;i++)
{
int a,b;
scanf("%d %d",&a,&b);
station[a].push_back(b);
station[b].push_back(a);
}
queue<int> q;
q.push(1);
vector<int> dist(n + 1,-1);
dist[1] = 0;
while(q.size())
{
auto u = q.front();
q.pop();
for(auto v : station[u])
{
if(v == fa[u])
{
continue;
}
int t = v;
while(dist[t] == -1)
{
q.push(t);
dist[t] = dist[u] + 1;
t = fa[t];
}
}
}
for(int i = 2;i<=n;i++)
{
printf("%d ",dist[i]);
}
}
int main()
{
int t = 1;
// scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}
I Impatient Patient
解题思路:
如果我们决定要在阶段\(i\)冒险，那么即使失败后重新抵达这里，我们仍然会选择冒险。
枚举在阶段\(1 \sim n\)选择冒险。
选择在阶段\(i\)冒险的期望时间:
\[res = i + 1 + (\frac {1}{p_i} - 1)\times(i - a_i + 1) \]从左到右解释：
\(i\)是走到第\(i\)阶段花费的时间。\(+1\)是在第\(i\)阶段第一次选择冒险。\(\frac {1}{p_i}\)是几何概型期望，即这么多次才会成功。\(-1\)是最后一次成功，不用跳回去在重来。\(i - a_i + 1\)是失败一次后，重新回到第\(i\)阶段选择挑战花费的时间。
时间复杂度:\(O(n)\)
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi
#define se
int n;
int m;
void solve()
{
scanf("%d",&n);
vector<int> a(n + 1);
vector<double> p(n + 1);
for(int i = 0;i < n;i++)
{
scanf("%d",&a[i]);
}
for(int i = 0;i < n;i ++)
{
scanf("%lf",&p[i]);
p[i] /= (double)1e5;
}
double ans = n;
for(int i = 0;i<n;i ++)
{
double res = (i + 1.0 + (1.0 / p[i] - 1) * (i - a[i] + 1));
ans = min(ans,res);
}
printf("%.12lf\n",ans);
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}
K Super-knight
解题思路:
在\(x\)上我们每次能移动\(a\)格，在没跳过边界之前，我们每次移动\(x\)都只会比之前大。\(y\)上同理。
题目要我们求最小的欧几里得距离，那么很明显，答案只会在开头那一跳和跨界的跳之中。
根据题目循环边界的设定，假设我们跳了\(k\)次，那么\(x = (x + k * a) \%n,y = (y + k * b)\%n\)。
所以，我们每跳\(n\)次，就一定会回到原点。答案一定在跳\(n\)次之内。
那么，\(n\)次之内，我们最多找到多少个边界跳点呢？
以\(x\)上每次跳\(a\)格举例。
第一次从原点开始跳大概跳\(\frac{n}{a}\)下能到边，跳过边界后又会回到较底部的位置，大概又会跳\(\frac{n}{a}\)下到边界。最多跳\(n\)次。所以最多经过\(\frac{n}{\frac{n}{a}} = a\)个边界。在\(y\)上每次跳\(b\)格同理，最多经过\(b\)个边界。
假设每次\(x,y\)上的边界经过都不同步，那最多我们要找\(a + b\)个点。
由于\(1 \leq a,b\leq100\),每次找边界都是\(O(1)\)的。时间足够。
本题最终要求\(x^2 + y^2\),看边界\(2 \leq n \leq10^{18}\),好像会爆\(long long\)。其实，根据上面所提的内容，(100,100)就是答案的上界了。
\(res = \sqrt{2 \times 100^2} = \sqrt{2}\times100\)就是\(x,y\)的极限了，我们这里取上限为\(200\)也足够优化了。不会爆\(long\ long\)。
时间复杂度:\(O((a+b)*t)\)
代码:
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int,int> pii;
#define fi
#define se
int n;
int m;
void solve()
{
int a,b;
ll n;
scanf("%d %d %lld",&a,&b,&n);
ll x = a % n;
ll y = b % n;
ll ans = 1e9;
while(!(x == 0 && y == 0))
{
if(x < 200 && y < 200)
{
ans = min(ans,x * x + y * y);
}
ll kx = (n - x + (a - 1)) / a;
ll ky = (n - y + (b - 1)) / b;
ll k = min(kx,ky);
x = (x + k * a) % n;
y = (y + k * b) % n;
}
printf("%lld\n",ans);
}
int main()
{
int t = 1;
scanf("%d",&t);
while(t--)
{
solve();
}
return 0;
}
L Super-palindrome
解题思路:
注意本题一定是划分为偶数个小部分。
直接暴力枚举对称位置,然后从对称位置开始贪心向两边扩散。
判断两字符串是否相等用哈希。
具体操作看代码比较好懂。
时间复杂度:\(O(n^2)\)
代码:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> pii;
#define fi
#define se
using ull = unsigned long long;
const int P = 13331;
void solve()
{
string s;
cin >> s;
int n = s.size();
s = ' ' + s;
vector<ull> h(n + 1), p(n + 1);
p[0] = 1;
for (int i = 1; i <= n; i++)
{
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + s[i];
}
auto get = [&](int l, int r) -> ull
{
return h[r] - h[l - 1] * p[r - l + 1];
};
ll ans = 0;
// 枚举对称点
for (int i = 1; i <= n; i++)
{
int sl = i + 1;
int sr = i;
// 从对称点向两端搜
for (int l = i, r = i + 1; l > 0 && r <= n; l--, r++)
{
if (get(l, sl - 1) == get(sr + 1, r))
{
ans++;
sl = l;
sr = r;
}
}
}
printf("%lld\n", ans);
}
int main()
{
int t = 1;
scanf("%d", &t);
while (t--)
{
solve();
}
return 0;
}