codeforces-1142 (div1)

div1真难，现在就是后悔， 非常后悔

A.显然如果我们知道起点和终点是哪两个点，我们可以算出距离通过b / gcd(a,b)的方式求出需要走几步的。

并且数据范围似乎也允许我们这么做，所以直接枚举取最大小值就可以了

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 110;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
LL N,K,s,t;
LL gcd(LL a,LL b){
    return b == 0?a:gcd(b,a % b);
}
LL lcm(LL a,LL b){
    return b / gcd(a,b);
}
LL check(LL s,LL t){
    if(t < 1 || t > N * K) return -1;
    if(s < 1 || s > N * K) return -1;
    LL d = t - s;
    while(d <= 0) d += N * K;
    while(d > N * K) d -= N * K;
    return lcm(d,N * K);
}
LL solve(LL S){
    if(S > N * K || S < 1) return 1e18;
    LL ans = 1e18;
    for(int i = 0; i < N ; i ++){
        LL x = check(S,i * K + 1 + t);
        if(~x) ans = min(ans,x);
        x = check(S,(i + 1) * K + 1 - t);
        if(~x) ans = min(ans,x);
    }
    return ans;
}
LL solve2(LL S){
    if(S > N * K || S < 1) return 0;
    LL ans = 0;
    for(int i = 0; i < N ; i ++){
        LL x = check(S,i * K + 1 + t);
        if(~x) ans = max(ans,x);
        x = check(S,(i + 1) * K + 1 - t);
        if(~x) ans = max(ans,x);
    }
    return ans;
}
int main(){
    scanf("%lld%lld%lld%lld",&N,&K,&s,&t); 
    LL ans = solve(s + 1);
    ans = min(ans,solve(K + 1 - s));
    printf("%lld ",ans);
    ans = solve2(s + 1);
    ans = max(solve2(K + 1 - s),ans);
    printf("%lld",ans);
    return 0;
}
A

B.显然第一个全排列类似于题目重定义了一个全排列的顺序，那我们依照这个像字典序一样的东西，把需要查询的排列换回正常的序列。

题目就变成了区间查询一个序列内是否存在1 - N的全排列的环的问题。

事实上不难发现，每一个点如果要跳的话贪心的跳最近的下一个点是最好的，跳完整个全排列就是跳N - 1步的路程。

对于查询的预处理，想到的是预处理出一个数字r[i]表示i这个点为起点最近的终点使得之间包含一个全排列环

那么首先可以想到i点跳N - 1步的位置就是r[i],对于每个点，倍增一下就可以了，时间复杂度O(nlogn)

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,Q;
int Hash[maxn];
int b[maxn],near[maxn];
int fa[maxn],dp[maxn];
int nxt[maxn];
vector<int>Stack[maxn];
int find(int t){
    if(t == fa[t]) return t;
    return fa[t] = find(fa[t]);
}
const int SP = 20;
int pa[maxn][SP];
int r[maxn];
int main(){
    Sca3(N,M,Q);
    for(int i = 1; i <= N; i ++) Hash[read()] = i;
    for(int i = 1; i <= M; i ++) b[i] = Hash[read()];
    for(int i = M; i >= 1; i --){
        int la = b[i] + 1;
        if(la == N + 1) la = 1;
        if(!near[la]) nxt[i] = M + 1;
        else nxt[i] = near[la]; 
        near[b[i]] = i;
    }
    for(int i = 1; i <= M ; i ++) pa[i][0] = nxt[i];
    pa[M + 1][0] = M + 1;
    for(int i = 1; i < SP; i ++){
        for(int j = 1; j <= M + 1; j ++){
            pa[j][i] = pa[pa[j][i - 1]][i - 1];
        }
    }
    //cout << pa[1][0] << endl;
    N--;
    for(int i = 1; i <= M ; i ++){
        r[i] = i;
        for(int j = SP - 1; j >= 0; j --){
            if(N & (1 << j)) r[i] = pa[r[i]][j];
        }
    }
    for(int i = M - 1; i >= 1; i --) r[i] = min(r[i],r[i + 1]);
    while(Q--){
        int L,R; Sca2(L,R);
        if(R < r[L]) printf("0");
        else printf("1");
    }
    return 0;
}
B 倍增

事实上还是有O(n)的做法的，如果将每一个点往他的前驱连边，就会发现形成一颗树，节点t的答案就是往上数N个祖先。

这就可以线性做出来了。

#include <map>
#include <set>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define For(i, x, y) for(int i=x;i<=y;i++)  
#define _For(i, x, y) for(int i=x;i>=y;i--)
#define Mem(f, x) memset(f,x,sizeof(f))  
#define Sca(x) scanf("%d", &x)
#define Sca2(x,y) scanf("%d%d",&x,&y)
#define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define Scl(x) scanf("%lld",&x);  
#define Pri(x) printf("%d
", x)
#define Prl(x) printf("%lld
",x);  
#define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
#define LL long long
#define ULL unsigned long long  
#define mp make_pair
#define PII pair<int,int>
#define PIL pair<int,long long>
#define PLL pair<long long,long long>
#define pb push_back
#define fi first
#define se second 
typedef vector<int> VI;
int read(){int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){if (c == '-') f = -1;c = getchar();}
while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
const double eps = 1e-9;
const int maxn = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7; 
int N,M,Q;
int Hash[maxn];
int b[maxn],near[maxn];
int fa[maxn],dp[maxn];
int nxt[maxn];
vector<int>Stack[maxn];
int find(int t){
    if(t == fa[t]) return t;
    return fa[t] = find(fa[t]);
}
struct Edge{
    int to,next;
}edge[maxn * 2];
int head[maxn],tot;
void init(){
    for(int i = 0 ; i <= M + 1; i ++) head[i] = -1;
    tot = 0;
}
void add(int u,int v){
//    cout << u << ' ' << v << endl;
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot++;
}
int r[maxn];
int pos[maxn],dep[maxn];
void dfs(int t){
    pos[dep[t]] = t;
    if(dep[t] >= N)    r[t] = pos[dep[t] - N + 1];
    else r[t] = M + 1;
    for(int i = head[t]; ~i; i = edge[i].next){
        int v = edge[i].to; dep[v] = dep[t] + 1;
        dfs(v);
    }
}
int main(){
    Sca3(N,M,Q); init();
    for(int i = 1; i <= N; i ++) Hash[read()] = i;
    for(int i = 1; i <= M; i ++) b[i] = Hash[read()];
    for(int i = M; i >= 1; i --){
        int la = b[i] + 1;
        if(la == N + 1) la = 1;
        if(!near[la]) nxt[i] = M + 1;
        else nxt[i] = near[la]; 
        near[b[i]] = i;
    }
    for(int i = 1; i <= M ; i ++) add(nxt[i],i);
    dep[M + 1] = 0;
    dfs(M + 1);
    for(int i = M - 1; i >= 1; i --) r[i] = min(r[i],r[i + 1]);
    while(Q--){
        int L,R; Sca2(L,R);
        if(R < r[L]) printf("0");
        else printf("1");
    }
    return 0;
}
B dfs
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Hugh-Locke/p/10758519.html