寒假训练第一场-创新互联

首先不希望桌子有空闲时间，所以谁先到谁就先排队。
所以我们先排序所有人的到达时间，从到达时间小的开始放置。
假设对于我们当前要放置的队伍来说，肯定放在最先结束的桌子上。找到三个桌子谁先结束。所以我们需要维护每个桌子当前结束时间。

void solved()
{cin >>n;
    for(int i = 0; i< n; i++) cin >>a[i];
    cin >>m;
    
    //初始化桌子，时间都归0
    for(int i = 0 ;i< 3; i++)
        que[i] = 0;
    
    //排序让先到的进行
    sort(a, a + n);

    for(int i = 0; i< n; i++)
    {int x = a[i];
        int mnn = 1e9; // 找到三个桌子谁最先结束
        int xb = 0;    //记录是第几个桌子
        for(int j = 0; j< 3; j++)
        {if(que[j]< mnn) mnn = que[j], xb = j;
        }
        
        //如果说当前队伍大于等于最先结束的了，那么肯定按照当前队伍到达的时间来开始
        if(x >= mnn)
        {que[xb] = x + m;
        }else que[xb] = mnn + m; 
        //如果我们到达的时候还没有空桌子,那么肯定等空桌子结束我们开始

    }
    
    //三个桌子找到最晚结束的就是我们的答案
    int ans = 0;
    for(int i = 0; i< 3; i++)
    {ans = max(ans, que[i]);
    }

    cout<< ans<< endl;

}

首先题目中说所有说话的人是相邻的（上下左右）， 对于竖着相邻的人来说，横着的过道才能影响，对于横着相邻的来说，竖着的过道影响。
对于一条竖着的过道，影响的只能是相邻两列的人，所以贪心的来说，对于每一条过道我们都希望是影响最多的人。
那么统计一下每对人如果要拆开，需要在哪一列 / 一行，防止过道。然后排序从大到小，输出题目要求的过道数量即可。
需要注意的点，题目要求输出过道的位置时，要求从小到大输出。
因为我们需要输出哪个过道被统计的数量最多，所以我们在统计次数的时候，也要标记上是哪个过道，这样排序的时候我们知道是哪个过道最多。
所以使用结构体存。

#includeusing namespace std;
const int N = 2010;
int hs[N], ls[N];

struct Node
{int id, w;
}he[N], le[N]; //分别统计行和列的次数


bool bmp(Node x, Node y)
{return x.w >y.w;
}


int main()
{int n, m, k, l, d;
    cin >>n >>m >>k >>l >>d;

    for(int i = 0; i< d; i++)
    {int x1, y1, x2, y2;
        cin >>x1 >>y1 >>x2 >>y2;
        
        //上下相邻
        if(x1 == x2)
        {he[min(y1, y2)].w++;
            he[min(y1, y2)].id = min(y1, y2); //避免排序时候不知道是哪个过道
        }else if(y1 == y2) //左右相邻
        {le[min(x1, x2)].w++;
            le[min(x1, x2)].id = min(x1, x2);
        }
    }
    
    //按照统计次数，从大到小
    sort(he, he + N, bmp), sort(le, le + N, bmp);

    
    //因为题目要求输出的时候按照 过道的下标从小到大
    vectorans1, ans2;

    for(int i = 0; i< k; i++)
        ans1.push_back(le[i].id);

    for(int i = 0; i< l; i++)
        ans2.push_back(he[i].id);
        
        
    sort(ans1.begin(), ans1.end()), sort(ans2.begin(), ans2.end());

    for(int i = 0; i< ans1.size(); i++)
        cout<< ans1[i]<< " ";
    cout<< endl;
    for(int j = 0; j< ans2.size(); j++)
        cout<< ans2[j]<< " ";


    return 0;
}

题目规定，最多 2 个物品一组，并且组内大物品不能超过上限值，问你最少多少组。
我们肯定希望尽可能满足 2 个物品一组，所以我们让最小的价值和大的价值组一块是最优解。如果说不能组一块，那大价值只能自己一组。
那么最小值就依次找次小值。

#includeusing namespace std;
const int N = 30010;

int n, m;
int a[N];

int main()
{cin >>m >>n;

    for(int i = 0; i< n; i++) cin >>a[i];

    sort(a, a + n);

    int l = 0;
    int ans = 0;

    for(int i = n - 1; i >= l; i--)
    {if(i == l)
        {ans++;
            break;
        }

        if(a[i] >= m) ans++;
        else
        {if(a[i] + a[l] >m)
            {ans++;
            }else
            {ans++;
                l++;
            }
        }
    }

    cout<< ans;

    return 0;
}

需要注意的点，土球会先撞，再回复，如果说撞的时候就< 0， 那么就失败了。

首先我们可以把所有的障碍分为两类，一类是撞完会增加的，另一类是撞完会减少的。
因为我们希望尽可能的把球的稳定性变成大，然后再减小，这样尽可能满足更多的障碍。
所以我们先撞增加的，再撞减小的。

对于先撞增加的这一类：
因为先撞再增加，所以尽可能的使得撞的值小的放在前面，让球的稳定性尽可能大，避免撞完就小于0。

可能会说，存在一个增加的障碍，但是他的损耗是很大的，肯定会导致撞完就小于0，不能回复。
这样因为他是撞完增加的，我们把他放在前面，是不是最优解？。
因为我们的要求是能够到达终点，而不是通过最多的障碍。
因为这个是损耗大的回复，所以我们肯定把他放在这一类的最后来撞，因为这时已经是极大值的稳定性，如果这时都不能通过，所以肯定不能到达终点。

对于撞完损耗这一类：
因为我们目标是到重点，那么如果到终点，我们大值 + 回复 一定大于所有的损耗 （损耗是一个定值），否则肯定会在路上失败。
那么我们尽可能的让回复多的在前面，这样就尽可能的满足稳定性大。

#includeusing namespace std;

typedef pairPII; //typedef 同define， pair用法 csdn搜索

#define x first
#define y second


const int N = 500010;

int n, m;

bool bmp1(PII a, PII b)
{return a.x< b.x;
}

bool bmp2(PII a, PII b)
{return a.y >b.y;
}

PII all[N];

void solved()
{cin >>n >>m;

    vectorzh, fu;

    for(int i = 0; i< n; i++)
    {cin >>all[i].x >>all[i].y;

        if(all[i].y - all[i].x >= 0) zh.push_back(all[i]);
        else fu.push_back(all[i]);
    }

    sort(zh.begin(), zh.end(), bmp1);
    sort(fu.begin(), fu.end(), bmp2);

    long long sum = m;

    for(int i = 0; i< zh.size(); i++)
    {if(sum - zh[i].x< 0)
        {cout<< "No"<< endl;
            return;
        }else sum -= zh[i].x, sum += zh[i].y;
    }

    for(int i = 0; i< fu.size(); i++)
    {if(sum - fu[i].x< 0)
        {cout<< "No"<< endl;
            return;
        }else sum -= fu[i].x, sum += fu[i].y;
    }

    cout<< "Yes"<< endl;
}
int main()
{int T;
    cin >>T;
    while(T--) solved();

    return 0;
}

暴力的解法就是 从 左区间l到右区间r 找到满足条件数的个数。但考虑到 l和r的大小 可以先预处理出来所有的平方数，然后用二分查找到 处于区间（l，r）满足条件数的范围。即 查找 l和r所在预处理数组中的位置。

#include#includeusing namespace std;
#define ll long long
vectorv;
void solve(){ll l1,r1;cin>>l1>>r1;
    ll l=0,r=v.size()-1;
    ll k1=-1;
    ll k2=-1;
    //找到第一个 大于等于 l1的
    while(lll mid=(l+r)>>1;
        if(v[mid]>=l1)r=mid;
        else l=mid+1;
    }
    k1=l;
    //找到最后一个 小于等于r1的
    l=0,r=v.size()-1;
    while(lll mid=(l+r+1)>>1;
        if(v[mid]<=r1)l=mid;
        else r=mid-1;
    }
    k2=l;
    cout<for(ll i=0;i*i<=1e9;i++){v.push_back(i*i);
    }
    ll t;cin>>t;
    while(t--)solve();
}

可以使用二分答案 枚举区间（0,100）内的所有数字，注意写好check函数就可以了。这里可以学习经典 浮点数二分的处理方法。

#include#include#define ll long long
using namespace std;
double n;
double check(double m){ double s=m*m*m*m*2018+m*21+5*m*m*m+5*m*m+14;
    return s;
}
void solve(){cin>>n;
    if(check(100)cout<<"-1"<0.00001){double mid=(l+r)/2.0;
        if(check(mid)>=n)r=mid;
        else l=mid+0.00000001;
    }
    printf("%.4f\n",l);
}
int main(){ll t;cin>>t;
    while(t--){solve();
    }
    return 0;
}

使用二分答案，通过枚举 答案 即最短跳跃距离的大值，check（）函数是判断该答案是否可行，是通过 计算 在满足该条件下需要移走岩石的个数，是否满足题目限制的大移动岩石个数。

#include#include#include#include
#include#include#include#include#define ll long long
const double eps = 1e-4;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a; }//最小公约数__gcd()
using namespace std;
const int NX=1e5+10;
ll x[NX];
ll y[NX];
ll L, N, M;
bool check(ll k)
{ll sum = 0;
    for (int i = 1; i<= N; i++)
    {ll j = i - 1;
        while (y[j] != 0)j--;
        if ((x[i] - x[j])sum++;
            y[i] = 1;
            if (sum >M)return false;
        }
    }
    ll s = N;
    while (y[s] != 0)s--;
    if ((x[N + 1] - x[s])< k)sum++;
    if (sum >M) return false;
    else return true;
}
int main()
{cin >>L >>N >>M;
    for (int i = 1; i<= N; i++)
    {cin >>x[i];
    }
    x[0] = 0;
        x[N + 1] = L;
    ll l = 0;
    ll r = 1e9+10;
    while (l< r)
    {memset(y, 0, sizeof(y));
        ll mid = (l + r) >>1;
        if (check(mid))l =mid+1;
        else r = mid;
    }
    cout<< l-1<< endl;
    return 0;
}

该题目 相当于是 跳石头 的一个拓展，同样是枚举答案 需要通知哪个申请人修改订单。注意check（）函数的书写，在判断答案 是否可行的时候 需要用到 一点差分的知识。 使用差分处理完该申请人 之前的所有订单，然后看是否有不符合要求的情况，即供不应求（需要的教室个数 大于 有空闲的教室个数。

#include#include#includeusing namespace std;
#define ll long long
const int N=1e6+10;
ll n,m;
ll a[N],b[N],c[N],d[N],e[N]={0};
bool check(int k)
{memset(e,0,sizeof(e));
   for(int i=1;i<=k;i++)
   {   e[c[i]]+=b[i];
       e[d[i]+1]-=b[i];
   }
    for(int i=1;i<=n;i++)
    {e[i]+=e[i-1];
        if(e[i]>a[i])return false;
    }
    return true;
}
int main()
{cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>b[i]>>c[i]>>d[i];
    ll l=1,r=m;
    while(l  ll mid=(l+r)>>1;
       if(check(mid))l=mid+1;
        else r=mid;
    }
    if (l != m){cout<<"-1"<

#include#include 
#include#include#include#include

#includeusing namespace std;
#define ll long long
const int N=1e5+10;
ll q[N],tmp[N];
ll ans=0;
void merge_sort(ll q[], ll l, ll r)
{if (l >= r) return;

    ll mid =( l + r) >>1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    ll k = 0, i = l, j = mid + 1;
    while (i<= mid && j<= r)
        if (q[i]<= q[j]) tmp[k ++ ] = q[i ++ ];
        else {tmp[k ++ ] = q[j ++ ];ans+=mid-i+1;}

    while (i<= mid) tmp[k ++ ] = q[i ++ ];
    while (j<= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i<= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){ll n;cin>>n;
    for(int i=1;i<=n;i++)cin>>q[i];
    merge_sort(q, 1, n);
    cout<

#includeusing namespace std;
#define ll long long
ll dfs(ll k){if(k==1)return 1;
    if(k%2)return dfs(k-1);
    else return dfs(k-1)+dfs(k/2);
}
int main(){ll n;cin>>n;
   cout<< dfs(n)<

#include#include#include
#include#define ll long long
using namespace std;
ll solve(ll n)
{if(n==0)return 0;
    if(n==1)return 1;
    return solve(n/2)+solve(n%2);
}
int main()
{ ll t;cin>>t;
    while(t--)
    {ll n;cin>>n;
        ll a=solve(n);
        ll p=pow(2,a)-1;
        printf("%lld %lld\n",a,p);
    }
    return 0;
}

#include#includeusing namespace std;
#define ll long long
void solve(string s1,string s2){ll k1=s1.size();
    ll k2=s2.size();
    if(k2<=0)return;
      cout<string s1,s2;cin>>s1>>s2;
                solve(s1,s2);
	return 0;
 }

#include#include#include
#include

#include#include#include
#include