记录下第一次一个人vp整场比赛，而且还打到金牌区啦~

虽然是省赛

比赛地址：Dashboard - The 2024 International Collegiate Programming Contest in Hubei Province, China - Codeforces

A

题意：给出 $x,y$ ，求 $a,b$ 满足：
$$
\sqrt{\frac{lcm(x,y)}{gcd(x,y)}}=a\sqrt{b}
$$
且 $a\times b$ 最大。

令 $a=1$ 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<bits/stdc++.h>
using namespace std;
#define LL long long
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        LL a,b;
        cin>>a>>b;
        LL ans=a*b/__gcd(a,b)/__gcd(a,b);
        cout<<1<<" "<<ans<<endl;
    }
    return 0;
}

B

题意：在二维平面上给出 $n$ 个点，在其中选取若干个点构成凸多边形且使多边形面积最小。$n\leq 100$

很明显构成三角形面积最小。直接暴力枚举三个顶点，求面积时用叉积即可。注意判断三角形是否存在。

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
#include<bits/stdc++.h>
using namespace std;

pair<int,int>v[200];

double cross(int i,int j,int k)
{
    pair<int,int>ij,ik;
    ij={v[i].first-v[j].first,v[i].second-v[j].second};
    ik={v[i].first-v[k].first,v[i].second-v[k].second};
    return (double)1*abs(ij.first*ik.second-ij.second*ik.first)/2;
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>v[i].first>>v[i].second;

    double ans=9999999999;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=n;k++)
            {
                if(i==j || j==k || i==k)continue;
                // cout<<i<<" "<<j<<" "<<k<<" "<<cross(i,j,k)<<endl;
                double tmp=cross(i,j,k);
                if(tmp>0.1)
                ans=min(cross(i,j,k),ans);

            }
        }
    }
    if(ans==9999999999 || ans<0.5)cout<<-1<<endl;
    else cout<<ans<<endl;
}

int main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

E

水题

G

题意：在一个 $19\times 19$ 的棋盘上下围棋，给出每一步之后黑棋和白起分别被提多少颗。

一个大模拟题，时限4s，可以暴力过。

每一步都全局dfs一次，先找对方每一个块的气，若气为零就把这个块清除掉，然后再找下棋方每一个块的气。

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
#include<bits/stdc++.h>
using namespace std;

int bd[20][20];
int t;
bool v[20][20];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int sum;
int ans;
vector<pair<int,int> >qz;

void dfs(int x,int y)
{
    qz.push_back({x,y});
    v[x][y]=1;
    for(int i=0;i<=3;i++)
    {
        int nx=x+dx[i];
        int ny=y+dy[i];
        if(nx<1 || nx>19 || ny<1 || ny>19 || v[nx][ny])continue;
        if(bd[nx][ny]==0)sum++;
        else if(bd[nx][ny]==t)dfs(nx,ny);
    }

}

void check()
{
    memset(v,0,sizeof(v));
    for(int i=1;i<=19;i++)
    {
        for(int j=1;j<=19;j++)
        {
            if(!v[i][j] && bd[i][j]==t)
            {
                // cout<<t<<" "<<i<<" "<<j<<" "<<bd[i][j]<<" "<<endl;
                qz.clear();
                sum=0;
                dfs(i,j);
                // cout<<"sum="<<sum<<endl;
                if(!sum && qz.size())
                {
                    ans+=qz.size();
                    for(auto i:qz)
                    {
                        bd[i.first][i.second]=0;
                    }
                }
                
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin>>n;
    for(int i=1,op=1;i<=n;i++,op^=3)
    {
        int x,y;
        cin>>x>>y;
        bd[x][y]=op;
        t=op^3;
        ans=0;
        check();
        int ans1=ans;
        ans=0;
        t=op;
        check();
        int ans2=ans;
        if(op==1)cout<<ans2<<" "<<ans1<<endl;
        else cout<<ans1<<" "<<ans2<<endl;
        // for(int p=1;p<=19;p++)
        // {
        //     for(int q=1;q<=19;q++)cout<<bd[p][q]<<" ";cout<<endl;
        // }
    }
    return 0;
}

字典树

H

题意：在一个 $1000\times 1000$ 的池塘里有不超过10个池塘有鱼，每个池塘的鱼不超过3条，现在用炸弹炸池塘，每次以炸弹为中心的“十”字范围内5个池塘每个池塘的鱼减少1条。求炸死所有的鱼最少需要多少次。

考虑状压dp来存状态。把状态构造成一个不超过10位的四进制数，存下所有能炸到鱼的位置，这样的位置不超过50个，然后用bfs的方法暴力炸鱼，最终状态为 $dp[0]$ 。

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
#include<bits/stdc++.h>
using namespace std;
#define LL long long
LL pow4[20];
int dp[2000005];
int v[2000005];
int n,m,k;
//检查这一位是否为0
bool check(LL st,int p)
{
    st/=pow4[p];
    st%=4;
    if(st)return 1;
    else return 0;
}

void de(long long status)
{
    int dd[20]={0};
    int tot=0;
    while(status)
    {
        dd[++tot]=status%4;
        status/=4;
    }
    for(int i=k;i>=1;i--)cout<<dd[i];cout<<endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    pow4[0]=1;
    for(int i=1;i<=12;i++)pow4[i]=pow4[i-1]*4;
    
    cin>>n>>m>>k;
    LL status=0;
    map<pair<int,int>,int>mp;
    vector<pair<int,int> >pos;

    for(int i=1;i<=k;i++)
    {
        int x,y,cnt;
        cin>>x>>y>>cnt;
        mp[{x,y}]=i;
        pos.push_back({x,y});
        if(x>1)pos.push_back({x-1,y});
        if(x<n)pos.push_back({x+1,y});
        if(y>1)pos.push_back({x,y-1});
        if(y<m)pos.push_back({x,y+1});
        status+=pow4[i-1]*cnt;
    }

    int ans=0;
    queue<LL>q;
    bool flag=0;
    dp[status]=0;
    q.push(status);
    while(q.size())
    {
        LL sta=q.front();
        q.pop();

        int bit[20]={0};
        int tot=0;
        LL tst=sta;
        while(tst)
        {
            bit[tot++]=tst%4;
            tst/=4;
        }

        // for(int i=k-1;i>=0;i--)cout<<bit[i];cout<<endl;

        for(auto i:pos)
        {
            int x=i.first;
            int y=i.second;

            LL st=sta;
            // cout<<x<<" "<<y<<" "<<mp[{x,y}]<<endl;
            if(mp[{x,y}]!=0)
            {
                if(bit[mp[{x,y}]-1])st-=pow4[mp[{x,y}]-1];
            }
            if(mp[{x-1,y}]!=0)
            {
                if(bit[mp[{x-1,y}]-1])st-=pow4[mp[{x-1,y}]-1];
            }
            if(mp[{x+1,y}]!=0)
            {
                if(bit[mp[{x+1,y}]-1])st-=pow4[mp[{x+1,y}]-1];
            }
            if(mp[{x,y-1}]!=0)
            {
                if(bit[mp[{x,y-1}]-1])st-=pow4[mp[{x,y-1}]-1];
            }
            if(mp[{x,y+1}]!=0)
            {
                if(bit[mp[{x,y+1}]-1])st-=pow4[mp[{x,y+1}]-1];
            }

            if(!v[st])
            {
                v[st]=1;
                dp[st]=dp[sta]+1;
                q.push(st);
                // cout<<"x="<<x<<" y="<<y<<" step="<<dp[st]<<" ";
                // de(st);
                // system("pause");
            }
            
        }

    }
    cout<<dp[0];
    // system("pause");
    return 0;
}

dp，bfs/dfs

J

题意：给出一个长为 $n$ 的数组 $a$ ，每次任选两个数将其删除并将这两个数的平均数加入数组。求最后的数的期望。

可以猜测最后的数就是平均数，因为每个数被选的概率相同。

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
#include<bits/stdc++.h>
using namespace std;

const int mod=998244353;

long long qsm(long long base, long long power) 
{
    long long result = 1;
    while (power > 0) 
    {
        if (power & 1) result = result * base % mod;
        power >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

int main()
{
    int n;
    cin>>n;
    long long sum=0;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        sum=(sum+x)%mod;
    }
    long long d=qsm(n,mod-2);
    sum=(sum*d)%mod;
    cout<<sum;
    return 0;
}

L

题意：有一个包含无数多个整数点的完全图，任两个点的距离 $d(i,j)=lcm(i,j)$ 。先给出两个点 $a,b$ ，求这两个点的最短路。

分类讨论，假设 $a<b $：

  1. 若 $a=b $ ，答案是0；
  2. 若 $b%a=0$ ，答案是 $b$ ;
  3. 若 $gcd(a,b)!=1$ ，答案是 $a+b$ ；
  4. 若 $gcd(a,b)=1$ ，那么从 $a$ 到 $b$ 只可能经过 $a$ 、$b$ 、$2$ 、$a$ 的最小质因数、$b$ 的最小质因数。找出这5个数两两的距离跑floyed即可。若分类讨论很可能漏情况。
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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=1e9;

int Lcm(int a,int b)
{
    return a*b/__gcd(a,b);
}

void solve()
{
    int a,b;
    cin>>a>>b;
    if(a>b)swap(a,b);
    if(a==b)
    {
        cout<<0<<endl;
        return ;
    }
    if(b%a==0)
    {
        cout<<b<<endl;
        return ;
    }
    if(__gcd(a,b)!=1)
    {
        cout<<a+b<<endl;
        return ;
    }

    int yza=0,yzb=0;
    for(int i=2;i<=sqrt(a);i++)
    {
        if(a%i==0)
        {
            yza=i;
            break;
        }
    }
    if(!yza)yza=inf;

    for(int i=2;i<=sqrt(b);i++)
    {
        if(b%i==0)
        {
            yzb=i;
            break;
        }
    }
    if(!yzb)yzb=inf;
    
    int f[10][10];
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=5;i++)f[i][i]=0;

    int tmp[6]={0,a,b,2,yza,yzb};
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=5;j++)
        {
            if(i==j)f[i][j]=0;
            else f[i][j]=Lcm(tmp[i],tmp[j]);
        }
    }

    for(int k=1;k<=5;k++)
    {
        for(int i=1;i<=5;i++)
        {
            for(int j=1;j<=5;j++)
            {
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            }
        }
    }

    cout<<f[1][2]<<endl;
    
}

signed main()
{
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}

最短路，math