Toyota Programming Contest 2024#9（AtCoder Beginner Contest 370）

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
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
	string s, t;
	cin >> s >> t;
	vector<int> v, vv;
	for (int i = 0; i < t.size(); i++)
	{
		if (s[i] > t[i])
		{
			v.push_back(i);
		}
		if (s[i] < t[i])
		{
			vv.push_back(i);
		}
	}
	cout << v.size() + vv.size() << endl;

	for (auto x : v)
	{
		s[x] = t[x];
		cout << s << endl;
	}
	reverse(vv.begin(), vv.end());
	for (auto x : vv)
	{
		s[x] = t[x];
		cout << s << endl;
	}

	return 0;
}

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
using namespace std;
#define debug(a) cout<<#a<<"="<<a<<endl;
#define endl '\n'
#define ls u<<1
#define rs u<<1|1
#define rep(x , l , r) for(int x = l;x<=r;++x)
#define int long long
#define ll long long
#define ld long double
#define INF 0x3f3f3f3f
const ld eps = 1e-9;
const int mod = 1e9+7;
typedef pair<int,int> pii;
int h , w , q;
void solve() {
    cin>>h>>w;
    vector<set<int>>r(h) , c(w);
    rep(i , 0 , h-1){
        rep(j , 0 ,w-1){
            r[i].insert(j);
            c[j].insert(i);
        }
    }
    int ans = h * w;
    int q;
    cin>>q;
    while(q--){
        int x , y;
        cin>>x>>y;
        x-- , y--;
        if(r[x].count(y)){
            ans--;
            r[x].erase(y);
            c[y].erase(x);
        }
        else{
            auto it = r[x].upper_bound(y);
            if(it != r[x].begin()){
                int b = *(prev(it));
                ans--;
                r[x].erase(b);
                c[b].erase(x);
            }
            if(it != r[x].end()){
                int b = *it;
                ans --;
                r[x].erase(b);
                c[b].erase(x);
            }
            it = c[y].upper_bound(x);
            if(it != c[y].begin()){
                int b = *(prev(it));
                ans--;
                c[y].erase(b);
                r[b].erase(y);
            }
            if(it != c[y].end()){
                int b = *it;
                ans--;
                c[y].erase(b);
                r[b].erase(y);
            }
        }
    }
    cout<<ans<<endl;
    
  
}

signed main(){
    ios::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);
    int _ = 1;
   
    while(_--)solve();
    return 0;
}

E

dp 数组是用来动态记录可以进行的有效划分数量。具体来说，每个 dp[i] 表示到第 i 个元素为止，能够产生的有效划分数目，即不包含任何子序列的和等于 K 的划分方式。

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
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;
const int mod = 998244353;
int qmi(int a, int b)
{
	if(b == -1) return 1;
	int res = 1;
	while(b)
	{
		if(b & 1) res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
void solve()
{
	int n, k;
	cin >> n >> k;
	vector<int> dp(n + 1);
	map<int, int> q;
	int cnt = 0;
	q[0] = 1;
	int tot = 1;
	for(int i = 1; i <= n; i ++)
	{
		int x;
		cin >> x;
		cnt += x;
		dp[i] = tot;
		if(q.count(cnt - k)) dp[i] = (dp[i] - q[cnt - k] + mod) % mod;
		tot = (tot + dp[i]) % mod;
		q[cnt] = (q[cnt] + dp[i]) % mod; 
	}
	cout << dp[n] << '\n';
}
signed main()
{
        solve();
    return 0;
}