2011 Asia Fuzhou Regional Contest

この2,3日セットの問題をして、2011の福州地区の試合、基本的にできる7問題をして、このセットの問題が多いと感じて、2つのアルゴリズムが混ざって、無理に1つの問題を作りました--しかもいくつかの問題がrmqを使いました.
A:暴力黒帅が歩く4つの方向を列挙して、それからすべての赤棋が攻撃できるかどうかを列挙して、細部に注意します
B:まず月餅ごとに、(m-i)*sを加えると、等差数列の影響を解消し、注文ごとに時間を処理した後、nowとnow-tの中で最小値を見つけるにはrmqを使えばいいです.それから、元の追加部分を加えるといいです.
C:各点の最も遠い点の距離を前処理して、まず直径の2点を探し出して、それから2点から探して大きい距離を記録して、それから1つの2つのポインタがrmqをプラスして、2つのポインタは毎回最大値の最小値が満たす範囲にあることを保証して、クエリはrmqを使います
E:この問題は穴がだめで、構造木は木を建てることができなくて、直接線分の木を利用して、毎回現在の区間の最も左の数字を調べて、それからkmpはマッチングの回数を求めて、問題はいくつかの再帰することができなくて、暴桟ができて、非再帰版を書いて深く探して、その上空間はコントロールして、空間も死んでしまいます
F:最小生成ツリーを求めて、重み付け値のエッジごとに、このエッジを除いて、2つの集合の最小エッジを連通することができて、このエッジと小さい最適を選択して、問題はどのように最小エッジを探すかで、私はまず1つのdfsシーケンスをして、それから1つの生成ツリーの上のエッジを列挙して、片側に対して列挙点を集合して、それからrmqで別の集合区間の最小値を尋ねて、dfsシーケンスであるため,rmqで解くことができる連続区間に肯定的である.
G:反復深さ探索枝切り、枝切り点は、現在染められる色数プラスステップ数が反復するステップ数を超えている場合は、そのままではいけません.その後、状態を1で染めた点、2で染められる点を表します.そして、毎回染めます.もし色が染められる点がなければ、下に検索しません.
H:推理＋枝切り、まずダメな状況を簡単に判断して、それから先に出して、せいぜい2人で走って、それから枝切りは、一人si>sj,ti>tjなら、iという点は無視できます.
コード:
A:

#include 
#include 
#include 
using namespace std;

const int N = 15;

int n, sx, sy, vis[N][N], g[N][N];
char c[N][2];
int x[N], y[N];

const int d1[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
const int d2[8][2] = {1, 2, -1, 2, 2, -1, 2, 1, -2, 1, -2, -1, 1, -2, -1, -2};

bool judge2(int sx, int sy) {
    for (int i = 0; i < n; i++) {
        if (c[i][0] == 'G') {
            for (int j = x[i] - 1; j >= 1; j--) {
                if (g[j][y[i]]) break;
                if (j == sx && y[i] == sy) return true;
            }
        }
        if (c[i][0] == 'R') {
            for (int k = 0; k < 4; k++) {
                int xx = x[i] + d1[k][0], yy = y[i] + d1[k][1];
                while (xx >= 1 && xx <= 10 && yy >= 1 && yy <= 9 && g[xx][yy] == 0) {
                    if (xx == sx && yy == sy) return true;
                    xx += d1[k][0];
                    yy += d1[k][1];
                }
            }
        }
        if (c[i][0] == 'C') {
            for (int k = 0; k < 4; k++) {
                int xx = x[i] + d1[k][0], yy = y[i] + d1[k][1];
                while (xx >= 1 && xx <= 10 && yy >= 1 && yy <= 9 && g[xx][yy] == 0) {
                    xx += d1[k][0];
                    yy += d1[k][1];
                }
                xx += d1[k][0]; yy += d1[k][1];
                while (xx >= 1 && xx <= 10 && yy >= 1 && yy <= 9 && g[xx][yy] == 0) {
                    if (xx == sx && yy == sy) return true;
                    xx += d1[k][0];
                    yy += d1[k][1];
                }
            }
        }
        if (c[i][0] == 'H') {
            for (int k = 0; k < 8; k++) {
                int xx = x[i], yy = y[i];
                int xxx = xx + d1[k / 2][0], yyy = yy + d1[k / 2][1];
                if (xxx >= 1 && xxx <= 10 && yyy >= 1 && yyy <= 9 && g[xxx][yyy]) continue;
                xxx = xx + d2[k][0], yyy = yy + d2[k][1];
                if (xxx >= 1 && xxx <= 10 && yyy >= 1 && yyy <= 9 && sx == xxx && sy == yyy) return true;
            }
        }
    }
    return false;
}

bool judge() {
    for (int i = 0; i < 4; i++) {
        int xx = sx + d1[i][0];
        int yy = sy + d1[i][1];
        if (xx < 1 || xx > 3 || yy < 4 || yy > 6) continue;
        int tmp = g[xx][yy];
        g[xx][yy] = 0;
        if (!judge2(xx, yy)) return false;
        g[xx][yy] = tmp;
    }
    return true;
}

int main() {
    while (~scanf("%d%d%d", &n, &sx, &sy) && n || sx || sy) {
        memset(vis, 0, sizeof(vis));
        memset(g, 0, sizeof(g));
        for (int i = 0; i < n; i++) {
            scanf("%s", c[i]);
            scanf("%d%d", &x[i], &y[i]);
            g[x[i]][y[i]] = 1;
        }
        printf("%s
", judge() ? "YES" : "NO");
    }
    return 0;
}

B:

#include 
#include 
#include 
#include 
#include 

C:

#include 
#include 
#include 
#include 
#include 
using namespace std;

const int N = 50005;
int n, m;

struct Edge {
    int v, w;
    Edge() {}
    Edge(int v, int w) {
        this->v = v;
        this->w = w;
    }
} edge[N * 2];

int head[N], nxt[N * 2], en;

void addedge(int u, int v, int w) {
    edge[en] = Edge(v, w);
    nxt[en] = head[u];
    head[u] = en++;
}

int d[N];
queue Q;

int get(int s) {
    Q.push(s);
    memset(d, -1, sizeof(d));
    d[s] = 0;
    int ans = s;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        if (d[u] > d[ans]) ans = u;
        for (int i = head[u]; i + 1; i = nxt[i]) {
            int v = edge[i].v;
            int w = edge[i].w;
            if (d[v] != -1) continue;
            d[v] = d[u] + w;
            Q.push(v);
        }
    }
    return ans;
}

int dp[N];

void gao(int s) {
    Q.push(s);
    memset(d, -1, sizeof(d));
    d[s] = 0;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        dp[u] = max(dp[u], d[u]);
        for (int i = head[u]; i + 1; i = nxt[i]) {
            int v = edge[i].v;
            int w = edge[i].w;
            if (d[v] != -1) continue;
            d[v] = d[u] + w;
            Q.push(v);
        }
    }
}

inline void scanf_(int &num)//ÎÞ¸ºÊý
{
    char in;
    while((in=getchar()) > '9' || in='0'&&in<='9')
        num*=10,num+=in-'0';
}

int rmax[N][20], rmin[N][20], rmi[N];

void rmqinit(int *A, int n) {
    rmi[0] = -1;
    for (int i = 1; i <= n; i++) {
        rmi[i] = ((i&(i - 1)) == 0) ? rmi[i - 1] + 1 : rmi[i - 1];
        rmax[i][0] = A[i];
        rmin[i][0] = A[i];
    }
    for (int j = 1; j <= rmi[n]; j++) {
        for (int i = 1; i + (1< q) l++;
                ans = max(ans, r - l + 1);
            }
            printf("%d
", ans);
        }
    }
    return 0;
}

E:

#include 
#include 
#include 
#include 
using namespace std;

const int N = 600006;
const int M = 7005;

int t, n, m, num[N], v[N];

#define lson(x) ((x<<1)+1)
#define rson(x) ((x<<1)+2)

int node[N * 4];

inline void pushup(int x) {
    node[x] = min(node[lson(x)], node[rson(x)]);
}

void build(int l, int r, int x = 0) {
    if (l == r) {
        node[x] = v[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, lson(x));
    build(mid + 1, r, rson(x));
    pushup(x);
}

int query(int l, int r, int L, int R, int x = 0) {
    if (L >= l && R <= r) return node[x];
    int mid = (L + R) / 2;
    int ans = n + 1;
    if (l <= mid) ans = min(ans, query(l, r, L, mid, lson(x)));
    if (r > mid) ans = min(ans, query(l, r, mid + 1, R, rson(x)));
    return ans;
}

int jump[M];
char str[M];

void getjump(char *str, int n) {
    jump[1] = 0;
    int j = 0;
    for (int i = 2; i <= n; i++) {
        while (j && str[i] != str[j + 1]) j = jump[j];
        if (str[i] == str[j + 1]) j++;
        jump[i] = j;
    }
}

int kmp(char *A, int n, char *B, int m) {
    int j = 0;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        while (j && A[i] != B[j + 1]) j = jump[j];
        if (A[i] == B[j + 1]) j++;
        if (j == m) {
            ans++;
            j = jump[j];
        }
    }
    return ans;
}

struct State {
    int l, r, tp;
    State() {}
    State(int l, int r, int tp) {
        this->l = l;
        this->r = r;
        this->tp = tp;
    }
} st[N];

int now, ans;

void dfs(int sl, int sr) {
    now = 0; ans = 0;
    int top = 0;
    st[++top] = State(sl, sr, 0);
    while (top) {
        int l = st[top].l, r = st[top].r, tp = st[top].tp;
        int tmp = num[query(l, r, 1, n)];
        while (now && tmp % 2 + '0' != str[now + 1]) now = jump[now];
        if (tmp % 2 + '0' == str[now + 1]) now++;
        if (now == m) {
            ans++;
            now = jump[now];
        }
        if (tp == 0) {
            if (l <= tmp - 1) {
                st[top].tp = 1;
                st[++top] = State(l, tmp - 1, 0);
            } else {
                if (tmp + 1 <= r) {
                    st[top].tp = 2;
                    st[++top] = State(tmp + 1, r, 0);
                } else top--;
            }
        } else if (tp == 1) {
            if (tmp + 1 <= r) {
                st[top].tp = 2;
                st[++top] = State(tmp + 1, r, 0);
            } else top--;
        } else top--;
    }
}

inline void scanf_(int &num)//ÎÞ¸ºÊý
{
    char in;
    while((in=getchar()) > '9' || in='0'&&in<='9')
        num*=10,num+=in-'0';
}

int main() {
    int cas = 0;
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf_(num[i]);
            v[num[i]] = i;
        }
        scanf("%s", str + 1);
        m = strlen(str + 1);
        getjump(str, m);
        build(1, n);
        dfs(1, n);
        printf("Case #%d: %d
", ++cas, ans);
    }
    return 0;
}

F:

#include 
#include 
#include 
#include 
using namespace std;

const int N = 3005;
const int INF = 0x3f3f3f3f;

int n, m, g[N][N], g2[N][N];

struct Edge {
    int u, v;
    Edge() {}
    Edge(int u, int v) {
        this->u = u;
        this->v = v;
    }
} edge[N];

int d[N], fa[N];
bool vis[N];
bool isprim[N][N];
int val[N][N];

vector G[N];

int prim() {
    memset(isprim, false, sizeof(isprim));
    memset(vis, false, sizeof(vis));
    vis[1] = true;
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        d[i] = g[1][i];
        fa[i] = 1;
        G[i].clear();
    }
    for (int i = 1; i <= n - 1; i++) {
        int Min = INF, pos;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && d[j] < Min) {
                Min = d[j];
                pos = j;
            }
        }
        if (Min == INF) return INF;
        ans += Min;
        vis[pos] = true;
        edge[i] = Edge(fa[pos], pos);
        G[pos].push_back(fa[pos]);
        G[fa[pos]].push_back(pos);
        isprim[pos][fa[pos]] = isprim[fa[pos]][pos] = true;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && g[pos][j] < d[j]) {
                d[j] = g[pos][j];
                fa[j] = pos;
            }
        }
    }
    return ans;
}

int left[N], right[N], idx;

void dfs(int u, int fa) {
    left[u] = ++idx;
    for (int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if (v == fa) continue;
        dfs(v, u);
    }
    right[u] = idx;
}

int rmin[N][20], rmi[N];

void rmqinit(int *A, int n) {
    rmi[0] = -1;
    for (int i = 1; i <= n; i++) {
        rmi[i] = ((i&(i - 1)) == 0) ? rmi[i - 1] + 1 : rmi[i - 1];
        rmin[i][0] = A[i];
    }
    for (int j = 1; j <= rmi[n]; j++)
        for (int i = 1; i + (1< r) return INF;
    int k = rmi[r - l + 1];
    return min(rmin[l][k], rmin[r - (1< '9' || in < '0') && in != '-');
    if(in == '-') {
        neg = true;
        while((in = getchar()) >'9' || in < '0');
    }
    num = in - '0';
    while(in = getchar(), in >= '0' && in <= '9')
        num *= 10, num += in -'0';
    if(neg)
        num = 0 - num;
}

int main() {
    while (~scanf("%d%d", &n, &m) && n || m) {
        int u, v, w;
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++) {
                g[i][j] = g[j][i] = INF;
                val[i][j] = val[j][i] = INF;
            }
        for (int i = 1; i <= m; i++) {
            scanf_(u); scanf_(v); scanf_(w);
            u++; v++;
            g[u][v] = g[v][u] = w;
        }
        int tmp = prim();
        idx = 0;
        dfs(1, 0);
        for (int i = 1; i <= n - 1; i++)
            if (left[edge[i].u] < left[edge[i].v]) swap(edge[i].u, edge[i].v);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                g2[left[i]][left[j]] = g2[left[j]][left[i]] = g[i][j];
            }
        }
        for (int i = 1; i <= n; i++) {
            rmqinit(g2[i], n);
            for (int j = 1; j <= n - 1; j++) {
                int u = edge[j].u, v = edge[j].v;
                if (left[u] < i && i <= right[u]) {
                    val[u][v] = val[v][u] = min(val[u][v], min(rmqmin(1, left[u] - 1), rmqmin(right[u] + 1, n)));
                } else if (left[u] == i) {
                    if (left[v] >= 1 && left[v] <= left[u] - 1) {
                        val[u][v] = val[v][u] = min(val[u][v], min(rmqmin(1, left[v] - 1), rmqmin(left[v] + 1, left[u] - 1)));
                        val[u][v] = val[v][u] = min(val[u][v], rmqmin(right[u] + 1, n));
                    }
                    if (left[v] >= right[u] + 1 && left[v] <= n) {
                        val[u][v] = val[v][u] = min(val[u][v], rmqmin(1, left[u] - 1));
                        val[u][v] = val[v][u] = min(val[u][v], min(rmqmin(right[u] + 1, left[v] - 1), rmqmin(left[v] + 1, n)));
                    }
                }
            }
        }
        int q;
        scanf("%d", &q);
        double sum = 0;
        for (int i = 0; i < q; i++) {
            scanf("%d%d%d", &u, &v, &w);
            u++; v++;
            if (isprim[u][v] == 0) sum += tmp * 1.0;
            else sum += (tmp - g[u][v] + min(val[u][v], w)) * 1.0;
        }
        printf("%.4f
", sum / q);
    }
    return 0;
}

G:

#include 
#include 
#include 
using namespace std;

const int N = 10;

int n, g[N][N], vis[N][N], d;

int bitcount(int x) {
    return x == 0 ? 0 : bitcount(x>>1) + (x&1);
}

int f() {
    int col = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (vis[i][j] == 1) continue;
            col |= (1<= n || yy < 0 || yy >= n || vis[xx][yy] == 1) continue;
        vis[xx][yy] = 2;
        if (g[xx][yy] == col) fuck(xx, yy, col);
    }
}

int gao(int col) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (g[i][j] != col) continue;
            if (vis[i][j] == 2) {
                fuck(i, j, col);
                cnt++;
            }
        }
    }
    return cnt;
}

bool dfs(int h) {
    if (h == d) return f() == 0;
    if (h + f() > d) return false;
    int tmp[N][N];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            tmp[i][j] = vis[i][j];
    for (int i = 0; i <= 5; i++) {
        if (gao(i) == 0) continue;
        if (dfs(h + 1)) return true;
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                vis[j][k] = tmp[j][k];
    }
    return false;
}

int main() {
    while (~scanf("%d", &n) && n) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &g[i][j]);
                vis[i][j] = 0;
            }
        }
        d = 0;
        fuck(0, 0, g[0][0]);
        while (true) {
            if (dfs(0)) break;
            d++;
        }
        printf("%d
", d);
    }
    return 0;
}

H:

#include 
#include 
#include 
using namespace std;

const int N = 10005;

typedef long long ll;

void scanf_(int &num)
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in'9' || in='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}

void scanf_ll(ll &num)
{
    char in;
    bool neg=false;
    while(((in=getchar()) > '9' || in'9' || in='0'&&in<='9')
        num*=10,num+=in-'0';
    if(neg)
        num=0-num;
}

struct Mem {
    ll s, t;
    void read() {
        scanf_ll(s);
        scanf_ll(t);
    }
} mem[N];

bool cmp(Mem a, Mem b) {
    if (a.t != b.t) return a.t < b.t;
    return a.s < b.s;
}

int t, n;
ll d, l, w;

bool judge() {
    l -= d * n;
    if (l < 0) return false;
    for (int i = 0; i < n; i++) w -= mem[i].s * d;
    if (w < 0) return false;
    for (int i = 0; i < n; i++) if (mem[i].s * l <= w) return true;
    return false;
}

double cal(Mem a, Mem b) {
    if (a.t > b.t) swap(a, b);
    if (a.s * l <= w) return a.t * l;
    if (b.s * l > w) return 1e20;
    double x = (w - b.s * l) * 1.0 / (a.s - b.s);
    return a.t * x * 1.0 + b.t * 1.0 * (l * 1.0 - x);
}

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf_(n); scanf_ll(d);
        scanf_ll(l); scanf_ll(w);
        for (int i = 0; i < n; i++) mem[i].read();
        if (!judge())
            printf("No solution
");
        else {
            double ans = 1e20;
            sort(mem, mem + n, cmp);
            int sn = 0;
            ll r = 100005;
            double tmp = 0;
            for (int i = 0; i < n; i++) {
                tmp += mem[i].t * d * 1.0;
                if (mem[i].s * l <= w) ans = min(ans, mem[i].t * l * 1.0);
                if (mem[i].s >= r) continue;
                r = min(mem[i].s, r);
                mem[sn++] = mem[i];
            }
            for (int i = 0; i < sn; i++) {
                for (int j = i + 1; j < sn; j++) {
                    ans = min(ans, cal(mem[i], mem[j]));
                }
            }
            printf("%.2f
", ans + tmp);
        }
    }
    return 0;
}