Codeforces Round 971 (Div. 4)

A

观察样例可得。

或者通过理解数轴也可以发现，当c在中间就是最优秀的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
void Totoro()
{

int a,b;
cin>>a>>b;
cout<<abs(a-b)<<'\n';
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        Totoro();
    }
    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
37
38
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
void Totoro()
{
int n;
cin>>n;
vector<int>ans;
for(int i=1;i<=n;i++)
{
    for(int j=1;j<=4;j++)
    {
char c;
cin>>c;
if(c=='#')
{
    ans.push_back(j);
}
    }
}
reverse(ans.begin(),ans.end());
for(auto x:ans)
{
    cout<<x<<' ';
}
cout<<'\n';
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        Totoro();
    }
    return 0;  
}

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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int mod=1e9+7;
void Totoro()
{
int x,y,k;
cin>>x>>y>>k;
int a=x/k+(x%k!=0);
int b=y/k+(y%k!=0);
if(a>b)
{
    cout<<2*max(a,b)-1<<'\n';
}
else
{
    cout<<2*max(a,b)<<'\n';
}

}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        Totoro();
    }
    return 0;  
}

D

三角形我分为2种情况，下面两个点，上面一个点。上面两个点，下面一个点。

情况是一样的，看第一种。

  • 如果纵向还有点，那么加上所有横线上的点。
  • 如果横向加2有点，纵向加1有点，那么就是等腰直角三角形，样例的第二种。
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
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{

int n;
cin>>n;
vector<int>x;
vector<int>y;
map<int,int>mp1;
map<int,int>mp2;
for(int i=1;i<=n;i++)
{
    int a,b;
    cin>>a>>b;
    if(b==0)
    {
        x.push_back(a);
        mp1[a]++;
    }
    else
    {
y.push_back(a);
mp2[a]++;

    }
}
sort(x.begin(),x.end());
sort(y.begin(),y.end());
ll ans=0;
for(auto a:x)
{
    if(mp2[a])
    {
ans+=(x.size()-1);
    }
    if(mp1[a+2]&&mp2[a+1])
    {
        ans++;
    }
}
for(auto a:y)
{
    if(mp1[a])
    {
ans+=(y.size()-1);
    }
    if(mp2[a+2]&&mp1[a+1])
    {
        ans++;
    }
}
cout<<ans<<'\n';



}
int main()
{
    int t ;
    cin>>t;
    while(t--)
    {
        solve();
    }
}

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{

    ll n, k;
    cin >> n >> k;
    auto check = [&](ll mid) -> ll
    {
        ll res = (k + k + mid - 1) * mid / 2 - (k + mid + k + n - 1) * (n - mid) / 2;
        return res;
    };

    ll l = 1, r = n;
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        if (check(mid) <= 0)
            l = mid + 1;
        else
            r = mid - 1;
    }
    ll ans = min(abs(check(l)), abs(check(r)));
    cout << ans << '\n';
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

F

普通的前缀和加上一点点思考就行。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
    int n, q;
    cin >> n >> q;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    vector<ll> pre(n + 1);
    for (int i = 0; i < n; i++)
    {
        pre[i + 1] = pre[i] + a[i];
    }

    auto query = [&](ll m)
    {
        int u = m / n;
        ll res = pre[n] * u;
        int v = m % n;
        if (v > 0)
        {
            if (u + v <= n)
            {
                res += pre[u + v] - pre[u];
            }
            else
            {
                res += pre[u + v - n] + pre[n] - pre[u];
            }
        }
        return res;
    };

    while (q--)
    {
        ll l, r;
        cin >> l >> r;
        l--;
        ll ans = query(r) - query(l);
        cout << ans << "\n";
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}

G1

考虑用双指针。

神来之笔是：一开始全部加上一个n-i+1，这样就只需要算数字相同即可。

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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve()
{
    int n, k, q;
    cin >> n >> k >> q;

    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        a[i] += n - i - 1;
    }

    vector<int> f(n - k + 1);

    vector<int> cnt(2 * n), freq(n + 1);
    freq[0] = 2 * n;
    int res = 0;
    for (int i = 0; i < k - 1; i++)
    {
        freq[cnt[a[i]]]--;
        res = max(res, ++cnt[a[i]]);
        freq[cnt[a[i]]]++;
    }
    for (int i = 0; i <= n - k; i++)
    {
        freq[cnt[a[i + k - 1]]]--;
        res = max(res, ++cnt[a[i + k - 1]]);
        freq[cnt[a[i + k - 1]]]++;

        while (freq[res] == 0)
        {
            res--;
        }
        f[i] = k - res;

        freq[cnt[a[i]]]--;
        cnt[a[i]]--;
        freq[cnt[a[i]]]++;
    }

    while (q--)
    {
        int l, r;
        cin >> l >> r;
        l--;
        cout << f[l] << "\n";
    }
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
}