Codeforces Round #549 (div.1)

codeforces

A The Beatles

题目大意：

给出一个圆，圆上一共有n*k个点，其中，在编号为k*t+1的点上有快餐店。现在有一个人一开始在编号为s的点，每次跑l km，当他再次跑回s时停止。但他忘记了s和l的值，只知道一开始距离最近的饭店的距离为a km，跑了一次（l km）后，离最近的饭店为b km。求最少跑步次数和最多跑步次数。

解题思路：

根据题目，我们可以知道，l所满足的条件分为：
l=i*k-a-b,l=i*k-a+b,l=i*k+a-b,l=i*k+a+b
我们枚举所有的l的情况，那么他们走的次数即为r=lcm(n*k，l)/l=n*k/gcd(n*k,l)。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll x,ll y)
{
    return y==0?x:gcd(y,x%y);
}
ll n,k;
ll a,b;
int main()
{
    cin >> n >> k;
    cin >> a >> b;
    ll ansmx=0;
    ll ansmn=1e10;
    for(ll i=0;i<=n;i++)
    {
        ll l,r;
        l=i*k-a-b;
        if(l>0)
        {
            r=n*k/gcd(n*k,l);
            ansmx=max(ansmx,r);
            ansmn=min(ansmn,r);
        }
        l=i*k-a+b;
        if(l>0)
        {
            r=n*k/gcd(n*k,l);
            ansmx=max(ansmx,r);
            ansmn=min(ansmn,r);
        }
        l=i*k+a-b;
        if(l>0)
        {
            r=n*k/gcd(n*k,l);
            ansmx=max(ansmx,r);
            ansmn=min(ansmn,r);
        }
        l=i*k+a+b;
        if(l>0)
        {
            r=n*k/gcd(n*k,l);
            ansmx=max(ansmx,r);
            ansmn=min(ansmn,r);
        }
    }
    cout << ansmn << " " << ansmx << endl;
    return 0;
}

B Lynyrd Skynyrd

题目大意：

给出一个长度为n的数组p和一个长度为m的数组a，对a进行q次查询，每次查询判断区间内，是否存在子序列恰好等于p的某个cyclic shifts。
cyclic shifts表示把p不断向左移动，移动出的的数放到右边。比如p为{2,1,3}，那么，我们通过移动得到的数组就有{2,1,3}，{1,3,2}，{3,2,1}

解题思路：

我们首先找到离a[i]的最近上一个数字a[j]在什么位置，使得a[j]和a[i]恰好满足p[k-1]和p[k]，我们把位置记为pre[i]。那么我们对每一个位置i进行这个查询，如果能找到，则在pre中记录离i最近的那个点。最后，通过log(n)次这样的操作，得到所有满足条件的情况。最后q次查询的时间复杂度为O(1)。    
            1      2     3       1       2       3
查询一次： -1      -1     1       2       3       4    pre[i] f[u][0]
查询二次： -1      -1    -1      -1      1       2    f[f[u][0]][0]   f[u][1]

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+7;
const int INF = 0x3f3f3f3f;
int f[MAXN][(int)log(MAXN)+5];
int pre[MAXN];
int p[MAXN],a[MAXN];
int posa[MAXN],posp[MAXN];
int ans[MAXN];
int n,m,q,k;
int findpre(int u){
    int t=n-1;
    while(t&&u){
        for(int i=k;i>=0;i--){
            if((1<<i)<=t){
                u=f[u][i];
                t-=(1<<i);
                break;
            }
        }
    }
    return u;
}
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++){
        cin>>p[i];
        posp[p[i]]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>a[i];
        posa[a[i]]=i;
    }
    for(int pj,i=1;i<=m;i++){
        pj=(posp[a[i]]-1+n-1)%n+1;
        pre[i]=posa[p[pj]];
        posa[a[i]]=i;
    }
    for(int u=1;u<=m;u++){
        f[u][0]=pre[u]<u?pre[u]:0;
    }
    k=log(n)+1;
    for(int i=1;i<=k;i++){
        for(int u=1;u<=m;u++){
            f[u][i]=f[f[u][i-1]][i-1];
        }
    }
    for(int t,u=n;u<=m;u++){
        t=findpre(u);
        ans[u]=max(t,ans[u-1]);
    }
    for(int l,r,i=1;i<=q;i++){
        cin>>l>>r;
        if(ans[r]>=l)
            cout<<"1";
        else
            cout<<"0";
    }
    cout<<endl;
    return 0;
}