寒假訓練第一場-創(chuàng)新互聯(lián)

首先不希望桌子有空閑時間，所以誰先到誰就先排隊。
所以我們先排序所有人的到達時間，從到達時間小的開始放置。
假設對于我們當前要放置的隊伍來說，肯定放在最先結束的桌子上。找到三個桌子誰先結束。所以我們需要維護每個桌子當前結束時間。

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;

}

首先題目中說所有說話的人是相鄰的（上下左右）， 對于豎著相鄰的人來說，橫著的過道才能影響，對于橫著相鄰的來說，豎著的過道影響。
對于一條豎著的過道，影響的只能是相鄰兩列的人，所以貪心的來說，對于每一條過道我們都希望是影響最多的人。
那么統(tǒng)計一下每對人如果要拆開，需要在哪一列 / 一行，防止過道。然后排序從大到小，輸出題目要求的過道數量即可。
需要注意的點，題目要求輸出過道的位置時，要求從小到大輸出。
因為我們需要輸出哪個過道被統(tǒng)計的數量最多，所以我們在統(tǒng)計次數的時候，也要標記上是哪個過道，這樣排序的時候我們知道是哪個過道最多。
所以使用結構體存。

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

struct Node
{int id, w;
}he[N], le[N]; //分別統(tǒng)計行和列的次數


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);
        }
    }
    
    //按照統(tǒng)計次數，從大到小
    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;
}

題目規(guī)定，最多 2 個物品一組，并且組內大物品不能超過上限值，問你最少多少組。
我們肯定希望盡可能滿足 2 個物品一組，所以我們讓最小的價值和大的價值組一塊是最優(yōu)解。如果說不能組一塊，那大價值只能自己一組。
那么最小值就依次找次小值。

#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， 那么就失敗了。

首先我們可以把所有的障礙分為兩類，一類是撞完會增加的，另一類是撞完會減少的。
因為我們希望盡可能的把球的穩(wěn)定性變成大，然后再減小，這樣盡可能滿足更多的障礙。
所以我們先撞增加的，再撞減小的。

對于先撞增加的這一類：
因為先撞再增加，所以盡可能的使得撞的值小的放在前面，讓球的穩(wěn)定性盡可能大，避免撞完就小于0。

可能會說，存在一個增加的障礙，但是他的損耗是很大的，肯定會導致撞完就小于0，不能回復。
這樣因為他是撞完增加的，我們把他放在前面，是不是最優(yōu)解？。
因為我們的要求是能夠到達終點，而不是通過最多的障礙。
因為這個是損耗大的回復，所以我們肯定把他放在這一類的最后來撞，因為這時已經是極大值的穩(wěn)定性，如果這時都不能通過，所以肯定不能到達終點。

對于撞完損耗這一類：
因為我們目標是到重點，那么如果到終點，我們大值 + 回復 一定大于所有的損耗 （損耗是一個定值），否則肯定會在路上失敗。
那么我們盡可能的讓回復多的在前面，這樣就盡可能的滿足穩(wěn)定性大。

#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;
}

暴力的解法就是 從 左區(qū)間l到右區(qū)間r 找到滿足條件數的個數。但考慮到 l和r的大小 可以先預處理出來所有的平方數，然后用二分查找到 處于區(qū)間（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();
}

可以使用二分答案 枚舉區(qū)間（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