比赛链接：The 2023 ICPC China Shaanxi Provincial Programming Contest - Dashboard - Contest - QOJ.ac

A

题意：给定一个包含加减括号的式子，涉及到的数字都是一位数。在式子中最多出现两个问号，现需要在问号填入数字，使得式子的值最大。

直接枚举“0 0”，“0 9”，“9 0”，“9 9”即可。

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
int cal(string s)
{
    int len=s.length();

    stack<char>op;
    string ex;
    ex.clear();
    for(int i=0;i<len;i++)
    {
        if(s[i]>='0' && s[i]<='9')ex.push_back(s[i]);
        else
        {
            if(op.empty())op.push(s[i]);
            else if(s[i]=='(')op.push(s[i]);
            else if(s[i]=='+'||s[i]=='-')
            {
                if(op.top()!='(')
                {
                    ex.push_back(op.top());
                    op.pop();
                    op.push(s[i]);
                }
                else
                {
                    op.push(s[i]);
                }
            }
            else if(s[i]==')')
            {
                while(op.top()=='+'||op.top()=='-')
                {
                    ex.push_back(op.top());
                    op.pop();
                }
                
                op.pop();
            }
        }
        // cout<<ex<<endl;
    }
    while(op.size())ex.push_back(op.top()),op.pop();
    // cout<<ex<<endl;

    len=ex.size();
    stack<int>num;
    for(int i=0;i<len;i++)
    {
        if(ex[i]>='0'&&ex[i]<='9')
        {
            num.push((ex[i]-'0'));
        }
        else
        {
            int b=num.top();
            num.pop();
            int a=num.top();
            num.pop();
            int t;
            if(ex[i]=='+')t=a+b;
            else t=a-b;
            num.push(t);
        }
    }
    // cout<<num.top()<<endl;
    return num.top();
}

signed main()
{
    string s;
    cin>>s;
    int len=s.length();
    int pos[3],cnt=0;
    for(int i=0;i<len;i++)
    {
        if(s[i]=='?')
        {
            cnt++;
            pos[cnt]=i;
        }
    }
    if(cnt==0)
    {
        cout<<cal(s);
    }
    if(cnt==1)
    {
        string st;
        st=s;
        st[pos[1]]='9';
        int ans=cal(st);
        st[pos[1]]='0';
        ans=max(ans,cal(st));

        // cout<<st<<endl;
        cout<<ans;
    }
    if(cnt==2)
    {
        string st;
        st=s;
        st[pos[1]]='0';
        st[pos[2]]='0';
        // cout<<st<<endl;
        int ans=cal(st);
        

        st[pos[1]]='0';
        st[pos[2]]='9';
        // cout<<st<<endl;
        ans=max(ans,cal(st));
        

        st[pos[1]]='9';
        st[pos[2]]='0';
        // cout<<st<<endl;
        ans=max(ans,cal(st));
        
        
        st[pos[1]]='9';
        st[pos[2]]='9';
        // cout<<st<<endl;
        ans=max(ans,cal(st));
        cout<<ans;
    }
    // system("pause");
    return 0;
}

E

题意：有 $n$ 个人排成一排，每次可以在 $1\sim n-1$ 个人中任选一些参加一场游戏。现在每个人有一个 $a_i$ 值，要满足 $b_i+c_i\leq a_i$ ，其中：

$b_i$ 表示玩家 $i$ 参与游戏而玩家 $i+1$ 没参加游戏的场次；

$c_i$ 表示玩家 $i$ 没参加游戏而玩家 $i+1$ 参加游戏的场次。认为玩家 $n$ 与玩家1相邻。

求最多的比赛场次。

易得每次选取一段连续的玩家 $l\sim r$ 时，只有 $c_{l-1},b_r$ 加1.要使游戏场次最多，则每次选取连续区间，相当于有一数组 $a$ ，每次任选两个数减1，但是每个数不能比0小，求最多操作次数。

和cf上某一题相同结论。

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

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    int maxx = 0;
    i64 sum = 0;
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        maxx = max(a, maxx);
        sum += a;
    }
    
 if(sum/2<maxx)cout<<sum-maxx;
    else cout << sum/2 << "\n";
    
    return 0;
}

math

G

题意：给定一个排列 $p$ ，求 $p$ 的每一个前缀排序后的中位数。

对顶堆模板题。维护一个大根堆和一个小根堆实现动态维护。

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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n;
int a[10000010],p[10000010];
int mid;
LL ans,qp=19;
priority_queue <int> q1,q2;
int main(){
    scanf("%d%d",&n,&a[0]);
    for(int i=1;i<=n;++i)   p[i]=i;
    for(int i=1;i<=n;++i)   a[i]=(1ll*a[i-1]*998244353+1000000007)%1000000009;
    for(int i=1;i<=n;++i)   swap(p[i],p[a[i]%i+1]);
    mid=p[1];
    ans=mid*19%998244353;
    for(int i=2;i<=n;++i){
        qp=qp*19%998244353;
        if(i&1){
            if(p[i]>-q2.top())   q2.push(-p[i]),mid=-q2.top(),q2.pop();
            else if(p[i]>q1.top())  mid=p[i];
            else q1.push(p[i]),mid=q1.top(),q1.pop();
            ans=(1ll*ans+mid*qp%998244353)%998244353;
        }
        else{
            if(p[i]>mid)    q2.push(-p[i]),q1.push(mid);
            else q1.push(p[i]),q2.push(-mid);
            ans=(1ll*ans+q1.top()*qp%998244353)%998244353;
        }
    }
    printf("%lld",ans);
}

对顶堆

I

题意：水题，模拟就完了

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
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int n,m,q;
struct node{
    int a,b,id;
}a[1010];
bool cmp(node a,node b){
    return a.a>b.a;
}
int rr[1010],vis[1010];
set <int> s;
signed main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i)   scanf("%d%d",&a[i].a,&a[i].b),a[i].id=i;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;++i)   rr[a[i].id]=i;
    while(q--){
        int op,x;
        scanf("%d%d",&op,&x);
        if(op==1)           scanf("%d",&a[rr[x]].b);
        else{
            for(int i=1;i<=n;++i)   vis[i]=0;
            for(int i=1;i<=n;++i){
                if(a[i].b==1){
                    vis[i]=1;
                    break;
                }
            }
            for(int i=1,cnt=2;i<=n&&cnt<=m;++i){
                if(vis[i])  continue;
                vis[i]=1;
                ++cnt;
            }
            if(vis[rr[x]]==1)   puts("1");
            else puts("0");
        }
    }
}

J

题意：给定一个 $n\times n$ 的地图，有些店不能走，现在从 $(1,1)$ 出发到达 $(n,n)$ 。每一步除了上下左右走之外还可以瞬移：
$$
f^i(x,y)=f^{i-1}(y+1,x)\ or\ (x,y)\ if\ i=0
$$
$i$ 可以任选但不能超过 $k$ 。求最小步数。

可以发现瞬移在图上显示出使两条斜角线，故仍可采用 $bfs$ ，只是在瞬移时采用并查集的思想，将从某一个点采用不限 $i$ 的瞬移能到达的地方并为一个并查集，并利用路径压缩，在存储时将二维地图 $(i,j)$ 压缩成 $i\times (n+1)+j$ ，因此在对每个点进行扩展时直接找到这个点所属并查集的扩展的最远点进行扩展，每个点只扩展一次，复杂度为 $O(n^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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <bits/stdc++.h>
using namespace std;

constexpr int dx[4] = {0, 0, -1, 1};
constexpr int dy[4] = {-1, 1, 0, 0};
int dis[5006][5006];
int f[5001 * 5001];

int find(int x)
{
    while (x != f[x])
    {
        x = f[x] = f[f[x]];
    }
    return x;
}

int main()
{

    int n, k;
    cin >> n >> k;
    for (int i = 0; i < 5006; i++)
    {
        for (int j = 0; j < 5006; j++)
            dis[i][j] = -1;
    }
    dis[0][0] = 0;

    vector<std::string> s(n);
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }

    queue<pair<int, int>> q;
    q.emplace(0, 0);

    iota(f, f + (n + 1) * (n + 1), 0);

    while (!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int k = 0; k < 4; k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if (0 <= nx && nx < n && 0 <= ny && ny < n && dis[nx][ny] == -1 && s[nx][ny] == '.')
            {
                q.emplace(nx, ny);
                dis[nx][ny] = dis[x][y] + 1;
            }
        }
        while (true)
        {
            int u = find(x * (n + 1) + y);
            int nx = u / (n + 1), ny = u % (n + 1);
            if (nx == n || ny == n || nx + ny > x + y + k)
            {
                break;
            }
            if (dis[nx][ny] == -1 && s[nx][ny] == '.')
            {
                q.emplace(nx, ny);
                dis[nx][ny] = dis[x][y] + 1;
            }
            f[nx * (n + 1) + ny] = (ny + 1) * (n + 1) + nx;
        }
    }

    cout << dis[n - 1][n - 1] << "\n";

    return 0;
}

bfs/dfs

K

题意：在一个 $n\times m$ 的方格内注水，若某一个空格相邻的至少两个方格内有水，那么这个方格就会被填满水。求初始最少要注入多少水。

在最大的正方形中对角线注满水，然后隔一行/列注一格。

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

int main()
{
    int n,m;
    cin>>n>>m;
    int ans;
    if(n>m) ans=m+(n-m+1)/2;
    else ans=n+(m-n+1)/2;
    cout<<ans<<endl;
    if(n>m)
    {
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(i==j)cout<<"1 ";
                else cout<<"0 ";
            }
            cout<<endl;
        }
        for(int i=1;i<=n-m;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(i%2==0 && j==1 || (n-m)%2==1&&i==n-m&&j==1)cout<<"1 ";
                else cout<<"0 ";
            }
            cout<<endl;
        }
    }

    else
    {
        int mp[n+1][m+1];
        memset(mp,0,sizeof(mp));
        for(int i=1;i<=n;i++)
        {
            mp[i][i]=1;
        }
        for(int i=n+1;i<=m;i++)
        {
            if((i-n)%2==0)mp[1][i]=1;
        }
        if((m-n)%2==1)mp[1][m]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)cout<<mp[i][j]<<" ";cout<<endl;
        }    
    }
    return 0;
}