The 2023 ICPC 网络赛第二场 MDIELK

Nannan Lv5
  2023-09-25 21:53 2023-09-25 21:53 Created   2024-09-30 17:36:04 2024-09-30 17:36:04 Updated      

**The 2023 ICPC Asia Regionals Online Contest (2) **MDIELK

M Dirty Work

题意：总共有个问题，对于第个问题需要分钟。你可以随便选择一个没过的题去写，写完以后马上交，你有的概率会错，错了不能跳题，你要花额外的时间去。问你以最佳策略的最小罚时。

思路：因为有基础罚时(即做完这个题的总时间)，那么问题变成求前缀和的和的最小值。那么把小的放前面即可(每个值为)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// 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

题意：有条水平的直线和条垂直的直线交叉形成一个网格图。每一个点有一个花费(可以是负数)。当我们选择点，那么可以覆盖第行和第列。问最小花费是多少可以覆盖完所有。

思路：首先，很显然的和负数一定要选。又因为要全覆盖，那么每行至少有一个要选，每列至少有一个要选。

两种覆盖策略：

  1. 覆盖行
  2. 覆盖列

那么当我们选完和负数之后呢，如果还有没被覆盖的，优先选小的。

注意初始化！！！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// 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

题意：你受伤了，现在要恢复。一开始在恢复的第阶段，到第阶段才算恢复完全。

第天，你可以选择什么都不干就只是休息，那么每天可以恢复一个阶段，那么天恢复完全。你可以可以选择挑战自己，如果一旦挑战成功呢，你就会直接恢复完全，否则的话你会回到第阶段。其中挑战成功的概率是。

思路：我们连接每一个阶段和能到达的阶段，发现是一个图，每一条边有一个概率。那么因为我们采用的是最佳策略，我们会怎么做呢？我们一定会到达一个成功期望天数最小的点不断挑战。对于第天的成功概率是的话，成功的期望次数是,那么失败的期望的天数就是天，每次失败会回到，那么我们又从走到(花费)然后尝试()。注意挑战也要花费的天数所以。

那么对于第个点的期望天数就是：。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
// 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

题意：有个点，条边，形成一颗树。

给你条公交路线，从(表示两个点之间最短的树上距离)。我们可以从或者上车,可以从路径上任何一点下车。问你从号点到每一个点至少需要多少条公交路线。

思路：

考虑从(因为我们只能从1上车)做为起点加入队列，花费。

然后考虑从能到那些点，如果之前没被遍历到，那么去把它加入队列。

然后再以队列里面某个点为起点去往上眺，因为我们一开始是从开始的，那么之后的点一定可以到达的。如果某个点能到达，那么它的父亲也一定可以，我们也把它的父亲能到的点加入。一直重复，直到队列为空。

注意已经访问过的就不要重复访问了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
// 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

题意：我们定义，如果能把拆成偶数个部分，并且，我们称之为超级回文串。给你一个串,让你去找它有多少个超级回文子串。

思路：哈希+双指针

我们对于每个点和，去向两边扩展，直到找到离它最近的满足,统计答案，并更新

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 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

题意：一开始你在 ,每次你可以走。

假设当前的点是，那么你可以走到的点是

问你能走到的离最近的点的欧几里得距离的平方。

思路：我们发现最终的答案一定在红色框框内。

![image-20230925214515984](C:\Users\Zhou Yanan\Desktop\image-20230925214515984.png)

所以只有当它越界了才有可能是答案。

![image-20230925215023155](C:\Users\Zhou Yanan\Desktop\image-20230925215023155.png)

那么如果当前的坐标是，那么如果我要走到越界，那么我需要走

如果当我们走到之前走过的那就停止，因为之后都是一样的了。对于所有可能的答案取个即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 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;
}

  • Title: The 2023 ICPC 网络赛第二场 MDIELK
  • Author: Nannan
  • Created at : 2023-09-25 21:53:00
  • Updated at : 2024-09-30 17:36:04
  • Link: https://redefine.ohevan.com/2023/09/25/The 2023 ICPC Asia Regionals Online Contest (2)/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
The 2023 ICPC 网络赛第二场 MDIELK
  1. **The 2023 ICPC Asia Regionals Online Contest (2) **MDIELK
    1. M Dirty Work
    2. D Project Manhattan
    3. I Impatient Patient
    4. E Another Bus Route Problem
    5. L Super-palindrome
    6. K Super-knight