牛客寒假算法训练营2

骑猪看日落 2023-07-04 04:49 10阅读 0赞

#  牛客寒假算法训练营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;
    }