image-20240321162843653

2019年华南理工大学程序设计竞赛（春季赛）

希望校赛打出好成绩

A

image-20240321161216978

深搜满足条件的数字

询问l,r

可以用类似于前缀和的思想，算出l-1和r

然后减去（期间可以加上模数保证正确性）

深搜逻辑见代码

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
#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;
const int mod=1e9+7;
unordered_map<ll,ll>mp;
ll dfs(ll x)
{
    if(x<1)
    {
        return 0;
    }
    //如果数字等于0也就意味着不能被整除就返回0
    if(mp[x])
    {
        return mp[x];
    }
    //之前已经出现过这个数字，可以返回，记忆化搜索
    ll ans=0;
    //答案
rep(i,2,9)
{
    ll y=x/i;
    //这个就是除
    if(y>=1)
    {
        //除完大于1，证明满足题意，数字是正确的
        ans++;
        //答案加加
    }
ans+=dfs(y);
    //继续往下搜这个数字
ans%=mod;
    //注意取模
}
return mp[x]=ans;
    //记忆化搜索
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
ll l,r;
cin>>l>>r;
ll sum2 = dfs(r);
ll sum1=dfs(l-1);
cout<<(sum2-sum1+mod)%mod<<'\n';
    }
}

B

不会写，搁置

C

image-20240321161552535

讲解一下思路

每次都进行翻转比较

先拿大的

然后删掉

很暴力就是了

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;
const int mod = 1e9 + 7;
int cnt=0;
void solve()
{
    cnt++;
    string s1,s2,t1,t2;
    cin>>s1>>t1;
    cout << "Case #" << cnt << ": ";
    while(s1.length()||t1.length())
    {
        s2 = s1;
        reverse(s1.begin(), s1.end());
        s1 = max(s1, s2);
        t2 = t1;
        reverse(t1.begin(), t1.end());
        t1 = max(t1, t2);
        if (s1 < t1)
            swap(s1, t1);
        cout << s1[0];
        s1.erase(0, 1);
    }
cout<<'\n';
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

D

暂时也不会

E

image-20240321161713099

深搜，注意check函数，3个块的判断

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>
#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;
int a[10][10];
bool check(int x,int y,int z)
{
    rep(i,0,8)
    {
        if(a[x][i]==z)
        return 0;
    }
    rep(i,0,8)
    {
        if(a[i][y]==z)
        {
            return 0;
        }
    }
    int I=x/3*3;
    int J=y/3*3;
    rep(i,I,I+2)
    {
        rep(j,J,J+2)
        {
            if(a[i][j]==z)
            {
                return 0;
            }
        }
    }
    return 1;
}
//判断3个块
bool dfs(int x)
{
    if(x==81)
    {
return 1;
    }
    //成功
    int i=x/9;
    int j=x%9;
    if(a[i][j])
    {
        return dfs(x+1);
    }
    //继续搜
    rep(k,1,9)
    {
        if(check(i,j,k))
{
    a[i][j]=k;
    if(dfs(x+1))
    {
        return 1;
    }
            //检查合理性，赋值，继续搜
    a[i][j]=0;
            //不行回溯
}
    }
    return 0;
}
int main()
{
    rep(i,0,8)
    {
        rep(j,0,8)
        {
            cin>>a[i][j];
        }
    }
    //输入
    dfs(0);
    //深搜
    rep(i,0,8)
    {
        rep(j,0,8)
        {
            cout<<a[i][j]<<' ';
        }
        cout<<'\n';
            }
    //输出
            return 0;
}

F

image-20240321161922260

​

说明

$$ 以下叙述n=2时的最优策略。

  1. 随机选择两张扑克牌。有概率两张牌相同，直接消除，跳至(4)；有概率不同，跳至(2)。

  2. 选择一张已经选过的扑克牌，和一张没有选过的扑克牌。有的概率相同，直接消除，跳至(4)；有的概率不同，跳至(3)。

  3. 这时已经知道所有扑克牌的图案，选择一个对子消除，跳至(4)。

  4. 消除最后两张扑克牌。 数学期望为：E=13×2+13×3+13×4=3.00E = + + = 3.00E=31×2+31×3+31×4=3.00。 $$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    double n;
    while (t--)
    {
        cin >> n;
        printf("%.2lf\n", 2 * n - 1);
    }
    return 0;
}

H

image-20240321162101468

很有趣，先算出总的

然后两次暴力

如果已经等于总的，直接加

不然就慢慢加

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>
#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 = 500000 + 10, INF = 1e9, mod = 1e9 + 7;
ll n, m, k;
ll f[N], a[N];
void solve()
{
    cin >> n;
    ll res = 0;
    ll ans = 0;
    rep(i, 1, n)
    {
        cin >> a[i];
        res = __gcd(res, a[i]);
    }
    //gcd前缀和

    rep(i, 1, n)
    {
        ll gcd = a[i];
        rep(j, i, n)
        {
            gcd = __gcd(gcd, a[j]);
            if (gcd == res)
            {
                ans = (ans + (n - j + 1) * res) % mod;
                break;
            }
            else
            {
                ans += gcd;
                ans %= mod;
            }
        }
    }
    cout << ans << '\n';
}

signed main()
{
    int _ = 1;
    while (_--)
        solve();

    return 0;
}

I

image-20240321162229931

很水的买卖股票问题

定义dpi [0]为第i天未持有股票

dpi [1]为第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
#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=5e5+100;
ll dp[N][3];
ll a[N];
int main()
{
int n;
cin>>n;
rep(i,1,n)
{
    cin>>a[i];
    if(i==1)
    {
        dp[i][1]=-a[i];
        dp[i][0]=0;
    }
    else
{
    dp[i][0]=max(dp[i-1][0],dp[i-1][1]+a[i]);
    dp[i][1]=max(dp[i-1][1],dp[i-1][0]-a[i]);
}
}
cout<<max(dp[n][0],dp[n][1]);
}

K

image-20240321162555845 
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
#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 =1234;
ll t, seed = 131, ans[N];
ll f[N], g[N], sum, x; // f【i】为前i个字母组成的前缀哈希成的数字
unordered_map<ll, int> pre, now;
char s[N];
ll geth(int l, int r)
{
    return f[r] - f[l - 1] * g[r - l + 1];
}
int main()
{
    scanf("%s", s + 1);
    cin>>t;
     // 输入字符串,从一开始
    int n = strlen(s + 1);      
    // 长度为n
    g[0] = 1;                   
    rep(i,1,n)
    {                                  
        g[i] = g[i - 1] * seed;        
        // g用于求子串的哈希值
        f[i] = f[i - 1] * seed + s[i]; 
        // 将每个前缀哈希成一个数字（fi是ll）
    }
   rep(i,1,N)
   {
       rep(j,i,n)
           {
             pre[geth(i, j)]++;
           }
    } 
    // i到j为一条子串，并将该子串哈希，放到pre里面，个数++
    rep(i,1,n)
    { 
        // 从一开始设置断点
        frep(j,i,1)
        {
            ll id = geth(j, i); 
            // 获得前件后缀的哈希值
            now[id]++;          
            // 当前后缀的个数++
            if (pre[id])        
            // 若后件有该子串，sum+上该子串的个数
                sum += pre[id];
        }
        rep(j,i,n)
        {
            ll id = geth(i, j); 
            // 获取后件子串的哈希值
            pre[id]--;          
            // 子串个数--(这里是因为这一部分子串实际上已经不需要了，已经统计过了)
            if (now[id])
            //注意要减去一部分，因为重复计算
                sum -= now[id];
        }
        ans[i] = sum; 
        // 对此时的断点预处理完成   大重点，sum没有初始化，是继续用的
    }
    while (t--)
    {
        cin>>x;
        cout<<ans[x]<<'\n';
    }
    return 0;
}

L

image-20240321162624635 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int n;
string s;
int main()
{
    cin >> n;
    while (n--)
    {
        cin >> s;
        if (s == "Rock")
            cout << "Paper" << endl;
        if (s == "Scissors")
            cout << "Rock" << endl;
        if (s == "Paper")
            cout << "Scissors" << endl;
    }
}

烟花总是转瞬即逝，但快乐不会，不是吗？

image-20240321162924978