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;
}