设为首页 加入收藏

TOP

Codeforces #200(div.2) 模拟练习赛
2015-11-21 01:01:07 来源: 作者: 【 】 浏览:2
Tags:Codeforces #200 div.2 模拟 练习赛

A题:

题意:一行磁铁,同性相斥,找到这行磁铁可以分为多少块 思路:边读边计算,读到和上一次不一样的就加1(第一组数据特判) 手速题然而我没有把思路理清楚再写,比队友满了太多=_+。

代码:

#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; typedef long long int LL; const int M = 100009,INF = 0x3fffffff; int main(void) { //problem: cf#200, address: int n, y, last = -1, ans = 1; string x; cin >> n; while(n--) { cin >> x; if(x == "10") y = 10; else y = 1; if(last != -1 && y != last) ans++; last = y; } cout << ans << endl; return 0; } 
             
            
           
          
         
        
       
      
     
   

B题:

题意:给定三个原子编号(A,B,C),每个原子一个化学价表示要与其他原子相连接的化学键个数(然而图没有给好,误导了大量时间) 解法:只要知道A和B原子之间的化学键个数 x ,其它两条边的原子个数都可以用含有 x 的式子表示出来,再来检验是否满足原子价要求即可。

代码:

#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; typedef long long int LL; const int M = 100009,INF = 0x3fffffff; int main(void) { //problem:cf#200 , address: int a, b, c; cin >> a >> b >> c; bool ok = false; for(int i = 0; i <= b; i++) { if(b - i == c - (a - i)) { ok = true; cout << i << " " << b - i << " "<< a - i << endl; break; } } if(!ok) cout << "Impossible" << endl; return 0; }
             
            
           
          
         
        
       
      
     
   

C题:

题意:给定无限制个单位电阻,每一次操作可给当前电路并联或者串联一个单位电阻,求达到目标阻值(为一假分数的形式)的电阻所需要的最小操作次数。 思路:开始的想法是从一个单位电阻开始,用广度优先搜索遍历出目标解的最小次数,然而这种正向求解空间是2的指数级别大小必定爆队列或者超时。然后决定由答案开始倒着推到初始状态,显然大大减少了解空间大小。有时候从目标解出发倒着推,是非常良好的思路可以大大缩减解空间大小。下午周赛A题就用了这个思想,顺利做出。 注意:这个题中数据用的long long 然而我只是读入的两个数据用的long long 中间计算用到的数据却还是int 一直WA,细节。

代码:

#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; typedef long long int LL; const int M = 100009,INF = 0x3fffffff; LL a, b, ans; void dfs(LL x, LL y) { if(y == 0) return; ans += x / y; x %= y; swap(x, y); dfs(x, y); } int main(void) { //problem: cf#200, address: cin >> a >> b; dfs(a, b); cout << ans << endl; return 0; } 
             
            
           
          
         
        
       
      
     
   

D题:

题意:缠绕的绳子,问是否能够解开? 思路:只要两个连着的覆盖都是同样的一根线,这两个覆盖就可以直接消除。这样很容易用一个栈一边读取一边模拟实现。

代码:


#include 
   
     #include
     #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               using namespace std; typedef long long int LL; const int M = 100009,INF = 0x3fffffff; int main(void) { //problem: , address: char c; stack
              
                s; while ((c = getchar()) != '\n') { int x = (c == '+' ? 1 : -1); if(s.empty()) {s.push(x); continue;} if(x == s.top()) s.pop(); else s.push(x); } cout << (s.empty() ? "Yes" : "No") << endl; return 0; }
              
             
            
           
          
         
        
       
      
     
   

总结:代码细节把握,思维能力训练。

】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇POJ 题目1986 Distance Queries(.. 下一篇Aquarium Tank(csu1634+几何+二..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容: