当前位置: 首页 > news >正文

js网站开发视频教程珠海服务好的网站建设

js网站开发视频教程,珠海服务好的网站建设,中国域名网站排名,wordpress主题收费https://ac.nowcoder.com/acm/contest/11255/E 题目大意#xff1a;有n个点#xff0c;每一点有一个区间[l,r]范围的权值可能#xff0c;有n-1条边#xff0c;边上的权值为w,ww(u)^w(v),问你满足权值范围和边权值的方案数。 思路#xff1a;我们把树根的值设为0#xff…https://ac.nowcoder.com/acm/contest/11255/E 题目大意有n个点每一点有一个区间[l,r]范围的权值可能有n-1条边边上的权值为w,ww(u)^w(v),问你满足权值范围和边权值的方案数。 思路我们把树根的值设为0这样其他点的w值也随之确定然后树根的值变为a那么其他点的值也会变为w^a。根据这个性质那我们只要求出a的范围就好了即所有的区间异或对应的w值就可以求出a的范围再求出所有点a的范围的交集。对于区间异或上w值我们可以使用线段树。 我们将利用线段树 将不连续的区间分为logw段连续的区间。 做法一n*logn 使用线段树可以求出所有不合法区间的并集把不合法的区间标记为1可以没有标记过的区间说明对于这n个点这些区间都是合法的。 #include cstdio #include cstring #include string #include cmath #include iostream #include algorithm #include queue #include cstdlib #include stack #include vector #include set #include map #include bitset #include complex #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson rt1 #define rson rt1|1 #define lowbit(a) ((a)-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define sc second #define pb push_back #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pairll,ll pii; const ll mod1e97; const ll N 6e610; const double eps 1e-6; const double PIacos(-1); ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);} ll re(){ll x;scanf(%lld,x);return x;} int dx[8] {1,0,-1,0,1,1,-1,-1}, dy[8] {0,1,0,-1,1,-1,1,-1}; int n; int ch[N][2],sum[N]; bool tag[N]; vectorpii g[N]; int l[N],r[N]; int cnt1,root1; void add(int rt,int l,int r,int x,int y,int w){int lenr-l1;int l1l^(w(~(len-1)));// ~(len-1)代表求出类11000000的格式再将w前面的几位屏蔽掉在和L异或就是他们的起点了。int r1l1len-1;//l-r这个区间可以由l1-r1这个区间异或w得到if(l1xr1y) return;if(!rt) rtcnt;//动态开点if(l1y||r1x){//将其他区间的值设为1tag[rt]1;//标记该区间都是不合法的sum[rt]len;return;}if(tag[rt]) return;int mid(lr)/2;add(ch[rt][0],l,mid,x,y,w);add(ch[rt][1],mid1,r,x,y,w);if(tag[rt]) sum[rt]len;else sum[rt]sum[ch[rt][0]]sum[ch[rt][1]]; } void dfs(int u,int f,int w){add(root,0,(130)-1,l[u],r[u],w);for(pii v:g[u]){if(v.fif) continue;dfs(v.fi,u,w^(v.sc));} } void solve(){cinn;for(int i1;in;i) cinl[i]r[i];for(int i1;in;i){int u,v,w;cinuvw;g[u].pb({v,w});g[v].pb({u,w});}dfs(1,0,0);cout(130)-sum[1]\n; }int main() {iosint T1;while(T--){solve();}return 0; } 做法二n*logn*logn直接用线段求出所有合法区间最后再利用差分求区间并区间并n时该段区间合法。 #include cstdio #include cstring #include string #include cmath #include iostream #include algorithm #include queue #include cstdlib #include stack #include vector #include set #include map #include bitset #include complex #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson rt1 #define rson rt1|1 #define lowbit(a) ((a)-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define sc second #define pb push_back #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pairll,ll pii; const ll mod1e97; const ll N 1e610; const double eps 1e-6; const double PIacos(-1); ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);} ll re(){ll x;scanf(%lld,x);return x;} int dx[8] {1,0,-1,0,1,1,-1,-1}, dy[8] {0,1,0,-1,1,-1,1,-1}; int n; vectorpii g[N]; vectorpii ans; int l[N],r[N];void gao(int l,int r,int w){int lenr-l1;int l1l^(w~(len-1));ans.pb({l1,l1len-1}); } void add(int l,int r,int x,int y,int w){//线段树if(xlry){gao(l,r,w);return;}int mid(lr)1;if(xmid) add(l,mid,x,y,w);if(ymid) add(mid1,r,x,y,w); } void dfs(int u,int f,int w){add(0,(130)-1,l[u],r[u],w);for(pii v:g[u]){if(v.fif) continue;dfs(v.fi,u,w^v.sc);} }void gg(){vectorpii dp;for(pii v:ans){dp.pb({v.fi,1});dp.pb({v.sc1,-1});}sort(all(dp));int sum0;int ans0;for(int i0;idp.size();i){pii vdp[i];sumv.sc;if(sumn) ansdp[i1].fi-v.fi;}coutansendl; } void solve(){cinn;for(int i1;in;i) cinl[i]r[i];for(int i1;in;i){int u,v,w;cinuvw;g[u].pb({v,w});g[v].pb({u,w});}dfs(1,0,0);gg(); } int main() {iosint T1;while(T--){solve();}return 0; }看到群上说用trie树也可以写就去学习了一下一样的把不合法的标记了最后求出没有标记过的点数量就是答案代码有注释了 #include cstdio #include cstring #include string #include cmath #include iostream #include algorithm #include queue #include cstdlib #include stack #include vector #include set #include map #include bitset #include complex #define INF 0x3f3f3f3f3f3f3f3f #define inf 0x3f3f3f3f #define FILL(a,b) (memset(a,b,sizeof(a))) #define lson rt1 #define rson rt1|1 #define lowbit(a) ((a)-(a)) #define ios std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0); #define fi first #define sc second #define pb push_back #define all(x) (x).begin(),(x).end() using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pairll,ll pii; const ll mod1e97; const ll N 6e610; const double eps 1e-6; const double PIacos(-1); ll gcd(ll a,ll b){return !b?a:gcd(b,a%b);} ll re(){ll x;scanf(%lld,x);return x;} int dx[8] {1,0,-1,0,1,1,-1,-1}, dy[8] {0,1,0,-1,1,-1,1,-1};int n; vectorpii g[N]; int l[N],r[N]; int tag[N],ch[N][2],cnt; ll ans; int newnode(){cnt;tag[cnt]ch[cnt][0]ch[cnt][1]0;return cnt; } int add(int x,int f,int l,int r,int w){if(tag[x]2){//tag2表示01两科子树下都没有答案return tag[x];}if((r-l)((1(f1))-1)){//出现00000000~11111111的情况时因为在这个子树下现在w的所以答案都是合法的无论怎么异或都是在这个子树的所以保持该子树的状态return tag[x];}if(!ch[x][0]) ch[x][0]newnode();//动态开点if(!ch[x][1]) ch[x][1]newnode();if((l(1f))(r(1f))){//第f位相同的情况下int id(((l(1f))^(w(1f)))!0);//求出第f位的状态因为第f位相同所以只有一种状态tag[ch[x][!id]]2;//id的这个子树所有答案都是不合法的int kadd(ch[x][id],f-1,l%(1f),r%(1f),w);//遍历到下一个子树if(k2) tag[x]2;else tag[x]1;}else{//第f位不同的情况下int id((w(1f))!0);//观察w的f位情况//分割区间 第f位为0和为1的情况int k1add(ch[x][id],f-1,l%(1f),(1f)-1,w);//第f位是0的情况下int k2add(ch[x][!id],f-1,0,r%(1f),w);//第f位是1的情况下if(k12k22)tag[x]2;else if(k1!2||k2!2) tag[x]1;}return tag[x]; } void dfs(int u,int f,int w){add(1,29,l[u],r[u],w);for(pii v:g[u]){if(v.fif) continue;dfs(v.fi,u,w^v.sc);} } void gg(int x,int f){if(tag[x]0){//该子树下的答案全部是合法的ans(1ll(f1));}else if(tag[x]1){if(tag[ch[x][1]]!2) gg(ch[x][1],f-1);if(tag[ch[x][0]]!2) gg(ch[x][0],f-1);} } void solve(){cinn;for(int i1;in;i) cinl[i]r[i];for(int i1;in;i){int u,v,w;cinuvw;g[u].pb({v,w});g[v].pb({u,w});}newnode();dfs(1,0,0);gg(1,29);//递归计算统计答案coutansendl; } int main() {iosint T1;while(T--){solve();}return 0; }
http://www.huolong8.cn/news/211091/

相关文章:

  • 湖州网站开发公司锡林郭勒盟建设工程造价信息管理网站
  • 个人电影网站备案衡阳网络营销公司
  • 做托福的网站怎样重新运行wordpress
  • 建设文明网站包括19
  • asp开发网站详细步骤做设计网站的工作内容
  • 网站建设咨询什么宿州高端网站建设公司哪家好
  • 网站建设推广案例c 转网站开发
  • 网站代码怎么看网站开发 硬件环境
  • 公司企业网站设计尺寸网站建设的企业目标
  • 搜索引擎站长平台云南官网制作
  • 做网站需要了解什么漳州微信网站开发
  • 八年级信技做网站网站建设客户资源
  • 注册网站需要多少钱手机端怎么变成电脑端
  • 外国网站建设公司中国河北网站
  • 建设银行网站打不井工作室有专门的网站
  • 阿里巴巴国际站首页网站主机与服务器
  • 建立网站找什么公司狮山镇建设局网站
  • 做游戏视频网站要批证吗新闻式软文经典案例
  • 手机网站建设平台wordpress 作品主题
  • 建立门户网站多少钱无锡新区网站制作
  • 衡水做网站的地方德安县建设局网站
  • 建设vip网站相关视频下载wordpress实现翻页效果
  • 手机网站设计技巧松山湖网站建设
  • 做暖暖小视频免费网站网站建设玖金手指花总
  • 关于网站建设的调查报告做营销的一般逛哪些网站
  • 企业网站源码推荐网络营销和推广的方法
  • 长沙做网站微联讯点很好简洁大气网站模板
  • 服装购物网站排名wordpress 管理界面
  • 上海手机网站开发价格7月8月带孩子适合去哪里旅游
  • 北京 设计 网站建设自己公司内网网站和外网怎么做同步