首页 > 代码库 > HDU5845 Best Division
HDU5845 Best Division
递归写法,好久不写很容易就gg了...
dp[i]=max(dp[j])+1,并且s[i]XORs[j]<=x
01字典树优化一下转移。
![技术分享](/d/file/p/2024/07/04/de81369d012be1946270c873f0eb8afa.gif)
1 #include <bits/stdc++.h> 2 #define ll long long 3 using namespace std; 4 5 const int maxn = 1e5+5; 6 ll a[maxn], s[maxn], f[maxn]; 7 int X, L; 8 struct T{ 9 int node[maxn][2];10 int val[maxn];11 ll dp[maxn];12 int tot;13 void init(){14 node[1][0] = node[1][1] = val[1] = 0;15 dp[1] = -1e9;16 tot = 2;17 }18 int newnode(){19 node[tot][0] = node[tot][1] = val[tot] = 0;20 dp[tot] = -1e9;21 return tot++;22 }23 ll query(int x, int now = 1, int dep = 30){24 if(dep == -1)25 return dp[now];26 ll ret = -1e9;27 int tmp = (X>>dep)&1, tt = (x>>dep)&1;28 if(tmp){29 if(node[now][tt]) ret = max(ret, dp[ node[now][tt] ]);30 if( node[now][!((x>>dep)&1)] ) ret = max(ret, query(x, node[now][!((x>>dep)&1)], dep-1));31 return ret;32 }33 if(node[now][tt])34 return query(x, node[now][tt], dep-1);35 return ret;36 }37 void add(int x, int d, ll v, int now = 1, int dep = 30){38 if(dep == -1){39 val[now] += d;40 if(d > 0)41 dp[now] = max(dp[now], v);42 else if(dp[now] <= v)43 dp[now] = -1e9;44 return ;45 }46 int tmp = (x>>dep)&1;47 if(node[now][tmp] == 0)48 node[now][tmp] = newnode();49 add(x, d, v, node[now][tmp], dep-1);50 val[now] += d;51 dp[now] = -1e9;52 if(node[now][0]&&val[ node[now][0] ]) dp[now] = max(dp[now], dp[ node[now][0] ]);53 if(node[now][1]&&val[ node[now][1] ]) dp[now] = max(dp[now], dp[ node[now][1] ]);54 }55 };56 T Tree;57 int main(){58 ios::sync_with_stdio(false);59 int T; cin >> T;60 ll n, p, q;61 while(T--){62 cin >> n >> X >> L;63 cin >> a[1] >> p >> q;64 s[1] = a[1];65 for(int i = 2; i <= n; i++)66 a[i] = (a[i-1]*p+q)%268435456, s[i] = a[i]^s[i-1];67 68 Tree.init();69 Tree.add(s[0], 1, f[0]);70 int i = 1;71 for( ; i <= n&&i <= L; i++){72 f[i] = Tree.query(s[i])+1;73 Tree.add(s[i], 1, f[i]);74 }75 for( ; i <= n; i++){76 Tree.add(s[i-L-1], -1, f[i-L-1]);77 f[i] = Tree.query(s[i])+1;78 Tree.add(s[i], 1, f[i]);79 }80 cout << max(f[n], 0LL)<< endl;81 }82 return 0;83 }
HDU5845 Best Division
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。