2020 ICPC 南京 EFKL

Nannan Lv5
  2023-10-04 12:43 2023-10-04 12:43 Created   2024-09-30 17:08:01 2024-09-30 17:08:01 Updated      

2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)

E. Evil Coordinate

思路：因为如果给定了起点和初始走法，其实我们的终点是一定确定的。我们不妨让上下左右的连着一块走，那么对于一共有种走法(全排列)，我们暴力枚举然后就可以了。

为什么这样是对的？为什么一条路走到底就可以把所以情况考虑完全了？

其实答案走法有很多种，但是我们可以把答案的走法拼接成连续的走法，这样就可以实现了。

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
#define int long long
int a[25][5];
int cnt[5];
int tmp[5];
bool vis[5];
int cn = 0;
void dfs(int step)
{
    if(step>4)
    {
        cn++;
        for(int i = 1;i<=4;i++)
            a[cn][i] = tmp[i];
        return;
    }

    for(int i = 1;i<=4;i++)
    {
        if(!vis[i])
        {
            vis[i] = true;
            tmp[step] = i;
            dfs(step+1);
            tmp[step] = 0;
            vis[i] = false;
        }
    }
}

void init()
{
    dfs(1);
}

signed main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
  
    int t;
    cin>>t;
    init();
    while(t--)
    {
        int mx,my;
        cin>>mx>>my;
        string s;
        cin>>s;
        int sz = s.size();
        s = "?"+s;
        memset(cnt,0,sizeof(cnt));
        for(int i = 1;i <= sz;i++)
        {
            if(s[i]=='R')cnt[1]++;
            else if(s[i]=='L')cnt[2]++;
            else if(s[i]=='U')cnt[3]++;
            else if(s[i]=='D')cnt[4]++;
        }

        //R1,L2,U3,D4
        bool flag = false;
        for(int i = 1;i<=24;i++)
        {
            bool ok = true;
            int lastx = 0,lasty = 0;
            int x = 0,y = 0;

            for(int j = 1;j<=4;j++)
            {
                //cout<<"i = "<<i<<"\n";
               // cout<<"a[i][j] = "<<a[i][j]<<"\n";
                if(a[i][j]==1&&cnt[1]){
                    x+=cnt[1];
                   // cout<<" x = "<<x<<" lastx = "<<lastx<<"\n";
                    if(y==my)
                    {
                        if((lastx<=mx&&mx<=x)||(x<=mx&&mx<=lastx)){
                            ok = false;
                        }else lastx = x;
                    }
                    else lastx = x;
                }
                else if(a[i][j]==2&&cnt[2]){
                    x-=cnt[2];
                    if(y==my)
                    {
                        if((lastx<=mx&&mx<=x)||(x<=mx&&mx<=lastx)){
                            ok = false;
                        }else lastx = x;
                    }
                    else lastx = x;
                }
                else if(a[i][j]==3&&cnt[3]){
                    y += cnt[3];
                    if(x==mx)
                    {
                        if((lasty<=my&&my<=y)||(y<=my&&my<=lasty)){
                            ok = false;
                        }
                        else lasty = y;
                    }else lasty = y;
                }
                else if(a[i][j]==4&&cnt[4]){
                    y -= cnt[4];
                    if(x==mx)
                    {
                        if((lasty<=my&&my<=y)||(y<=my&&my<=lasty)){
                            ok = false;
                        }
                        else lasty = y;
                    }else lasty = y;
                }

            }
            if(ok)
            {
                for(int j = 1;j<=4;j++)
                {
                    for(int k = 1;k<=cnt[a[i][j]];k++)
                    {
                        if(a[i][j]==1)
                            cout<<"R";
                        else if(a[i][j]==2)
                            cout<<"L";
                        else if(a[i][j]==3)
                            cout<<"U";
                        else cout<<"D";
                    }
                }
                cout<<"\n";
                flag = true;
                break;
            }
        }
        if(!flag)
            cout<<"Impossible\n";
    }

    return 0;
}

F.Fireworks

思路：一开始我们想成了求平均期望，思路上有问题的，因为题目求的是最优的。是求最小期望花费。

我们要做次点亮一次，那么这次中至少有一个是完美的概率就是全部都不完美的概率，那全部都不完美的概率就是次方，即至少有一个是完美的概率是。

期望制作轮数，期望时间：

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
const double eps = 1e-6;
double n,m,p,q;

double f(double x)
{
    return (x*n+m)/(1.0-pow(q,x));
}
/*
3
1 1 5000
1 1 1
1 2 10000
*/

int main()
{
   // ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        
        cin>>n>>m>>p;
        p = 1.0*p/10000.0;
        q = 1.0-p;
        //cout<<"p = "<<p<<" q = "<<q<<endl;
        ll l = 1,r = 1e9;
        while(r-l>2)
        {
            int mid1 = l+(r-l)/3;
            int mid2 = r-(r-l)/3;
            if(f(mid1)<=f(mid2))r = mid2;
            else l = mid1;
        }
        double ans = 1e18;
        for(int i = l;i <= r;i++)
            ans = min(ans,f(i));
        printf("%.10lf\n",ans);
    }
    return 0;
}

K. K Co-prime Permutation

思路：因为每一个数一定和下一个数互质，注意和所有数都互质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,k;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    cin>>n>>k;
    if(k==0)cout<<-1<<"\n";
    else{
        for(int i = 1;i<=k-1;i++)
            cout<<i+1<<" ";
        cout<<1<<" ";    
        for(int i = k+1;i<=n;i++)
            cout<<i<<" ";
    }
    return 0;
}

L. Let’s Play Curling

思路：求连续的红色的最大数量。注意可能有重叠。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
  
    int t;
    cin>>t;
    while(t--)
    {
        set<int>a,b;
        map<int,int>cnt;
        int n,m;
        cin>>n>>m;
        for(int i = 1;i <= n; i++){
            int x;
            cin>>x;
            a.insert(x);
            cnt[x]++;
        }
        for(int i = 1;i <= m; i++){
            int x;
            cin>>x;
            b.insert(x);
        }
        vector<int> v;
        for(auto x:a)
            v.push_back(x);
        for(auto x:b)
            v.push_back(x);
        sort(v.begin(), v.end());
        int tmp = 0,ans = 0;
        int k = v.size();
        for(int i = 0;i<k;i++)
        {
            if(a.find(v[i])!=a.end()&&b.find(v[i])==b.end())
                tmp += cnt[v[i]];
            else ans = max(ans,tmp),tmp = 0;
        }
        ans = max(ans,tmp);
        if(ans==0)cout<<"Impossible\n";
        else
            cout<<ans<<"\n";
    }

    return 0;
}
  • Title: 2020 ICPC 南京 EFKL
  • Author: Nannan
  • Created at : 2023-10-04 12:43:00
  • Updated at : 2024-09-30 17:08:01
  • Link: https://redefine.ohevan.com/2023/10/04/2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
2020 ICPC 南京 EFKL
  1. 2020-2021 ACM-ICPC, Asia Nanjing Regional Contest (XXI Open Cup, Grand Prix of Nanjing)
    1. E. Evil Coordinate
    2. F.Fireworks
    3. K. K Co-prime Permutation
    4. L. Let’s Play Curling