2020牛客寒假算法基础训练营2

发布日期：2022-03-30 18:18:17 浏览次数：41 分类：博客文章

本文共 9366 字，大约阅读时间需要 31 分钟。

2020牛客寒假算法基础训练营2

A.做游戏(思维)

题意：两个人玩石头剪刀布，牛牛出石头a次，剪刀b次，布c次，牛可乐出石头x次，剪刀y次，布z次，问牛牛最多可以赢多少次

题解：对牛牛每次可以赢的出法取最小值即可

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
               using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read(); int main(){ ll a,b,c,x,y,z; cin>>a>>b>>c>>x>>y>>z; ll ans = min(a,y)+min(b,z)+min(c,x); cout<
              
               <

B.排数字(思维)

题意：给定一个由纯数字构成的字符串，你可以随机排列这些数字，问你排出的字符串最多包含多少个“616”子串，61616这样的算两个

题解：最好的情况肯定是“61616”这样排列，结果就是6和1的数量取最小值。

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();int main(){ int n,cnt6 = 0,cnt1 = 0; string s; cin>>n>>s; for(int i = 0; i < n; i++){ if(s[i]=='6')cnt6++; if(s[i]=='1')cnt1++; } cout<
              
               <

C.算概率(DP)

题意：一共n道题，每道题做对的概率为pi，问做对0-n道题的概率分别是多少，结果对1e9+7取模

题解：\(dp_{i,j}\)表示前i道题做对了j道，则有状态转移方程\(dp_{i,j}\) = \(dp_{i-1,j}\)x(1-\(p_i\))+\(dp_{i-1,j-1}\)x\(p_i\)，注意j=0的特殊情况，时间复杂度O(\(n^2\))

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;using ll = long long;const ll N = 2019;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();ll n,p[N],dp[N][N];const ll mod = 1e9+7;int main(){ cin>>n; dp[0][0] = 1; for(int i = 1; i <= n; i++) cin>>p[i]; for(int i = 1; i <= n; i++){ dp[i][0] = dp[i-1][0]*(mod+1-p[i])%mod; for(int j = 1; j <= i; j++){ dp[i][j] = (dp[i-1][j]*(mod+1-p[i])+dp[i-1][j-1]*p[i])%mod; } } for(int i = 0; i <= n; i++){ cout<
              
               <<" "; } return "BT7274", NULL;}inline ll read() { ll hcy = 0, dia = 1;char boluo = getchar(); while (!isdigit(boluo)) {if (boluo == '-')dia = -1;boluo = getchar();} while (isdigit(boluo)) {hcy = hcy * 10 + boluo - '0';boluo = getchar();} return hcy * dia;}

D.数三角(极角排序)

题意：给定n个不重复的点，求一共可以组成多少个钝角三角形

题解：对每个点进行极角排序后双指针找上下界统计钝角数量

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();struct node1{ double x,y;}a[1000];double node[1500];int main(){ int n; cin>>n; for(int i = 1; i <= n; i++)cin>>a[i].x>>a[i].y; ll ans = 0; for(int i = 1; i <= n; i++){ int cnt = 0; for(int j = 1; j <= n; j++){ if(i==j)continue; node[++cnt] = atan2(a[i].y-a[j].y,a[i].x-a[j].x); if(node[cnt] < 0)node[cnt]+=2*PI; } sort(node+1,node+1+cnt); for(int j = 1; j <= cnt; j++) node[j+cnt] = node[j]+2*PI; int l = 1,r = 1; for(int j = 1; j <= cnt; j++){ while(r <= 2*cnt&&node[r] - node[j] < PI)r++; while(l <= 2*cnt&&node[l] - node[j] <= 0.5*PI)l++; ans+=r-l; } } cout<
              
               <

E.做计数(完全平方数)

题意：给定一个n，问有多少个不同的三元组{i，j，k}，满足\(\sqrt{i}+\sqrt{j} = \sqrt{k}\)，i，j，k均为正整数，且i * j <= n，i，j，k有一者不同即为不同

题解：展开算式可得 i + j + 2\(\sqrt{ij}\) = k，可见i*j必须是完全平方数，枚举n以内的完全平方数，再枚举其因数即可

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();int main(){ int ans = 0; int n; cin>>n; for(int i = 1; i*i <= n; i++){ for(int j = 1; j <= i; j++){ if(i*i%j==0){ ans+=2; } }ans-=1; } cout<
              
               <

F.拿物品(贪心)

题意：对于n个物品，每个物品都有一个a值和b值，牛牛和牛可乐依次选择这n个物品，每次从剩下的里面选一个，牛牛先选，牛牛最后的权值为选择物品的a值总和，牛可乐的权值为选择的物品的b值总和，两者都希望自己的权值最大，在两者的最优选择方案下两者会如何选择

题解：贪心，两者都尽量选择a+b值大的物品，可以理解成削弱你就是增强我、

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();struct node{ int a,b,v,id;};bool cmp(node a,node b){ return a.v>b.v;}int main(){ int n; cin>>n; node a[N]; for(int i = 1; i <= n; i++){ cin>>a[i].a; } for(int i = 1; i <= n; i++){ cin>>a[i].b; a[i].v = a[i].a+a[i].b; a[i].id = i; } vector
              
                v1,v2; sort(a+1,a+n+1,cmp); for(int i = 1; i <= n; i++){ if(i&1){ v1.push_back(a[i].id); }else v2.push_back(a[i].id); } for(int i = 0; i < v1.size(); i++){ cout<
               
                <<" "; }cout<

G.判正误(hash)

题意：给定t组a，b，c，d，e，f，g，a-g的范围在int内，判断\(a^d + b^e + c^f = g\)是否成立

题解：直接计算肯定是会TLE的，这里我选择了快速幂%1e9+7这个神奇的数字居然过了，跟出题人所描述的方法不太相同，也不太理解这道题目的意义

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
               using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();const ll mod = 1e9+7;ll quick_mod(ll a,ll b){ ll ans = 1,t = a; while(b){ if(b&1==1){ ans = (ans*t)%mod; } b>>=1; t = (t*t)%mod; } return ans;}int main(){ Test{ ll a,b,c,d,e,f,g,x,y,z,ans; cin>>a>>b>>c>>d>>e>>f>>g; x = quick_mod(a,d); y = quick_mod(b,e); z = quick_mod(c,f); ans = x+y+z; if(g==ans){ cout<<"Yes"<

H.施魔法(DP)

题意：一共n个元素，第i个元素的值为ai，每次从中最少选择k个元素，费用是每次选中的元素的极差，每个元素只能选择一次，求最小花费

题解：先从小到大排序，选择方案一定是连续的一系列数，并且选择次数越多花费越小，假设将这个数列切割m次，每次切割都会使最大花费减少切割位置左右两个元素的差值，比如在i位置切割，花费会减少\(a_{i+1} - a_i\)，这样即可得到状态转移方程，dp[i] = \(max_{j\in[1,i-k]}\){dp[j]}+d[i]，dp[i]表示在位置i处切割后最多减少的花费，d[i]表示在i位置切割减少的花费，其中最大值可以在计算中维护，时间复杂度O(n)

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();int a[N],d[N],dp[N];int main(){ int n,k; cin>>n>>k; for(int i = 1; i <= n; i++){ cin>>a[i]; } sort(a+1,a+1+n); ll ans = a[n] - a[1]; int now = 0; for(int i = 1; i <= n-1; i++){ d[i] = a[i+1] - a[i]; } memset(dp,0,sizeof(dp)); int pre = 0; for(int i = k; i <= n-k; i++){ pre = max(pre,dp[i-k]); dp[i] = pre+d[i]; now = max(now, dp[i]); } cout<
              
               <

I.建通道(二进制)

题意：给定n个点，每个点都有一个权值v，两点之间建立一条路的花费为lowbit(v1\(\bigoplus\)v2)，问连通所有点的最小花费

题解：将权值相同的点去重，设去重后有m个点，接着利用&和|运算统计出所有权值中二进制中既有1又有0的位数，找到最小的二进制第k位，结果就是\(2^k*(m-1)\)

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
               using namespace std;using ll = long long;const ll N = 1e6;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();int v[N];int main(){ int v1,v0,n; cin>>n; v1 = 0x7fffffff,v0 = 0; for(int i = 1; i <= n; i++){ cin>>v[i]; v1 &= v[i]; v0 |= v[i]; } v1 ^= v0; sort(v+1,v+1+n); int m = 0; for(int i = n; i > 0; i--){ if(v[i]!=v[i+1])m++; } ll ans; for(int i = 0; i <= 30; i++){ int cur = 1<

J.求函数(线段树)

题意：有n个一次函数，第i个函数f(i) = \(k_i\)*x+\(b_i\)，有m次操作，每次操作分两种

1 i k b 将\(f_i(x)\)修改为\(f_i(x) = k*x+b\)

2 l r 求\(f_r(f_{r-1}(...f_{l+1}(f_l(1))...))\)，答案对1e9+7取模

题解：对于第二种操作所求结果可以计算为

\[\prod_{i=l}^rk_i+\sum_{i=l}^rb_i*\prod_{j=i+1}^rk_j\]

需要注意的使当j=i+1>r时按\(\prod_{j=i+1}^rk_j\) = 1计算。

那么对于上式，我们可以采用两棵线段树分别维护加号左右的两个式子，重点就是如何合并这两个区间

对于区间[l,r]，我们把它分成两部分\([l_1,r_1]\)，\([l_2,r_2]\)，令式子\(\prod_{i=l_1}^{r_1}k_i = n1\)，\(\prod_{i=l_2}^{r_2}k_i = n2\)

\(\sum_{i=l_1}^rb_i*\prod_{j=i+1}^rk_j\) = m1，\(\sum_{i=l_2}^rb_i*\prod_{j=i+1}^rk_j\) = m2，那么合并区间时，加号左边部分的合并方法就是 \(n1*n2\)，加号右侧的合并方法是\(m1*n2+m2\)，注意这些式子累加符号的上限仍然是r

代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;using ll = long long;const ll N = 2e5+5;const ll mod = 1e9+7;using pii = pair
              
               ;const double PI = acos(-1.0);#define Test ll tesnum;tesnum = read();while(tesnum--)ll read();ll st1[N<<2],st2[N<<2],k[N];void modify(int id, int l, int r, int i, int k, int b){ if(l == r){ st1[id] = k;st2[id] = b; return ; } int mid = (l+r)>>1; if(i<=mid) modify(id<<1,l,mid,i,k,b); else modify(id<<1|1,mid+1,r,i,k,b); st1[id] = (st1[id<<1]*1ll*st1[id<<1|1])%mod; st2[id] = (st2[id<<1]*1ll*st1[id<<1|1]+st2[id<<1|1])%mod;}pii merge( pii a, pii b){ return {(a.first*1ll*b.first)%mod,(a.second*1ll*b.first+b.second)%mod};}pii query(int id,int l,int r,int ql,int qr){ if(ql<=l&&r<=qr) return {st1[id],st2[id]}; int mid = (l+r)>>1; if(qr<=mid){ return query(id<<1,l,mid,ql,qr); } if(ql>mid){ return query(id<<1|1,mid+1,r,ql,qr); } return merge(query(id<<1,l,mid,ql,qr),query(id<<1|1,mid+1,r,ql,qr));}int main(){ int n,m,b; cin>>n>>m; for(int i = 1; i <= n; i++)cin>>k[i]; for(int i = 1; i <= n; i++){ cin>>b; modify(1,1,n,i,k[i],b); } while(m--){ int f; cin>>f; if(f==1){ int i,k,b; cin>>i>>k>>b; modify(1,1,n,i,k,b); }else{ int l,r; cin>>l>>r; pii ans = query(1,1,n,l,r); cout<<(ans.first+ans.second)%mod<

转载地址：https://www.cnblogs.com/cloudplankroader/p/12275042.html 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：2020牛客寒假算法基础训练营1

下一篇：codeforces-1385E(拓扑排序)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

2020牛客寒假算法基础训练营2

A.做游戏(思维)

B.排数字(思维)

C.算概率(DP)

D.数三角(极角排序)

E.做计数(完全平方数)

F.拿物品(贪心)

G.判正误(hash)

H.施魔法(DP)

I.建通道(二进制)

J.求函数(线段树)

发表评论

最新留言

关于作者

推荐文章