牛客寒假算法訓練營2

C.算機率

連結：https://ac.nowcoder.com/acm/contest/3003/C

來源：牛客網

牛牛剛剛考完了期末，盡管牛牛做答了所有 n 道題目，但他不知道有多少題是正确的。

不過，牛牛知道第 i道題的正确率是 pi。

牛牛想知道這 n 題裡恰好有 0,1,…,n 題正确的機率分别是多少，對 10^9+7 取模。對 10^9 + 7取模的含義是：對于一個 b≠0 的不可約分數 a/b，存在 q 使得 b×q mod (109+7)=a，q 即為 a/b 對 10^9+7取模的結果。

這裡其實就是逆元，在考慮的時候，被分數的模數有點吓到了，不知道從何下手，以及如何轉換，其實直接用就可以了。。。。也算是漲了一波見識，順便溫習了一下逆元的知識。

由費馬小定理我們知道，a mod p如果P為質數，而且a不為p的倍數，那麼有 a^(p-1) = 1(mod p)，是以a^(p - 2) = 1 / a(mod p),即a的逆元，用于除法的模運算

這道題，給出的機率就直接用就行，不用去考慮什麼轉化，隻要注意取模就好

#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
const int base = 1e9 + 7;
ll p[2003];
ll ans[2003][2003];
int n;

void input(){
    scanf("%d",&n);
    for(int i = 1;i <= n;i++){
        scanf("%lld",&p[i]);
    }
}

void work(){
    ans[0][0] = 1;
    for(int i = 1;i <= n;i++){
        ans[i][0] = ans[i - 1][0] * (base + 1 - p[i]) % base;
    }
    for(int i = 1;i <= n;i++){
        for(int j = 1; j <= i;j++){
            ans[i][j] = (ans[i - 1][j] * (base + 1 - p[i]) + ans[i - 1][j - 1] * p[i]) % base;
        }
    }
    for(int i = 0;i <= n;i++){
        printf("%lld ",ans[n][i]);
    }
}

int main(){
    input();
    work();
    return 0;
}

D-數三角

連結：https://ac.nowcoder.com/acm/contest/3003/D

來源：牛客網

牛牛得到了一個平面，這個平面上有 n 個不重合的點，第 i 個點的坐标為 (xi,yi)。

牛牛想知道，這 n 個點形成的三角形中，總共有多少個鈍角三角形

高中的知識又全部倒給老師了。。。怎麼判斷鈍角都給忘了。。。。，題目本身感覺也不是特别難的樣子，自己做的時候又是判斷長度，判斷距離的，給搞得太複雜了。。。

#include <cstdio>
#include <utility>
#include <vector>
#include <math.h>
using namespace std;
const int maxn = 503;
int x[maxn];
int y[maxn];
int n;
void input(){
    scanf("%d",&n);
    int a,b;
    for(int i = 0;i < n;i++){
        scanf("%d%d",&x[i],&y[i]);
    }
}

bool check(int a,int b,int c){
    if((x[a] - x[b]) * (x[c] - x[b]) + (y[a] - y[b]) * (y[c] - y[b]) < 0){
        if((x[a] - x[b]) * (y[c] - y[b]) - (x[c] - x[b]) * (y[a] - y[b]) != 0){
            return true;
        }
    }
    return false;
}

void work(){
    int ans = 0;
    for(int i = 0;i < n - 2;i++){
        for(int j = i + 1;j < n - 1;j++){
            for(int k = j + 1;k < n;k++){
                if(check(i,j,k) || check(k,i,j) || check(j,k,i)){
                    ans++;
                }
            }
        }
    }
    printf("%d\n",ans);

}

int main(){
    input();
    work();
    return 0;
}

F-拿物品

連結：https://ac.nowcoder.com/acm/contest/3003/F

來源：牛客網

牛牛和牛可樂面前有 n 個物品，這些物品編号為 1,2,…,n每個物品有兩個屬性 ai,bi。

牛牛與牛可樂會輪流從剩下物品中任意拿走一個，牛牛先選取。

設牛牛選取的物品編号集合為 H，牛可樂選取的物品編号的集合為 T，取完之後，牛牛得分為 ∑i∈H；而牛可樂得分為 ∑i∈Tbii。

牛牛和牛可樂都希望自己的得分盡量比對方大（即最大化自己與對方得分的差）。

你需要求出兩人都使用最優政策的情況下，最終分别會選擇哪些物品，若有多種答案或輸出順序，輸出任意一種。

每一個物品對于自己的而言的戰略價值就等于 a + b，是以雙方每一次選取戰略價值最高的對自己最有利。其實就是貪心啦。。。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn = 2e5 + 7;
int n;
struct node{
    ll a;
    int num;
};
node res[maxn];
bool cmp(node a,node b){
    return a.a > b.a;
}

void input(){
    scanf("%d",&n);
    for(int i = 0;i < n;i++){
        scanf("%lld",&res[i].a);
    }
    for(int i = 0;i < n;i++){
        ll temp;
        scanf("%lld",&temp);
        res[i].a += temp;
        res[i].num = i + 1;
    }
}

void work(){
    sort(res,res + n,cmp);
    for(int i = 0;i < n;i += 2){
        printf("%d ",res[i].num);
    }
    puts("");
    for(int i = 1;i < n;i += 2){
        printf("%d ",res[i].num);
    }
}

int main(){
    input();
    work();
    return 0;
}

G-判正誤

連結：https://ac.nowcoder.com/acm/contest/3003/G

來源：牛客網

牛可樂有七個整數 a,b,c,d,e,f,g并且他猜想 a^d + b^e + c^f =g。但牛可樂無法進行如此龐大的計算。

請驗證牛可樂的猜想是否成立。

原本想着硬着頭皮去算一算，看到數那麼大有點發怵，後來倒是也想到了，整一個模數，在模數的意義下成立也行。為了保險起見，搞了三個模數，本來想着所有的都成立，才判斷為正确的。結果是隻要任意一個成立，就可以。（模數其實越大越醜越好）

#include <cstdio>
#define ll long long
const int base1 = 413;
const int base2 = 517;
const int base3 = 4177;
int t;
ll quick(ll a,ll b,int mod){
    ll res = 1;
    while(b){
        if(b & 1){
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

 bool work(ll a,ll b,ll c,ll d,ll e,ll f,ll g,int mod){
    a %= mod;
    b %= mod;
    c %= mod;
    d %= (mod - 1);
    e %= (mod - 1);
    f %= (mod - 1);
    g %= mod;
    ll tempa = quick(a,d,mod);
    ll tempb = quick(b,e,mod);
    ll tempc = quick(c,f,mod);
    if((tempa + tempb + tempc) % mod == g){
        return true;
    }else{
        return false;
    }
}

void input(){
    scanf("%d",&t);
    ll a,b,c,d,e,f,g;
    for(int i = 0;i < t;i++){
        scanf("%lld%lld%lld%lld%lld%lld%lld",&a,&b,&c,&d,&e,&f,&g);
        bool flag1 = work(a,b,c,d,e,f,g,base1);
        bool flag2 = work(a,b,c,d,e,f,g,base2);
        bool flag3= work(a,b,c,d,e,f,g,base3);
        if(flag1 || flag2 || flag3){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
}

int main(){
    input();
    return 0;
}

H-施魔法

連結：https://ac.nowcoder.com/acm/contest/3003/H

來源：牛客網

牛可樂有 n 個元素( 編号 1…n )，第 i 個元素的能量值為 ai。

牛可樂可以選擇至少 k 個元素來施放一次魔法，魔法消耗的魔力是這些元素能量值的極差。形式化地，若所用元素編号集合為 S，則消耗的魔力為 max i∈S{ai}−min i∈S{ai}。

牛可樂要求每個元素必須被使用恰好一次。

牛可樂想知道他最少需要多少魔力才能用完所有元素，請你告訴他。

我們将能量值按照從小到大的順序進行排列，那麼每一次我們消耗元素的時候，一定是按照順序消耗元素。不然魔力就不是最少的了。我們假設dp[i]為消耗第i個元素的時候，耗費的最小魔力，有轉移方程

d p [ i ] = m i n ( d p [ j − 1 ] − a [ j ] ) + a [ i ] ( j ∈ [ 1 , i − k + 1 ] ) dp[i] = min(dp[j - 1] - a[j]) + a[i](j\in[1,i - k + 1]) dp[i]=min(dp[j−1]−a[j])+a[i](j∈[1,i−k+1])

那麼我們隻需要維護好dp[j - 1] - a[j]的最小值就可以了。

#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn = 3e5 + 7;
ll a[maxn];
int n,k;
void input(){
    scanf("%d%d",&n,&k);
    for(int i = 1;i <= n;i++){
        scanf("%lld",&a[i]);
    }
}

void work(){
    sort(a + 1,a + n + 1);
    ll dp[maxn];
    for(int i = 1;i <= n;i++){
        dp[i] = 1e9 + 7;
    }
    ll pre = -a[1];
    for(int i = k;i <= n;i++){
        dp[i] = pre + a[i];
      //pre用來維護最小值
        pre = min(pre,dp[i -k + 1] - a[i - k + 2]);
    }
    printf("%lld",dp[n]);
}

int main(){
    input();
    work();
    return 0;
}

I-建通道

連結：https://ac.nowcoder.com/acm/contest/3003/I

來源：牛客網

在無垠的宇宙中，有 n 個星球，第 i 個星球有權值 vi。

由于星球之間距離極遠，是以想在有限的時間内在星際間旅行，就必須要在星球間建立傳送通道。

任意兩個星球之間均可以建立傳送通道，不過花費并不一樣。第 i 個星球與第 j 個星球的之間建立傳送通道的花費是 lowbit(vi⊕vj)，其中 ⊕為二進制異或，而 lowbit(x）為 x 二進制最低位 1 對應的值，例如 lowbit(5)=1,lowbit(8)=8。特殊地，lowbit(0)=0。牛牛想在這 n 個星球間穿梭，于是――你需要告訴牛牛，要使這 n 個星球互相可達，需要的花費最少是多少。

這道題是真的沒想到還可以這麼做。首先我們要把權值相同的星球給去掉，因為權值相同的星球，異或結果就是0，對答案沒有影響，是以去除這一部分。然後我們求出對于剩下的星球而言，權值的最低的一位（存在i個星球這一位為0，且存在j個星球這一位為1），相當于我們将這i個星球與j個星球相連即為最小

#include <cstdio>
#include <algorithm>
using namespace std;
#define ll long long
const int maxn = 2e5 + 7;
int v[maxn];
int n;
void input(){
    scanf("%d",&n);
    for(int i = 0;i < n;i++){
        scanf("%d",&v[i]);
    }
}

void work(){
    sort(v,v + n);
    int va = 0x7ffffff;
    int vo = 0;
    for(int i = 0;i < n;i++){
        va &= v[i];
        vo |= v[i];
    }
  	//va用來存放0的位置
  	//vo用來存放1的位置
  	//k用來判斷不重複的點有多少個
    int k = 0;
    v[n] = 1e9 + 7;
    for(int i = 0;i < n;i++){
        k += (v[i] != v[i + 1]);
    }
  	//va^vo可以将全1，全0的位置全部變成0，将既有0又有1的位置變成1
    va ^= vo;
    long long ans = 0;
    for(int i = 0;i <= 30;i++){
        long long cur = 1ll << i;
      //這裡就是判斷滿足條件的最低的lowbit
        if(va & cur){
            ans = cur * (k - 1);
            break;
        }
    }
    printf("%lld",ans);
}

int main(){
    input();
    work();
    return 0;
}

J-求函數

連結：https://ac.nowcoder.com/acm/contest/3003/J

來源：牛客網

牛可樂有 n 個一次函數，第 i 個函數為 fi(x)=ki×x+bi

牛可樂有 m 次操作，每次操作為以下二者其一：

• 1 i k b 将 fi(x)修改為 fi(x)=k×x+b

• 2 l r求 fr(fr−1(⋯(fl+1(fl(1)))⋯ ))。

牛可樂當然(bu)會做啦，他想考考你——

答案對 10^9 + 7 取模。

我們可以将2轉化為公式

∏ i = l r k i + ∑ i = 1 r b i ∏ j = i + 1 r \prod_{i=l}^{r}k_i+\sum_{i=1}^rb_i\prod_{j=i+1}^{r} i=l∏rki+i=1∑rbij=i+1∏r

多次的查詢，修改，我們可以想到通過線段樹來進行解決。又出現一個問題，左右兩邊要如何進行合并。對左邊我們設 ∏ i = l m i d k i = m 1 \prod_{i = l}^{mid}k_i = m_1 ∏i=lmidki=m1, ∑ i = 1 m i d b i ∏ j = i + 1 m i d = n 1 \sum_{i = 1}^{mid}b_i\prod_{j = i + 1}^{mid} = n_1 ∑i=1midbi∏j=i+1mid=n1,

對右邊 ∏ i = m i d + 1 r k i = m 2 \prod_{i = mid + 1}^{r}k_i = m_2 ∏i=mid+1rki=m2, ∑ i = m i d + 1 r b i ∏ j = i + 1 r = n 2 \sum_{i = mid + 1}^{r}b_i\prod_{j = i + 1}^{r} = n_2 ∑i=mid+1rbi∏j=i+1r=n2

那麼左右合并時， ∏ i = l r k i = m 2 ∗ m 1 \prod_{i = l}^{r} k_i=m2 * m1 ∏i=lrki=m2∗m1, ∑ i = 1 r b i ∏ j = i + 1 r = m 2 ∗ n 1 + n 2 \sum_{i = 1}^{r}b_i\prod_{j = i + 1}^{r} = m2 * n1 + n2 ∑i=1rbi∏j=i+1r=m2∗n1+n2

結合線段樹即可解決。（算是第一個自己寫的線段樹過的題QAQ，雖然當場還是沒有寫出來）

#include <cstdio>
#include <utility>
using namespace std;
typedef long long ll;
int n,m;
const int maxn = 2e5 + 7;
const int base = 1e9 + 7;
ll k[maxn];
ll b[maxn];
struct node{
    int l;
    int r;
    pair<ll,ll>key;
    node* left;
    node* right;
};
void input(){
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;i++){
        scanf("%lld",&k[i]);
    }
    for(int i = 1;i <= n;i++){
        scanf("%lld",&b[i]);
    }
}
//建立線段樹
node* buildTree(int l,int r){
    node* root = new node;
    root -> l = l;
    root -> r = r;
    if(l == r){
        root -> key = {k[l],b[l]};
    }else{
        int mid = (l + r) / 2;
        root -> left = buildTree(l,mid);
        root -> right = buildTree(mid + 1,r);
      //左右合并
        int temp1 = root -> left -> key.first * root -> right -> key.first % base;
        int temp2 = root -> left -> key.second * root -> right -> key.first % base + root -> right -> key.second % base;
        root -> key = {temp1,temp2};
    }
    return root;
}
//這裡用來合并數值
pair<int,int> merge(node* root){
    int temp1 = root -> left -> key.first * root -> right -> key.first % base;
    int temp2 = root -> left -> key.second * root -> right -> key.first % base + root -> right -> key.second % base;
    return {temp1,temp2};
}
//更新
node* update(node* temp,int k,int x,int y){
    if(temp -> l == temp -> r){
        temp -> key = {x,y};
        return temp;
    }
    int mid = (temp -> l + temp -> r) / 2;
    if(k <= mid){
        temp -> left = update(temp -> left,k,x,y);
    }else
        temp -> right = update(temp -> right,k,x,y);
    temp -> key = merge(temp);
    return temp;
}
//搜尋
pair<int,int> search(node* temp,int l,int r){
    if(temp -> l >= l && temp -> r <= r){
        return temp -> key;
    }
    int mid = (temp -> l + temp -> r) / 2;
    if(r <= mid){
        return search(temp -> left,l,r);
    }
    if(l > mid){
        return search(temp -> right,l,r);
    }
    pair<ll,ll> temp1 = search(temp -> left,l,mid);
    pair<ll,ll> temp2 = search(temp -> right,mid + 1,r);
    ll keyl = temp1.first * temp2.first % base;
    ll keyr = (temp1.second * temp2.first % base + temp2.second) % base;
    return {keyl,keyr};
}


void output(){
    node* root = buildTree(1,n);
    int x,y,z,c;
    for(int i = 0;i < m;i++){
        scanf("%d%d%d",&x,&y,&z);
        if(x == 2){
            pair<ll,ll> temp = search(root,y,z);
            printf("%lld\n",(temp.first + temp.second) % base);
        }else{
            scanf("%d",&c);
            update(root,y,z,c);
        }
    }
}

int main(){
    input();
    output();
    return 0;
}

牛客寒假算法訓練營2 牛客寒假算法訓練營2

牛客寒假算法訓練營2

C.算機率

D-數三角

F-拿物品

G-判正誤

H-施魔法

I-建通道

J-求函數

繼續閱讀

Codeforces 1417 D. Make Them Equal(思維+構造)

查找算法之二分查找查找算法之二分查找

查找算法學習之二分查找（Python版本）——BinarySearch

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

Command Network(POJ 3164)---定根最小樹形圖模闆題題目描述輸入格式輸出格式輸入樣例輸出樣例分析源程式

開源低帶寬語音編解碼器

241 Different Ways to Add Parentheses（C代碼版）

【趨高機器視覺】機器視覺技術原了解析及解決方案

CSMA/CD1． CSMA/CD的概述2． CSMA 的工作原理3． CSMA/CD控制規程及特點4． CSMA/CD協定5． CSMA/CD的優點6．結束語

極大似然法(ML)與最大期望法(EM)

C++ 第十五周報告1--《冒泡法排序》

筆試面試題目：滑動視窗(二)

資料結構與算法（27）——排序（二）

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

hdu7108哈希