组合 1001 

第一题就小难，出题的好像是浙大的大牛？

找到一个规律：a[i] = x, s[i..i+x]都想同。a[i] = a[i+1] + 1 (a[i] > 0)，否则就是与后一个颜色不同，方案*25。第一次颜色相同的26种方案。

#include 
     
      typedef long long ll;const int N = 1e5 + 5;const int MOD = 1e9 + 7;int a[N];int main() {    int T; scanf ("%d", &T);    while (T--) {        int n; scanf ("%d", &n);        for (int i=1; i
      
       =1; --i) {            if (a[i] == 0) {                ans = 1ll * ans * 25 % MOD;            } else if (a[i] != a[i+1] + 1) {                ans = 0;                break;            }        }        printf ("%d\n", ans);    }    return 0;}
      
     

最短路 1002 

多加了3条边，6个点分别看成起点跑SPFA，然后原来的距离是abs （u - v)，取最小值

#include 
     
      const int N = 1e5 + 5;const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int a[6], d[6][N], z[N];bool vis[N];std::vector
      
        G[N];int n, m;void add_edge(int u, int v) {    G[u].push_back (v);    G[v].push_back (u);}void SPFA(int k, int s) {    memset (d[k], INF, sizeof (d[k]));    memset (vis, false, sizeof (vis));    d[k][s] = 0; vis[s] = true;    std::queue
       
         que; que.push (s);    while (!que.empty ()) {        int u = que.front (); que.pop ();        for (auto v: G[u]) {            if (vis[v]) continue;            d[k][v] = d[k][u] + 1;            vis[v] = true;            que.push (v);        }    }}int main() {    int T; scanf ("%d", &T);    while (T--) {        scanf ("%d%d", &n, &m);        for (int i=1; i<=n; ++i) {            G[i].clear ();        }        for (int i=1; i
        
          v) std::swap (u, v);            int &best = z[i];            best = v - u;            for (int i=0; i<6; ++i) {                best = std::min (best, d[i][u] + d[i][v]);            }        }        int ans = 0;        for (int i=0; i
        
       
      
     

二进制 + BFS 1003 

s -> t = s ^ t = x，所以要预处理出0到x的最小步骤，翻转某一位可以转换为^ (1<<i)

#include 
     
      const int N = 30;const int MAX = (1 << 17);const int INF = 0x3f3f3f3f;const int MOD = 1e9 + 7;int a[N], d[MAX];bool vis[N];int n, m;void BFS(int s) {    std::queue
      
        que; que.push (s);    memset (d, INF, sizeof (d)); d[s] = 0;    while (!que.empty ()) {        int x = que.front (); que.pop ();        for (int i=1; i<=n; ++i) {            int y = x ^ a[i];            if (y > MAX) break;            if (d[y] < INF) continue;            d[y] = d[x] + 1;            que.push (y);        }    }}int main() {    int T; scanf ("%d", &T);    while (T--) {        scanf ("%d%d", &n, &m);        a[0] = 0;        for (int i=1; i<=n; ++i) {            scanf ("%d", a+i);        }        int k = 0;        for (int k=0; k<100; ++k) {            int x = 1 << k;            if (x > MAX) break;            a[++n] = x;        }        BFS (0);        int ans = 0;        for (int i=0; i
      
     

1004 

待补