Codeforces Round 933 (Div. 3)

img

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
//by Totoro
//遍历康康是不是都小于等于即可
//这里失误点是敲错一个字母
#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--)
#define ll long long
const int N=1e6+100;
ll a[N];
ll b[N];
void solve()
{
int  n,m,k;
cin>>n>>m>>k;
rep(i,1,n)
{
    cin>>a[i];
}
sort(a+1,a+1+n);
rep(i,1,m)
{
 cin>>b[i];   
}
sort(b+1,b+1+m);
int ans=0;
rep(i,1,n)
{
    rep(j,1,m)
    {
        if(a[i]+b[j]<=k)
        {
            ans++;
        }
        if(a[i]+b[j]>k)
        {
            break;
        }
    }
    if(a[i]+b[1]>k)
    {
        break;
    }
}
cout<<ans<<'\n';


}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    solve();
}

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>
#include <cstring>
#include <vector>
using namespace std;
using LL = long long;

int main()
{

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    int T;
    cin >> T;
    while (T--)
    {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n), b(m);
    for (auto &x : a)
        cin >> x;
    for (auto &x : b)
        cin >> x;
    int ans = 0;
    for (auto x : a)
    {
        for (auto y : b)
        {
            ans += (x + y <= k);
        }
    }
    cout << ans << "\n";
    }
}

B

按照题意遍历一次

康康最后两个数字是不是0即可 这里的失误点是忘记特判倒数第二个数字

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
// by Totoro
#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--)
#define ll long long
const int N = 1e6 + 100;
ll a[N];
void solve()
{
    int n;
    cin >> n;
    rep(i, 1, n)
    {
        cin >> a[i];
    }
    rep(i, 1, n - 2)
    {
        if (a[i] < 0)
        {
            cout << "NO" << '\n';
            return;
        }
        if (a[i] != 0)
        {
            ll t = a[i];
            a[i] -= t;
            a[i + 1] -= 2 * t;
            a[i + 2] -= t;
            if (a[i + 1] < 0 || a[i + 2] < 0)
            {
                cout << "NO" << '\n';
                return;
            }
        }
    }
    if (a[n] != 0 || a[n - 1] != 0)
    {
        cout << "NO" << '\n';
    }
    else
    {
        cout << "YES" << '\n';
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
}

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
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
using LL = long long;
int main()
{

    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        vector<LL> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];
        for (int i = 0; i + 2 < n; i++)
        {
            if (a[i] < 0)
                break;
            LL t = a[i];
            a[i] -= t;
            a[i + 1] -= 2 * t;
            a[i + 2] -= t;
        }
        cout << (a == vector<LL>(n, 0) ? "YES" : "NO") << '\n';
    }
}

C

C题也是跑一遍就好 贪心 mapie，删除p 否则删除a,和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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// by Totoro
#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--)
#define ll long long
inline void solve()
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    int ans1 = 0;
    rep(i, 0, n - 1)
    {
        if (s[i] == 'm' && s[i + 1] == 'a' && s[i + 2] == 'p' && s[i + 3] == 'i' && s[i + 4] == 'e' && i + 4 <= n - 1)
        {
            ans1++;
            i += 4;
        }
        else if (s[i] == 'm' && s[i + 1] == 'a' && s[i + 2] == 'p' && i + 2 <= n - 1)
        {
            ans1++;
            i += 2;
        }
        else
        {
            if (s[i] == 'p' && s[i + 1] == 'i' && s[i + 2] == 'e' && i + 2 <= n - 1)
            {
                ans1++;
                i += 2;
            }
        }
    }
    cout << ans1 << '\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin >> t;
    while (t--)
        solve();
}

D

集合暴力即可

感觉还不是正解，看到网上有人用dp（其实赛时有想到，不敢写QWQ）

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
//本题可以直接集合暴力枚举了
//不需要花里胡哨（指自己）
#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--)
#define ll long long
using namespace std;
void solve()
{
    ll n, m, x;
    cin >> n >> m >> x;
    set<ll> u;
    u.insert(x);
    while (m--)
    {
        set<ll> uu;
        ll r;
        cin >> r;
        char fx;
        cin >> fx;
        if (fx == '?')
        {
            for (auto a : u)
                //遍历集合
            {
                uu.insert((a + r) > n ? (a + r) % n : a + r);
                //顺时针
                uu.insert((a - r) > 0 ? a - r : a - r + n);
                //逆时针
            }
        }
        else if (fx == '0')
        {
            for (auto a : u)
            {
                uu.insert((a + r) > n ? (a + r) % n : a + r);
                //顺时针
            }
        }
        else
        {
            for (auto a : u)
            {
                uu.insert((a - r) > 0 ? a - r : a - r + n);
                //逆时针
            }
        }
        u = uu;
    }
    cout << u.size() << "\n";
    for (auto a : u)
        //输出
        cout << a << " ";
    cout << "\n";
}
int main()
{
    int t = 1;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

这个也许就是正解了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void solve(){
	ll n,m,x; cin>>n>>m>>x;
	vector<vector<ll>> dp(m+1,vector<ll>(n+1,0));
	dp[0][x-1] = 1;
	for(int i=1;i<=m;i++){
		ll len; char op;
		cin>>len>>op;
		for(int j=0;j<n;j++){
			if(dp[i-1][j]){
				if(op=='0') dp[i][(j+len)%n] |= dp[i-1][j];
				else if(op=='1') dp[i][(j-len+n)%n] |= dp[i-1][j];
				else{
					dp[i][(j+len)%n] |= dp[i-1][j];
					dp[i][(j-len+n)%n] |= dp[i-1][j];
				}
			}
		}
	}
	vector<int> ans;
	for(int i=0;i<n;i++){
		if(dp[m][i]) ans.push_back(i);
	}
	cout<< (int)ans.size()<<endl;
	for(int i=0;i<ans.size();i++) cout<<ans[i]+1<<" \n"[i==ans.size()-1];

E

考虑每一行安装支架的最小代价，取连续k行即可。

相距距离不能超过d，实际上上可以维护一个滑动窗口，来优化dp

dp[j]表示在这一列安装支架的最小花费

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
//单调队列+dp优化
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);
    int T;
    cin >> T;
    while (T--)
    {
        int n, m, k, d;
        cin >> n >> m >> k >> d;
        vector<vector<int>> a(n, vector<int>(m));
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                cin >> a[i][j];
            }
        }
        vector<LL> ans(n);
        for (int i = 0; i < n; i++)
        {
            vector<LL> dp(m, 1e18);
            dp[0] = 1;
            deque<int> q;
            q.push_back(0);
            for (int j = 1; j < m; j++)
            {
                while (!q.empty() && j - q.front() - 1 > d)
                    q.pop_front();
                dp[j] = dp[q.front()] + a[i][j] + 1;
                while (!q.empty() && dp[j] <= dp[q.back()])
                    q.pop_back();
                q.push_back(j);
            }
            ans[i] = dp[m - 1];
        }
        vector<LL> s(n + 1);
        for (int i = 0; i < n; i++)
        {
            s[i + 1] = s[i] + ans[i];
        }
        LL mn = 1e18;
        for (int i = 1; i + k - 1 <= n; i++)
        {
            mn = min(mn, s[i + k - 1] - s[i - 1]);
        }
        cout << mn << '\n';
    }
}