热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

2017.11.26【清华集训2017】模拟

T15483.【清华集训2017模拟11.26】简单路径T25484.【清华集训2017模拟11.26】快乐树T35485.【清华集训2017模拟11.26】字符串T1结论题,结论很

T1 5483. 【清华集训2017模拟11.26】简单路径
T2 5484. 【清华集训2017模拟11.26】快乐树
T3 5485. 【清华集训2017模拟11.26】字符串

T1 结论题,结论很显然任意两条路径权异或后,会将两条路径的交的贡献删去。
然后用个桶存一下出现过的异或和,暴力判一下就可以了

code

 1 #include
 2 #include
 3 #include
 4 #include
 5 #define fo(i,a,b) for(int i=a;i<=b;i++)
 6 #define fd(i,a,b) for(int i=a;i>=b;i--)
 7 #define fh(i,x) for(int i=head[x];i;i=next[i])
 8 typedef long long LL;
 9 using namespace std;
10 inline int max(int x,int y) {return (xy:x;}
11 inline int min(int x,int y) {return (xx:y;}
12 inline int read() {
13     int x=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9') f=(ch=='-')?-1:f,ch=getchar();
15     while(ch>='0'&&ch<='9') x=x*10+(ch-'0'),ch=getchar();return f*x;
16 }
17 const int N=1e3+100;
18 struct node {
19     int _lca,v;
20     node() {}
21     node(int a,int b):_lca(a),v(b) {}
22 };
23 struct node1 {
24     int val,u,v,_lca;
25     node1() {}
26     node1(int _val,int _u,int _v,int l):val(_val),u(_u),v(_v),_lca(l){}
27 }to1[N*N],g[N*N];
28 int to[N],w[N],next[N],head[N],tot,cnt,mx;
29 int tot1,next1[N*N],head1[N*N],fa[N],ans;
30 int dep[N],go[N][20],gw[N][20],n,x;
31 void add(int x,int y,int ww) {to[++tot]=y,w[tot]=ww,next[tot]=head[x],head[x]=tot;}
32 void add1(int val,int u,int v,int _lca) {to1[++tot1]=node1(val,u,v,_lca),next1[tot1]=head1[val],head1[val]=tot1;}
33 void dfs(int x) {
34     fh(i,x) {
35         dep[to[i]]=dep[x]+1,go[to[i]][0]=x,gw[to[i]][0]=w[i];
36         dfs(to[i]);
37     }
38 }
39 void init_lca() {
40     dep[0]=1,dfs(0);
41     fo(i,1,17) fo(j,0,n-1) go[j][i]=go[go[j][i-1]][i-1],gw[j][i]=gw[j][i-1]^gw[go[j][i-1]][i-1];
42 }
43 node lca(int a,int b) {
44     if(dep[a]>dep[b]) swap(a,b);
45     int f=dep[b]-dep[a],z=0;
46     fo(i,0,17) if(f&(1<go[b][i];
47     if(a==b) return node(a,z);
48     fo(i,0,17) {
49         if(go[a][i]!=go[b][i]) z^=gw[a][i]^gw[b][i],a=go[a][i],b=go[b][i];
50     }
51     return node(go[a][0],z^gw[a][0]^gw[b][0]);
52 }
53 int main() {
54     n=read();
55     fo(i,1,n-1) fa[i]=read();
56     fo(i,1,n-1) x=read(),add(fa[i],i,x);
57     init_lca();
58     fo(i,0,n-1) {
59         fo(j,i+1,n-1) {
60             node tmp=lca(i,j);
61             add1(tmp.v,i,j,tmp._lca);
62             g[++cnt]=node1(tmp.v,i,j,tmp._lca);
63             mx=max(mx,tmp.v);
64         }
65     }
66     fd(i,2048,mx) {
67         fo(j,1,cnt) {
68             if(!head1[i^g[j].val])continue;
69             else {
70                     printf("%d\n",i);return 0;
71             }
72         }
73     }
74     printf("%d\n",max(mx,ans));
75     return 0;
76 }

 

T2 算是一道dp题吧?有一个结论:“0”的影响范围一定是包括0的联通块。
先做一遍不考虑有“0”的dp,f[x]表示以x为子树的最优解。
然后g[x]表示x在“0”的联通块里,则g[x]=Σmax(f[son1],g[son1])
ans=max(f[0],g[0]);

Code

 1 #include
 2 #include
 3 #include
 4 #include
 5 #define fo(i,a,b) for(int i=a;i<=b;i++)
 6 #define fd(i,a,b) for(int i=a;i>=b;i--)
 7 #define fh(i,x) for(int i=head[x];i;i=next[i])
 8 typedef long long LL;
 9 using namespace std;
10 inline int max(int x,int y) {return (xy:x;}
11 inline int min(int x,int y) {return (xx:y;}
12 inline int read() {
13     int x=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9') f=(ch=='-')?-1:f,ch=getchar();
15     while(ch>='0'&&ch<='9') x=x*10+(ch-'0'),ch=getchar();return f*x;
16 }
17 const int N=1e3+50;
18 int f[N],g[N],val[N],n,fa[N];
19 int to[N],next[N],head[N],tot;
20 void add(int x,int y) {to[++tot]=y,next[tot]=head[x],head[x]=tot;}
21 void dfs(int x) {
22     f[x]=val[x];
23     fh(i,x) dfs(to[i]);
24     fh(i,x) f[x]+=max(f[to[i]],0);
25 }
26 void dp(int x) {
27     fh(i,x) dp(to[i]);
28     fh(i,x) g[x]+=max(f[to[i]],g[to[i]]);
29 }
30 int main() {
31     n=read();
32     fo(i,1,n-1) fa[i]=read(),add(fa[i],i);
33     fo(i,0,n-1) val[i]=read();
34     dfs(0),dp(0);
35     printf("%d\n",max(f[0],g[0]));
36     return 0;
37 }

 

T3 
显然dp,设dp[i][j],i表示做到了第i位,且当前贡献为k'+j的最小分段数。
可以O(26)转移方程预处理出在i点的右推贡献,贪心转移。

Code

 1 #include
 2 #include
 3 #include
 4 #include
 5 #define fo(i,a,b) for(int i=a;i<=b;i++)
 6 #define fd(i,a,b) for(int i=a;i>=b;i--)
 7 #define fh(i,x) for(int i=head[x];i;i=next[i])
 8 typedef long long LL;
 9 using namespace std;
10 inline int max(int x,int y) {return (xy:x;}
11 inline int min(int x,int y) {return (xx:y;}
12 inline int read() {
13     int x=0,f=1;char ch=getchar();
14     while(ch<'0'||ch>'9') f=(ch=='-')?-1:f,ch=getchar();
15     while(ch>='0'&&ch<='9') x=x*10+(ch-'0'),ch=getchar();return f*x;
16 }
17 const int N=1e5+50,inf=0x3f3f3f3f;
18 char s[N];
19 int g[N][27],b[27],cnt[N][27],f[N][27],l,r,n,m,now;
20 int main() {
21     //freopen("c.in","r",stdin),freopen("c.out","w",stdout);
22     n=read(),m=read();
23     scanf("%s",s+1);
24     fo(i,1,n) cnt[i][s[i]-'a']++;
25     fo(j,0,25) fo(i,1,n) cnt[i][j]+=cnt[i-1][j];
26     fo(j,1,26) g[0][j]=1;
27     fo(i,1,n) {
28         int t=s[i]-'a';
29         fo(j,1,26) b[j]=n+1;
30         fo(j,1,26) {
31             if(cnt[i-1][t]-cnt[g[i-1][j]-1][t]==0) b[j+1]=min(b[j+1],g[i-1][j]);
32             else b[j]=min(b[j],g[i-1][j]);
33         }
34         b[1]=min(b[1],i);
35         fo(j,1,26) g[i][j]=b[j];
36     }
37     fo(i,0,27) f[1][i]=1;
38     fo(i,2,n) {
39         fo(j,0,26) f[i][j]=n+1;
40         fo(j,0,26) {
41             fo(t,1,26) {
42                 l=g[i][t],l--;
43                 (t==1)?r=i:r=g[i][t-1];
44                 r--;
45                 fo(st,0,j+1-t) f[i][j]=min(f[i][j],f[l][st]+1);
46             }
47         }
48         if(i1,26) f[i][j]=min(f[i][j],f[i][j-1]);
49     }
50     fd(j,26,0) {
51         if(f[n][j]<=m) now=j;
52         else break;
53     }
54     printf("%d\n",m+now);
55 }

 


推荐阅读
  • [Offer收割]编程竞赛第8轮 A 小Ho的完美主义倾向
    题目链接:小Ho的完美主义倾向题目描述:小Ho在一条直线型的街道上漫步。这条街道由若干块长度为L的石板铺设而成,因此每隔L的距离就会出现一道石板间的接缝。小Ho对这些规律排列的接缝产生了浓厚的兴趣,他决定研究如何在这条街道上行走,以满足自己对完美路径的追求。本题要求在给定的约束条件下,计算出小Ho能够实现其目标的所有可能方案数。 ... [详细]
  • 经过两天的努力,终于成功解决了半平面交模板题POJ3335的问题。原来是在`OnLeft`函数中漏掉了关键的等于号。通过这次训练,不仅加深了对半平面交算法的理解,还提升了调试和代码实现的能力。未来将继续深入研究计算几何的其他核心问题,进一步巩固和拓展相关知识。 ... [详细]
  • 本文介绍如何使用线段树解决洛谷 P1531 我讨厌它问题,重点在于单点更新和区间查询最大值。 ... [详细]
  • 题目要求维护一个数列,并支持两种操作:一是查询操作,语法为QL,用于查询数列末尾L个数中的最大值;二是更新操作,用于修改数列中的某个元素。本文通过ST表(Sparse Table)优化查询效率,确保在O(1)时间内完成查询,同时保持较低的预处理时间复杂度。 ... [详细]
  • Codeforces 1065D 解题心得与代码实现分析 ... [详细]
  • 数据结构第三章,栈、队列、数组,期末不挂科指南,第3篇
    数据结构第三章,栈、队列、数组,期末不挂科指南,第3篇,Go语言社区,Golang程序员人脉社 ... [详细]
  • WinMain 函数详解及示例
    本文详细介绍了 WinMain 函数的参数及其用途,并提供了一个具体的示例代码来解析 WinMain 函数的实现。 ... [详细]
  • [转]doc,ppt,xls文件格式转PDF格式http:blog.csdn.netlee353086articledetails7920355确实好用。需要注意的是#import ... [详细]
  • poj 3352 Road Construction ... [详细]
  • 开机自启动的几种方式
    0x01快速自启动目录快速启动目录自启动方式源于Windows中的一个目录,这个目录一般叫启动或者Startup。位于该目录下的PE文件会在开机后进行自启动 ... [详细]
  • 本文介绍了 NOI Open Judge 6049 购书问题的详细解法,代码简洁易懂,并附有详细的注释和解释。 ... [详细]
  • 本文节选自《NLTK基础教程——用NLTK和Python库构建机器学习应用》一书的第1章第1.2节,作者Nitin Hardeniya。本文将带领读者快速了解Python的基础知识,为后续的机器学习应用打下坚实的基础。 ... [详细]
  • 本文详细介绍了Java反射机制的基本概念、获取Class对象的方法、反射的主要功能及其在实际开发中的应用。通过具体示例,帮助读者更好地理解和使用Java反射。 ... [详细]
  • 题目链接:http://codeforces.com/gym/101190/attachments题意:在一个共享三轮车站点,某些用户需要租用车辆。该问题涉及如何通过离线查询和排序优化策略来高效地管理和分配车辆资源。具体来说,需要设计一种算法,在满足所有用户需求的同时,最小化总等待时间和资源浪费。通过合理的数据结构和算法优化,可以显著提高系统的整体性能和用户体验。 ... [详细]
  • 在牛客2021多校竞赛的一道题目中,涉及了5000×5000×5000的复杂度计算。实验结果显示,使用bitset进行数据处理仅需140毫秒,而使用bool数组则显著较慢。本文通过详细的性能分析,探讨了bitset与bool在数据处理速度上的差异,并提出了针对不同应用场景的优化建议。具体来说,bitset在位级操作上具有更高的效率,适用于大规模数据处理任务,而bool数组则在某些特定场景下更为灵活。通过对这两种数据结构的深入对比,本文旨在为开发者提供选择合适数据结构的参考依据。 ... [详细]
author-avatar
三个人999
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有