The 2023 ICPC Asia Regionals Online Contest (2) MDIELK
M Dirty Work
题意：总共有\(n\)个问题，对于第\(i\)个问题需要\(a_i\)分钟。你可以随便选择一个没过的题去写，写完以后马上交，你有\(p_i\)的概率会错，错了不能跳题，你要花额外\(b_i\)的时间去\(debug\)。问你以最佳策略的最小罚时。
思路：因为有基础罚时(即做完这个题的总时间)，那么问题变成求前缀和的和的最小值。那么把小的放前面即可(每个值为\(a_i+b_i*p_i\))。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
double a[N],b[N],p[N],s[N];
int main()
{
//ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n;
scanf("%d",&n);
for(int i = 1;i <= n; i++)
{
cin>>a[i]>>b[i]>>p[i];
s[i] = a[i]+p[i]*b[i];
}
sort(s+1,s+1+n);
double ans = 0;
for(int i = 1;i <= n; i++)
s[i] += s[i-1],ans += s[i];
printf("%.12lf\n",ans);
}
return 0;
}
D Project Manhattan
题意：有\(n\)条水平的直线和\(n\)条垂直的直线交叉形成一个网格图。每一个点有一个花费(可以是负数)。当我们选择点\((i,j)\)，那么可以覆盖第\(i\)行和第\(j\)列。问最小花费是多少可以覆盖完所有。
思路：首先，很显然的\(0\)和负数一定要选。又因为要全覆盖，那么每行至少有一个要选，每列至少有一个要选。
两种覆盖策略：
- 覆盖\(n\)行
- 覆盖\(n\)列
那么当我们选完\(0\)和负数之后呢，如果还有没被覆盖的，优先选小的。
注意初始化！！！
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 510;
ll a[N][N];
bool c[N],r[N];
ll minc[N],minr[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
cin>>a[i][j];
memset(minc,127,sizeof(minc));
memset(minr,127,sizeof(minr));
memset(c,false,sizeof(c));
memset(r,false,sizeof(r));
ll ans = 0;
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
{
if(a[i][j]<=0)r[i] = true,c[j] = true,ans += a[i][j];
}
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
{
minr[i] = min(minr[i],a[i][j]);
}
for(int j = 1;j <= n; j++)
for(int i = 1;i <= n; i++)
{
minc[j] = min(minc[j],a[i][j]);
}
ll sr = 0,sc = 0;
for(int i = 1;i <= n; i++)
{
if(r[i])continue;
else sr += minr[i];
}
for(int j = 1;j <= n; j++)
{
if(c[j])continue;
else sc += minc[j];
}
cout<<min(sc,sr)+ans<<"\n";
}
return 0;
}
I Impatient Patient
题意：你受伤了，现在要恢复。一开始在恢复的第\(0\)阶段，到第\(n\)阶段才算恢复完全。
第\(i\)天，你可以选择什么都不干就只是休息，那么每天可以恢复一个阶段，那么\(n\)天恢复完全。你可以可以选择挑战自己，如果一旦挑战成功呢，你就会直接恢复完全，否则的话你会回到第\(a_i\)阶段。其中挑战成功的概率是\(p_i\)。
思路：我们连接每一个阶段和能到达的阶段，发现是一个图，每一条边有一个概率。那么因为我们采用的是最佳策略，我们会怎么做呢？我们一定会到达一个成功期望天数最小的点不断挑战。对于第\(i\)天的成功概率是\(p_i\)的话，成功的期望次数是\(\dfrac{1}{p_i}\),那么失败的期望的天数就是\(\dfrac{1}{p_i}-1\)天，每次失败会回到\(a_i\)，那么我们又从\(a_i\)走到\(i\)(花费\(i-a[i]\))然后尝试(\(+1\))。注意挑战也要花费\(1\)的天数所以\(+1\)。
那么对于第\(i\)个点的期望天数就是：\((i+1)+(i-a[i]+1)*(\dfrac{1}{p_i}-1)\)。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 5e5 + 10;
const double M = 1e5;
int n;
double a[N],q[N],p[N];
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
cin>>n;
for(int i = 0;i < n; i++)
cin>>a[i];
double ans = n;
for(int i = 0;i < n; i++)
{
double q;
cin>>q;
if(q==0)continue;
double p = q/M;
double tmp = i+1+(1/p-1)*(i-a[i]+1);
ans = min(ans,tmp);
}
printf("%.12lf\n",ans);
}
return 0;
}
E Another Bus Route Problem
题意：有\(n\)个点，\(n-1\)条边，形成一颗树。
给你\(m\)条公交路线，从\(u_i->v_i\)(表示两个点之间最短的树上距离)。我们可以从\(u_i\)或者\(v_i\)上车,可以从\(u_i->v_i\)路径上任何一点下车。问你从\(1\)号点到每一个点至少需要多少条公交路线。
思路：\(bfs\)
考虑从\(1\)(因为我们只能从1上车)做为起点加入队列，花费\(0\)。
然后考虑从\(1\)能到那些点，如果之前没被遍历到，那么去把它加入队列。
然后再以队列里面某个点为起点去往上跳，因为我们一开始是从\(1\)开始的，那么之后的点一定可以到达\(1\)的。如果某个点\(u\)能到达\(1\)，那么它的父亲也一定可以，我们也把它的父亲能到的点加入。一直重复，直到队列为空。
注意已经访问过的就不要重复访问了。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,m,fa[N];
queue<pair<int,int>>q;
int ans[N];
vector<int>e[N];
void find(int u,int d)
{
while(u!=-1)
{
if(ans[u] != -1)return;
ans[u] = d;
// cout<<"u = "<<u<<" d = "<<d<<"\n";
// cout<<"size = "<<e[u].size()<<"\n";
for(auto v : e[u])
if(ans[v] == -1)
q.push({v,d+1});
u = fa[u];
}
return;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
cin>>n>>m;
fa[1] = -1;
for(int i = 2;i <= n; i++)
cin>>fa[i];
for(int i = 1;i <= m; i++)
{
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i = 1;i <= n; i++)
ans[i] = -1;
q.push({1,0});
while(!q.empty())
{
auto x = q.front();
q.pop();
find(x.first,x.second);
}
for(int i = 2;i <= n; i++)
cout<<ans[i]<<" ";
cout<<"\n";
return 0;
}
L Super-palindrome
题意：我们定义，如果能把\(S\)拆成偶数个部分，并且\(S_i = S_{2k-i+1}\)，我们称之为超级回文串。给你一个串\(S\),让你去找它有多少个超级回文子串。
思路：哈希+双指针
我们对于每个点\(l_1 = i\)和\(r_1 = i+1\)，去向两边扩展，直到找到离它最近的满足\(S_{l_1,r_1}=S_{l_2,r_2}\),统计答案，并更新\(r_1 = l_1-1,l_2 = r_2+1\)
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
typedef pair<long long, long long> pll;
struct DoubleStringHash
{
vector<long long> h1, h2, w1, w2;
long long base1 = 131, base2 = 13331;
long long p1 = 1e9 + 7, p2 = 1e9 + 9;
void init(string s) {
int len = s.size();
s = " " + s;
h1.resize(len + 1), w1.resize(len + 1);
h2.resize(len + 1), w2.resize(len + 1);
h1[0] = 0, w1[0] = 1;
h2[0] = 0, w2[0] = 1;
for(int i = 1; i <= len; i++) {
h1[i] = (h1[i - 1] * base1 + s[i]) % p1, w1[i] = w1[i - 1] * base1 % p1;
h2[i] = (h2[i - 1] * base2 + s[i]) % p2, w2[i] = w2[i - 1] * base2 % p2;
}
}
pll get(int l, int r) {
return {(h1[r] - h1[l - 1] * w1[r - l + 1] % p1 + p1) % p1, (h2[r] - h2[l - 1] * w2[r - l + 1] % p2 + p2) % p2};
}
}ha;
int main()
{
ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
string s;
cin>>s;
int sz = s.size();
ha.init(s);
s = "?"+s;
ll ans = 0;
for(int i = 1;i < sz; i++)
{
int l1 = i,r1 = i;
int l2 = i+1,r2 = i+1;
while(l1>=1&&r2<=sz)
{
if(ha.get(l1,r1)==ha.get(l2,r2))
{
//cout<<"l1 = "<<l1<<" r1 = "<<r1<<" l2 = "<<l2<<" r2 = "<<r2<<"\n";
ans++,r1 = l1-1,l2 = r2+1;
}
l1--,r2++;
}
}
cout<<ans<<"\n";
}
return 0;
}
K Super-knight
题意：一开始你在 \((0,0)\),每次你可以走\((+a,+b)\)。
假设当前的点是\((x,y)\)，那么你可以走到的点是\(((x+a)\%n,(y+b)\%n)\)
问你能走到的离\((0,0)\)最近的点的欧几里得距离的平方。
思路：我们发现最终的答案一定在红色框框内。
所以只有当它越界了才有可能是答案。
那么如果当前的坐标是\((x,y)\)，那么如果我要走到越界，那么我需要走\(min(\dfrac{n-x+a-1}{a},\dfrac{n-y+b-1}{b})\)
如果当我们走到之前走过的那就停止，因为之后都是一样的了。对于所有可能的答案取个\(min\)即可。
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
inline __int128 read(){__int128 x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-'){f=-1;}ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
inline void write(__int128 x){if (x < 0){putchar('-');x = -x;}if (x > 9) write(x / 10);putchar(x % 10 + '0');}
typedef __int128 ll;
int main()
{
//ios::sync_with_stdio(false); cin.tie(nullptr), cout.tie(nullptr);
int t;
cin>>t;
while(t--)
{
ll n,a,b;
a = read(),b = read(),n = read();
ll x = a,y = b;
map<pair<ll,ll>,int>mp;
x %= n,y %= n;
ll ans = 100*100*2;
while(mp.find({x,y})==mp.end())
{
mp[{x,y}] = 1;
ll tmp = x*x+y*y;
if(tmp==0)break;
ans = min(ans,tmp);
ll step = min((n-x+a-1)/a,(n-y+b-1)/b);
x += a*step;
y += b*step;
x %= n,y %= n;
}
write(ans),cout<<"\n";
}
return 0;
}