div2 919

div2配套训练

A:A. Satisfying Constraints

思路：大于的有一个上界，小于的有一个下界，中间的如果在这两个界之间，直接减就行

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
using ll=long long;
#define rep(i,a,n)  for(ll i=a;i<=n;i++)
#define frep(i,a,n) for(ll i=a;i>=n;i--)
int n;
int q[N];
void solve()
{
    cin>>n;
    int cnt=0;
    int maxn=0;
    int minn=1e9;
    int ans=0;
    rep(i,1,n)
    {
        int a,b;
        cin>>a>>b;
        if(a==1)
        {
            maxn=max(maxn,b);
        }
        else if(a==2)
        {
        minn=min(minn,b);   
        }
        else
        {
        q[++cnt]=b; 
        }
    }
    rep(i,1,cnt)
    {
        if(q[i]>=maxn&&q[i]<=minn)
        {
            ans--;
        }
    }
    if(ans+minn-maxn+1<=0)
    {
        cout<<0<<'\n';
    }
    else
    cout<<ans+minn-maxn+1<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
} 

B：B. Summation Game

思路：我们首先可以贪心的思考两个点：

1.由于这些数字一定是正的，所以操作二一定会尽全力的执行（就是有数并且他有次数他一定会执行）2.操作一则不一定全部执行，但如果执行的话一定扔掉最大的那些数字（排序的原因）

总结：于是我们就得到了一个思路：就是暴力枚举操作1，然后操作二直接执行，期间可以用前缀和优化一下。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
using ll=long long;
#define rep(i,a,n)  for(ll i=a;i<=n;i++)
#define frep(i,a,n) for(ll i=a;i>=n;i--)
int n,k,x;
ll a[N],sum[N];
bool cmp(int a,int b)
{
    return a>b;
}
//自定义排序
void solve()
{
    ll ans=-1e9;
cin>>n>>k>>x;
rep(i,1,n)
{
    cin>>a[i];
}
    //输入
sort(a+1,a+1+n,cmp);
    //使得正的在前面
rep(i,1,n)
{
    sum[i]=sum[i-1]+a[i];
}
    //前缀和
rep(i,0,k)
{
ll _sum=sum[n]-sum[i];//这是删除数后的和
    //比如 1 2 3 4 5 ，如果i=1的话，那么_sum=2+3+4+5
if(i+x>n)
{
ans=max(_sum-2*(sum[n]-sum[i]),ans);
    //如果i+x>n就是-1×的数字越界了所以需要特判
}
else
ans=max(_sum-2*(sum[i+x]-sum[i]),ans);
}
cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
int t;
cin>>t;
while(t--)
{
solve();
}
} 

C: Partitioning the Array

思路：首先题目要求是我们要求出一个K,使得有m>1使得每隔k个数的二个数字同余。

于是m是所有这样每隔两个数的因子，那么就完美符合条件了。

#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--)
const int N=1e6+10;
int a[N];
void solve()
{
    int n;
    cin>>n;
    rep(i,1,n)
    {
        cin>>a[i];
    }
    int ans=0;
    rep(k,1,n)//枚举k
    {
        if(n%k==0)
        {
            int g=0;//计算m
            for(int i=1;i+k<=n;i++)
            {
                g=__gcd(g,abs(a[i+k]-a[i]));    
            }
            ans+=(g!=1);//不为1就可以计算贡献
        }
    }
    cout<<ans<<'\n';
}
int main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); 
int t;
cin>>t;
while(t--)
{
    solve();
}
    return 0;
}

D:Array Repetition

思路：暴力枚举k，然后进行二分查找那个数字对应的范围，并不断往前找

#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--)
using ll = long long;
using pii = pair<ll, ll>;
#define fi first
#define se second
const int N=1e6+10;
using i128 = __int128_t;
int a[N];
void solve()
{
ll n,q;
cin>>n>>q;
vector<pii>v;
map<ll,ll>mp;
i128 len=0;
rep(i,1,n)
{
    int t,x;
    cin>>t>>x;
    if(t==1)
    {
        len=len+1;
        mp[1ll*len]=x;
    }
    else
    {
        if(len>1e18)
        {
            continue;
        }
        ll t=0;
        if(len<=1e18)
        {
        t=len;
        len=len*(x+1);
        }
        if(len>1e18)
        {
            len=1e18+1;
        }
        v.push_back({len,t});
    }
}
    sort(v.begin(),v.end());
    while(q--)
    {
        ll x=0;
        cin>>x;
        while(!mp.count(x))
        {
            auto it=lower_bound(v.begin(),v.end(),(pii){x,0ll});
            ll len=(*it).se;
            x%=len;
            if(x==0)
            {
                x=len;
            }
        }
        cout<<mp[x]<<" ";
    }
    cout<<'\n';
}
int main()
{
     ios_base::sync_with_stdio(0); cin.tie(0); 
int t;
cin>>t;
while(t--)
{
    solve();
}
    return 0;
}