算法 ACM C++ 数学

A. 完全 k 叉树

若想找到最长的一条路径，不妨找出两个离根最远，且没有公共路径的点。假设树共有 m 层，那么左下角的点到根的距离是 m-1，且这个点一定一个足够远的点。如果最后一层的点的数量大于倒数第二层的点数，则可以取最后一层的最右边的点作为计算最大距离的点，它到根的距离为 m-1。否则取倒数第二层最右边的点作为计算最大距离的点，它到根的距离为 m-2。（取点方法不唯一）由于没有公共路径，所以直接把这两个点到根的距离相加即可。

标程的这种写法中还会有一种情况是最后一层点数为 0，则左下角和右下角的点到根的距离都为 m-2。(当然你可以采取其他方法免除这种情况)
注意 k=1 的 text，此时应当输出 n-1。（如果不特判，在计算树的层数时可能会超时）

时间复杂度O(log𝑘 𝑛)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    ll n, k, cnt = 0, now = 1, t;
    cin >> t;
    while(t--){
        cnt = 0, now = 1;
        cin >> k >> n;
        if(k == 1){
            cout << n-1 << "\n";
            continue;
        } 
        while(n > 0) {
            n -= now;
            now *= k;
            cnt++;
            if(n < now)    break;
        }
        if(n == 0)    cout << cnt * 2 - 2 << endl;
        else if(n <= now / k)    cout << cnt * 2 - 1 << endl;
        else    cout << cnt * 2 << endl;
    }
}

B. 距离产生美

签到题，首先我们比较当前位置和上一位置的数字，如果距离过近，就需要改变数字。用贪心的思想发现，把当前位置的数字改成一个很大的值，确保它和相邻的两个数字的距离都足够大，这样的方案是最优的。（因为可以修改的值域是1018，所以一定能找出这样的数字）然后再往后扫描即可。扫描一遍之后就可以输出答案了。

时间复杂度O(n)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
ll co[maxn];
int main(){
    ll n, m, ans = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> co[i];
    }
    for(int i = 2; i <= n; i++)
        if(abs(co[i] - co[i-1]) < m)
            ans++, i++;
    cout << ans;
}

C. 烤面包片

首先根据范围可得 4!!一定大于109(事实上甚至大于1018)，所以 4!!!一定能被 mod 整除（n>4 也同理）。那么我们只需要判断 n≤3的情况了。直接计算即可。如果写一个阶乘函数，然后调用连续三次来获得答案，如：((n!%mod)!%mod)!%mod 可能会无法通过以下的 text：

2 2

（本应输出 0，但三次调用阶乘函数最终会输出 1，因为第一次调用得到 0，之后再调用阶乘函数发现 0！是 1）一个较好的处理方式是将 n=0，1，2 特判掉，然后预先计算出 3!!为720，然后用一次 for 循环解决这道题。

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long n, mod, now = 1;
    cin >> n >> mod;
    if(n == 0)    return cout << 1 % mod, 0;
    if(n < 3)    return cout << n % mod, 0;
    if(n > 3)    return cout << 0, 0;
    for(int i = 1; i <= 720; i++)
        now = now * i % mod;
    cout << now % mod;
}

D. 茶颜悦色

由题设 k 为正方形边长。首先我们可以通过确定正方形的底边来确定正方形。比如底边是由[x, y],[x + k, y]两点连成的边，那么这样的底边可以确定一个由[x, y],[x + k, y],[x, y + k],[x + k, y + k]四个点组成的正方形。假设我们用左下角的点[x, y]来代表这个正方形(下同)。现在我们来考虑某个点(a,b)可以被怎样的正方形包含。那么我们会发现，左下角的点的 x 坐标满足（a − k ≤ x ≤ a）且 y 坐标满足（b − k ≤ y ≤ b）会包含(a,b)这个点。

我们不妨用扫描线的思想来解决这道题。我们从左到右地扫描 x坐标，并用线段树维护当前 y 坐标上的点数量。即当目前扫描到区间[a − k, a]时，点(a,b)对 y 坐标为[b-k,b]中的正方形有贡献。所以当扫描到 a-k 时，将区间[b-k,b]全部+1。当扫描到 a 时，将区间对地-1。这样就可以描述(a,b)点对题目答案的贡献了。具体的做法：每个点(a,b)存两遍，一遍存(a-k,b)且置 flag 为 1，代表扫描到此点时要将区间+1，第二遍存(a,b)且置 flag 为-1，代表扫描到此点时要将区间-1。然后按 x 坐标排序，用线段树扫描 x 坐标即可。每次+1 之后区间查询全局最大值，更新答案。

时间复杂度O(𝑛log2 𝑛)

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<sstream>
#include<set>
#include<map>
#include<queue>
#include<bitset>
#include<vector>
#include<limits.h>
#include<assert.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL,LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(LL &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const LL &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T,class U> void _W(const pair<T,U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
 #define DEBUG(...) {printf("# ");printf(__VA_ARGS__);puts("");}
#else
 #define DEBUG(...)
#endif
int MOD = 1e9+7;
void ADD(LL& x,LL v){x=(x+v)%MOD;if(x<0)x+=MOD;}
/*}}}*/
const int SIZE = 1e6+10;
LL ma[SIZE],_tmp[SIZE];
void push(int id){
    if(_tmp[id]==0)return;
    _tmp[id*2]+=_tmp[id];
    ma[id*2]+=_tmp[id];
    _tmp[id*2+1]+=_tmp[id];
    ma[id*2+1]+=_tmp[id];
    _tmp[id]=0;
}
void pull(int id){
    ma[id]=max(ma[id*2],ma[id*2+1]);
}
LL qq(int L,int R,int id,int ll,int rr){
    if(R<ll||L>rr)return LLONG_MIN;
    if(L>=ll&&R<=rr)return ma[id];
    int mm=(L+R)/2;
    push(id);
    return max(qq(L,mm,id*2,ll,rr),qq(mm+1,R,id*2+1,ll,rr));
}
void ins(int L,int R,int id,int ll,int rr,LL v){
    if(R<ll||L>rr)return;
    if(L>=ll&&R<=rr){
        ma[id]+=v;
        _tmp[id]+=v;
        return;
    }
    int mm=(L+R)/2;
    push(id);
    ins(L,mm,id*2,ll,rr,v);
    ins(mm+1,R,id*2+1,ll,rr,v);
    pull(id);
}
struct Data{
    int x,y,ty;
    Data(int x=0,int y=0,int ty=0):x(x),y(y),ty(ty){}
    bool operator<(const Data& b)const{
        return x<b.x||(x==b.x&&ty>b.ty);
    }
}d[SIZE];
int dn;
VI yy;
int main(){
    int n,k; R(n,k);
    FOR(i,1,n){
        int x,y;
        R(x,y);
        yy.PB(y-1);
        yy.PB(y+k);
        d[dn++]=Data(x,y,1);
        d[dn++]=Data(x+k,y,-1);
    }
    SORT_UNIQUE(yy);
    sort(d,d+dn);
    LL an=0;
    REP(i,dn){
        int x=GET_POS(yy,d[i].y-1)+1;
        int y=GET_POS(yy,d[i].y+k);
        ins(0,SZ(yy)-1,1,x,y,d[i].ty);
        LL res=qq(0,SZ(yy)-1,1,0,SZ(yy)-1);
        //W(x,y,d[i].ty,res);
        an=max(an,res);
    }
    W(an);
    return 0;
}

E. 飞行棋

由题设骰子面数为 k，首先我们先来考虑当前到终点的距离 d 小于 k 的情况。只有当扔出的点数Q == d时，可以到达终点，概率为1/𝑘。否则都会到达一个新的点𝑑′,且𝑑′ < 𝑘，则相当于还是会有1𝑘的概率到达终点。每次掷骰子到达终点的概率均为1/𝑘，则此时的期望为 k。现在我们可以假设我们从终点出发，倒着做即可。假设现在到终点的距离为 n，那么只有可能从距离[n − k, n − 1]的区间掷骰子到此点，且概率均为1/𝑘，再加上投掷骰子的动作会使得期望+1。所以用概率 DP 的思想推得公式为

但是由于 n 过大，线性的递推是无法解决问题的，所以需要用矩阵快速幂优化计算过程来求解此题。

时间复杂度𝑂(𝑘³log₂𝑛)

#include <cstdio>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <list>
#include <cmath>
using namespace std;

#define mp make_pair
#define sz(a) a.size()

#define Se second
#define Fi first
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(int i=0;i<(n);i++)
#define for1(i, n) for(int i=1;i<=(n);i++)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pl;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<long long > vl;


const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int maxn = (int)200000+7;

const int me = 1;
const int fr = 10000000;
ll powmod(ll a,ll b) {ll res=1;a%=MOD; if(b<0) return -1; for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
#define mod(x) (((x)%MOD+MOD)%MOD)
int n=54;
struct  mat{
    ll m[55][55];
} unit;
mat operator *(mat a,mat b){
    mat ret;
    ll x;
    forn(i,n)
        forn(j,n){
            x =0 ;
            forn(k,n)
                x+=mod((ll)a.m[i][k]*b.m[k][j]);
            ret.m[i][j] = mod(x);
        }
    return ret;
}

void init_unit(){
    forn(i,55)
        unit.m[i][i]=1;
    return ;
}

mat pow_mat(mat a,ll n){
    mat ret = unit;
    while(n){
        if(n&1) ret = ret*a;
        a = a * a;
        n>>=1;
    }
    return ret;
}


int main() {
    ll x;
    init_unit();
    mat t;
    ll n,k;
    int m;
    cin>>n>>k; 
        ll p = powmod(k,MOD-2);
        if(n <= k)
            return cout<<k, 0;
        mat tag;
        forn(i,55) forn(j,55) tag.m[i][j] = 0;
        for1(i,k) tag.m[i][3] = k;
        tag.m[k+1][4] = 1;
        forn(i,55) forn(j,55) t.m[i][j] = 0;
        for1(i,k-1) t.m[i][i+1] = 1;
        for1(i,k) t.m[k][i] = p;
        t.m[k][k+1] = 1;
        t.m[k+1][k+1] = 1;
        mat res;
        res = pow_mat(t,n - k);
        res = res * tag;
        x = res.m[k][5];
        cout<<x<<endl;
}

F :三元组

对于一组满足条件的(i, j):

2 ∗ min(𝑎𝑖 + 𝑎𝑗, 𝑏𝑖 + 𝑏𝑗) ≤ max(𝑎𝑖 + 𝑎𝑗, 𝑏𝑖 + 𝑏𝑗)

也必然满足:

min(ai + aj, 𝑏𝑖 + 𝑏𝑗) ≤ max(𝑎𝑖 + 𝑎𝑗, 𝑏𝑖 + 𝑏𝑗)

不妨设 2(𝑎𝑖 + 𝑎𝑗) ≤ 𝑏𝑖 + 𝑏𝑗,即ai + aj ≤ 𝑏𝑖 + 𝑏𝑗
此时,显然不需要考虑min(𝑎𝑖 + 𝑎𝑗, 𝑏𝑖 + 𝑏𝑗) = 𝑎𝑖 + 𝑎𝑗这个条件
移项可得

(2 ∗ 𝑎𝑖 − bi) + (2 ∗ 𝑎𝑗 − bj) ≤ 0

直接按照2 ∗ 𝑎𝑖 − 𝑏𝑖升序进行排序,记数组为P
此时可以发现性质:
若𝑃𝑖最多只能和𝑃𝑗匹配,则𝑃𝑖 + 1只能和[i + 1, j]之间的匹配
此时使用滑窗即可计算答案
又因为我们只考虑了2(𝑎𝑖 + 𝑎𝑗) ≤ bi + bj的情况
再对每个三元组中的𝑎𝑖, bi进行交换,计算一次答案即可。

时间复杂度O(n + nlog2 𝑛)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e5+10;
const ll mod = 1e9+7;
struct node{ll a, b, c;}p[maxn];
bool cmp(node x, node y) {return (2*x.a-x.b) < (2*y.a-y.b);}
int n;
ll sum[maxn];
ll solve() {
    sort(p+1, p+1+n, cmp);   // 2a-b 从小到大排序
    sum[0] = 0;
    for(int i = 1; i <= n; i++)
        sum[i] = (sum[i-1]+p[i].c)%mod;
    int l = 1, r = n, sign = 0;  ll k = 2*p[1].a-p[1].b;  //二分找出最右边  on遍历也行
    while(l <= r) {
        int mid = (l+r)>>1;
        ll t = 2*p[mid].a-p[mid].b;
        if((k+t) <= 0)  sign = mid, l = mid+1;
        else r = mid-1;
    }
    ll res = 0;  //双指针
    for(l = 1, r = sign; l <= r; l++) {
        while(r >= l && (2ll*p[l].a+2ll*p[r].a-p[l].b-p[r].b) > 0)  r--;
        if(r < l)  break;
        ll tmp = (sum[r]-sum[l-1]+mod)%mod;
        res = (res + p[l].c*tmp%mod)%mod;
    }
    return res;
}
int main() {
    cin>>n;
    for(int i = 1; i <= n; i++) cin>>p[i].a>>p[i].b>>p[i].c;
    ll ans = solve();
    for(int i = 1; i <= n; i++) swap(p[i].a, p[i].b);
    ans += solve();
    ans%=mod;
    cout<<ans<<endl;
}

G: 篮球校赛
选出每种能力的前 5 个人(很显然，如果一个人某个位置不在前 5，那么他不可能作为此位置出战)，总共选出 25 人（可能重复）然后使用 DFS 判断答案即可（当然，这一步可以用状压 DP 优化时间，但没必要）

时间复杂度O(𝑛 + 5⁵)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
bool vis[maxn];
ll co[maxn][6];
ll mmax[6][6], ans = 0;
void dfs(int now, ll tmp){
    if(now == 6){
        ans = max(ans, tmp);
        return;
    }
    for(int i = 1; i <= 5; i++){
        if(vis[mmax[i][now]])    continue;
        vis[mmax[i][now]] = 1;
        dfs(now + 1, tmp + co[mmax[i][now]][now]);
        vis[mmax[i][now]] = 0;
    }
}
int main(){
    ll n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= 5; j++){
            cin >> co[i][j];
            for(int pos = 1; pos <= 5; pos++){
                if(co[i][j] > co[mmax[pos][j]][j]){
                    for(int k = 5; k >= pos + 1; k--)
                        mmax[k][j] = mmax[k-1][j];
                    mmax[pos][j] = i;
                    break;
                }
            }
        }
    }
    dfs(1, 0);
    cout << ans << endl;
}

H: 分配学号

先排序，然后判断当前位置的同学的学号有几种选择的方案，累乘获得结果。

时间复杂度O(nlog₂ 𝑛)

#include <bits/stdc++.h>
typedef long long lld;
using namespace std;
const int MAXN = 1e5+5;
const int MOD = 1e9+7;
int n; lld a[MAXN];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%lld", &a[i]);
    sort(a, a+n);

    lld ans = 1;
    for (int i = 0, j; i < n; i = j)
        for (j = i+1; j < n && a[j] < a[i]+j-i; j++)
            ans = ans * (a[i]+j-i-a[j]+1) % MOD;
    printf("%lld\n", ans);
    return 0;
}

I: Gree 的心房

签到题，假设要走的路线是沿着地图的两条边走，那么最优的情况就是这 k 个物品都不挡路，所以判断 k 与(n-1)*(m-1)的关系即可。

时间复杂度 O(1)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll n, m, k;
    cin >> n >> m >> k; 
    if(k <= (n-1) * (m-1))
        cout << n + m - 2;
    else
        cout << -1;
}

本文由 Time 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Jul 28, 2019 at 09:10 pm