wool sequence 表示一个序列中可以找到一个连续的子区间使得区间异或值为0
那么求的是不含这种情况的序列个数
题目中数据范围是，在0~2^m - 1中选n个数作为一个序列
n和m都是10^5
仔细思考一下。
第一位 有2^m-1种情况
第二位由于不能跟其一样 有2^m-2种情况
第三位由于不能跟第二位一样，并且不能跟前两位的异或值一样，有2^m-3种情况
依次类推，得到公式
(2^m-1)*(2^m-2)*...*(2^m-n)
int mod = 1000000009;int main(){ int n, m; scanf("%d%d", &n, &m); if(m < 20 && (1 << m) <= n ) { printf("0\n"); return 0; } long long ans = 1; for(int i = 0; i < m; i++) { ans = ans * 2LL % mod; } long long res = 1; for(int i = 1; i <= n; i++) { long long tmp = ans - i; if(tmp < 0) tmp += mod; res = res * tmp % mod; } printf("%I64d\n", res); return 0;}
给出一个序列a和一个数值h
将序列划分为两部分，某部分可以为空
然后f函数式这么计算
如果两个数在同个部分
f函数的值就是两个数的和
不在同部分就两个数的和加上h
求一种划分使得f函数的最大值和最小值的差值最小
有一种贪心方案，
就是f的最大值一定跟序列中最大的几个有关
最小值一定跟序列中最小的几个有关
这里我取得最小的5个和最大的5个
直接枚举放第一部分或者第二部分即可
为啥这样可以
仔细想一下。
可以发现其他的任何情形都没有这种情况下优
int n, h;struct node { int x, id;}p[111111], tmp[15];int ans[111111];bool cmp(node x, node y) { return x.x < y.x;}vectorlft, rht;int main(){ scanf("%d%d", &n, &h); for(int i = 0; i < n; i++) { scanf("%d", &p[i].x); p[i].id = i; } sort(p, p + n, cmp); int cnt = 0; if(n > 10) { for(int i = 0; i < 5; i++) tmp[cnt++] = p[i]; for(int i = n - 5; i < n; i++) tmp[cnt++] = p[i]; } else { cnt = n; for(int i = 0; i < n; i++) tmp[i] = p[i]; } int vs[12]; int d = INF; int num = 0; for(int i = 0; i < (1 << cnt); i++) { lft.clear(); rht.clear(); for(int j = 0; j < cnt; j++) { node x = tmp[j]; if((1 << j) & i) { lft.push_back(x); } else rht.push_back(x); } int mx = 0; int mi = INF; int sz1 = lft.size(); for(int j = 0; j < sz1; j++) { for(int k = j + 1; k < sz1; k++) { mx = max(mx, lft[j].x + lft[k].x); mi = min(mi, lft[j].x + lft[k].x); } } int sz2 = rht.size(); for(int j = 0; j < sz2; j++) { for(int k = j + 1; k < sz2; k++) { mx = max(mx, rht[j].x + rht[k].x); mi = min(mi, rht[j].x + rht[k].x); } } for(int j = 0; j < sz1; j++) { for(int k = 0; k < sz2; k++) { mx = max(mx, lft[j].x + rht[k].x + h); mi = min(mi, lft[j].x + rht[k].x + h); } } if(d > mx - mi) { d = mx - mi; num = 0; for(int j = 0; j < sz1; j++) vs[num++] = lft[j].id; } } printf("%d\n", d); for(int i = 0; i < n; i++) ans[i] = 2; for(int i = 0; i < num; i++) ans[vs[i]] = 1; for(int i = 0; i < n; i++) printf("%d ", ans[i]); printf("\n"); return 0;} C
一颗无根树
有向边
从树上不多于两个点出发，遍历所有的点，
问需要改变最少多少个有向边的方向
那么就是一个树dp了
枚举根作为第一个点，
然后第二个点就需要dp
从根往下遍历所有的点的话，需要修改边的方向很容易算出来，每个点访问自己所有子树需要修改的边数也很容易算
然后数组开 dp[n][2]
dp[u][0]代表从u走到根需要修改多少边
dp[u][1]表示从跟走到u需要修改多少边
struct node { int v, w; node() {} node(int _v, int _w) {v = _v; w = _w;}};vector g[3333];int ss[3333], dp[3333][2];int total;void dfs0(int u, int f, int x) { total += x; ss[u] = ss[f] + x; int sz = g[u].size(); for(int i = 0; i < sz; i++) { int v = g[u][i].v; int w = g[u][i].w; if(v == f) continue; dfs0(v, u, w); }}void dfs(int u, int f, int x) { if(f == 0) { dp[u][0] = dp[u][1] = 0; } else { dp[u][1] = dp[f][1] + x; dp[u][0] = min(dp[f][0], dp[f][1]) + !x; } int sz = g[u].size(); for(int i = 0; i < sz; i++) { int v = g[u][i].v; int w = g[u][i].w; if(v == f) continue; dfs(v, u, w); }}int n;int main(){ int u, v; scanf("%d", &n); for(int i = 1; i <= n; i++) g[i].clear(); for(int i = 1; i < n; i++) { scanf("%d%d", &u, &v); g[u].push_back(node(v, 0)); g[v].push_back(node(u, 1)); } int ans = INF; for(int i = 1; i <= n; i++) { ss[i] = 0; total = 0; dfs0(i, 0, 0); dfs(i, 0, 0); for(int j = 1; j <= n; j++) ans = min(ans, total - ss[j] + min(dp[j][0], dp[j][1])); } printf("%d\n", ans); return 0;}
D.
留坑 不会
E
看了ACMonster的才大约懂做，其实还是很模糊
有个有向图，边的长度都一样
n<=100
有个人要从起点到终点去，必须做公交
然后有若干辆公交 有各自的起点和终点
保证每秒都有一辆公交发出，意思就是那个人一到某个点就可以换乘相应的公交
然后这些公交很奇怪， 从自己的起点到终点，它会随机走一条最短路径过去
现在问，最小的（他在最坏情况下的换乘次数）
就是寻找一条线路使得他在最坏情况下换乘bus的次数最小
这个由于是求换乘次数，所以这个图就没法按dag那种dp方法
首先预处理任意两点间的最短路
然后把每个点必然经过的公交线路存下来
然后就倒着dp
从终点往起点dp
非常之暴力
令dp[i][j]表示人在点i在j车上时最小的换乘次数
但是有两种情况
一种是这个点一定在这个公交线路上
一种是这个点可能会在这个公交线路上或者就不在这个公交线路上
第一种情况是最终的合法解
第二种用来辅助第一种
然后更新的时候，对于每个点，枚举公交车，然后看这个点的邻接点，相对于这个路径是不是合法的，意思就是邻接点离该路径的终点应该是更近一步的，
即使这个点不会出现在这个公交路径上，也要更新，这是为了让那些后面的关键的点可以更新到，其实就相当于虚拟了一下，将这个公交的线路给延伸了
对于这些合法的邻接点， 选择一条最糟糕的
然后枚举换乘的时候，就必须是这个点一定在这个公交线路上， 因为换乘一定是在这些点上才能换乘，不然最糟糕的情况是等不到车的
然后如果有最优值被更新，那么整个dp再重复这个过程
int dis[111][111], dp[111][111];vectorg[111], bus[111];int bx[111], by[111], m, n, t, src, des;bool pass[111][111];int main(){ int u, v; scanf("%d%d%d%d", &n, &m, &src, &des); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i != j) dis[i][j] = INF; for(int i = 0; i < m; i++) { scanf("%d%d", &u, &v); dis[u][v] = 1; g[u].push_back(v); } for(int k = 1; k <= n; k++) { for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) if(dis[i][j] > dis[i][k] + dis[k][j]) dis[i][j] = dis[i][k] + dis[k][j]; } } m = 0; scanf("%d", &t); while(t--) { scanf("%d%d", &u, &v); if(dis[u][v] != INF) { m++; bx[m] = u; by[m] = v; } } for(int i = 1; i <= m; i++) { u = bx[i], v = by[i]; for(int j = 1; j <= n; j++) { if(dis[u][v] == dis[u][j] + dis[j][v]) pass[i][j] = 1; for(int k = 1; k <= n; k++) { if(k != j && dis[u][k] == dis[u][j] && dis[k][v] == dis[j][v]) { pass[i][j] = 0; break; } } if(pass[i][j]) bus[j].push_back(i); } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { if(i == des && pass[j][i]) dp[i][j] = 0; else dp[i][j] = INF; } } bool flag = 1; while(flag) { flag = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { int mx = -1; for(int k = 0; k < g[i].size(); k++) { v = g[i][k]; if(dis[i][by[j]] != dis[v][by[j]] + 1) continue; //if(!pass[j][i] || !pass[j][v]) continue; mx = max(mx, dp[v][j]); } if(mx != -1 && mx < dp[i][j]) { dp[i][j] = mx; flag = 1; } for(int k = 0; k < bus[i].size(); k++) { v = bus[i][k]; if(dp[i][v] + 1 < dp[i][j]) { dp[i][j] = dp[i][v] + 1; flag = 1; } } } } } int ans = INF; for(int i = 1; i <= m; i++) if(pass[i][src]) ans = min(ans, dp[src][i] + 1); if(ans == INF) ans = -1; printf("%d\n", ans); return 0;}
声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。TEL:177 7030 7066 E-MAIL:11247931@qq.com
Copyright © 2019-2024 51dongshi.com 版权所有
违法及侵权请联系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市万商天勤律师事务所王兴未律师提供法律服务
