Codeforces Beta Round #83 DIV2-白红宇

Codeforces Beta Round #83 DIV2

阅读量：5248 次

发布时间：2019-06-14

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

这一晚上。。。板子硬了点，睡的不太舒服，等会儿回宿舍补一觉~

在ID之间纠结了一阵子后，偶还是决定沿用Moon_1st这个ID，偶滴品牌不能丢了~ ^_^。

A：单纯模拟的~

B：刚开始想麻烦了，直观的想法是先排一下序，然后比较所有相邻且不同的数对，如果a(i+1)<=2*ai，那么必然输出Yes，由于(2^ai-1)^2 = 2^(2*ai)-2^(ai+1)+1，偶一直在考虑2^(ai+1)是否会对结果产生不利影响，不大容易看~但是从小case逐步增加的具体过程发现，除了ai==1的请况有影响外，其他的影响会随着ai的增大逐步递减，也就是没有影响。所以排序后直接判断相邻且不相等的数对就可以了。

C：一开始还兴冲冲地以为自己终于在正式比赛里碰到个网络流，没想到越看越不对劲，到最后正式确认是个水题~~不过孤立节点的trick需要注意一下，偶就改了一次，还好没被人cha到~

D：这个偶就木有什么发言权了，ff很快就秒掉了额。。。。偶还在纠结怎么写。。。直观的想法是sigma(C(sh-1, i)*C(sum-a[h], n-i-1)/C(sum-1,n-1)) (i=1,2,3,......,n-1)。偶还在想难道让偶用java BigDecimal么？？不太确信用C++怎么写，先看得第五题，结果还是不会啊~看完后lock了一下代码，发现某些人C题有trick，然后就开始找人cha（貌似应该说hack）。。。。越hack越起劲啦，哈哈，头一次在cf里hack，四次都命中啦~也没再干别的。赛后听方方说你边乘边除不就算出结果来了么，偶想了想也是啊~，以前自己不是经常这么干么，怎么比赛的时候忘了。。。太菜鸟~

另外，此题方方有更简洁的解法，计算补集，结果p=1-(C(sum-a[h],n-1)/C(sum,n-1)) ~~好像是这么写吧~~~ orz~~~

E：再研究一下吧~~有点想法，但怕误导他人还是别说了~~

总结了一下，怎么和上次一样又是3个啊，下次继续吧~~还好靠C的一个trick赚了400pt的外快~~偶们房一衰貌似挂了一次，但是应是靠各种challenge排到了前头。。orz各种AC神，各种cha神~~orz ff~~去吃饭去咧~~

A：

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                 #include 
                 
                   #include 
                  
                    using namespace std; #define MP(x, y) make_pair(x, y) #define FOR(i, x, y) for((i) = (x); (i) <= (y); (i)++) typedef long long llg; int main() { int a, b, ct, M = 24*60; int x1, y1, x2, y2; scanf("%d:%d", &a, &b); ct = a*60+b; while(1) { ct++; ct %= M; a = ct/60; b = ct%60; x1 = a/10; y1 = a%10; x2 = b/10; y2 = b%10; if(x1==y2 && x2==y1) { printf("%d%d:%d%d\n", x1, y1, x2, y2); break; } } return 0; }

B：

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                 #include 
                 
                   #include 
                  
                    using namespace std; #define MP(x, y) make_pair(x, y) #define FOR(i, x, y) for((i) = (x); (i) <= (y); (i)++) typedef long long llg; const int N = 100010; int n, a[N]; bool Yes(int a1, int a2) { if(a1 == 1) return false; else { if(a2 >= 2*a1) return false; else return true; } } int main() { int i; bool flag = false; scanf("%d", &n); for(i = 0; i < n; i++) scanf("%d", a+i); sort(a, a+n); for(i = 0; i < n-1; i++) if(a[i]!=a[i+1] && Yes(a[i], a[i+1])) { flag = true; break; } if(flag) printf("YES\n"); else printf("NO\n"); return 0; }

C：

View Code

#include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                 #include 
                 
                   #include 
                  
                    using namespace std; #define MP(x, y) make_pair(x, y) #define FOR(i, x, y) for((i) = (x); (i) <= (y); (i)++) typedef long long llg; const int N = 1010; const int inf = 0x7fffffff; int n, m, next[N], r[N], d[N]; struct node { int tank, tap, val; }; vector 
                   
                     g; bool cmp(const node &a, const node &b) { return a.tank < b.tank; } void deal(int u) { int i, limit = inf; node tmp; if(next[u] == 0) return; for(i = u; next[i] != 0; i = next[i]) limit = min(limit, d[i]); tmp.tank = u; tmp.tap = i; tmp.val = limit; g.push_back(tmp); } int main() { int i, a, b, c, len; memset(next, 0, sizeof(next)); memset(r, 0, sizeof(r)); scanf("%d%d", &n, &m); for(i = 0; i < m; i++) { scanf("%d%d%d", &a, &b, &c); next[a] = b; r[b] = a; d[a] = c; } g.clear(); for(i = 1; i <= n; i++) if(r[i] == 0) deal(i); sort(g.begin(), g.end(), cmp); len = g.size(); printf("%d\n", len); for(i = 0; i < len; i++) printf("%d %d %d\n", g[i].tank, g[i].tap, g[i].val); return 0; }

补一下D的代码：

#include 
     
       #include 
      
        #include 
       
         using namespace std; const int N = 1010; int n, m, h, sum, s[N]; double ans, a[105], b[105]; int main() {
    int i;     scanf("%d%d%d", &n, &m, &h);     sum = 0; for(i = 1; i <= m; i++)     {
            scanf("%d", s+i);         sum += s[i];     } if(sum < n)  printf("-1\n"); else     {
    for(i = 1; i < n; i++)         {
                a[i] = (double)(sum-s[h]-i+1);             b[i] = (double)(sum-i);         }         ans = 1.0; for(i = n-1; i > 0; i--)  ans = ans*a[i]/b[i];         printf("%.8f\n", 1.0-ans);     } return 0; }

转载于:https://www.cnblogs.com/zxndgv/archive/2011/08/24/2152553.html

你可能感兴趣的文章