/*
又是又双叒叕WA的一天...
我太弱鸡了...
今天上午打了4道CF
*/
Problem 1 meaning
给出q组询问，求下列函数的值$ f(a) = \max\limits_{0 < b < a} \{ gcd(a\oplus b,a \ \& \ b)\} $
对于100%的数据 $q\leq 1000, 2 \leq a_i \leq 2^{25}-1$
结论题，直接打表找结论，发现当$a \in [2^{n-1},2^{n}-2] (n \geq 2)$ 答案为$2^{n} - 1$
当$a = 2^n - 1 ,n \geq 1$时答案为a除自己外最大的约数。
直接打表处理26个特殊情况，实际程序复杂度$ O(q) $
# include <bits/stdc++.h>
using namespace std;
int a[],Pow[];
int fun(int x)
{
if (x==) return ;
for (int i=;i<=;i++)
if (x==Pow[i]-) return a[i];
int i;
for (i=;i<=;i++)
if (x<=Pow[i]-) break;
return Pow[i]-;
}
int main()
{
a[]=; a[]=; a[]=; a[]=; a[]=;
a[]=; a[]=; a[]=; a[]=; a[]=;
a[]=; a[]=; a[]=; a[]=;
a[]=; a[]=; a[]=; a[]=;a[]=;
a[]=; a[]=; a[]=; a[]=;
a[]=; a[]=; a[]=;
int n ;scanf("%d",&n);
Pow[]=;
for (int i=;i<=;i++) Pow[i]=Pow[i-]*;
int ans;
while(n--) {
int x;scanf("%d",&x);
printf("%d\n",fun(x));
}
return ;
}
meaning.cpp
Problem 2 Jongmah
给出n个数字在[1,m]内，构成若干个合法三元组，合法的定义是三元组内元素相同或连续。
对于100%的数据，$ n,m\leq 10^6 $
考虑一个dp，先记录每个数出现几次，作为cnt[]数组
考虑若连续三元组超过2个，那么就可以转化为3个相同的三元组，所以在计算中，连续三元组最多为2个。
其他的就被计算在不连续的三元组内。
f[i][k][l]值小于i的所有数，三元组(i,i+1,i+2)选取k$k\in [0,2]$,三元组(i-1,i,i+1)选取l个$l \in [0,2]$ 最多合法三元组个数。
考虑从f[i-1][l][j]转移过来，枚举 j $\in [0,2]$,转移。
当前状态和前继状态比较在原来基础上多出来k个连续三元组(i,i+1,i+2)，到此为止，已经用去
数 i-1 消耗 l+j 个； 数 i-2 消耗 j 个 ； 数 i 消耗 k+j+l个 ； 数 i+1 消耗 k+l ；数 i+2 消耗k个。
$ f[i-1][l][j] + k + \left \lfloor \frac{cnt[i] - k - j - l}{3} \right \rfloor $
初始化全是0
需要满足限制$ cnt[i-1]\geq l+j,cnt[i-2] \geq j,cnt[i] \geq k+j+l,cnt[i+1]\geq k+l,cnt[i+2]\geq k$即可转移。
# include<bits/stdc++.h>
# define fp(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
const int N=1e6+;
int f[N][][],cnt[N];
int n,m;
int main()
{
scanf("%d%d",&n,&m);
int t;
fp(i,,n) scanf("%d",&t),cnt[t]++;
int ans=;
fp(i,,m) fp(k,,) fp(l,,) fp(j,,)
{
if(k+j+l>cnt[i]) continue;
if(l+j>cnt[i-]) continue;
if(j>cnt[i-]) continue;
if(k+l>cnt[i+]) continue;
if(k>cnt[i+]) continue;
f[i][k][l]=max(f[i][k][l],f[i-][l][j]+k+(cnt[i]-k-j-l)/);
ans=max(ans,f[i][k][l]);
}
cout<<ans<<'\n';
return ;
}
jongmah.cpp
Problem C magic
有n个元素数组为$c_i$，对于第$i$个元素($i \in [2,n-1]$)可以发生"同步"，即$c_i = c_{i-1} + c_{i+1} - c_i$
给定目标含n个元素数组$t_i$，给出$q个询问，输出$c_i$能否经过若干次"同步"后变成数组$t_i$
我们认为，当两个数组任意对应位置上的数值一样时，这两个数组相同，即$\forall i \in \{1,2...n\} 满足 a_i = b_i 那么 a[] = b[]$
对于100%的数据$n \leq 10^5 , q \leq 10 $
我们对$ c_i = c_{i-1} + c_{i+1} - c_i $观察对$c$差分数组的影响，
即数组$ \{c_{i-1},c_i,c_{i+1} \}$变成$\{c_{i-1},c_{i-1} + c_{i+1} - c_i,c_{i+1} \}$
对于原来的差分数组，发现差分值从$\{ \delta , c_i-c_{i-1} , c_{i+1}-c_i\}$变成了$\{\delta,c_{i+1}-c_i,c_i - c_{i-1} \}$，
交换差分数组中的两位，若两个数组相等那么其差分数组也相等，但是两个差分数组相等的数组，必须首位相等才会相等。
所以，先判断a[1]=t[1] and a[n]=t[1] 是否成立,若成立 继续判断a[],t[]的差分数组排序后是否相同，若相同输出$ Yes $，若不是此种情况输出 $ No $.
时间复杂度$O(q \times n log_2 n)$
# include <bits/stdc++.h>
# define long long
using namespace std;
const int N=1e6+;
int a[N],b[N],da[N],db[N],n;
bool check()
{
for (int i=;i<=n;i++)
if (da[i]!=db[i]) return false;
return true;
}
signed main()
{
int T; scanf("%d",&T);
while (T--) {
scanf("%lld",&n);
for (int i=;i<=n;i++) scanf("%lld",&a[i]);
for (int i=;i<=n;i++) scanf("%lld",&b[i]);
if (a[]!=b[]||a[n]!=b[n]) {
puts("No");
continue;
}
for (int i=;i<=n;i++)
da[i]=a[i]-a[i-],
db[i]=b[i]-b[i-];
sort(da+,da++n);
sort(db+,db++n);
if (check()) puts("Yes");
else puts("No");
} return ;
}
magic.cpp
Problem D leaf
一棵根为1的含有n个节点的树，保证每个点i的父亲$p_i<i$，设$(p_i,i)$权值为$w_i$
现在有$m$个询问，每个询问包含$u l r$，描述从节点u出发，到达叶子节点[l,r]中的一个最短路径长度。
数据保证[l,r]节点中一定有叶子节点。
对于100%的数据$n,m \leq 5 \times 10^5$
考虑一个性质，对于这棵树，保证一棵子树中的节点编号是连续的（像树链剖分一样）
然后就可以维护一棵线段树，离线算法统计了。
首先从根出发，到各叶子节点，记录dis[]数组表示唯一路径长度。
对于叶子节点，将其在线段树中的值+dis[v]，然后对该树从根1开始进行dfs，
线段树中保存的是各个叶子节点的权值（不是叶子节点的值为正无穷）
考虑从u走到v经过一条权为w的边那么考虑对该子树中的叶子路径是减小w，但是不在该子树中的叶子路径时增大w。
而这棵树又有一个子树节点编号连续的性质，所以先全局[1,n] + w , 然后 直接线段树区间修改 [u,mx[u]] -2w ，其中mx[u]表示以节点u为子树根的最大编号的儿子。
离线统计答案。
注意最大值inf不要开得太满，否则会爆long long。
# pragma GCC optimize()
# include <cstdio>
# include <cstring>
# include <vector>
# define int long long
using namespace std;
const int N=1e6+;
struct rec{int pre,to,w;}a[N];
struct node{int l,r,val,tag;};
const int inf=5e14;
int n,m,tot;
int mx[N],l[N],r[N],head[N],ans[N],dis[N];
vector<int>q[N];
inline int read()
{
int X=,w=; char c=;
while(c<''||c>'') {w|=c=='-';c=getchar();}
while(c>=''&&c<='') X=(X<<)+(X<<)+(c^),c=getchar();
return w?-X:X;
}
inline void write(int x)
{
if (x<) x=-x,putchar('-');
if (x>) write(x/);
putchar(''+x%);
}
struct Segment_Tree{
node t[N<<];
# define ls *x
# define rs *x+
void build (int x,int l,int r)
{
t[x].l=l; t[x].r=r;
if (l==r) { t[x].val=; return;}
int mid=(l+r)>>;
build(ls,l,mid);
build(rs,mid+,r);
t[x].val=max(t[ls].val,t[rs].val);
}
void down(int x)
{
t[ls].val+=t[x].tag; t[rs].val+=t[x].tag;
t[ls].tag+=t[x].tag; t[rs].tag+=t[x].tag;
t[x].tag=;
}
void update(int x,int opl,int opr,int d)
{
if (opl<=t[x].l&&t[x].r<=opr) {
t[x].val+=d;t[x].tag+=d;
return;
}
down(x);
int mid=(t[x].l+t[x].r)/;
if (opl<=mid) update(ls,opl,opr,d);
if (opr>mid) update(rs,opl,opr,d);
t[x].val=min(t[ls].val,t[rs].val);
}
int query(int x,int opl,int opr)
{
if (opl<=t[x].l&&t[x].r<=opr) return t[x].val;
down(x);
int mid=(t[x].l+t[x].r)/;
int val=inf;
if (opl<=mid) val=min(val,query(ls,opl,opr));
if (opr>mid) val=min(val,query(rs,opl,opr));
return val;
}
}tree;
void adde(int u,int v,int w)
{
a[++tot].pre=head[u];
a[tot].to=v;
a[tot].w=w;
head[u]=tot;
}
void dfs1(int u)
{
mx[u]=u;
for (int i=head[u];i;i=a[i].pre){
int v=a[i].to;
dis[v]=dis[u]+a[i].w;
dfs1(v);
mx[u]=max(mx[u],mx[v]);
}
}
void dfs2(int u)
{
for (int i=;i<q[u].size();i++) {
ans[q[u][i]]=tree.query(,l[q[u][i]],r[q[u][i]]);
}
for (int i=head[u];i;i=a[i].pre){
int v=a[i].to,w=a[i].w;
tree.update(,,n,w); tree.update(,v,mx[v],-*w);
dfs2(v);
tree.update(,,n,-w); tree.update(,v,mx[v],*w);
}
}
signed main()
{
n=read();m=read();
tree.build(,,n);
for (int i=;i<=n;i++) {
int u=read(),v=i,w=read();
adde(u,v,w);
}
dfs1();
for (int i=;i<=n;i++)
if (i==mx[i]) tree.update(,i,i,dis[i]);
else tree.update(,i,i,inf);
for (int i=;i<=m;i++) {
int v=read(); l[i]=read();r[i]=read();
q[v].push_back(i);
}
dfs2();
for (int i=;i<=m;i++) write(ans[i]),putchar('\n');
return ;
}
leaf.cpp