Butteruni Blog
0%

2023牛客暑期多校1（A B D H J K M）

发表于 更新于 分类于

题目链接

由易到难为：D，J，K，HM，AB

D. Chocolate

简单结论，除了1 x 1会直接拿完，其他情况先手必胜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m;
int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    if(n == 1 && m == 1)
        cout<<"Walk Alone";
   	else 
        cout << "Kelin";
    return 0;
}

J. Roulette

分析一下可知每次最多前进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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
ll inv[60];
ll n,m;
ll qpow(ll x,ll y)
{
    ll res = 1;
    while(y)
    {
        if(y & 1)
            res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return ((res % mod) + mod) % mod;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin>>n>>m;
    ll res = 1;
    ll a = 0,b = 0;
    for(ll i = 1;i <= 70;++i)
    {
        if((res << i) >= (n + 1) && (a == 0))
        {
            a = i - 1;
        }
        if((res << i) > (n + m))
        {
            b = i;
            break;
        }
    }
//     cout << a << " " << b << '\n';
    for(ll i = a - 1;i <= b + 1;++i)
    {
        ll temp = ((ll)1 << i);
        inv[i] = qpow(temp,mod - 2);
    }
    ll ans = 1;
    ll sum = 0;
    for(ll i = a;i < b;++i)
    {
        ll temp = 0;
        if(i == a)
        {
//             cout << "st" << "\n";
            temp = ((ll)1 << (i + 1)) - (n + 1);
            if(a == b - 1)
            {
                temp = m;
            }
        }else if(i == b - 1)
        {
//             cout << "end" << '\n';
            temp = (n + m + 1) - ((ll)1 << i);
        }else
        {
            temp = ((ll)1 << i);
        }
//         cout << temp << ' ' << i << '\n';
        ll son = ((ll)1 << i) - 1;
        ans = ((ans % mod) * (qpow(son * inv[i] % mod,temp) % mod) % mod + mod) % mod;
//         cout << ans << '\n';
    }
    cout << ans << '\n';
    return 0;
}

K. Subdivision

要求裂边后距离点 距离小于等于K的点最多，先考虑如何裂边使得收益最大。将所有边分成两类考虑，一类为删去后不影响当前图上个点距离 最短路（即成环的边)，此类边可不断分裂至上限；第二类为除第一类边的集合。

考虑第二类边如何分裂，考虑最短路径 ，若无法到达 则连接该条最短路的第二类边无需分裂（分裂后贡献为0） ，若可以到达，则考虑如何裂边，显然若 存在一条以上出边则在 后侧分裂，否则损失 后侧的点，否则则在 间裂边至上限。

整个过程先使用bfs处理一边最短路，然后遍历整个图即可

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
ll h[N],ne[N << 1],e[N << 1],idx;
ll dis[N];
ll d[N];
ll n,m,k;
bool vis[N],vis_link[N << 1];
ll ans = 0;
void add(int a,int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
void bfs()
{
    queue<int>q;
    memset(dis,-1,sizeof(dis));
    q.push(1);
    dis[1] = 0;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        for(int i = h[cur];i != -1;i = ne[i])
        {
            int j = e[i];
            if(j != cur && dis[j] == -1)
            {
                dis[j] = dis[cur] + 1;
                q.push(j);
            }
        }
    }
}
void dfs(int cur,int fa)
{
    if(vis[cur])
        return;
    ans++;
    vis[cur] = 1;
    for(int i = h[cur];i != -1;i = ne[i])
    {
        int j = e[i];
        if(j == fa)
            continue;
        if(dis[j] == dis[cur] + 1) //为第二类边
        {
            if(dis[j] <= k) 
                dfs(j,cur);
        }else if(!vis_link[i]) //为第一类边
        {
            ans += 2 * k - dis[j] - dis[cur];
            vis_link[i] = 1,vis_link[i ^ 1] = 1; 
        }
    }
    if(d[cur] == 1 && cur != 1) //可到达且出度为1
    {
        ans += k - dis[cur];
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n >> m >> k;
    memset(h,-1,sizeof(h));
    for(int i = 1;i <= m;++i)
    {
        int v,u;
        cin >> u >> v;
        add(u,v);
        add(v,u);
        d[u]++,d[v]++;
    }
    bfs();
    dfs(1,0);
    cout << ans << '\n';
    return 0;
}

H. Matches

如果暴力比较每种交换的贡献复杂度为 考虑如何优化选择，将每次的 定义成一个由 指向 的箭头， 时箭头向上， 箭头向下，题目所求即为两个箭头最大重合部分。对于一个向上箭头，与向上箭头交换后贡献为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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long ll;
ll a[N],b[N];
priority_queue<ll>po_up;
priority_queue<ll>po_down;
struct Po
{
    ll st,ed;
    int dir;
}pos[N];
bool cmp(Po x,Po y)
{
    if(x.st != y.st)
    {
        return x.st < y.st;
    }
    if(x.ed != y.ed)
    {
        return x.ed < y.ed;
    }
    return x.dir < y.dir;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1;i <= n;++i)
        cin >> a[i];
    for(int i = 1;i <= n;++i)
        cin >> b[i];
    ll sum = 0;
    for(int i = 1;i <= n;++i)
    {
        if(a[i] > b[i]) // 向上箭头
        {
            pos[i].dir = 1;
        }else // 向下箭头
        {
            pos[i].dir = -1;
        }
        sum += abs(a[i] - b[i]);
        pos[i].st = min(a[i],b[i]);
        pos[i].ed = max(a[i],b[i]);
    }
    ll ans = 0;
    sort(pos + 1,pos + 1 + n,cmp);
    for(int i = 1;i <= n;++i)
    {
        if(pos[i].dir == 1)
        {
            if(!po_down.empty())
            {
                ans = max(ans,min(po_down.top(),pos[i].ed) - pos[i].st);
            }
            po_up.push(pos[i].ed);
        }
        if(pos[i].dir == -1)
        {
            if(!po_up.empty())
            {
                ans = max(ans,min(po_up.top(),pos[i].ed) - pos[i].st);
            }
            po_down.push(pos[i].ed);
        }
    }
    cout << sum - 2 * ans << '\n';
    return 0;
}

M. Water

若 无法用 线性表示则无法通过合法操作得到 ，对于一种线性表示 ，有唯一确定操作数 ，于是使用拓展欧几里德找到最接近原点的线性表示后枚举几种取最小值

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b)
    {
        x=1;y=0;
        return a;
    }
    ll k=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return k;
}
ll calc(ll x,ll y)
{
    if(x >= 0 && y >= 0)
    {
        return 2 * x + 2 * y;
    }else{
        if(x < 0)
        {
            if(y == 1)
            {
                return y - 2 * x;
            }else
            {
                return 2 * y - 2 * x - 1;
            }
        }
        else
        {
            if(x == 1)
            {
                return x - 2 * y;
            }else
            {
                return 2 * x - 2 * y - 1;
            }
        }
    }
}
int t;
ll a,b,n;
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> a >> b >> n;
        if(a > b)
            swap(a,b);
        ll x,y;
        ll t = exgcd(a,b,x,y);
        if(n % t)
        {
            cout << -1 << '\n';
        }else 
        {
            ll ans = 1e18;
            a /= t,b /= t,n /= t;
            ll ty = n / b;
            n %= b;
            ll tx = n / a;
            n %= a;
            x *= n,y *= n;
            x += tx ,y += ty;
            for(ll i = x / b - 4;i <= x / b + 4;++i)
            {
                ans = min(ans,calc(x - i * b,y + i * a));
            }
            cout << ans << endl;
        }
    }
}

A. Almost Correct

根据已知条件 显然基于交换的排序能在 次操作内使所有长度为 的01串变得有序，又已知题目要求恰无法使给定的字串 变得有序。于是关键在于使得 无序同时使操作数尽可能少。控制字串 中始终有0在1右侧 （一旦交换使0全部在1左侧则字串有序）。

定义 为 中所有 的集合， 为 中所有 的集合， 显然 中最大值 大于 中最小值 （已知 无序) 。考虑使其他字串有序，先在 内部排序使得 为 内所有点最大值，在 内排序使得 为 内最小值。对于所有除 外字串，这样操作后存在 !(s[l] == '1' && s[r] == '0')

之后固定 进行排序，使得字串除 外有序，接下来考虑如何有移动 使得整个字串有序且 无序。

接下来使得 转换成形如 ，由于第一种操作后其他字串不会出现 s[l] == '1' && s[r] == '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
#include <bits/stdc++.h>
using namespace std;
const int N = 20;
int a[N];
int n;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int t;
    cin >> t;
    while(t--)
    {    
        cin >> n;
        string s;
        cin >> s;
        vector<int> s1;
        vector<int> s0;
        for(int i = 0;i < n;++i)
        {
            if(s[i] == '1')
            {
                a[i + 1] = 1;
                s1.push_back(i + 1);
            }
            else 
            {
                a[i + 1] = 0;
                s0.push_back(i + 1);
            }
        } 
        int l_1 = s0[0],r_1 = s0[s0.size() - 1];
        int l_2 = s1[0],r_2 = s1[s1.size() - 1];
        vector<pair<int,int>> ans;
        for(int i = 1;i <= n;++i)
        {
            if(a[i] == 1)
            {
                if(i != l_2)
                    ans.push_back(make_pair(l_2,i));
            }else
            {
                if(i != r_1)
                {
                    ans.push_back(make_pair(i,r_1));
                }
            }
        }
        for(int i = 1;i <= n;++i)
        {
            if(i == l_2 || i == r_1)
                continue;
            for(int j = i + 1;j <= n;++j)
            {
                if(j == l_2 || j == r_1)
                {
                    continue;
                }
                ans.push_back(make_pair(i,j));
            }
        }
        for(int i = s0.size();i > l_2;--i)
        {
            ans.push_back(make_pair(l_2,i));    
        }
        for(int i = 1;i < l_2;++i)
        {
            ans.push_back(make_pair(i,l_2));
        }
        for(int i = s0.size() + 1;i < r_1;++i)
        {
            ans.push_back(make_pair(i,r_1));
        }
        for(int i = n;i > r_1;--i)
        {
            ans.push_back(make_pair(r_1,i));
        }
        cout << ans.size() << '\n';
        for(auto x:ans)
        {
            cout << x.first << " " << x.second << '\n';
        }
    }
}

B. Anticomplementary Triangle

感觉和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
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double eps = 1e-8;
const double inf = 1e20;
const double pi = acos(-1.0);
const int maxp = 1010;
const int N = 1e6 + 10;
int sgn(double x)
{
    if(fabs(x) < eps)return 0;
    if(x < 0)return -1;
    return 1;
}
struct Point
{
    int x, y;
    Point(){};
    Point (int _x, int _y)
    {
        x = _x,y = _y;
    }
    bool operator == (const Point b)
    {
        return sgn(x - b.x) == 0 && sgn(y - b.y) == 0;
    }
    bool operator < (const Point b)
    {
        return sgn(x - b.x) == 0 ? sgn(y - b.y) < 0:x < b.x;
    }
    Point operator -(const Point b)
    {
        return Point(x - b.x,y - b.y);
    }
    Point operator +(const Point b)
    {
        return Point(x + b.x,y + b.y);
    }
};
vector<Point> po;
ll cross(Point a,Point b)
{
    return((ll)a.x * b.y - (ll)a.y * b.x);
}
ll calc_area(int a,int b,int c)
{
    return cross(po[a] - po[b],po[c] - po[b]);
}
int n;
int nex(int x)
{
    if(x < n)
        return x + 1;
    else 
        return 1;
}
int pre(int x)
{
    if(x != 1)
        return x - 1;
    else 
        return n;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin >> n;
    po.clear();
    po.resize(n + 10);
    for(int i = 1;i <= n;++i)
    {
        cin >> po[i].x >> po[i].y;
    }
    int r = 1,s = 2,t = 3;
    while(1)
    {
        ll area = calc_area(r,s,t);
        if(calc_area(nex(r),s,t) > area)
        {    
            r = nex(r);
        }else if(calc_area(r,nex(s),t) > area)
        {
            s = nex(s);
        }else if(calc_area(r,s,nex(t)) > area)
        {
            t = nex(t);
        }else if(calc_area(pre(r),s,t) > area)
        {    
            r = pre(r);
        }else if(calc_area(r,pre(s),t) > area)
        {
            s = pre(s);
        }else if(calc_area(r,s,pre(t)) > area)
        {
            t = pre(t);
        }else
        {
            cout << r << " " << s << " " << t << '\n';
            break;
        }
    }

}