NOIp'17 TG SOL

math

Prob.

给互质数对 $ a, b $，求不能被 $ ax+by (x,y \ge 0) $ 表示的最大整数。

Sol.

答案为 $ ab-a-b $，下面给出若干种证明。

1st Proof 不妨设 $ a<b $ ，则考虑模 $ a $ 剩余系。由 $ (a,b)=1 $，每一个剩余类最小可以被表示出来的数一定有形式 $ ib $，最大不可表现出来的有形式 $ ib-a $（反证易得）。由完全剩余系的互质倍仍然是原来的剩余系这一性质即 $ (0,1,\cdots,a-1)=b(0,1,\cdots,a-1)=(0,b,\cdots,(a-1)b) $，可得最大不可表现出来的数即为 $ (b-1)a-a $.

2nd Proof 令 $ ua+vb=(a,b)=1, u>0 $（可由 Bezout's Theorem 保证），则 $ ab-a-b+i \equiv (b-1+iu)a+(iv-1)b $。$ \forall i > 0,$ 可以反复操作 $ u \leftarrow u-b, v\leftarrow v+a $ 可以保证二系数均大于 $ 0 $. 当 $ i=0 $ 时易发现该式失效，此时为答案。

3rd Proof 可以考虑使用逆元代替剩余系性质进行讨论，自证不难，留作练习。

[BONUS]
参见 POI 2003 X SUM
同余最短路的构造和做法给出来了证明1的一个自然的思路。

[BONUS]
参见 1965年全俄数学奥林匹克：
如上定义，能被表示出来得数称为好的，反之为坏的。
(i) 证明存在整数 $ c $，使得整数 $ n $ 与 $ c-n $ 始终一好一坏。（这个$ c=ab-a-b $）
(ii) 坏数的数量。（答案是 $ \frac{(a-1)(b-1)}{2} $）
[TIPS] Bezout' Thm, 坐标映射。

Code

没有，滚。

complexity

Prob./Sol./Code

没有，滚。

park

Prob.

求有向图与最短路相差 $ k $ 以内的路径数计数。

Sol.

cheese

Prob./Sol./Code

没有，滚。

treasure

Prob.

定义一棵有根生成树的权值为各边权值乘以到达点的深度，最小化该权值。

Sol.

枚举新连的每一层转移。
预处理每一组点的转移，有 $ f[S][d+1]\leftarrow f[S'][d] + g[S'][S]*(d+1), S' \belong S $。
再加上枚举子集复杂度可以做到 $ O(n3^n) $。
注意预处理为什么是对的，因为新连局面倘若不全部连在最下一层则必不可能为最优情形，即已被或即将被更优情形枚举更新得到。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const int maxn = 1005, INF = 0x3f3f3f3f;
struct E{int v, n, w; }e[maxn << 1];
int h[maxn], ec = 1;
inline void add_edge(int u, int v, int w){e[ec] = (E){v, h[u], w}; h[u] = ec++;}
int f[15][4100], g[4100][4100], d[4100][15];
int main()
{
    int n, m; read(n, m);
    int u, v, w; while(m--) read(u, v, w), --u, --v, add_edge(u, v, w), add_edge(v, u, w);
    int S = 1 << n;
    memset(d, INF, sizeof d);
    for(int i = 0; i < S; ++i) for(int j = 0; j < n; ++j) if(i >> j & 1) 
        for(int l = h[j], v = e[l].v; l; l = e[l].n, v = e[l].v) if(!(i >> v & 1))
            d[i][v] = min(d[i][v], e[l].w);
    memset(g, INF, sizeof g);
    for(int i = 0; i < S; ++i)
    {
        int j = (~i) & (S - 1);
        for(int k = j; k; k = j & (k - 1))
        {
            for(int l = 0; l < n; ++l) if((k >> l & 1))
            {
                if(d[i][l] == INF){g[i][i | k] = INF; break;}
                else if(g[i][i | k] == INF) g[i][i | k] = 0;
                g[i][i | k] += d[i][l];
            }
        }
    }
    memset(f, INF, sizeof f);
    for(int i = 0; i < n; ++i) f[1][1 << i] = 0;
    for(int i = 2; i <= n; ++i) for(int j = 1; j < S; ++j) for(int T = j & (j - 1); T; T = j & (T - 1)) if(g[T][j] != INF)
        f[i][j] = min(f[i][j], f[i - 1][T] + g[T][j] * (i - 1));
    int ans = INF;
    for(int i = 1; i <= n; ++i) ans = min(ans, f[i][S - 1]);
    printf("%d\n", ans);
    return 0;
}

phalanx

Prob.

初始按顺序填一个数表。每次取出一个数，当行向左对齐，最后一列向上对齐，该数置于最后。
求每次定位的那个数是什么。

Sol.

splay.

Code

没有，滚。