NOIP2017 题解(给自己看的) --有坑要填

D1T1精妙证明:
D1T3
D2T2

几道水题就不写了....

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拉!!!

这道题卡常丧心病狂...

这个程序会re(60分)...不敢开longlong... 求dalao debug..

#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;}

const int maxn = 1e5+5, maxm = 3e5+5, mxk = 51;

int n, m, p;

//邻接表

struct graph{

    int v, w, nxt;

}edge[maxm];

int head[maxn];

void adde(int u, int v, int w){

    static int cnt = 0;

    edge[++cnt].v = v;

    edge[cnt].w = w;

    edge[cnt].nxt = head[u];

    head[u] = cnt;

}

//精简dijstra

priority_queue<pii> pq;

int dis[maxn]; bool vis[maxn];

void dijstra(){

    memset(dis, 0x3f, sizeof dis);

    memset(vis, 0, sizeof vis);

    dis[1] = 0;

    pq.push(make_pair(0, 1));

    while(!pq.empty()){

        int u = pq.top().second; pq.pop();

        if(vis[u]) continue;

        vis[u] = 1;

        for(int e = head[u]; e; e = edge[e].nxt){

            int v = edge[e].v, w = edge[e].w;

            if(dis[u] + w < dis[v]) {

                dis[v] = dis[u] + w;

                pq.push(make_pair(-dis[v], v));

            }

        }

    }

}

int T, k; 

const int mxhsh = maxn*mxk;

int f[mxhsh], ind[mxhsh], le[mxhsh], ri[mxhsh], cnt, pt[mxhsh], q[mxhsh];

#define hsh(_k, _u) ((_k)*n + _u)

#define mod(_cur) if(_cur > p) _cur -= p;

signed main(){

    T = read();

    while(T--){

        n = read(), m = read(), k = read(), p = read();

        memset(head, 0, sizeof head), memset(edge, 0, sizeof edge);

        rep(i, 1, m){

            int u = read(), v = read(), w = read();

            adde(u, v, w);

        }

		dijstra();

        //构建状态转移图 (该题中为一种扩展最短路图)

        cnt = 1; memset(ind, 0, sizeof ind);

        rep(u, 1, n) rep(x, 0, k){

            le[hsh(x, u)] = cnt;

            for(int e = head[u]; e; e = edge[e].nxt){

                int v = edge[e].v, w = edge[e].w, x2;

                x2 = dis[u] + w - dis[v] + x;

                if(x2 > k || x2 < 0) continue;

                ++ind[hsh(x2, v)];

				//printf("u=%d v=%d w=%d, fr = %d to = %d, ind = %d\n",u, v, w,  hsh(x, u), hsh(x2, v), ind[hsh(x2, v)]);

                pt[cnt++] = hsh(x2, v);

            }

            ri[hsh(x, u)] = cnt - 1;

        }

        //拓扑排序 + 状态转移

        memset(f, 0, sizeof f);

        f[hsh(0, 1)] = 1;

        int fr = 1, bk = 0;

        rep(i, 1, hsh(k, n)) if(!ind[i]) q[++bk] = i;//这句必须有！！常数再大也要加！！！

        while(bk >= fr){

            int u = q[fr++];

            rep(i, le[u], ri[u]){

                int v = pt[i];

                f[v] += f[u]; mod(f[v]);

                if( (--ind[v]) == 0) q[++bk] = v;

            }

        }

        //统计答案

        int infini = 0, ans = 0;

        rep(x, 0, k){

            if(ind[hsh(x, n)]) infini = 1;

            ans += f[hsh(x, n)]; mod(ans);

        }

        if(infini) puts("-1");

        else printf("%d\n", ans);

    }

    return 0;

}

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 题解(给自己看的) --有坑要填

D1T1精妙证明:

D1T3

D2T2

最新文章

热门文章