CF补题小合集

Posted on

由于后续CF比赛基本只参加VP，故特此记录一下

2025.01.17

Codeforces Round 996 (Div. 2)

这把打爽了，表现分差点上紫，D题最后一分钟调出来过样例 结果WA2了

C题

构造题

我们从(1,1)开始思考，假设场景是这样的

1

设每行每列的和都为，故(1,1)的数值和的大小成线性关系

也就是说，知道就能通过这一行的数求出(1,1)的数值（如蓝色所示）

同理，知道就能求出第二行的数值（如紫色所示）

按顺序（沿路径）向下递推，就必然可以计算出下一个方格的数据（如红色所示）

故得出结论：如果该位置的下一个是R，则通过列计算；否则通过行计算

但是还不知道哇~

梅瓜吸，是多少都可以，我直接让它是0（更正式的，由个未知数的个方程构成的方程组中，存在一个自由量，这个自由量可以是S；其中）

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

using namespace std;

const int N = 1e3;
int n , m;int a[N+10][N+10];
string s;

signed main(){
    int t;cin >> t;
    while( t -- ){
        cin >> n >> m >> s;
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= m;j ++){
                cin >> a[i][j];
            }
        }
        int x , y;x = y = 1;
        for(int p = 0,i,j;p < s.length();p ++){
            if( s[p] == 'D' ){
                for(j = 1;j <= m;j ++){
                    if( j == y ) continue;
                    a[x][y] += a[x][j];
                }a[x][y] = -a[x][y];
                x ++;
            }
            if( s[p] == 'R' ){
                for(i = 1;i <= n;i ++){
                    if( i == x ) continue;
                    a[x][y] += a[i][y];
                }a[x][y] = -a[x][y];
                y ++;
            }
        }
        for(int j = 1;j < m;j ++) a[n][m] += a[n][j];
        a[n][m] = -a[n][m];
        for(int i = 1;i <= n;i ++){
            for(int j = 1;j <= m;j ++){
                cout << a[i][j] << " ";
            }cout << endl;
        }
    }return 0;
}

D题

不容易的思维题，不过只要逻辑理清楚了，都很简单

1
2
3
4
5
考虑以下策略
仅考虑两个相邻的点
如果二者的距离小于k，则可以直接越过去，a[i]的值尽可能的大
如果二者的距离大于k但是小于k+已过去的时间，则右侧点有能力移动到a[i-1]+k，也不需要额外消耗时间
如果二者的距离大于k+已过去的时间，则右侧点应当从一开始就开始全力左移，并二者相向而行，代价是相向而行的时间

值得注意的是，long double最后要转成long long不然输出的可能是科学计数法（WA6）

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

using namespace std;

const int N = 2e5;
int n , k , l;
long double ans , time_now;
long double a[N+10];

signed main(){
    int t;cin >> t;
    while( t -- ){ans = 0;
        cin >> n >> k >> l;
        for(int i = 1;i <= n;i ++) cin >> a[i];
        ans += a[1]*2;
        time_now = a[1];
        a[1] = 0;
        for(int i = 2;i <= n;i ++){
            if( a[i] - a[i-1] > k ){
                if( a[i] - a[i-1] > k + time_now ){
                    a[i] -= time_now;
                    ans += (a[i] - a[i-1] - k);
                    time_now += (a[i] - a[i-1] - k)/2;
                    a[i] -= (a[i] - a[i-1] - k) / 2;
                }else{
                    a[i] = a[i-1] + k;
                }
            }else{
                a[i] = min( a[i-1] + k , a[i] + time_now );
            }
        }
        ans += max( (l - a[n] - k )*2 , (long double)0 );
        cout << (long long)ans << endl;
    }return 0;
}