[20151015]SCZ训练

T1：

在一个有$N(1\leq N \leq10000)$个点，$M(1\leq M\leq50000)$条边的图中，给出$K$个特殊点（$1\leq K\leq5$），要求从剩下的点中选一个点作为起点，至少经过每一个特殊点一次后回到起点，求最短距离。

Solution ：
$K!$枚举经过点的顺序，预处理出特殊点与所有点的最短距离，然后$O(N)$枚举起点即可

Code：

/*************************************************************************
    > File Name: relocation.cpp
    > Author: Archer
 ************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;

const int N = 11111;
const int M = 55555;
const int K = 10;
const int INF = 2147483647;
#define REP(i, l, r) for (int i = l; i <= r; i++)
struct E{ int to, c, nxt; }edge[M << 1];
int top = 0, last[N];
bool vis[N], shut[N];
int a[K], ans, dist[K][N], q[N << 2], n, m, k;

inline void setIO(){
    freopen("relocation.in", "r", stdin);
    freopen("relocation.out", "w", stdout);
}
inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
inline void addedge(int u, int v, int c){
    edge[++top].to = v; edge[top].c = c; edge[top].nxt = last[u]; last[u] = top;
    edge[++top].to = u; edge[top].c = c; edge[top].nxt = last[v]; last[v] = top;
}
inline void SPFA(int S, int no){
    int l, r, now; memset(vis, 0, sizeof(vis));
    REP(i, 1, n) dist[no][i] = INF;
    for (dist[no][q[l = r = 1] = S] = 0; l <= r; l++){
        now = q[l]; vis[now] = 0;
        for (int p = last[now]; p; p = edge[p].nxt)
            if (dist[no][edge[p].to] > dist[no][now] + edge[p].c){
                dist[no][edge[p].to] = dist[no][now] + edge[p].c;
                if (!vis[edge[p].to]) vis[q[++r] = edge[p].to] = 1;
            }
    }
}
inline void check(int S){
    int res = 0;
    REP(i, 1, k - 1) res += dist[q[i]][a[q[i + 1]]];
    ans = min(ans, res + dist[q[1]][S] + dist[q[k]][S]);
}
inline void dfs(int dep, int S){
    if (dep > k){check(S); return;}
    REP(i, 1, k)
        if (!vis[i]){
            vis[i] = 1; q[dep] = i;
            dfs(dep + 1, S);
            vis[i] = 0;
        }
}
int main(){
    setIO();

    n = read(); m = read(); k = read();
    REP(i, 1, k) shut[a[i] = read()] = 1;
    REP(i, 1, m){
        int u = read(), v = read(), c = read();
        addedge(u, v, c);
    }

    REP(i, 1, k) SPFA(a[i], i);
    ans = INF; memset(vis, 0, sizeof(vis));
    REP(i, 1, n) if (!shut[i]) dfs(1, i);
    printf("%d\n", ans);

    return 0;
}

T2 :

招募$n$个男的$m$个女的，每个人起初需要$10000$元，这些男女中存在朋友关系，假如在招募某个人之前已经招募了与这个人有朋友关系的人，招募费用就可以减少，减少的量为亲密度。求最少招募费用。

Solution :
显然对于一种招募顺序，有一棵生成树与之对应，我们求亲密度最大生成树，用$(n+m)*10000-W$即为答案

Code :

/*************************************************************************
    > File Name: conscription.cpp
    > Author: Archer
 ************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;

const int N = 22222;
const int M = 55555;
#define REP(i, l, r) for (int i = l; i <= r; i++)
struct E{int u, v, c;}edge[M << 1];
int m, n, r, fa[M << 1];

inline void setIO(){
    freopen("conscription.in", "r", stdin);
    freopen("conscription.out", "w", stdout);
}
inline int read(){
    int x = 0, f = 1; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}
inline bool cmp(E e1, E e2){ return e1.c > e2.c; }
inline int find(int k){ return fa[k] = fa[k] == k ? k : find(fa[k]); }
int main(){
    setIO();

    m = read(); n = read(); r = read();
    REP(i, 1, r) 
        edge[i].u = read() + 1, edge[i].v = read() + 1 + m, edge[i].c = read();
    REP(i, r + 1, r + n + m)
        edge[i].u = i, edge[i].v = n + m + 1, edge[i].c = 0;

    sort(edge + 1, edge + r + n + m, cmp);
    REP(i, 1, n + m + 1) fa[i] = i;

    int ans = 0, cnt = 0;
    REP(i, 1, r + n + m){
        if (find(edge[i].u) == find(edge[i].v)) continue;
        cnt++;
        fa[find(edge[i].u)] = find(edge[i].v);
        ans += edge[i].c;
        if (cnt == n + m) break;
    }
    printf("%d\n", (n + m) * 10000 - ans);
    return 0;
}

T3 :

求$[0,m-1](1\leq m \leq 2^{31}-1)$之间与$Z(Z\leq m)$有至少一个起始位置相同且长度为$r(r \leq 18)$的公共子串的数的个数

Solution :
数位DP。记$dp[i][j][less]$表示当前匹配到第i位，已经连续匹配了j个字符，是否卡死在上限的方案数，dfs转移。

Code :

/*************************************************************************
    > File Name: ticket.cpp
    > Author: Archer
 ************************************************************************/

#include <bits/stdc++.h>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/hash_policy.hpp>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 111;
ll dp[N][N][2], m, z, r, lenm, lenz;
char stm[N], stz[N];

inline void setIO(){
    freopen("ticket.in", "r", stdin);
    freopen("ticket.out", "w", stdout);
}
inline ll read(){
    ll x = 0ll, f = 1ll; char ch = getchar();
    while (!isdigit(ch)) {if (ch == '-') f = -1ll; ch = getchar();}
    while (isdigit(ch)) {x = x * 10ll + 1ll*(ch - '0'); ch = getchar(); }
    return x * f;
}

inline ll dfs(bool flag, int dep, int cnt){
    ll res = 0;
    if (~dp[dep][cnt][flag]) return dp[dep][cnt][flag];
    if (cnt == r){
        if (flag) return dp[dep][cnt][flag] = pow(10, lenm - dep);
        long long res = 0;
        for (int i = dep; i < lenm; i++)
                res = res * 10 + stm[i] - '0';
        return dp[dep][cnt][flag] = res + 1;
    }
    if (dep >= lenm) return 0;
    for (char c = '0'; c <= (flag ? '9' : stm[dep]); ++c){
        res += dfs(flag || c < stm[dep], dep + 1, c == stz[dep] ? cnt + 1 : 0);
    }
    return dp[dep][cnt][flag] = res;
}

int main(){
    setIO();

    int case_cnt = read();
    while (case_cnt--){
        m = read() - 1; z = read(); r = read(); 
        lenm = 0; lenz = 0;
        while (m > 0){ stm[lenm++] = (char)(m % 10ll + '0'); m /= 10ll; }
        while (z > 0){ stz[lenz++] = (char)(z % 10ll + '0'); z /= 10ll; }
        for (int i = lenz; i < lenm; i++) stz[i] = '0';
        for (int i = 0; i < lenm / 2; i++) swap(stm[i], stm[lenm - i - 1]);
        for (int i = 0; i < lenm / 2; i++) swap(stz[i], stz[lenm - i - 1]);
        memset(dp, 0xff, sizeof(dp));
        printf("%I64d\n", dfs(0, 0, 0));    
    }

    return 0;
}