Codeforces Round 971 (Div. 4) A~G1

A. Minimize!

签到不多说。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    
  	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    //c-a+b-c = b-a
    int t; cin>>t;
    while(t--)
    {
    	int a,b; cin>>a>>b;
    	cout<<b-a<<"\n";
    }
    return 0;
}

B. osu!mania

签到+1

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 500 + 10;

char a[N][N];

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        int n; cin>>n;
        for(int i = 1;i <= n; i++)
            for(int j = 1;j <= 4; j++)
                cin>>a[i][j];

        for(int i = n;i >= 1; i--)
        {
            for(int j = 1;j <= 4; j++)
            {
                if(a[i][j] == '#')
                    cout<<j<<" ";
            }
        }
        cout<<"\n";
    }


    return 0;
}

C. The Legend of Freya the Frog

这边有个小细节，因为总是x方向优先的，所以需要判断一下(类似于黑子先手那样差不多)。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        ll x,y,k; cin>>x>>y>>k;
        ll a = x / k + (x % k != 0);
        ll b = y / k + (y % k != 0);
        if(a > b)cout<<a * 2 - 1 <<"\n";
        else cout<<b * 2 <<"\n";
    }
    return 0;
}

D. Satyam and Counting

因为y的范围是[0,1]并且所有点都是整数点，那么问题看起来就简单了。直角三角形只有两种类型了(以y=0为例)，一种是在它的正上方有一个点，那么y=1的所有点都可以和这两个点变成直角三角形。第二种就是它的左边和右边刚好都有一个距离为1的点。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
#define int long long
signed main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--){
        int n; cin>>n;
        set<int>v0,v1;
        ll ans = 0;
        for(int i = 1;i <= n; i++)
        {
            int x,y; cin>>x>>y;
            if(y == 0) v0.insert(x);
            else v1.insert(x);
        }

        for(auto x : v0)
        {
            // cout<<"x = "<<x<<"\n";
            if(v1.find(x) != v1.end())
                ans += max(0ll,(int)v1.size()-1);
            if(v1.find(x-1) != v1.end() && v1.find(x+1) != v1.end()){
                // cout<<"!!!";
                 ans += 1;
            }
        }

        // cout<<"ans = "<<ans<<"\n";

        for(auto x : v1)
        {
            // cout<<"x = "<<x<<"\n";
            if(v0.find(x) != v0.end())
                ans += max(0ll,(int)v0.size()-1);
            if(v0.find(x-1) != v0.end() && v0.find(x+1) != v0.end()){
                // cout<<"###";
                 ans += 1;
            }
        }

        cout<<ans<<"\n";
    }


    return 0;
}

E. Klee’s SUPER DUPER LARGE Array!!!

题意：Klee 有一个长度为的数组，其中包含按顺序排列的整数。克利希望选择一个索引 ( )，使得最小。请注意，对于任意整数而言，表示的绝对值。

输出的最小可能值。

直觉就是一半的位置，二分它的左右界，然后两个取min即可。啊注意开long long(因为这个爆了一发)

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;


ll get(ll l,ll r,ll n)
{
    return (l+r)*n/2;
}
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        ll n,k; cin>>n>>k;
        ll s = (k + (k + n - 1)) * n / 2;

        int l = 1,r = n;
        while(l <= r)
        {
            int mid = (l + r)>>1;

            if((k + (k + mid - 1))*mid/2 >= s / 2) r = mid - 1;
            else l = mid + 1;
        }

        ll x = r + 1;
        l = 1,r = n;
        while(l <= r)
        {
            int mid = (l + r)>>1;

            if((k + (k + mid - 1))*mid/2 <= s / 2) l = mid + 1;
            else r = mid - 1;
        }   

        ll y = l - 1;
    
        ll res = min(abs(get(k,k+x-1,x)-get(k+x,k+n-1,n-x)),abs(get(k,k+y-1,y)-get(k+y,k+n-1,n-y)));

        cout<<res<<"\n";

    }


    return 0;
}

正经做法：

证明的话：因为前个为正数，后个为负数。都是等差，两部分求和为$\dfrac{(2k+i-1)i}{2} $和$ \dfrac{(2k+n+i-1)(n-i)}{2} $。两个相减就是$ \dfrac{-2kn+4ki-n^2+n+2i^2-2i}{2}$。是一个单调递增的函数。

那么最趋于0，无非就是最后一个负数和第一个正数取个min。

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;

ll T,n,k;
ll calc(ll i){
	return (-2*k*n+4*k*i-n*n+n+2*i*i-2*i)/2;
}
bool check(ll i){
	return calc(i)>=0;
}

int main(){
	cin>>T;
	while(T--){
		cin>>n>>k;
		ll l=1,r=n;
		while(l<r){
			ll mid=(l+r)>>1;
			if(check(mid))r=mid;
			else l=mid+1;
		}
		cout<<min(abs(calc(l-1)),abs(calc(l)))<<endl;
	}
	return 0;
}

F. Firefly’s Queries

题意：
萤火虫是一个给定长度为的数组。让表示数组的第次循环移动。她创建了一个新数组，使得其中 + 表示连接操作。

然后，她会向你提出个查询。对于每一个查询，输出从第个元素开始，到第个元素结束的子数组中所有元素的总和，包括两端的元素。

数组的第( ) 次循环移位是。请注意，第次移位就是最初的。

长度为的两个数组和 (换句话说， )的连接操作是。

思路：我们知道对于一个完整的和是固定的。我们可以先求出有多少个循环。然后多出来的部分单独算。

假设对于x位置的循环个数是，多出来的部分是。多出来的部分怎么处理呢？我们发现它是一个循环的，不难想到前后缀。如果的话直接求就可以了。但是如果的话，我们就用后面的部分加上前面的部分(相当于是一个前缀一个后缀加起来)。

然后求[l,r]这段的用个简单容斥就可以啦。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 10;
ll a[N];
ll s[N];
int n,q;
ll cal(ll x)
{
    ll rep = x / n;
    ll res = rep * s[n];
    ll last = x % n;
    // cout<<"s[n]="<<s[n]<<" s[rep] = "<<s[rep]<<" s[last+rep-n] = "<< s[last + rep - n]<<"\n";
    if(last + rep <= n)
        res += s[last + rep] - s[rep];
    else
        res += s[n] - s[rep] + s[last + rep - n];
    return res;

}

int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--){
        cin>>n>>q;
        for(int i = 1;i <= n; i++)
            cin>>a[i];
        s[0] = 0;
        for(int i = 1;i <= n; i++)
            s[i] = s[i-1] + a[i];
        for(int i = 1;i <= q; i++)
        {
            ll l,r; cin>>l>>r;
            cout<<cal(r)-cal(l-1)<<"\n";
        }
    }

    return 0;
}

G1. Yunli’s Subarray Queries (easy version)定长区间连续序列典例

题意：这是问题的简单版本。在这个版本中，可以保证适用于所有查询。

对于任意数组，云里可以执行任意多次下面的操作：

选择索引。设置，其中 x 是她想要的任意整数 $不限于区间$
将记为她需要执行的最小操作次数，直到 b 中存在一个长度至少为 k 的连续子数组。

给云莉一个大小为的数组并向你提出个查询。在每个查询中，你必须输出$ \sum {j=l+k-1}^{r} f([a_l, a{l+1}, \ldots, a_j]) $。请注意，在这个版本中，你只需要输出$ f([a_l, a_{l+1}, \ldots, a_{l+k-1}])$

如果存在一个从索引 i ( )开始的长度为的连续子数组，那么对于所有的都是

思路：

这个题很有意思也是很典型。一开始想到是长度固定的，有往滑动窗口去想，但是感觉不好实现。我们往本质去思考。转化一下这个题。

对于公差为1的等差(连续),如果我们对每个数加上一个n-i它们就会变成一样的。也就是说，加上之后，如果相等，那么它们在原序列里面是等差。

那么题目就转化为：对于一个，去找这个数里面的众数。而这样的最多也就个，果然还是用滑动窗口维护每一个的答案就行了。

这个滑动窗口，可以用multiest记录所有元素出现次数的数值集合,然后用map记录某个元素在当前窗口的出现次数。

关键——>定长区间连续序列，想到加上n-i转化为求众数，又因为定长可以用滑动窗口。

// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int n,k,q;
ll a[N],ans[N];
int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t; cin>>t;
    while(t--)
    {
        cin>>n>>k>>q;
        for(int i = 1;i <= n; i++)
        {
            cin>>a[i];
            ans[i] = 1;
            a[i] += (n-i);
        }
        //可以用multiest记录所有元素出现次数的数值集合
        //然后用map记录某个元素在当前窗口的出现次数。
        multiset<int>all;
        map<int,int>cnt;
        for(int i = 1;i <= n; i++)
        {
            int v = cnt[a[i]]++;
            if(all.find(v) != all.end())
                all.erase(all.find(v));
            all.insert(v + 1);

            if(i >= k){
                ans[i] = *all.rbegin();
                int w = cnt[a[i-k+1]]--;
                all.insert(w - 1);
                if(all.find(w) != all.end())
                    all.erase(all.find(w));
            }   
        }

        while(q--){
            int l,r; cin>>l>>r;
            cout<<k-ans[r]<<"\n";
        }
    }


    return 0;
}

tips（重要！）:

因为是定长区间，因此我们可以利用滑动窗口维护定长区间的众数的数量
对于公差为1的等差(连续),如果我们对每个数加上一个n-i它们就会变成一样的。也就是说，加上之后，如果相等，那么它们在原序列里面是等差。

Nannan blog

Codeforces Round 971 (Div. 4)A~G1