写网站建设的论文,网站如何引入流量,wordpress更新ftp,域名续费价格“钉耙编程(2)1001 | hdu7287#xff1a;Alice Game Alice 和 Bob玩游戏#xff0c;给定 n n n和 k k k#xff0c;初始有 n n n个石头排成一排#xff0c;两人轮流执行以下操作#xff1a; 选择一段个数 ≤ k \le k ≤k的石头#xff0c;直接拿掉选择一段个数 (2)1001 | hdu7287Alice Game Alice 和 Bob玩游戏给定 n n n和 k k k初始有 n n n个石头排成一排两人轮流执行以下操作 选择一段个数 ≤ k \le k ≤k的石头直接拿掉选择一段个数 k 1 k1 k1的石头拿走里面连续的 k k k个要求拿完之后这一段石头变成了两段 先无法操作者输。 SG函数的题好在还没忘记
根据SG的原理可以知道
首先 S G [ 0 ] 0 SG[0] 0 SG[0]0。
接下来小于 k k k的 S G [ 1... k ] 1 SG[1...k]1 SG[1...k]1。
由于 k 1 k1 k1无法操作 S G [ k 1 ] 0 SG[k1]0 SG[k1]0。
对于 k 1 k1 k1有 S G [ x ] m e x i 1 x − k − 1 ( S G [ i ] ⊕ S G [ x − k − i ] ) SG[x] mex_{i1}^{x-k-1}(SG[i] \oplus SG[x - k - i]) SG[x]mexi1x−k−1(SG[i]⊕SG[x−k−i])
然后打标找规律会发现符合 S G [ x ] 0 SG[x]0 SG[x]0的 x x x是一个等差数列公差为 4 k 2 4k2 4k2
“钉耙编程”(2)1005 | hdu7291Or 给出长度为 n n n的数组 a i a_i ai和 b i b_i bi。现在有 m m m组询问 [ l , r ] [l, r] [l,r]需要计算 ⨁ i l r ⨁ j i r ( a i ∑ k i 1 j b k ) \bigoplus_{il}^{r}\bigoplus_{ji}^r(a_i\sum_{ki1}^{j}b_k) il⨁rji⨁r(aiki1∑jbk) (这里的⊕ 表示OR操作) 数据范围 1 ≤ n ≤ 1 0 5 , 1 ≤ m ≤ 1 0 6 1\le n \le 10^5,1\le m\le 10^6 1≤n≤105,1≤m≤106 这题十分滴复杂。参考题解的思路来做
如果定下了一个 r r r不断将 l l l左移那么会增加一些新的数这些数是 a l , a l b l 1 , a l b l 1 b l 2 , ⋯ , a l b l 1 , a l b l 2 ⋯ b r a_l, a_lb_{l1},a_{l}b_{l1}b_{l2},\cdots,a_{l}b_{l1},a_{l}b_{l2}\cdotsb_{r} al,albl1,albl1bl2,⋯,albl1,albl2⋯br。我们知道题目中两个或与枚举全部数或一起是一样的就是看某一个二进制位在这些数中是不是有 1 1 1。解决或问题的入手点是找到某一个二进制位下最早出现 1 1 1的位置即可。在代码中用 n x t nxt nxt数组表示这里给出代码中 n x t nxt nxt的定义 n x t [ i ] [ o ] nxt[i][o] nxt[i][o]表示第 i i i个位置开始往后在第 o o o个二进制位上第一个出现 1 1 1的位置。
所以只要求出了 n x t nxt nxt就可以从 [ n , n ] [n,n] [n,n]开始逐渐向头扩张每次扩展加入 n x t [ l ] [ . ] nxt[l][.] nxt[l][.]的信息用树状数组维护。这个时候如果维护到了 [ l , n ] [l,n] [l,n]的信息做一个query(r)就可以得到 [ l , r ] [l, r] [l,r]之间的答案了。
现在难点是求nxt。
用前缀和可以改写式子为 a l s r − s l a_ls_r-s_l alsr−sl进一步做一个分组 ( a l − s l ) s r (a_l-s_l)s_r (al−sl)sr。然后就可以按照“套路”来做题了。
如果 y ≥ 0 y\ge 0 y≥0不妨记 x s r , y s l − a l xs_r,\, y s_l-a_l xsr,ysl−al接下来考虑 x − y x-y x−y的情况。目标是判断第 k k k位(这里第 k k k位从 0 0 0开始数)是不是 1 1 1。首先 x , y x,y x,y需要对 2 k 2^k 2k取模。如果 x x x的第 k k k位是 1 1 1 x ≥ y x\ge y x≥y且 y y y的第 k k k位是 0 0 0或者 x y xy xy且 y y y的第 k k k位是 1 1 1。如果 x x x的第 k k k位是 0 0 0要求 x ≥ y x\ge y x≥y且 y y y的第 k k k位是 1 1 1或者 x y xy xy且 y y y的第 k k k位是 0 0 0。整理一下现在需要当 y y y的第 k k k位是 0 0 0时需要在 x ≥ y x\ge y x≥y中找第 k k k位是 1 1 1的 x x x或者在 x y xy xy中找第 k k k位是 0 0 0的 x x x。如果 y y y的第 k k k为是 1 1 1也类似。
后来悟了上面说的太具体了其实就是当考虑第 k k k位时先看看第 k k k位之后的数(即对 2 k 2^k 2k取模)谁大 y y y大则表示需要向第 k k k位借位 y y y小则不用。如果需要借位则要求 x x x的第 k k k位是 0 0 0 y y y是 0 0 0。类似这样推理下去。
如果 y 0 y0 y0记 x s r , y − s l a l xs_r,\, y -s_la_l xsr,y−slal接下来考虑 x y xy xy的情况。借用上面的思路对 2 k 1 2^{k1} 2k1取模如果 2 k ≤ x y 2 k 1 2^k\le xy 2^{k1} 2k≤xy2k1或者 x y ≥ 2 k 1 2 k xy\ge 2^{k1}2^k xy≥2k12k则 x y xy xy的第 k k k位有 1 1 1。(很明显的有 2 k 2^k 2k就是第 k k k位上有 1 1 1嘛)
上面这两种情况都可以用线段树维护每一位都做三棵线段树都是求的区间最小值。
时间复杂度是 O ( n log 2 n m log n ) \mathcal{O}( n\log^2 nm\log n) O(nlog2nmlogn)
#include bits/stdc.h
//#define rt root, 0, L
#define ltree lc[x], l, mid
#define rtree rc[x], mid 1, r
using namespace std;
//typedef long long ll;
const int N 1e5 10, M 1e6 10;
const int L 1e9; // 设定线段树的上限
const int INF 1e9;int n, m;
int a[N], b[N], s[N];
int nxt[N][30];int ans[M];
vectorpairint, int Q[N]; // 记录、整理询问区间namespace calc_ans
{ const int base 233;const int p 998244353;inline int add(int x, int y) { return (x y) p ? x - p : x; } inline int mul(int x, int y) { return 1ll * x * y % p; }int calc() {int res 0, t 1; for (int i 1; i m; i){t mul(t, base);res add(res, mul(t, ans[i]));}return res;}
}struct SegmentTree
{int rt;int top, lc[N * 30], rc[N * 30], mn[N * 30]; // 动态开点void init(){rt top 0;mn[0] INF;}void change(int x, int l, int r, int p, int v){if(!x){x top;lc[x] rc[x] 0;mn[x] INF;}if(l r) return mn[x] min(mn[x], v), void();int mid l r 1;if(p mid) change(ltree, p, v);else change(rtree, p, v);mn[x] min(mn[lc[x]], mn[rc[x]]);}//int query(int x, int l, int r, int ql, int qr) debug没有去除掉非法情况(e.g. ql, qr -2, 0)//{// if(!x) return INF;// if(l ql r qr) return mn[x];// int mid l r 1;// if(qr mid) return query(ltree, ql, qr);// else if(mid ql) return query(rtree, ql, qr);// else return min(query(ltree, ql, mid), query(rtree, mid 1, qr));//}int query(int x, int l, int r, int ql, int qr){if(l qr || r ql || !x) return INF;if(ql l r qr) return mn[x];int mid l r 1;return min(query(lc[x], l, mid, ql, qr), query(rc[x], mid 1, r, ql, qr));}
}T[2], S;// 求最终答案部分
int Bit[N];
inline int lowbit(int x) { return x -x; }
void add(int x, int v)
{for(int i x; i n; i lowbit(i)) Bit[i] | v;
}
int query(int x)
{int ret 0;for(int i x; i 1; i - lowbit(i)) ret | Bit[i];return ret;
}void solve()
{scanf(%d%d, n, m);for(int i 1; i n; i) scanf(%d, a[i]);for(int i 1; i n; i){scanf(%d, b[i]);s[i] s[i - 1] b[i];}for(int o 0; o 30; o){T[0].init();T[1].init();S.init();for(int i n; i 1; i--){int d s[i] o 1; // s[i]第o位的值是几int v1 s[i] (1 o) - 1; // s[i]对2^o取模int v2 s[i] (1 o 1) - 1; // s[i]对2^(o1)取模T[d].change(T[d].rt, 0, L, v1, i);S.change(S.rt, 0, L, v2, i);if(s[i] a[i]){int d (s[i] - a[i]) o 1; // s[i]-a[i]的第o位int v (s[i] - a[i]) ((1 o) - 1); // 对2^o取模nxt[i][o] min(T[d].query(T[d].rt, 0, L, 0, v - 1), T[d ^ 1].query(T[d ^ 1].rt, 0, L, v, L));}else // s[i] a[i]{int v (a[i] - s[i]) ((1 o 1) - 1);nxt[i][o] min(S.query(S.rt, 0, L, (1 o) - v, (1 o 1) - v - 1),S.query(S.rt, 0, L, (1 o) (1 o 1) - v, L));}}}for(int i 1; i m; i){int l, r;scanf(%d%d, l, r);Q[l].push_back({r, i});}for(int l n; l 1; l--){for(int o 0; o 30; o)if(nxt[l][o] ! INF) add(nxt[l][o], 1 o);for(auto q : Q[l]) ans[q.second] query(q.first);}printf(%d\n, calc_ans::calc());for(int i 1; i n; i) Q[i].clear(), Bit[i] 0;
}int main()
{int T;scanf(%d, T);while(T--) solve();
}“钉耙编程(2)1010 | hdu7296Klee likes making friends 可莉找朋友有 n n n个朋友找每一个朋友需要花费 a [ i ] a[i] a[i]的代价。由于可莉是一个乐于交友的人在任意 m m m个连续的人中至少要有 2 2 2个可莉的朋友。请给出最少代价。 ( 2 ≤ n ≤ 20000 , 2 ≤ m ≤ 2000 , m ≤ n ) (2 \le n \le 20000, 2 \le m \le 2000, m \le n ) (2≤n≤20000,2≤m≤2000,m≤n) 算法是DP应该不难看出
状态设 f [ i ] [ j ] f[i][j] f[i][j]最后两个朋友是 i i i和 j j j时的最小代价则有转移方程: f [ j ] [ k ] min k − m 1 ≤ i ≤ j − 1 f [ i ] [ j ] a [ k ] f[j][k] \min_{k-m1\le i\le j-1}{f[i][j]a[k]} f[j][k]k−m1≤i≤j−1minf[i][j]a[k]
挺显然的目标就是让i最后三个朋友 i , j , k i, j, k i,j,k的分布能满足题意
接下里考虑时间复杂度如果直接枚举转移会产生 O ( n m ∗ m ) \mathcal{O}(nm*m) O(nm∗m)的复杂度。 n m nm nm是状态量 m m m是每个状态转移的复杂度。显然时间复杂度是不可接受的我们需要优化转移的时间复杂度
转移的过程中我们需要找到一个在区间范围内的i让f[i][j]最小。i和k之间的变化是一个线性变化所以可以很轻松的记录一个区间的最小值来解决这个问题。
留意到空间要开 O ( n 2 ) \mathcal{O}(n^2) O(n2)太大了但实际上用到的f只有 O ( m 2 ) \mathcal{O}(m^2) O(m2)所以不妨让i和j都对m取模做一个循环。
#include bits/stdc.h
using namespace std;
typedef long long ll;
const int N 2e4 10, M 2e3 10;
const ll INF 1e18;int n, m;
ll a[N], f[M][M];void solve()
{scanf(%d%d, n, m);for(int i 1; i n; i){scanf(%lld, a[i]);}for(int i 1; i m; i)f[0][i] a[i];for(int j 1; j n; j){ll mn INF;int i j; // debug i j - 1 初始未导入for(int k min(n, j m - 1); k j; k--){while(i 0 k - i m) {i--;mn min(mn, f[i % m][j % m]);// printf(%d %d\n, i, mn);}f[j % m][k % m] mn a[k]; // debug 忘记加a[k]// printf(%d %d %d\n, j, k, mn);}}ll ans INF;for(int i n - m 1; i n; i)for(int j i 1; j n; j)ans min(ans, f[i % m][j % m]);printf(%lld\n, ans);
}int main()
{int T;scanf(%d, T);while(T--) solve();
}
