程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces Round #305 (Div. 1) A.B.C 解題報告

Codeforces Round #305 (Div. 1) A.B.C 解題報告

編輯：C++入門知識

Codeforces Round #305 (Div. 1) 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<