几道水题就不写了....
D1T1精妙证明:
把ax+by = z 的z按照模a剩余系分类
由于((a,b)=1)所以对于每个(kin[0, a)), (kcdot 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
",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
", 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
", u, i, f[i][mxsta]);
}
cout<<ans<<endl;
return 0;
}