首页 博客列表 精选博客 智能问答 chat-GPT 关于我
Codeforces Round #320 (Div. 2) [Bayan Thanks-Round]
发布日期：2021-08-24 18:36:04 浏览次数：38 分类：技术文章

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

 

数学 

分析：如果1 << k == x，那么放1个就可以了；否则还要加上差值的二进制的1的个数。

/************************************************* Author        :Running_Time* Created Time  :2015/9/16 星期三 23:13:08* File Name     :A.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int main(void) { int x; scanf ("%d", &x); int i = 1; while (i < x) { i <<= 1; } if (i == x) { printf ("%d\n", 1); } else { int ans = 1; i >>= 1; int y = x - i; while (y) { if (y & 1) ans++; y >>= 1; } printf ("%d\n", ans); } return 0;}

 

贪心 

题意：每两个人组成一个team，两人之间有一个连接的强度，问所有人连接强度最大的team组合是怎样的

分析：按照连接强度排序，因为连接强度无重复。如果该连接强度连接的两个人没有组成team，那么他们就组成team，这样的选择是连接强度最大的

总结：这题的贪心方法没想到，按照每个人能连接的人的连接强度排序WA了

/************************************************* Author        :Running_Time* Created Time  :2015/9/16 星期三 23:13:11* File Name     :B.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 8e2 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;struct Team { int u, v, w; Team (int u = 0, int v = 0, int w = 0) : u (u), v (v), w (w) {} bool operator < (const Team &r) const { return w > r.w; }}t[N*N];int ans[N];int main(void) { int n; scanf ("%d", &n); int m = n * 2; int tot = 0; for (int i=2; i<=m; ++i) { for (int x, j=1; j<=i-1; ++j) { scanf ("%d", &x); t[++tot] = Team (i, j, x); } } sort (t+1, t+1+tot); memset (ans, 0, sizeof (ans)); for (int i=1; i<=tot; ++i) { int u = t[i].u, v = t[i].v; if (!ans[u] && !ans[v]) { ans[u] = v; ans[v] = u; } } for (int i=1; i<=m; ++i) { printf ("%d%c", ans[i], i == m ? '\n' : ' '); } return 0;}

　　

二分  

题意：有一个(0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – ... - (2kx, 0) – (2kx + x, x) – 的折线，问(a, b)是否在折线上

分析：两种情况，点在某个三角形的左边：a = 2 * k * x + b，或者在右边：a  = 2 * k * x - b，满足x >= b，二分查找k

/************************************************* Author        :Running_Time* Created Time  :2015/9/16 星期三 23:13:14* File Name     :C.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 1e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int main(void) { //UNAC double a, b; scanf ("%lf%lf", &a, &b); if (a < b) puts ("-1"); else { double ans = 1e9 + 10; int l = 1, r = 1e9; while (l <= r) { int mid = (l + r) / 2; double xx = (a - b) / (double) (2 * mid); if (xx >= b) { ans = min (ans, xx); l = mid + 1; } else r = mid - 1; } l = 1, r = 1e9; while (l <= r) { int mid = (l + r) / 2; double xx = (a + b) / (double) (2 * mid); if (xx >= b) { ans = min (ans, xx); l = mid + 1; } else r = mid - 1; } printf ("%.9f\n", ans); } return 0;}

　　

贪心+位运算 

题意：可以对n个数字其中的数字*x，最多k次，问 的最大值

分析：其决定因素的是二进制的最高位，如果ai*x，那么剩下的所有x都给ai，降低复杂度使用前缀和后缀，枚举选取ai得到最大值

/************************************************* Author        :Running_Time* Created Time  :2015/9/17 星期四 17:21:00* File Name     :D.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 2e5 + 10;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;ll a[N], prefix[N], suffix[N];int main(void) { int n, k, x; scanf ("%d%d%d", &n, &k, &x); for (int i=1; i<=n; ++i) scanf ("%I64d", &a[i]); ll y = 1; for (int i=1; i<=k; ++i) y *= x; for (int i=1; i<=n; ++i) { prefix[i] = prefix[i-1] | a[i]; } for (int i=n; i>=1; --i) { suffix[i] = suffix[i+1] | a[i]; } ll ans = 0; for (int i=1; i<=n; ++i) { ans = max (ans, prefix[i-1] | (a[i] * y) | suffix[i+1]); } printf ("%I64d\n", ans); return 0;}

　　

三分||二分 

题意：n个数字，每个数字减去x，使得求最大连续子序列和最小连续子序列的绝对值的最大值最小

分析：x增加，最大连续子序列f(x)递减，最小连续子序列g(x)递增，可用三分。二分的没想明白，先放着

三分：

/************************************************* Author        :Running_Time* Created Time  :2015/9/17 星期四 17:56:57* File Name     :E.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 2e5 + 10;const double INF = 1e10;const int MOD = 1e9 + 7;double a[N], b[N];int n;double cal_max(void) { double sum = 0, mx = 0; for (int i=1; i<=n; ++i) { sum = max (sum + b[i], b[i]); if (sum > mx) mx = sum; } return mx;}double cal_min(void) { double sum = 0, mn = INF; for (int i=1; i<=n; ++i) { sum = min (sum + b[i], b[i]); if (sum < mn) mn = sum; } return mn;}double cal(double x) { for (int i=1; i<=n; ++i) b[i] = a[i] - x; return max (cal_max (), -cal_min ());}int main(void) { scanf ("%d", &n); for (int i=1; i<=n; ++i) scanf ("%lf", &a[i]); double l = -INF, r = INF; for (int i=1; i<=200; ++i) { double mid = (l + r) / 2; double lmid = (l + mid) / 2; double rmid = (r + mid) / 2; if (cal (lmid) < cal (rmid)) r = rmid; else l = lmid; } printf ("%.10f\n", cal ((l + r) / 2)); return 0;}

　　

二分：

/************************************************* Author        :Running_Time* Created Time  :2015/9/17 星期四 17:56:57* File Name     :E.cpp ************************************************/#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      using namespace std;#define lson l, mid, rt << 1#define rson mid + 1, r, rt << 1 | 1typedef long long ll;const int N = 2e5 + 10;const double INF = 1e10;const int MOD = 1e9 + 7;double a[N], b[N];int n;double cal_max(void) { double sum = 0, mx = 0; for (int i=1; i<=n; ++i) { sum = max (sum + b[i], b[i]); if (sum > mx) mx = sum; } return mx;}double cal_min(void) { double sum = 0, mn = INF; for (int i=1; i<=n; ++i) { sum = min (sum + b[i], b[i]); if (sum < mn) mn = sum; } return mn;}bool check(double x) { for (int i=1; i<=n; ++i) b[i] = a[i] - x; double A = cal_max (); double B = cal_min (); return (-B > A);}int main(void) { scanf ("%d", &n); for (int i=1; i<=n; ++i) scanf ("%lf", &a[i]); double l = -INF, r = INF; for (int i=1; i<=200; ++i) { double mid = (l + r) / 2; if (check (mid)) r = mid; else l = mid; } for (int i=1; i<=n; ++i) b[i] = a[i] - l; printf ("%.10f\n", cal_max ()); return 0;}

 

转载于:https://www.cnblogs.com/Running-Time/p/4818822.html

转载地址：https://blog.csdn.net/weixin_33831196/article/details/93263096 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：拓扑排序 Codeforces Round #290 (Div. 2) C. Fox And Names
下一篇：微信公众号环境搭建

发表评论

最新留言

很好
[***.229.124.182]2024年04月09日 08时03分16秒

关于作者

    喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！
-- 愿君每日到此一游！

推荐文章

模拟器连接端口汇总和常用ADB命令 2019-04-27
MAC地址前三位是厂家标识符（Organizationally Unique Identifier），可以从IEEE官网查询 2019-04-27
ShaderGraph使用教程与各种特效案例：Unity2020（持续更新） 2019-04-27
Unity使用ShaderGraph，设置SRP的RenderPipelineAsset后，原有材质显示紫色的问题 2019-04-27
Unity后处理（图像优化特效技术），实现影视级别的镜头效果，辅助标签：PostProcessing 2019-04-27
Unity爆炸、闪电、火焰、雷雨特效Demo 2019-04-27
使用python登录和访问Confluence 2019-04-27
Unity2020中使用MemoryProfile卡死和报错的问题 2019-04-27
Unity中加载Texture2D不断消耗内存的问题 2019-04-27
手把手教你使用Unity制作一个飞机喷射火焰尾气的粒子效果 2019-04-27
gitee使用教程，创建项目仓库并上传代码 2019-04-27
Unity3D 上传日志 2019-04-27
Unity3D 序列帧 2019-04-27
Unity3D 动态创建图集并压入精灵(NGUI) 2019-04-27
C# 将Excel转xml 2019-04-27
Unity3D log写入文件 2019-04-27
Unity3D动态创建摄像机 2019-04-27
unity 根据纪元时间(1970/1/1)转换为DateTime 2019-04-27
C# 字符串md5加密 2019-04-27
unity3D 拖拽旋转3D物体 2019-04-27
白红宇的个人博客 - 记录点点滴滴的事 - 您是第 307930260 位访客
访问时间: 2024-04-26 01:05:40 访问IP: 3.133.160.156     Copyright © 2020 - 2023 blog.css8.cn 京ICP备2021015314号-1 手机版