img

2024年中国传媒大学程序设计大赛（同步赛）

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
//两边扩展
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n;i--)
using ll = long long;
using namespace std;
const int N=2e5+100;
ll a[N];
ll dp[N];
ll dq[N];
int main()
{
int n;
cin>>n;
ll sum=0;
rep(i,1,n)
{
cin>>a[i];
if(sum<0)
{
    sum=0;
}
sum+=a[i];
dp[i]=sum;
}
sum=0;
frep(i, n, 1)
{
if (sum < 0)
{
    sum = 0;
}
sum += a[i];
dq[i] = sum;
}
rep(i,1,n)
{
    cout<<dp[i]+dq[i]-a[i]<<' ';
}

}

B

这题还是不太懂原理

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
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
using namespace std;
const int N = 2e5 + 100;
ll a[N];
ll ans;
int main()
{
    int n;
    cin>>n;
    ll maxn=0;
    rep(i,1,n)
    {
        ll x;
        cin>>x;
        maxn=max(maxn,x);
        a[x]++;
    }
    for (int i = 1; i <= maxn; i++)
    {
        if (!a[i])
            continue;
        for (int j = i; j <= maxn; j += i)
        {
            if (!a[j])
                continue;
            for (int k = j; k <= maxn; k += j)
            {
                if (!a[k])
                    continue;
                ans += a[i] * a[j] * a[k];
            }
        }
    }
    cout << ans << '\n';
}

C

签到

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//很签到
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define N 1000000

int i, j, k, n, m, t;
ll p[N + 50], a[N + 50], mx[N + 50], mn[N + 50];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    if (n < 3)
        cout << -1;
    else
    {
        cout << "CUC";
        for (i = 4; i <= n; i++)
            cout << "X";
    }
}

D

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
//固定列交换行以达成效果
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
using namespace std;
const int N = 1e3 + 100;
map<int, int> mp1, mp2;
int main()
{
    int n;
    cin>>n;
    int a[n], b[n];
    string c[n];
    rep(i,0,n-1)
    {
        cin>>a[i];
    }
    rep(i,0,n-1)
    {
        cin>>b[i];
    }
    rep(i,0,n-1)
    {
        c[i]=string(n,'0');
    }
    rep(j,0,n-1)
    {
        rep(i,0,a[j]-1)
        {
c[i][j]='1';
//每一列置为目标值   
        }
    }
rep(i,0,n-1)
{
    int num=0;
    rep(j,0,n-1)
    {
        if(c[i][j]=='1')
        {
            num++;
        }
    }
    mp1[num] = i; // 和num对应的行i
    mp2[i] = num; // 行i的和num
}
rep(i,0,n-1)
{
    if(mp2[i]!=b[i])
    {
        int u=mp1[b[i]];
        swap(c[i],c[u]);
        mp2[u]=mp2[i];
        mp1[mp2[i]]=u;
        mp2[i]=b[i];
    } 
}
rep(j,0,n-1)
{
  rep(i,0,n-1)
  {
    cout<<c[i][j];
  }
  cout<<'\n';
}

}

E

直接硬构造即可

由于只能有（n-1)(m-1)个这样子的子矩形

因此可以先判断

然后全部变成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
//挺抽象的构造题，好像是直接构造
//开写：
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
using namespace std;
const int N=1e3+100;
int a[N][N];
int main()
{
    int n;
    cin>>n;
    int m,k;
    cin>>m>>k;
    if((n-1)*(m-1)<k)
    {
        cout<<-1;
        return 0;
    }
    rep(i,1,n)
    {
        rep(j,1,m){
            a[i][j]=1;
        }
    }
    int now=(n-1)*(m-1);
    rep(i,1,n){
        rep(j,1,m)
        {
            if(now>k)
            {
                a[i][j]=0;
            }
            if(j!=m){
                now--;
            }
    }
    }
    rep(i,1,n)
    {
    rep(j,1,m)
    {
cout<<a[i][j];
    }
    cout<<'\n';
    }
    return 0;
}

G

三指针，就当成板子收录了吧

题做少了，第一次见三指针

实际上就是用两个映射

找到3的位置和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
// 三指针法
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
using namespace std;
const int N = 1e5 + 100;
int a[N];
map<int,int>mp1;
map<int,int>mp2;
ll n,cnt1,cnt2,ans;
int main()
{
    cin>>n;
    rep(i,1,n)
    {
        cin>>a[i];
    }
    int l=1;
    int r=1;
    rep(i,1,n)
{
    mp1[a[i]]++;
    mp2[a[i]]++;
    if(mp1[a[i]]==1)
{
    cnt1++;
}
if(mp2[a[i]]==1)
{
    cnt2++;
}
while(cnt1>3&&l<i)
{
mp1[a[l]]--;
if(mp1[a[l]]==0)
{
    cnt1--;
}
l++;
}
while(cnt2>2&&r<i)
{
mp2[a[r]]--;
if(mp2[a[r]]==0)
{
    cnt2--;
}
r++;
}
if(cnt1==3&&cnt2==2)
{
    ans+=r-l;
}
}
cout<<ans<<'\n';
return 0;
}

H

遇到.就扩展

遇到*，就变成.，然后不扩展

这样子进行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
83
84
85
86
//貌似也是比较板子的BFS
//这个写完摆烂
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define frep(i, a, n) for (int i = a; i >= n; i--)
using ll = long long;
const int N=1e3+100;
char a[N][N];
bool flag[N][N];
struct node
{
    int x,y;
};
queue<node>q;
int main()
{
int n,m;
cin>>n>>m;
rep(i,1,n)
{
    rep(j,1,m)
    cin>>a[i][j];
}
rep(i,0,n)
{
    a[i][0]='.';
}
rep(i,0,m)
{
    a[0][i]='.';
}
rep(i,0,n)
{
    a[i][m+1]='.';
}
rep(i,0,m)
{
    a[n+1][i]='.';
}
q.push({0,0});
flag[0][0]=1;
while(!q.empty())
{
    node s=q.front();
    int x=s.x;
    int y=s.y;
    if(a[x][y]=='*')
    {
        a[x][y]='.';
        flag[x][y]=1;
        q.pop();
        continue;
    }
if(x+1>=0&&x+1<=n+1&&y>=0&&y<=m+1&&!flag[x+1][y])
{
    q.push({x+1,y});
    flag[x+1][y]=1;
}
if(x-1>=0&&x-1<=n+1&&y>=0&&y<=m+1&&!flag[x-1][y])
{
    q.push({x-1,y});
    flag[x-1][y]=1;
}
if(x>=0&&x<=n+1&&y+1>=0&&y+1<=m+1&&!flag[x][y+1])
{
    q.push({x,y+1});
    flag[x][y+1]=1;
}
if(x>=0&&x<=n+1&&y-1>=0&&y-1<=m+1&&!flag[x][y-1])
{
    q.push({x,y-1});
    flag[x][y-1]=1;
}
q.pop();
}
rep(i,1,n)
{
    rep(j,1,m)
    {
        cout<<a[i][j];
    }
    cout<<'\n';
}
return 0;
}
img