FJNU2024低程赛题解

Posted on

比赛链接

题目按总过题数量降序排列

A.

1
2
3
4
5
6
7
8
9
#include<iostream>
using namespace std;

signed main(){
    int a , b;cin >> a >> b;
    int c = a - b;if( c < 0 ) c = -c;
    cout << c << endl;
    return 0;
}

H.

1
2
3
4
5
6
7
8
9
10
#include<iostream>
using namespace std;

signed main(){
    int a , b , c;cin >> a >> b >> c;
    if( a == b && b == c ) cout << 1 << endl;
    else if( a == b || b == c || a == c ) cout << 2 << endl;
    else cout << 3 << endl;
    return 0; 
}

G.

前面填充0，剩下的位数从头开始输出字符串，直到凑齐n位，即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using namespace std;

signed main(){
    int n , k;cin >> n >> k;
    string s;cin >> s;
    for(int i = 1;i <= k;i ++){
        cout << 0;
    }
    for(int i = k+1;i <= n;i ++){
        cout << s[i-k-1];
    }cout << endl;
    return 0; 
}

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
#include<iostream>

using namespace std;

int x , k , r;

int leng( int num ){
    int ans = 0;
    while( num ){
        num /= 10;
        ans ++;
    }if( ans == 0 ) ans = 1;
    return ans;
}
void space( int num ){
    for(int i = 1;i <= num;i ++) cout << " ";
}

signed main(){
    cin >> x >> k;
    int len_init = leng(k) + 1 + leng(x);
    while( x ){
        space( len_init - leng(k) - 1 - leng(x) );
        r = x % k;
        cout << k << "|" << x << " ";
        if( r < 10 ) cout << r;
        else{
            cout << char(r-10+'A');
        }cout << '\n';
        space( len_init - leng(x) );
        for(int i = 1;i <= leng(x);i ++) cout << "-";
        cout << '\n';
        x /= k;
    }space(len_init-1);cout << 0 << '\n';
    return 0;
}

F.

一开始想二分套二分（大雾），后来发现只需要记录最长连续L的个数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;

const int N = 2e5;
int n;string s;
int top_R[N];

signed main(){
    cin >> n >> s;
    int top_num = 0;
    int ans = 1 , conti = 1;
    for(int i = 1;i <= n;i ++){
        if( s[i-1] == 'L' ) conti ++;
        else{
            conti = 1;
        }ans = max( conti , ans );
    }cout << ans << endl;
    return 0; 
}

C.

暴力会TLE，时间复杂度为 ，即使是夹半搜索也要 量级，故考虑dp

感觉和背包问题比较像，甚至要简单一点；不同点在于背包问题是求最优，而本题是求是否到达

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<iostream>
#include<queue>

using namespace std;

int n , x;
int a[110] , b[110];
int dp[10010][110];

signed main(){
    cin >> n >> x;
    for(int i = 1;i <= n;i ++){
        cin >> a[i] >> b[i];
    }
    dp[0][0] = 1;
    for(int i = 1;i <= n;i ++){
        for(int p = min(a[i],b[i]);p <= x;p ++){
            if( p >= a[i] ) dp[p][i] |= dp[p-a[i]][i-1];
            if( p >= b[i] ) dp[p][i] |= dp[p-b[i]][i-1];
        }
    }
    if( dp[x][n] ) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0; 
}

E.

并查集问题（当时写的时候以为是公共祖先弱化版，忘了并查集这个东西了）

然后判断每种情况的状态，最后合并即可

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
#include<iostream>

using namespace std;

const int N=1e5;
int n , m;
int ans , x , y , z;
int bin[N+10];
int fa[N+10];

int get_fa( int p ){
    if( fa[p] == p ) return p;
    return get_fa(fa[p]);
}

signed main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i ++){
        fa[i] = i;
    }
    for(int i = 1;i <= m;i ++){
        cin >> x >> y >> z;
        if( bin[x] == 0 && bin[y] == 0 ){
            ans ++;
        }else if( bin[x] && bin[y] ){
            if( get_fa(x) != get_fa(y) ){
                ans --;
            }
        }bin[x] = bin[y] = 1;
        fa[get_fa( x )] = fa[get_fa( y )] = min( get_fa( x ) , get_fa( y ) );
    }
    for(int i = 1;i <= n;i ++){
        if( bin[i] == 0 ) ans ++;
    }
    cout << ans << endl;
    return 0; 
}

G.

这题我也不知道怎么过的，应该是运气好凑巧了吧

结束前十分钟写完思路发现样例二过不了，以为是假了，然后写下了//做法假了，没时间了，开摆！这句；后来发现忘了翻转这一步，加上了然后样例二过了，一提交居然AC了

首先观察样例，因为存在不同解，所以试图找到解的规律

1
2 3 3 4 -4 -7 -4 -1

对以上操作积分一次（这个比喻有点抽象），可以发现只要确定了第一项，后面的就都确定了

不妨设第一项为 0

1
2
原式为： 2  3  3  4  -4  -7  -4  -1
积分后：0  2  1  2  2  -6  -1  -3  2

然后改变第一项，可以发现奇数项和偶数项分别加减第一项的改变值

1
2
3
原式为： 2  3  3  4  -4  -7  -4  -1
积分后：0  2  1  2  2  -6  -1  -3  2
改首项：1  1  0  3  1  -5  -2  -2  1

这时，我们只需要确定第一项即可

但是第一项的范围为 ±1e9，所以需要借助和 幸运数字 的差值

进一步的，我们如果希望改变后的数字是幸运数字，只需要和目标的幸运数字们分别作差；差值结果即为第一项为某一数字后，这一项在变换（积分）后会变为幸运数字

由于每个幸运数字不同，故我们对于这个二维列表，只需要统计出现相同数字的最大次数即可（使用map进行统计）

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
#include<iostream>
#include<map>
#define int long long

using namespace std;

const int N = 1e5;
int n , m;
int s[N+10] , t[15];
int state[N+10][11];

map < int , int > mp;

signed main(){
    mp.clear();
    cin >> n >> m;
    for(int i = 2;i <= n;i ++){
        cin >> s[i];
    }
    for(int i = 1;i <= m;i ++){
        cin >> t[i];
    }
    state[1][0] = 0;
    for(int i = 2;i <= n;i ++){
        state[i][0] = s[i] - state[i-1][0];
    }
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            state[i][j] = t[j] - state[i][0];
            if( i % 2 ) state[i][j] = -state[i][j];
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i ++){
        for(int j = 1;j <= m;j ++){
            mp[state[i][j]] ++;
            ans = max( ans , mp[state[i][j]] );
        }
    }
    cout << ans << endl;
    return 0; 
}