NOIP2017 题解(给自己看的)

几道水题就不写了....
D1T1精妙证明:

把ax+by = z 的z按照模a剩余系分类
由于\((a,b)=1\)所以对于每个\(k\in[0, a)\), \(k\cdot b\)都在不同剩余系内!!(反证法)

那么自然最大的取不到数在(a-1)*b的剩余系内, 也就是\((a-1)*b - a = ab-a-b?\)

D1T3
orz GXZ:https://www.cnblogs.com/GXZlegend/p/7838900.html
(记忆化搜索?) https://blog.csdn.net/enjoy_pascal/article/details/78592786
70分做法显然

100分做法: 思想是把DP转移抽象为DAG
如果不是DAG: 只要可转移到终点的合法状态不在环内就可以正常dp
否则puts("-1")
p.s. 只要在topsort中环加外向树上的点(illegal points) 入度都大于0 , 所以topsort一遍就ok拉!!!

D2T2
正解\(O(3^nn^2)\)....

//这题卡常!!!
#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;
#define FI first
#define SE second
#define PB push_back
#define rep(_i, _st, _ed) for(register int _i = (_st); _i <= (_ed); ++_i)
#define per(_i, _ed, _st) for(register int _i = (_ed); _i >= (_st); --_i)
inline int read(){int ans = 0, f = 1; char c = getchar();while(c < ‘0‘ || c > ‘9‘) f = (c == ‘-‘) ? -1 : f, c = getchar();while(‘0‘ <= c && c <= ‘9‘) ans = ans*10 + c - ‘0‘, c = getchar();return ans;}

#define min(a, b) ((a) < (b)) ? (a) : (b) //注意在这个宏定义中a, b都会算两次
int f[13][10005];
int n, m, mat[15][15], log_2[10005], mincost[15];
signed main(){
    n = read(), m = read();
    rep(i, 0, n) rep(j, 0, n) mat[i][j] = 1e7;
    rep(i, 1, m){
        int u = read(), v = read(), w = read();
        u--, v--;
        mat[v][u] = mat[u][v] = min(mat[u][v], w);
    }
    
    log_2[0] = 1;
    rep(i, 1, n) log_2[(1 << i)] = i;

    int mxsta = (1 << n) - 1, ans = 1e8;
    memset(f, 0x2f, sizeof f);
    rep(u, 0, n-1) f[0][(1<<u)] = 0;//这一步非常机智, 使得程序无需枚举起始点

    rep(l, 1, n) rep(sta, 0, mxsta){
        int rev = mxsta ^ sta;

        //求补集中每个节点向原图连边的mincost
        for(int cur = rev; cur; cur -= cur&(-cur)){
            int d = log_2[cur&(-cur)];
            mincost[d] = 1e8;
            rep(j, 0, n - 1)
                //当前集合中存在j
                if(sta & (1 << j))  
                    mincost[d] = min(mincost[d], mat[d][j] * l);
        }
        //不重复枚举补集的子集
        for(int sub = rev; sub; sub = (sub-1) & rev){
            int cost = 0;//将该子集连入树中的花费(dep == l)
            
            //枚举补集的子集中的每一个元素
            for(int cur = sub; cur; cur -= cur&(-cur)){
                int d = log_2[cur&(-cur)];
                //当前元素
                cost += mincost[d];
            }
            //cout<<cost<<endl;
            f[l] [sta | sub] = min( f[l] [sta | sub], f[l-1][sta] + cost);
        }
    }


    rep(i, 0, n){
        ans = min(ans, f[i][mxsta]);
        //printf("u=%lld i=%lld ans = %lld\n", u, i, f[i][mxsta]);            
    }
    cout<<ans<<endl;
    return 0;
}

NOIP2017 题解(给自己看的)

原文：https://www.cnblogs.com/Eroad/p/9539591.html