CF971

记录：又是做得非常糟糕的一场。

一些题明明只需要用简单的写法就行，自己却写了太多判断。

总是着急写题，没有想清楚情况，怎么写？使用什么STL都没有想清楚。

写题时还是一定得理清楚思路：确定好要写什么，怎么写。

同时一些技巧诸如精度之类（(x+k-1)/k）的要多多想起来用。

A

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int a,b;    cin>>a>>b;
    cout<<b-a<<"\n";
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

B

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n;  cin>>n;
    std::vector<string> v(n);
    for (int i = 0; i < n; ++i)
    {
        cin>>v[i];
    }
    for (int i = n-1; i >= 0; --i)
    {
        for (int j = 0; j < v[i].size(); ++j)
        {
            if(v[i][j]=='#')
            {
                cout<<j+1<<" ";
                break;
            }
        }
    }
    cout<<"\n";
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

C

这题写了一堆判断，写得很糟糕。

可以使用这个方法：(x+k-1)/k就可以控制其向上取整。

思路

其实就是分别计算走x和y方向需要多少步，取最大值。

如果是x最大那么，需要减一。

代码

一

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    ll x,y,k;   cin>>x>>y>>k;
    ll ans=0;
    ll a=(x+k-1)/k,b=(y+k-1)/k;
    if(b<a)
    {
        cout<<2*a-1<<"\n";
    }
    else    cout<<2*b<<"\n";
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

二

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    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<<2*b<<"\n";
    else        cout<<2*a-1<<"\n";
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

D

也是写得一坨，一定要想清楚用什么STL维护更好，怎么写再开始敲。

思路

不难想到只有四种情况。

----    |\		   /\        \------/
\  |	| \  	  /  \		  \    /
 \ |	|  \	 /    \        \  /
  \|	----    /------\   		\/

针对第一种情况，我们可以维护每一条竖边，然后计算对应的有多少个纵坐标为1的点即可。第二种情况也是类似。

第三种情况，我们可以枚举直角顶点，然后看看是否存在左右两个顶点，可以用set进行维护。第四种情况也是类似。

二三情况可以合并，我们可以先用一个vector维护，另外一四也是如此。

Trick

可以用map来维护竖边，然后用set来维护左右顶点是否存在。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n;  cin>>n;
    std::vector<int> x(n),y(n);
    std::map<int, int> map;
    std::vector<int> v0,v1;
    std::set<int>   s0,s1;
    int cnt0=0,cnt1=0;
    for (int i = 0; i < n; ++i)
    {
        cin>>x[i]>>y[i];
        map[x[i]]++;
        if(y[i]==0)
        {
            v0.push_back(x[i]);
            cnt0++;
            s0.insert(x[i]);
        }
        if(y[i]==1)
        {
            v1.push_back(x[i]);
            cnt1++;
            s1.insert(x[i]);
        }
    }
    ll ans=0;
    for (auto x: v0)
    {
        if(map[x]==2)   ans+=1ll*(cnt0-1);
        if(s1.count(x-1) && s1.count(x+1))  ans++;   
    }
    for (auto x: v1)
    {
        if(map[x]==2)   ans+=1ll*(cnt1-1);
        if(s0.count(x-1) && s0.count(x+1))  ans++;
    }
    cout<<ans<<"\n";
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

E

思路

很显然的二分，这里采取的是二分位置。我们可以二分绝对值最小的位置。

分析一下题目：随着i的增大，那么\(a_1+a_2+a_i-a_{i+1}-······-a_n\)肯定是越来越大的，那么，原来是负数，会逐渐变为正数，那么我们二分以上式子最接近0的位置即可。

这里的写法是pre>back返回false。否则返回true。

所以最后还需要比较一下l,l-1,l+1这三个位置对应的各自式子的和，取最小值即可。

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    ll n,k; cin>>n>>k;
    ll l=1,r=n;
    auto check=[&](ll x)
    {
        ll pre=(2*k+x-1)*(x)/2;
        ll back=(2*k+n+x-1)*(n-x)/2;
        if(pre>back)
        {
            return false;
        }
        else
        {
            return true;
        }
    };
    while(l+1<r)
    {
        ll mid=(l+r)>>1;
        if(check(mid))
        {
            l=mid+1;
        }
        else
        {
            r=mid;
        }
    }
    //cout<<"l :"<<l<<"\n";
    ll sum1=abs((2*k+l-1)*(l)/2-(2*k+n+l-1)*(n-l)/2);
    l++;
    ll sum2=abs((2*k+l-1)*(l)/2-(2*k+n+l-1)*(n-l)/2);
    l-=2;
    ll sum3=abs((2*k+l-1)*(l)/2-(2*k+n+l-1)*(n-l)/2);
    cout<<min({sum1,sum2,sum3})<<"\n";
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}

F

思路

不难发现一直重复循环，如果直接计算这个区间，似乎需要很复杂的分类讨论。

排列又是固定，而且是多次询问，所以考虑可以先离线处理。

利用数位dp的常用方法（其实就是前缀和）直接获取那段区间的结果（query(r)-query(l-1)）。

接下来就考虑处理query(r)这部分。手写几个例子可以发现，可能会出现312这样的情况。所以需要分类讨论。

记x为总共经过的完整区间（也就是偏移量），y就是剩余的个数。

如果x+y<=n，说明最大的一个元素（最初是123456，后面不断偏移234567 345678等等）没有越界。直接使用前缀和计算即可。

反之，说明越界。（如312中的31这种情况）。那么可以拆成两部分处理（对应就是3和1），直接sum[x+y-n]，得到的就是越界范围的数值（对应1）。

sum[n]-sum[x]就是正常范围的数字（对应3）.

代码

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
void solve()
{
    int n,q;    cin>>n>>q;
    std::vector<ll> a(n),sum(n+1,0);
    for (int i = 0; i < n; ++i)
    {
        cin>>a[i];
        sum[i+1]=sum[i]+a[i];
    }

    auto query=[&](ll m)
    {
        ll x=m/n;  //偏移量
        ll y=m%n;  //需要计算的个数
        ll ans=sum[n]*x;
        if(y)
        {
            if(x+y<=n)
            {
                ans+=sum[x+y]-sum[x];
            }
            else
            {
                ans+=sum[x+y-n]+sum[n]-sum[x];
            }
        }
        return ans;
    };

    while(q--)
    {
        ll l,r;
        cin>>l>>r;
        cout<<query(r)-query(l-1)<<"\n";
    }
}       
int main()
{
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)
    {
        //cout<<"case "<<t<<": ";
        solve();
    }
    return 0;
}