【Codeforces Round #430 (Div. 2) A C D三个题】

时间:2023-12-24 17:29:25

·不论难度,A,C,D自己都有收获!

[A. Kirill And The Game]

·全是英文题,述大意:

   给出两组区间端点:l,r,x,y和一个k。(都是正整数,保证区间不为空),询问是否在[x,y]区间内存在一个整数p,使得p*k属于[l,r],如果存在,则输出'YES',否则输出'NO'。(1<=l,r,x,y<=107)

·分析:

    首先看见了107,发现可以直接O(n)暴力枚举:枚举区间[x,y]的所有数,判断它与k的乘积是否在[l,r]中就可以了。从容AC:

 #include<stdio.h>
#include<iostream>
#define ll long long
#define go(i,a,b) for(int i=a;i<=b;i++)
ll l,r,x,y,k,L,R;bool can=;
int main()
{
std::cin>>l>>r>>x>>y>>k;
go(i,x,y)if(i*k<=r&&i*k>=l)can=;
puts(can?"YES":"NO");
return ;
}//Paul_Guderian

    其实在这之前大米饼首先想到的是O(1)的思路,即:利用[x,y]和k形成区间[x*k,y*k],然后判断该区间是否和[l,r]有交集。然后就笨笨地WA了。原因是这里只有整数点,新区间相邻点之间的间隔是k,可能[l,r]就夹在相邻两点之间并不接触两点,这样是NO而不是YES。例子如下:

【Codeforces Round #430 (Div. 2) A C D三个题】

     和它相似,只不过输出YES的例子就是这样:

【Codeforces Round #430 (Div. 2) A C D三个题】

观察两种情况的差异,我们找出第一个比l大的点p1,再找出第一个比r小的点p2(点就是满足[x*k,y*k]又是k的倍数的点),我们可以发现第一幅图中位置p1>p2,第二幅图中p1<p2,所以将其作为判断依据就可以了,总体思路就是:判断区间[p1,p2]是否为空,是否和[x,y]有交集,这其实是上文WA方法的倒过来同时统一单位的改进版。

#include<cmath>
#include<stdio.h>
#include<iostream>
#define go(i,a,b) for(int i=a;i<=b;i++)
long long l,r,x,y,k,L,R;bool can=;
int main()
{
std::cin>>x>>y>>l>>r>>k;
L=ceil(1.0*x/k);R=floor(1.0*y/k);
if(L<=R&&!(R<l||L>r))can=;
puts(can?"YES":"NO");return ;
}//Paul_Guderian

[C. Ilya And The Tree]

·述大意;
     给出一棵树,共有n个结点(1<=n<=200000),并且输入每个点的点权w(1<=w<=200000)。每一个点有一个美丽值,计算方法是它到根节点的路径(包括它)的点权值的GCD。要求按1~n输出每个点的美丽值。但是有两个条件:①可以将路径上一个点的权值修改为0。②每个点求解独立(就是说求完一个点,树又恢复原样)。

·分析:

     值得注意的是求解独立,然后只能修改一个点的权值为0。

     求所有节点的GCD?我们脑袋里可能会浮现这样的图:

【Codeforces Round #430 (Div. 2) A C D三个题】

    当然,白色的点表示我们将它变成0了(对于任意正整数a,GCD(a,0)=a)。这样看来我们要在这其中找到最优的GCD值。写DP难以转移,而且也不符合DP的要求。从数据范围来看,是可以使用"暴力"的方法求解的:

     对于每个点,我们都记录图中的所有情况GCD值,然后找到最大值就可以了,然而怎么找到个节点的所有情况——可以从它的父节点那里索取,即将父节点的每条情况链加入一个u,另一种是删掉当前的u(看图中一层一层的关系就可以了,这方法在代码中也很清晰)。

     具体的写法,网上多用set,大米饼用的是sort+unique,使用unique是因为不去重是会恰好MLE的。

     代码来啦:

 #include<stdio.h>
#include<vector>
#include<algorithm>
#define _ (ans[u]=max(ans[u],t))
#define go(i,a,b) for(int i=a;i<=b;i++)
#define fo(i,a,x) for(int i=a[x],v=e[i].v;i;i=e[i].next,v=e[i].v)
using namespace std;const int N=;
struct E{int v,next;}e[N*];vector<int>S[N];
int n,a[N],head[N],k=,t,ans[N];
int Gcd(int a,int b){if(a)while(a^=b^=a^=b%=a);return b;}
void ADD(int u,int v){e[k]=(E){v,head[u]};head[u]=k++;}
void Dfs(int u,int fa,int GCD)
{
if(S[fa].size())go(i,,S[fa].size()-)
S[u].push_back(t=Gcd(a[u],S[fa][i])),_;
S[u].push_back(t=GCD),_;GCD=Gcd(GCD,a[u]);t=GCD,_;
sort(S[u].begin(),S[u].end());
S[u].erase(unique(S[u].begin(),S[u].end()),S[u].end());
fo(i,head,u)if(v!=fa)Dfs(v,u,GCD);
}
int main()
{
scanf("%d",&n);
go(i,,n)scanf("%d",a+i);
go(i,,n){int u,v;scanf("%d%d",&u,&v);ADD(u,v);ADD(v,u);}
Dfs(,,);go(i,,n)printf("%d ",ans[i]);return ;
}//Paul_Guderian

[D. Vitya and Strange Lesson]

·述大意:

     输入n个数ai和m个询问(1<=n,m<=300000,0<=ai<=300000),每个询问输入x,表示将所有数异或x后,求n个数的Mex(异或结果对后来的询问依旧有效)。

·分析:

     先说网络上常用的一个解法吧——Mex一出现,或许考虑Trie树。

由于log2300000约等于18.2,所以我们构建一个深度为20的01字典树。所谓01字典树,就是只有左右儿子分别表示01的字典树。并且从根结点到叶子结点是二进制从高位到低为排的。那么字典树的所有叶子结点可以表示1~219的所有整数。首先不考虑异或的情况,我们将一些数字按照二进制形式从高位(20位)到低位插入字典树,怎样快速得到Mex?由于数字的存在在树上体现为叶子结点的存在,如果前缀为000000000000000001_ _的数字都存在(即4,5,6,7都存在),在树上的表现为某一个子树是"饱满的"(可以理解最底层所有叶子结点都存在)。那么我们要找的答案肯定是在一颗不饱满的子树中,这个呢,可以拿一个4层的缩小版01字典树来加以说明:如果是饱满的树,应该长这个样子:

【Codeforces Round #430 (Div. 2) A C D三个题】

·这样就很清晰,那么某子树不饱满是啥?是这个样子:

【Codeforces Round #430 (Div. 2) A C D三个题】

·很明显我们要求的Mex值为12,但是为了方便查找,我们不妨将不饱满状态向上传递,使得包含它的子树都被标记为"不饱满":

【Codeforces Round #430 (Div. 2) A C D三个题】

·这样的标记关系形成后,我们就可以利用二叉树的性质对于每个询问log地查找Mex的值。可是,如何处理将全部数异或上x的情况(这是本题的特点)?为了使得字典树继续发挥作用,我们可以将x像那些数一样写成二进制形式,然后呢,如果在字典树的第k层的一个节点,x的二进制的k位是1,那么我们怎样表示所有数的这一位被取反了呢?那就是改变该层节点的左右儿子的位置,然后其他的就照常进行啊。

·我们通过异或的基本运算法则之一:a^b^c==a^(b^c),那么其实每一个修改值x,我们可以将当前的所有修改值异或到一起得到新的X,这样就可以在最初的字典树上进行操作了。

·如果懂了上述思路,那么接下来代码也不难,注意这里直接使用二进制跨过了建树,可思想是一致的。注意!很简洁!

 #include<stdio.h>
int n,m,a,b=<<,x,P=,ans,t;
bool full[];
void Up(int u)
{
if((!(u>>=))||full[u])return;
if(full[u<<]&&full[u<<|])full[u]=,Up(u);
}
int main()
{
scanf("%d%d",&n,&m);
while(n--&&scanf("%d",&a))full[a+b]=,Up(a+b);
while(m--&&scanf("%d",&a))
{
x^=a;P=;ans=;t=;
while(t--){P<<=;
if((<<t)&x)(full[P|])?ans|=<<t:P|=;
else if(full[P])ans|=<<t,P|=;}
printf("%d\n",ans);
}
return ;
}//Paul_Guderian

苦苦安顿抚平的回忆,

骤然散落一如繁星的碎片......————汪峰《回忆之前忘记之后》