2020-11-26 13:08 已编辑江西师范大学前端工程师

关注

牛客算法竞赛入门课第三节习题

K-th Number

直接二分答案，然后判断答案是否符合要求即可。。。。

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

ll t , n , k , m;
ll a[N];

bool check(ll x){
    ll num = 0 , s = 0;
    for(int i = 1 , j = 1 ; j <= n ; ++j){
        if(a[j] >= x) num++;  //大于x的值的个数
        if(num == k){    //出现k个值大于等于x
            s += n - j + 1;  //将有边界大于等于j的区间都算上
            while(a[i] < x){ 
                s += n - j + 1;  //左边界右移 如果num没少 又加一次右边界等于大于j的区间
                i++;   //这个左边界值大于等于x
            }
            num--;
            i++;
        }
    }
    return s >= m;
}

int main(void){
    scanf("%lld" , &t);
    while(t--){
        scanf("%lld%lld%lld" , &n , &k , &m);
        for(int i = 1 ; i <= n ; ++i) scanf("%lld" , &a[i]);
        ll l = 1 ,  r = 1e9 , ans = 0 , mid;
        while(l <= r){
            mid = (l + r)>>1;
            if(check(mid)) ans = mid , l = mid + 1;
            else r = mid - 1;
        }
        printf("%lld\n" , ans);
    }
    return 0;
}

位数差

分治，将问题转换为，[0,n)这个区间假设我们存在一个分治函数，可以求到[0,mid),[mid,n)，之间的答案，那么最终的答案就还要加上a[i]在左边，a[j]在右边即可！

于是我们就只要匹配右边进位的个数然后二分查找即可

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

int a[N];
int b[9] = { 10,100,1000,10000,100000,1000000,10000000,100000000,1000000000 };

ll solve(int l , int r){
    if(r - l == 1) return 0;
    int mid = (l + r) >> 1;
    ll ans = solve(l , mid) + solve(mid , r);
    sort(a + mid , a +  r);
    for(int i = l ; i < mid ; ++i){
        for(int j = 0 ; j < 9 ; ++j){
            if(b[j] - a[i] > 0)
                ans += a + r - lower_bound(a + mid , a + r , b[j] - a[i]);

        }
    }
    return ans;
}

int main(void){
    int n = read();
    for(int i = 0 ; i < n ; ++i)
        a[i] = read();
    printf("%lld\n" , solve(0 , n));
    return 0;
}

栗酱的不等式

直接二分答案！冲，因为x最小是2，所以n要从8开始

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

int main(void){
    ll n;
    while(cin>>n){
        ll ans = -1 , l = 8 , r = 1e16 , mid;
        ll cnt , x;
        while(l <= r){
            mid = (l + r) >> 1;
            for(cnt = 0 , x = 2 ; x * x * x <= mid ; ++x){
                cnt += mid / (x * x * x);
            }
            if(cnt > n)     r = mid - 1;
            else if(cnt == n) ans = mid , r = mid - 1;
            else l = mid + 1; 
        }
        cout<<ans<<endl;
    }
    return 0;
}

完全平方数

因为完全平方数开根号之后就是一段连续的数字，所以可以直接对两个端点开根号然后剪一下就可以了

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

int main(void){
    int T = read();
    while(T--){
        int l = read() , r = read();
        cout << floor(sqrt(1.0 * r)) - ceil(sqrt(1.0 * l)) + 1 << endl;
    }
    return 0;
}

wyh的物品

二分答案，没有难点

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
int n , m;

struct node{
    double a , b , c;
    bool operator < (const node& b) const{
        return c > b.c;
    }
}a[N];

bool check(double x){
    for(int i = 1 ; i <= n ; ++i) {
        a[i].c = a[i].b - x * a[i].a;
    }
    sort(a + 1 , a + 1 + n);
    double ans = 0;
    for(int  i = 1 ; i <= m ; ++i)
        ans += a[i].c;
    return ans > eps;
}



int main(void){
    int T = read();
    while(T--){
        n = read() , m = read();
        for(int i = 1 ; i <= n ; ++i){
            a[i].a = read();
            a[i].b = read();
        }
        double l = eps , r = 1e9 , mid ;
        for(int i = 1 ; i <= 100 ; ++i){
            mid = (r + l) / 2.0;
            if(check(mid)) l = mid;
            else r = mid;
        }
        printf("%.2lf\n" , mid);
    }
    return 0;
}

聪明的质监员

二分+前缀和

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
ll n , m , s;
int w[N] , v[N];
int l[N] , r[N];
ll sum[N] , cnt[N];

ll calc(ll x){
    for(int i = 1 ; i <= n ; ++i){
        if(w[i] >= x){
            sum[i] = sum[i - 1] + v[i];
            cnt[i] = cnt[i - 1] + 1;
        }
        else{
            sum[i] = sum[i - 1];
            cnt[i] = cnt[i - 1];
        }
    }
    ll sm = 0;
    for(int i = 1; i <= m ; ++i){
        sm += (cnt[r[i]] - cnt[l[i] - 1]) * (sum[r[i]] - sum[l[i] - 1]);
    }
    return sm;
}

int main(void){
    n = read() , m = read() , s = read();
    for(int i = 1 ; i <= n ; ++i)
        w[i] = read() , v[i] = read();
    for(int i = 1 ; i <= m ; ++i)
        l[i] = read() , r[i] = read();
    int reft  = 0 , right = INF;
    while(reft <= right){
        int mid = (reft + right) >> 1;
        if(calc(mid) >= s) reft = mid + 1;
        else right = mid - 1;
    }  
    cout<<min(abs(calc(right) - s) , abs(calc(right + 1) - s))<<endl;
    return 0;
}

[CQOI2010]扑克牌

只要能想到二分答案这个题目就很简单了

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;
int n , m;
int a[55];

bool check(ll x){
    ll num = 0 ;
    for(int i = 1 ; i <= n ; ++i){
        if(a[i] < x) num += (x - a[i]);
    }
    return num <= m && num <=x;
}
int main(void){
    n = read() , m = read();
    for(int i = 1 ; i <= n ; ++i)
        a[i] = read();
    ll l = 0 , r = 2e9 , mid;
    while(l + 1 < r){
        mid = (l + r) >> 1;
        if(check(mid)) l = mid;
        else r = mid ;
    }
    cout<<l<<endl;
    return 0;
}

[SCOI2010]传送带

这个题目我们很容易就能想到在ab和cd上的某个点的时候，值有最大，过了和未达到都是小于，所以很明显是一个三分，只是在三分的时候要三分两次，及对ab三分和对cd三分，想明白了之后就很简单了，就是一个套两次三分的题目

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e7 + 7;
const int INF = 0x3f3f3f3f;

const double eps = 1e-4;
double p , q , r;

struct node{
    double x , y;
}a , b , c ,d , e , f;

double dis(node a , node b){
    return sqrt(eps + (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}

double check1(double x){
    f = { c.x + (x / dis(c,d) * (d.x - c.x)),c.y + (x / dis(c,d) * (d.y - c.y)) };
    return dis(e , f) / r + (dis(c , d) -  x) / q;
}

double check(double x){
    e = { a.x + x / dis(a , b) * (b.x - a.x) , a.y + x / dis(a ,b) * (b.y - a.y)};
    double l = 0 , r = dis(c , d);
    for(int i = 1 ; i <= 1000 ; ++i){
        double lm = l + (r - l) / 3 , rm = r - (r - l) / 3;
        if(check1(lm) >= check1(rm)) l = lm;
        else r = rm;
    }
    return check1(l) + x / p;
}

int main(){
    cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y>>d.x>>d.y;
    cin>>p>>q>>r;
    double l = 0 , r = dis(a , b);
    for(int i = 1 ; i <= 1000 ; ++i){
        double lm = l + (r - l) / 3 , rm = r - (r - l) / 3;
        if(check(lm) >= check(rm)) l = lm;
        else r = rm;
    } 
    printf("%.2f\n" , check(l));
    return 0;
}

[SHOI2017]期末考试

因为收到两个方程的约束，所以就是一个抛物线，三分最高点就好了

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ull read() { ull s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int INF = 0x3f3f3f3f;

const int N = 1e6 + 7;
ull a , b , c;
ull n , m ;
ull t[N] , g[N];

ull check(ull x){
    ll p = 0 , q = 0 , res = 0;
    for(int i = 1 ; i <= m ; ++i){
        if(g[i] >= x) p += g[i] - x;
        else q += x - g[i];
    }
    if(b <= a) res = p * b;
    else{
        if(q >= p) res = p * a;
        else res = q * a + (p - q) * b;
    }
    for(int i = 1 ; i <= n ; ++i)
        if(t[i] < x) res += (x - t[i]) * c;
    return res;
}

int main(void){
    a = read() , b = read() , c = read();
    n = read() , m = read();
    for(int i = 1 ; i <= n ; ++i)
        t[i] = read();
    for(int i = 1 ; i <= m ; ++i)
        g[i] = read();
    ull l = 1 , r = *max_element(g + 1 , g + m + 1);   
    while( l + 10 < r){
        ull m = l + r >>1 , mm = (m + l) >> 1;
        if(check(m) >= check(mm)) r = m;
        else l = mm;
    } 
    ull ans = 2e18;
    for(ll i = l ; i <= r ; ++i) ans = min(ans , check(i));
    cout<<ans<<endl;
    return 0;
}

华华给月月准备礼物

二分答案即可，要注意不能取到0

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ull read() { ull s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int INF = 0x3f3f3f3f;
const int N = 1e6 + 7;

ll a[N];
int n , k;

bool check(ll x){
    ll cnt = 0 ;
    for(ll i = 1 ; i <= n ; ++i){
        cnt += a[i] / x;
    }
    return cnt >= k;
}

int main(void){
    cin>>n>>k;
    for(int i = 1 ; i <= n ; ++i){
        cin>>a[i];
    }
    ll l = 0 , r = 1e9 + 7;
    while(l < r){
        ll mid = (r + l + 1 ) >> 1;
        if(check(mid)) l = mid;
        else r = mid  - 1;
    }
    cout<<l<<endl;
    return 0;

}

Chocolate Eating

这个题目以前好像做过，不是用二分做的，要做的话也不难，首先二分答案，然后在二分的过程中标记每一巧克力吃的时间，

code

#include<bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e5 + 7;
const int INF = 0x3f3f3f3f;

ll l , r , mid , ans ;
ll n , d , a[N] , day[N];

bool check(ll x){
    ll tot = 0 , sum = 0;
    for(int i = 1 ; i <= d ; ++i){
        sum = sum >> 1;
        while(sum < x){
            sum += a[++tot];
            if(tot > n) return false;
            if(x && x == ans) day[tot] = i;
        } 
    }
    return true;
}

int main(void){
    n = read() , d = read();
    for(int i = 1 ; i <= n ; ++i){
        a[i] = read() , r += a[i];
    }
    while( l <= r ){
        mid = (l + r) >> 1;
        if(check(mid)) ans = mid , l = mid + 1;
        else r = mid - 1;
    }
    printf("%lld\n" , ans );
    check(ans);`q
    for(int i = 1 ; i <= n ; ++i){
        if(day[i]) printf("%lld\n" , day[i]);
        else printf("%lld\n" , d);
    }
    return 0;
}

4 Values whose Sum is 0

最暴力的做法就是写一个四重循环然后去爆搜他，但是很明显是不行的，所以我们考虑更优的做法，我们可以算出三重循环的和，然后去二分第四重，但是这个还是不够用的，所以我们要考虑更优的做法

既然可以二分一重那么我就可以考虑二分两重，要二分两重就要考虑一些特殊的做法，比如我把两个的值加起来，形成一个新的数组，然后我们就只需要循环两重，然后二分这个新的数组去找就可以了.

还有就是我像一个憨憨一样拿着c++交了两发java，看到头文件报错还以为是poj。。

code

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e6 + 7;

int a[N] , b[N] , c[N] , d[N];

vector<int> v;

int main(void){
    int n = read();
    for(int i = 1 ; i <= n ; ++i){
        a[i] = read();
        b[i] = read();
        c[i] = read();
        d[i] = read();
    }
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            v.push_back(a[i] + b[j]);
        }
    }
    sort(v.begin() , v.end());
    ll ans = 0;
    for(int i = 1 ; i <= n ; ++i){
        for(int j = 1 ; j <= n ; ++j){
            int x = -(c[i] + d[j]);
            ans += upper_bound(v.begin() , v.end() , x) - lower_bound(v.begin() , v.end() , x);
        }
    }
    cout<<ans<<endl;
    return 0;
}

Drying

题目都读不懂。。。简直吐了，还有输入和输出的样例也是有毒，那个sample input #1和sample input #2是不用理的，输入和输出都不用理，然后那个还会卡一波cin选手，然后这个题目也就不难了，很容易就能看出来直接二分

code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;
ll a[N] , n , k;

bool check(ll x){
    ll ans = 0;
    for(int i = 1 ; i <= n; ++i){
        if(a[i] > x) ans += (a[i] - x + k - 2) / (k - 1);
    }
    return ans <= x;
}

int main(void){
    ll max ; 
    while(scanf("%lld" , &n)!=EOF){
        for(int i = 1 ; i <= n ; ++i){
            scanf("%lld" , &a[i]);
        }
        ll l = 1 , r = 1e9;
        scanf("%lld" , &k);
        if(k == 1){
            printf("%lld\n" , *max_element(a + 1 , a + 1 + n));
            continue;
        }
        while(l < r){
            ll mid = (l + r) >> 1;
            if(check(mid)) r = mid;
            else l = mid + 1 ;
        }
        printf("%lld\n" , l);
    }
    return 0;
}

Monthly Expense

题目的意思就是有n个数把他们分成m组，每一组求和，然后问m组最大的数字最小是多少

就是一个简单的二分题

code

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e6 + 7;
const int INF = 0x3f3f3f3f;

int n , m;
int a[N];

bool check(ll x){
    ll tmp = 0 , res = 1;
    for(int i = 1 ; i <= n ;++i){
        if(a[i] > x) return 0;
        if(tmp + a[i] > x){
            tmp = 0;
            res++;
        } 
        tmp += a[i];
    }
    return res <= m ;
}

int main(void){
    n = read() , m = read();
    for(int i = 1 ; i <= n ; ++i)
        a[i] = read();
    ll l = 0 , r = 1e9 ,ans;
    while(l <= r){
        int mid = (l + r) >>1;
        if(check(mid)) r = mid - 1 , ans = mid;
        else l = mid + 1; 
    }
    printf("%lld\n" , ans);
    return 0;
}