Mujin Programming Challenge 2017

A - Robot Racing

如果每个数都是一个一个间隔开的，那么答案是\(n!\)

考虑把一个数挪到1，第二个数挪到3，以此类推，如果不行，证明前面中有个数肯定会被选择，所以任意选一个数到终点，继续这样的操作

最后剩下的乘一个阶乘即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

    	if(c == '-') f = -1;

    	c = getchar();

    }

    while(c >= '0' && c <= '9') {

    	res = res * 10 +c - '0';

    	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

    	out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 1000000007;

int N,ans;

int x[MAXN];

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

void update(int &x,int y) {

    x = inc(x,y);

}

void Solve() {

    read(N);

    for(int i = 1 ; i <= N ; ++i) read(x[i]);

    int pre = 0;

    int cnt = 0,ans = 1;

    for(int i = 1 ; i <= N ; ++i) {

        if(x[i] > pre) {++cnt;pre += 2;}

        else ans = mul(ans,cnt + 1);

    }

    for(int i = 1 ; i <= cnt ; ++i) ans = mul(ans,i);

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

B - Row to Column

显然我们必须先恢复出一行来，然后去更新一开始没有全满的列

要么是第j列有黑格子，我们用它去恢复出第j行，要么给第j列创造一个黑格子，恢复出第j行

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 100005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

    	if(c == '-') f = -1;

    	c = getchar();

    }

    while(c >= '0' && c <= '9') {

    	res = res * 10 +c - '0';

    	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

    	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N;

char s[505][505];

int sumr[505],sumc[505];

bool vis[505];

void Solve() {

    read(N);

    bool flag = 0;

    for(int i = 1 ; i <= N ; ++i) {

        scanf("%s",s[i] + 1);

        for(int j = 1 ; j <= N ; ++j) {

            if(s[i][j] == '#') flag = 1;

        }

    }

    if(!flag) {

        puts("-1");return;

    }

    for(int i = 1 ; i <= N ; ++i) {

        for(int j = 1 ; j <= N ; ++j) {

            if(s[i][j] == '#') vis[j] = 1;

        }

    }

    int cnt = 0;

    for(int j = 1 ; j <= N ; ++j) {

        int c = 0;

        for(int i = 1 ; i <= N ; ++i) {

            c += (s[i][j] == '#');

        }

        if(c == N) ++cnt;

    }

    int ans = 2 * N;

    for(int i = 1 ; i <= N ; ++i) {

        int c = 0;

        for(int j = 1 ; j <= N ; ++j) {

            c += (s[i][j] == '.');

        }

        ans = min(ans,c + N - cnt + (vis[i] ^ 1));

    }

    out(ans);enter;

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

C - Robot and String

用处理出\(nxt(l)\)表示l之后到第几个位置能变成空

同时记录\(nxt_{a}(l),nxt_{b}(l)\)一直到z，初始时候先把s[l + 1]的数设成l + 1，然后从这个位置开始循环更新

然后我们一次询问就是不断的\(nxt(l - 1)\)嵌套，我们处理出2的次幂次操作即可

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 500005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

    	if(c == '-') f = -1;

    	c = getchar();

    }

    while(c >= '0' && c <= '9') {

    	res = res * 10 +c - '0';

    	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

    	out(x / 10);

    }

    putchar('0' + x % 10);

}

int N;

char s[MAXN];

int nxt[MAXN][27],ri[MAXN][27];

void Solve() {

    scanf("%s",s + 1);

    N = strlen(s + 1);

    for(int i = 0 ; i <= N + 1; ++i) {

        for(int j = 0 ; j <= 26 ; ++j) {

            nxt[i][j] = N + 1;

        }

    }

    for(int i = 0 ; i <= N + 1 ; ++i) {

        for(int j = 0 ; j <= 19 ; ++j) ri[i][j] = N + 1;

    }

    for(int i = N - 1 ; i >= 0 ; --i) {

        int x = s[i + 1] - 'a';

        nxt[i][x] = i + 1;

        for(int j = x + 1 ; j <= 26 ; ++j) {

            nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];

        }

        for(int j = 0 ; j < x ; ++j) {

            nxt[i][j] = nxt[nxt[i][26]][j];

        }

    }

    for(int j = 0 ; j <= 19 ; ++j) {

        for(int i = N - 1 ; i >= 0 ; --i) {

            if(j == 0) ri[i][j] = nxt[i][26];

            else ri[i][j] = ri[ri[i][j - 1]][j - 1];

        }

    }

    int Q;

    read(Q);

    int l,r;

    for(int i = 1 ; i <= Q ; ++i) {

        read(l);read(r);

        --l;

        for(int j = 19 ; j >= 0 ; --j) {

            if(ri[l][j] <= r) l = ri[l][j];

        }

        if(l == r) puts("Yes");

        else puts("No");

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

D - Oriented Tree

显然D是直径上取整

然后我们给每个点做一个标号，任取一个点\(h(v) = 0\)

如果\(u\rightarrow v\)有一条边那么\(h(v) - h(u) = 1\)

最后可以定义\(d(s,t) = (dist(s,t) + h(s) - h(t))/ 2\)

如果直径是偶数，那么可以发现

\(|h(s) - h(t)| \leq 2D - dist(s,t)\)

找到直径的中心\(r\)，距离中心距离为\(D\)的点，显然标号应该一样，假设标号都是0，我们可以得到任意一点u都有\(|h(u)| \leq D - dist(r,u)\)

这个是必要的，也是充分的，对于任意两点\(u,v\)

\(|h(u) - h(v)| \leq |h(u)| + |h(v)| \leq 2D - dist(r,u) - dist(r,v) \leq 2D - dist(u,v)\)

所以我们认为\(|h(u)| \leq D - dist(r,u)\)，做一个dp，可以得到所有解

如果直径是奇数，就有了两个中心，一个是s，一个是t

我们认为\(dist(u,s) < dist(t,u)\)的是白点，否则是黑点，那么有两种情况

如果u是白点，\(|h(u)| \leq D - 1 - dist(u,s)\)

如果u是黑点，\(|h(u)| \leq D - dist(u,t)\)

或者

u是白点，\(|h(u)| \leq D - dist(u,s)\)

u是黑点，\(|h(u)| \leq D - 1 - dist(u,t)\)

但是这两种情况有交集

就是白点的距离s最远的点全是0，另一边距离最远的全是-1，或者全是+1，这个时候我们如果所有点同时-1或者同时+1，会发现这两种情况等价但是我们重复统计了

这个时候条件是

u是白点，\(|h(u)| \leq D - dist(u,s)\)

u是黑点，\(|h(u) + 1| \leq D - dist(u,t)\)

或者是

u是白点，\(|h(u)| \leq D - dist(u,s)\)

u是黑点，\(|h(u) - 1| \leq D - dist(u,t)\)

#include <bits/stdc++.h>

#define fi first

#define se second

#define pii pair<int,int>

#define mp make_pair

#define pb push_back

#define space putchar(' ')

#define enter putchar('\n')

#define eps 1e-10

#define MAXN 1005

//#define ivorysi

using namespace std;

typedef long long int64;

typedef unsigned int u32;

typedef double db;

template<class T>

void read(T &res) {

    res = 0;T f = 1;char c = getchar();

    while(c < '0' || c > '9') {

    	if(c == '-') f = -1;

    	c = getchar();

    }

    while(c >= '0' && c <= '9') {

    	res = res * 10 +c - '0';

    	c = getchar();

    }

    res *= f;

}

template<class T>

void out(T x) {

    if(x < 0) {x = -x;putchar('-');}

    if(x >= 10) {

    	out(x / 10);

    }

    putchar('0' + x % 10);

}

const int MOD = 1000000007,V = 505;

struct node {

    int to,next;

}E[MAXN * 2];

int sumE,head[MAXN];

int N;

int dis[MAXN],fa[MAXN],D;

int dp[MAXN][MAXN * 2];

int inc(int a,int b) {

    return a + b >= MOD ? a + b - MOD : a + b;

}

int mul(int a,int b) {

    return 1LL * a * b % MOD;

}

void update(int &x,int y) {

    x = inc(x,y);

}

void add(int u,int v) {

    E[++sumE].to = v;

    E[sumE].next = head[u];

    head[u] = sumE;

}

void dfs(int u) {

    for(int i = head[u] ; i ; i = E[i].next) {

        int v = E[i].to;

        if(v != fa[u]) {

            fa[v] = u;

            dis[v] = dis[u] + 1;

            dfs(v);

        }

    }

}

void dfs1(int u,int lim,int on) {

    for(int i = head[u] ; i ; i = E[i].next) {

        int v = E[i].to;

        if(v != fa[u]) {

            dfs1(v,lim,on);

        }

    }

    int l = dis[u] - lim - on,r = lim - dis[u] - on;

    for(int i = l + V ; i <= r + V; ++i) {

        dp[u][i] = 1;

        for(int j = head[u] ; j ; j = E[j].next) {

            int v = E[j].to;

            if(v != fa[u]) {

                int t = inc(dp[v][i - 1],dp[v][i + 1]);

                dp[u][i] = mul(dp[u][i],t);

            }

        }

    }

}

int Process_even(int rt) {

    fa[rt] = 0;dis[rt] = 0;

    dfs(rt);

    memset(dp,0,sizeof(dp));

    dfs1(rt,D,0);

    int ans = 0;

    for(int i = 0 ; i <= V * 2 ; ++i) {

        update(ans,dp[rt][i]);

    }

    return ans;

}

int Process_odd(int s,int t,int on) {

    fa[s] = t;fa[t] = s;dis[s] = 0;dis[t] = 0;

    dfs(s);dfs(t);

    memset(dp,0,sizeof(dp));

    dfs1(s,D - 1,0);

    dfs1(t,D,on);

    int ans = 0;

    for(int i = 1 ; i <= V * 2 ; ++i) {

        update(ans,mul(dp[s][i],inc(dp[t][i - 1],dp[t][i + 1])));

    }

    return ans;

}

void Solve() {

    read(N);

    int a,b;

    for(int i = 1 ; i < N ; ++i) {read(a);read(b);add(a,b);add(b,a);}

    dis[1] = 0;fa[1] = 0;dfs(1);

    int u = 1;

    for(int i = 2 ; i <= N ; ++i) {

        if(dis[i] > dis[u]) u = i;

    }

    dis[u] = 0;fa[u] = 0;

    dfs(u);

    u = 1;

    for(int i = 2 ; i <= N ; ++i) {

        if(dis[i] > dis[u]) u = i;

    }

    if(dis[u] % 2 == 0) {

        int r = u;

        for(int i = 1 ; i <= dis[u] / 2 ; ++i) r = fa[r];

        D = dis[u] / 2;

        int ans = Process_even(r);

        out(ans);enter;

    }

    else {

        int s = u;

        for(int i = 1 ; i <= dis[u] / 2 ; ++i) s = fa[s];

        int t = fa[s];

        D = dis[u] / 2 + 1;

        int ans = inc(Process_odd(s,t,0),Process_odd(t,s,0));

        update(ans,MOD - Process_odd(s,t,-1));

        update(ans,MOD - Process_odd(s,t,1));

        out(ans);enter;

    }

}

int main() {

#ifdef ivorysi

    freopen("f1.in","r",stdin);

#endif

    Solve();

}

巴特西

【AtCoder】Mujin Programming Challenge 2017

Mujin Programming Challenge 2017

A - Robot Racing

B - Row to Column

C - Robot and String

D - Oriented Tree

最新文章

热门文章