Codeforces Round #305 (Div. 1) A && B

冷不防 2022-08-05 00:55 195阅读 0赞

## 547A - Mike and Frog ##

先考虑，从h1\->a1的过程，计算需要的时间  
如果在M次内，没有到达则不可到达  
然后再判断是否符合h2\->a2的时间

如果还是不行就进行周期考虑，假设h1已经变成了a1，h2变成了xxx  
计算从a1\->a1的时间（假设为c），然后通过以下的方式  
假设g(x) = Xh2 \+ Y，然后f(x) = g(g(...(g(x)))) (c次)。

c = 1, d = 0
    for i = 1 to c
         c = (cX) % p
         d = (dX + Y) % p
    Then,
    f(x)
         return (cx + d) % p

然后找到从a1\->a1且xxx\->a2的周期  
如果在迭代M次之后还没有找到，则不可到达

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    
    typedef long long ll;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    #define MID(x,y) (x+((y-x)>>1))
    #define speed std::ios::sync_with_stdio(false);
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    ll M;
    ll H1, A1, X1, Y1;
    ll H2, A2, X2, Y2;
    
    int main()
    {
        read(M);
        read(H1),read(A1),read(X1),read(Y1);
        read(H2),read(A2),read(X2),read(Y2);
        ll i;
        for(i=1; i<=M; i++)
        {
            H1=(H1*X1+Y1)%M;
            if(H1==A1)
                break;
        }
        if(i>M)
        {
            printf("-1\n");
            return 0;
        }
        for(int j=0; j<i; j++)
            H2=(H2*X2+Y2)%M;
        if(H2==A2)
        {
            printf("%d\n",i);
            return 0;
        }
        ll X3=1, Y3=0;
        ll j;
        for(j=1; j<=M; j++)
        {
            H1=(H1*X1+Y1)%M;
            ll X4=X2*X3%M, Y4=(X2*Y3+Y2)%M;
            X3=X4;
            Y3=Y4;
            if(H1==A1)
                break;
        }
        if(j>M)
        {
            printf("-1\n");
            return 0;
        }
        for(ll k=1; k<=M; k++)
        {
            H2=(H2*X3+Y3)%M;
            if(H2==A2)
            {
                write(i+j*k),putchar('\n');
                return 0;
            }
        }
        printf("-1\n");
        return 0;
    }

## 547B - Mike and Feet ##

方法很多，我用了一个很傻逼很麻烦很慢的方法  
题目需要找长度为x的区间中最小值的最大值  
则我们按照数的大小进行排序，然后用set维护较小的数的位置，从而能够找到每个数影响到的区间，  
然后维护一个区间最大值的线段树，区间是指长度

// whn6325689
    // Mr.Phoebe
    // http://blog.csdn.net/u013007900
    #include <algorithm>
    #include <iostream>
    #include <iomanip>
    #include <cstring>
    #include <climits>
    #include <complex>
    #include <fstream>
    #include <cassert>
    #include <cstdio>
    #include <bitset>
    #include <vector>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <ctime>
    #include <set>
    #include <map>
    #include <cmath>
    #include <functional>
    #include <numeric>
    #pragma comment(linker, "/STACK:1024000000,1024000000")
    
    
    using namespace std;
    
    typedef long long ll;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef complex<ld> point;
    typedef pair<int, int> pii;
    typedef pair<pii, int> piii;
    typedef vector<int> vi;
    
    #define CLR(x,y) memset(x,y,sizeof(x))
    #define mp(x,y) make_pair(x,y)
    #define pb(x) push_back(x)
    #define lowbit(x) (x&(-x))
    #define MID(x,y) (x+((y-x)>>1))
    #define speed std::ios::sync_with_stdio(false);
    #define eps 1e-9
    #define PI acos(-1.0)
    #define INF 0x3f3f3f3f
    #define LLINF 1LL<<62
    
    template<class T>
    inline bool read(T &n)
    {
        T x = 0, tmp = 1;
        char c = getchar();
        while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();
        if(c == EOF) return false;
        if(c == '-') c = getchar(), tmp = -1;
        while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();
        n = x*tmp;
        return true;
    }
    template <class T>
    inline void write(T n)
    {
        if(n < 0)
        {
            putchar('-');
            n = -n;
        }
        int len = 0,data[20];
        while(n)
        {
            data[len++] = n%10;
            n /= 10;
        }
        if(!len) data[len++] = 0;
        while(len--) putchar(data[len]+48);
    }
    //-----------------------------------
    
    #define ls idx<<1
    #define rs idx<<1|1
    const int MAXN=200010;
    
    struct Tree
    {
        int l,r;
        int maxx,lab;
    }t[MAXN<<2];
    
    void build(int idx,int l,int r)
    {
        t[idx].maxx=t[idx].lab=0;
        t[idx].l=l;t[idx].r=r;
        if(l==r)    return;
        int mid=MID(l,r);
        build(ls,l,mid);
        build(rs,mid+1,r);
    }
    
    void update(int idx,int l,int r,int v)
    {
        if(t[idx].l==l && r==t[idx].r)
        {
            t[idx].lab=t[idx].maxx=v;
            return;
        }
        if(t[idx].lab)
        {
            t[ls].maxx=t[ls].lab=t[rs].maxx=t[rs].lab=t[idx].lab;
            t[idx].lab=0;
        }
        int mid=MID(t[idx].l,t[idx].r);
        if(l>mid)
            update(rs,l,r,v);
        else if(r<=mid)
            update(ls,l,r,v);
        else
        {
            update(ls,l,mid,v);update(rs,mid+1,r,v);
        }
    }
    
    int query(int idx,int x)
    {
        if(t[idx].l==t[idx].r)
        {
            return t[idx].maxx;
        }
        if(t[idx].lab)
        {
            t[ls].maxx=t[ls].lab=t[rs].maxx=t[rs].lab=t[idx].lab;
            t[idx].lab=0;
        }
        int mid=MID(t[idx].l,t[idx].r);
        if(x>mid)
            return query(rs,x);
        else
            return query(ls,x);
    }
    
    int n;
    set<int> st;
    set<int>::iterator it;
    
    struct Node
    {
        int num,id;
        bool operator < (const Node& b) const
        {
            return num<b.num;
        }
    }a[MAXN];
    
    int main()
    {
        read(n);
        build(1,1,n);
        for(int i=1;i<=n;i++)
        {
            read(a[i].num);
            a[i].id=i;
        }
        sort(a+1,a+n+1);
        st.insert(0);st.insert(n+1);
        for(int i=1,l,r;i<=n;i++)
        {
            it=st.lower_bound(a[i].id);
            r=*it;l=*(--it);
            if(r-l-1>=1)
                update(1,1,r-l-1,a[i].num);
            st.insert(a[i].id);
        }
        for(int i=1;i<=n;i++)
            write(query(1,i)),putchar(' ');
        putchar('\n');
        return 0;
    }