Codeforces Round #305 (Div. 1) A.B.C 解题报告 - c++编程基础

TOP

Codeforces Round #305 (Div. 1) A.B.C 解题报告

2015-11-21 01:00:58 来源: 作者: 【大中小】浏览:1次

Tags：Codeforces Round #305 Div. A.B.C 解题报告

A. Mike and Frog
枚举。
先是找循环，然后很容易得出一个两元一次方程，然后可以发现解也是有循环节的，所以最小的那个肯定出现在一定范围内，否则就后面也不可能出现。假设两个变量为x,y,系数分别为z1,z2。很显然，两者的最小公倍数便是一个周期，所以如果枚举x的话，只需要枚举到z2就可以了。
细节比较多。。错了好多次。。比赛中也跪了。。
代码如下：

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include
          #include 
          
            #include 
           
             using namespace std; #define LL __int64 #define pi acos(-1.0) #define root1 0, 1000001, 1 #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 //#pragma comment(linker, "/STACK:1024000000") const int mod=1e4+7; const int INF=0x3f3f3f3f; const double eqs=1e-3; const int MAXN=600000+10; int a[MAXN], c[20], ha[MAXN], vis[MAXN]; LL Cal(int x, int f) { int i, cnt=0, tmp, tot, y, j; LL ans=0; for(i=2;i*i<=x;i++){ if(x%i==0){ while(x%i==0) x/=i; c[cnt++]=i; } } if(x!=1) c[cnt++]=x; tot=1<

B. Mike and Feet 单调栈（或者线段树）这题的大体思路很容易，就是找出每个数作为最小值的向左向右延伸的最大范围，那么这个范围之内的都有可能会以这个最小值作为最大值，于是用标记法标记前缀的最大值就可以了。然后就是找延伸的范围了。弱只想到了万能的离散化+线段树的思路。也不算很麻烦，但是复杂度略高。还有一个更简单的方法是单调栈的思路。不止复杂度低，只有O（n）,代码复杂度也低。用单调栈来保证栈内始终是递增的，所以栈底就是延伸的最大范围。在这里只贴个线段树的思路的，也是弱比赛的时候写的。话说比赛的时候因为定义了两个n。。调试了将近一个小时。。。时间全浪费在这上面了。。。。代码如下：

#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              using namespace std; #define LL __int64 #define pi acos(-1.0) #define root 0, cnt-1, 1 #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 //#pragma comment(linker, "/STACK:1024000000") const int mod=1e4+7; const int INF=0x3f3f3f3f; const double eqs=1e-3; const int MAXN=200000+10; int dp[MAXN], b[MAXN], ans[MAXN], a[MAXN], c[MAXN], cnt, fro[MAXN], last[MAXN], n; int Max[800000], Min[800000]; int BS(int x) { int low=0, high=cnt-1, mid; while(low<=high){ mid=low+high>>1; if(c[mid]==x) return mid; else if(c[mid]>x) high=mid-1; else low=mid+1; } } void PushUp(int rt) { Max[rt]=max(Max[rt<<1],Max[rt<<1|1]); Min[rt]=min(Min[rt<<1],Min[rt<<1|1]); } void Update(int p, int x, int l, int r, int rt) { if(l==r){ Max[rt]=Min[rt]=x; return ; } int mid=l+r>>1; if(p<=mid) Update(p,x,lson); else Update(p,x,rson); PushUp(rt); } int Query(int f, int ll, int rr, int l, int r, int rt) { if(ll<=l&&rr>=r){ if(f) return Max[rt]; return Min[rt]; } int mid=l+r>>1, ans; if(f) ans=-1; else ans=n; if(f){ if(ll<=mid) ans=max(ans,Query(f,ll,rr,lson)); if(rr>mid) ans=max(ans,Query(f,ll,rr,rson)); } else{ if(ll<=mid) ans=min(ans,Query(f,ll,rr,lson)); if(rr>mid) ans=min(ans,Query(f,ll,rr,rson)); } return ans; } int main() { int i, j, x; while(scanf("%d",&n)!=EOF){ for(i=0;i
             
              =0;i--){ x=BS(a[i]); if(x==0) last[i]=n; else last[i]=Query(0,0,x-1,root); Update(x,i,root); } memset(dp,0,sizeof(dp)); memset(ans,0,sizeof(ans)); int tmp; for(i=0;i
              
               =1;i--){ ans[i]=max(ans[i+1],dp[i]); } for(i=1;i<=n;i++){ printf("%d ",ans[i]); } puts(""); } return 0; }

C. Mike and Foam 状压+容斥这题只要想清楚一点就很简单了。。。就是5*10^5范围内的任意一个数的质因子的个数都不会超过6个。。只要想到了这点，就很简单了，状压一下再容斥一下乱搞搞就解决了。代码如下：

#include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include
           #include 
           
             #include 
            
              using namespace std; #define LL __int64 #define pi acos(-1.0) #define root1 0, 1000001, 1 #define lson l, mid, rt<<1 #define rson mid+1, r, rt<<1|1 //#pragma comment(linker, "/STACK:1024000000") const int mod=1e4+7; const int INF=0x3f3f3f3f; const double eqs=1e-3; const int MAXN=600000+10; int a[MAXN], c[20], ha[MAXN], vis[MAXN]; LL Cal(int x, int f) { int i, cnt=0, tmp, tot, y, j; LL ans=0; for(i=2;i*i<=x;i++){ if(x%i==0){ while(x%i==0) x/=i; c[cnt++]=i; } } if(x!=1) c[cnt++]=x; tot=1<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】
分享到:
上一篇：ZOJ 3203 Light Bulb (三分+计算..	下一篇：Codeforces 547C Mike and Foam ..

帐　　号:

密码: (新用户注册)

验证码:

表　　情:

内　　容: