第四场

A题：不会
https://vjudge.net/problem/AtCoder-abc203_f

B题：
https://vjudge.net/problem/Gym-102700E
题意：好玩的交互题，给定一个深度n，构造一个深度为n的完全二叉树，然后寻找一个特殊节点，可以问最多n个问题，每一次都会答询问节点到目标节点的距离，求目标节点的编号
思路：模拟寻找的过程，每到一层新的问左端点，如果距离变小，就在左子树，距离变大，在右子树

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;//long long 啊，开long long
typedef pair<LL,LL> PII;
const LL N=1e5+10;
const LL INF=1e18;
const double small=1e-18;
//不要用puts和gets，切记

void solve()
{
    LL t;
    cin>>t;
    LL cnt=1;
    LL cheng=1;
    LL res;
    LL now=1;
    cout<<"1"<<endl;
    fflush(stdout) ;
    cin>>res;
    while(res>0)
    {
        cheng++;
        LL left=now*2;
        LL right=now*2+1;
        cout<<left<<endl;
        fflush(stdout) ;
        LL tmp;
        cin>>tmp;
        if(tmp<res)
        {
            now=left;
        }
        else now=right;
        res--;
    }
    cout<<"! "<<now<<endl;
     fflush(stdout) ;
}

int main()
{
    LL t;
    t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}

C题：
https://vjudge.net/problem/CodeForces-369B
题意：一场比赛有n个选手，每个选手得分上限是r，下限是l，给出得分最高的k个选手的得分和sk，得到所有选手的得分和sall，求每个选手的得分情况
思路：把前k个划分为一个区域，其他的为另一个区域，直接平均分配得分即可

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;//long long 啊，开long long
typedef pair<LL,LL> PII;
const int N=1e5+10;
const LL INF=1e18;
const double small=1e-18;
//不要用puts和gets，切记
LL res[N],idx=1;
void solve()//1 3 1 3 13 9
{
    LL n,k,l,r,sall,sk;
    cin>>n>>k>>l>>r>>sall>>sk;
    //cout<<n<<k<<l<<r<<sall<<sk;
    if(n==1)
    {
        cout<<sall<<endl;
        return;
    }
    if(n-k!=0)
    {
    LL ans=sall-sk;
    LL each=ans/(n-k)+1;
    LL cnt=each*(n-k)-ans;
    //cout<<each<<endl;
    for(int i=0;i<n-k;i++)
    {
        res[idx++]=each;
        if(cnt>0)res[idx-1]-=1;
        cnt-=1;
    }
    }
    if(k!=0)
    {
    LL ans=sk;
    LL each=ans/k+1;
    LL cnt=each*k-ans;
    for(int i=0;i<k;i++)
    {
        res[idx++]=each;
        if(cnt>0)res[idx-1]-=1;
        cnt-=1;
    }
    }

    for(int i=1;i<=n;i++)cout<<res[i]<<" ";
    cout<<endl;
}

int main()
{
    LL t;
    t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}

D题：
https://vjudge.net/problem/CodeForces-729C
题意：
思路：

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <queue>
#include <map>
#include <cmath>
using namespace std;
typedef long long LL;//long long 啊，开long long
typedef pair<LL,LL> PII;
const LL N=2e5+100;
const LL INF=1e18;
const double small=1e-18;
//不要用puts和gets，切记
 LL n,k,s,t;
 PII num[N];
 LL sta[N];

 bool check(LL mid)
 {
     LL tt=0;
     for(int i=1;i<=k+1;i++)
     {
        LL ans=sta[i]-sta[i-1];
        //cout<<ans<<"*"<<endl;
        if(ans>mid)return false;
        if(mid>=2*ans)tt+=ans;
        else tt+=2*ans-(mid-ans);
        if(tt>t)return false;
     }
     if(tt>t)return false;
     //cout<<mid<<endl;
     //cout<<tt<<"*"<<endl;
     return true;
 }

 bool cmd(PII a,PII b)
 {
     return a.second<b.second;
 }

void solve()
{

    cin>>n>>k>>s>>t;
    for(int i=0;i<n;i++)
    {
        cin>>num[i].first>>num[i].second;
    }
    for(int i=1;i<=k;i++)cin>>sta[i];
    sta[0]=0;
    sta[k+1]=s;
    sort(sta,sta+2+k);
    sort(num,num+n,cmd);
    LL l=1,r=1e9+10;
    while(l<r)
    {
        LL mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    LL res=l;
    if(!check(res))
    {
        cout<<"-1"<<endl;
        return;
    }
    LL p=INF;
    for(int i=0;i<n;i++)
    {
        if(num[i].second>=res)p=min(p,num[i].first);
    }
    if(p!=INF)
    cout<<p<<endl;
    else cout<<"-1"<<endl;
}

int main()
{
    LL t;
    t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}