摘要
/ | A | B | C | D | E | F | G | H | I | J |
---|---|---|---|---|---|---|---|---|---|---|
场上 | ✔ | ✔ | ||||||||
zyj | ✔ | |||||||||
wrf | ✔ | ✔ | ||||||||
lmj | ✔ |
题目
A.Tree
题意
给出一棵树,规定边的方向都指向子树。
可以在树上加一条边,使得存在尽量多的点对(i,j)
,使得点i
能够到达点j
。
题解
做法
两次 dfs。
第一次维护所有点子树的补集大小,第二次维护到根的路径上补集大小之和。
取最大的即可。
证明
首先,显然所加边必然是从叶节点连向根节点。
设从根到所求叶节点的路径上各点为 $a_1,a_2,...,a_m$,其子树大小分别为 $k_{a_1},k_{a_2},...,k_{a_m}$。
这里面的每一个点都能到达整棵树。
对于其中的节点 $a_i$ 而言,它原本能够到达 $k_{a_i}$ 个点,而现在可以到达所有的 $n$ 个点,贡献为 $n-k{a_i}$。
那么某一种连接方案的总贡献即为:
$$ n+\sum (n-k_{a_i}) $$
维护和式内的值即可。
时间复杂度
$O(n)$
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;
const int N=100020;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
typedef vector<vector<int> > graph;
int dfs1(graph& g,vector<int>& v,int n)
{
v[n]=1;
for(auto a:g[n])
{
v[n]+=dfs1(g,v,a);
}
return v[n];
}
ll dfs2(graph &g,vector<int>& v,int n)
{
ll ans=0;
for(auto a:g[n])
{
ans=max(dfs2(g,v,a),ans);
}
ans+=v[n];
return ans;
}
int main(void)
{
//ios::sync_with_stdio(false);
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
for(int _=read();_>0;_--)
{
int n=read();
graph g(n+1);
vector<int> v(n+1);
for(int i=2;i<=n;i++)
{
g[read()].push_back(i);
}
dfs1(g,v,1);
ll s=0;
for(int i=1;i<=n;i++) s+=v[i],v[i]=n-v[i];
printf("%lld\n",dfs2(g,v,1)+s);
}
return 0;
}
B.Absolute Math
题意
题解
代码
C.Slime and Stones
题意
有两堆石子,博弈双方每次要么从一堆中取石子,要么在两堆中取相差不超过 k
的石子,求先手是否必胜。
题解
做法
检测所求石子堆是否满足如下形式即可:
$$ \{min(a,b),max(a,b)\}=\{\lfloor n\alpha \rfloor,\lfloor n\alpha \rfloor+k+1\} $$
其中
$$ \alpha= {2-(k+1)+\sqrt{(k+1)^2+4} \over 2} $$
证明
本题属于威佐夫博弈的一种推广。
首先,显然所有的必败点关于 $y=x$ 对称。
记 $x \leq y$ 的所有必败点按 $x$ 单调递增排序为 $(x_i,y_i)$,研究它们的性质:
显然有
$$ x_n=\mathop{\mathrm{mex}}\limits_{i<n}\{x_i,y_i\} \tag{1} $$
且 $x$ 与 $y$ 均单调递增。
值得注意的是,任何正整数要么属于 $x$,要么属于 $y$,且只能属于其中之一。原因在于坐标系上每行每列有且仅有一个必败态。
这就可以推得,必然有 $x_n \leq y_n$。反之,由 $(1)$,$y_n$必然会与某个 $x_i$ 或 $y_i$ 相等,矛盾。
接下来记 $y_n=x_n+f(n)$。分两种情况讨论:
- 必败态不能转移到必败态。
- 必胜态一定存在能转移到的必败态。
首先分析第一种情况。
先分析相反情况:如果必败态转移到了必败态,必然是同时从两堆中拿,因为每行每列有且仅有一个必败态。设两个必败态标号分别为 $n$、$m$,保证 $n>m$。
那么就存在 $|(y_n-y_m)-(x_n-x_m)| =|f(n)-f(m)|\leq k$,返回原问题即得:
$$ \forall m<n , |f(n)-f(m)| > k \tag{2.1} $$
再分析第二种情况。
记该必胜态为 $(x',y')$,$x' \leq y'$。
如果 $x' \in y$,记该必胜态为 $(y_n,y')$,则 $x_n \leq y_n \leq y'$,构造转移 $(y_n,y') \rightarrow (y_n,x_n)$ 即可。
如果 $x' \in x$,记该必胜态为 $(x_n,y')$,情况比较复杂:
- 如果 $y' \geq y_n$,构造转移 $(x_n,y') \rightarrow (x_n,y_n)$ 即可。
- 否则必然存在 $(x_m,y_m)$,使得 $|(y'-y_m)-(x_n-x_m)|=|y'-x_n-f(m)| \leq k$,即
$$ \forall n>0,\forall y'<y_n,\exists m<n, |y'-x_n-f(m)| \leq k \tag{2.2} $$
令 $y'=y_n-1$,结合 $(2.1)$ 与 $(2.2)$ 两个约束可得:
$$ \forall n>0,\exists m<n, |y_n-1-x_n-f(m)|=|f(n)-f(m)-1| \leq k < |f(n)-f(m)| $$
分类讨论易得:
$$ \forall n>0,\exists m<n,f(n)=f(m)+k+1 \tag{3} $$
而每个 $f(n)$ 都可以最终转移到 $f(0)=0$,所以可以记 $f(n)=(k+1)f'(n)$,$f'(n)$ 为转移次数。
那么上面的式子可以改写为:
$$ \forall m<n , |f'(n)-f'(m)| \geq 1 \tag{1.1} $$
$$ \forall n>0,\exists m<n,f'(n)=f'(m)+1 \tag{3.1} $$
由归纳法可证 $f(n)=(k+1)n$,即
$$ y_n=x_n+n(k+1) \tag{4} $$
接下来考察它的通项。
之前已经注意到,任何正整数要么属于 $x$,要么属于 $y$,且只能属于其中之一。即 ${x_i}$、${x_i+(k+1)i}$ 构成一个对正整数的划分。
考虑贝蒂定理:
贝蒂定理
设 $a$、$b$ 是正无理数且 $\frac{1}{a}+\frac{1}{b}=1$,则 $\lfloor na \rfloor$、$\lfloor nb \rfloor$ 构成一个对正整数的划分。
证明:
- 先证组内没有重复:由原式可得 $a>1,b>1$,所以显然。
- 再证两集合没有交:如果有交,记为 $k=\lfloor na \rfloor=\lfloor mb \rfloor$,则 $\frac{k}{a} \leq m<\frac{k+1}{a},\frac{k}{b} \leq n<\frac{k+1}{b}$。由 $\frac{1}{a}+\frac{1}{b}=1$,两式相加得 $k \leq m+n <k+1$,与 $k$、$m$、$n$ 均为整数矛盾。
- 最后证包含了全体正整数:如果存在正整数 $k$ 未被包含,那么 $\lfloor ma \rfloor< k <\lfloor (m+1)a \rfloor,\lfloor nb \rfloor< k <\lfloor (n+1)b \rfloor$,即 $ma< k < (m+1)a-1,nb< k < (n+1)b-1$。同样的,${m \over k}< {1 \over a} < {m+1 \over k+1} -{1\over ak} <{m+1 \over k+1},{n \over k}< {1 \over b}<{n+1 \over k+1}$。两式相加得 $m+n<k<k+1<m+n+2$,与 $k$、$m$、$n$ 均为整数矛盾。
我们即是要找到一对 $(\alpha,\beta)$,使得 $\lfloor n\alpha \rfloor+n(k+1)=\lfloor n\beta \rfloor$,且 $\frac{1}{\alpha}+\frac{1}{\beta}=1$。
显然,$\lfloor n(\alpha+k+1) \rfloor=\lfloor n\beta \rfloor$,即 $\alpha+k+1=\beta$。与贝蒂定理联立解得:
$$ \alpha= {2-(k+1)+\sqrt{(k+1)^2+4} \over 2} $$
这就是所要求的。
时间复杂度
$O(1)$
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const int inf=0x3f3f3f3f;
const ll mint=0x7fffffff;
const ll linf=1000000000000000000LL;
const ll mod=998244353LL;
const double eps=1e-3;
const int N=1020;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
ll dp[N][N];
int main(void)
{
//ios::sync_with_stdio(false);
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
for(int _=read();_>0;_--)
{
ll a=read(),b=read(),k=read();
if(a>b) swap(a,b);
double p=(sqrt((k+1)*(k+1)+4)+2-(k+1))/2.0,q=p+(k+1);
bool f=false;
ll n1=floor(a/p),n2=floor(b/q);
for(int i=max(0LL,n1-10);i<n1+10;i++)
{
ll ta=ll(floor(p*i)),tb=ll(floor(q*i));
// printf("%d %lld %lld\n",i,ta,tb);
if(ta==a && tb==b) f=true;
}
for(int i=max(0LL,n2-10);i<n2+10;i++)
{
ll ta=ll(floor(p*i)),tb=ll(floor(q*i));
// printf("%d %lld %lld\n",i,ta,tb);
if(ta==a && tb==b) f=true;
}
printf("%d\n",int(!f));
}
return 0;
}
D.Product
题意
题解
代码
E.Resistance
题意
题解
代码
F.Skyscrapers
题意
题解
代码
G.Game
zyj (赛后)
题意
阿巴阿巴阿巴
题解
直接用$Treap$模拟即可
代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(auto i=(a);i<=(b);++i)
#define dep(i,a,b) for(auto i=(a);i>=(b);--i)
#define pb push_back
typedef long long ll;
const int maxn=(int)1e6+100;
const int mod=(int)1e9+7;
template<class T>
struct fhq_Treap{
static const int N=2e5+5;
int rt,tot,lc[N],rc[N],sz[N];
unsigned int rnd[N];
T val[N],mn[N],mx[N];
ll sum[N];
void clear(){
fill(lc,lc+tot+1,0);
fill(rc,rc+tot+1,0);
fill(sz,sz+tot+1,0);
rt=tot=0;
}
fhq_Treap(){
rt=tot=0;
srand(clock()+time(0));
mn[0]=1e9,sum[0]=val[0]=mx[0]=0;
}
inline void pushup(int u){
sz[u]=sz[lc[u]]+sz[rc[u]]+1;
mn[u]=min({val[u],mn[lc[u]],mn[rc[u]]});
mx[u]=max({val[u],mx[lc[u]],mx[rc[u]]});
sum[u]=sum[lc[u]]+sum[rc[u]]+val[u];
}
void split_by_sz(int u,const int left_size,int &x,int &y){//sz[x]==v
if(!u)return x=y=0,void();
if(sz[lc[u]]+1<=left_size)x=u,split_by_sz(rc[u],left_size-sz[lc[u]]-1,rc[u],y);
else y=u,split_by_sz(lc[u],left_size,x,lc[u]);
pushup(u);
}
void split_by_min(int u,const int right_mn,int &x,int &y){//mn[l]<v
if(!u)return x=y=0,void();
if(mn[rc[u]]<right_mn||val[u]<right_mn) x=u,split_by_min(rc[u],right_mn,rc[u],y);
else y=u,split_by_min(lc[u],right_mn,x,lc[u]);
pushup(u);
}
void split_lower(int u,const int left_val,int &x,int &y){//val[x]<v
if(!u)return x=y=0,void();
if(val[u]<left_val)x=u,split_lower(rc[u],left_val,rc[u],y);
else y=u,split_lower(lc[u],left_val,x,lc[u]);
pushup(u);
}
void split_upper(int u,const int left_val,int &x,int &y){//val[x]<=v
if(!u)return x=y=0,void();
if(val[u]<=left_val)x=u,split_upper(rc[u],left_val,rc[u],y);
else y=u,split_upper(lc[u],left_val,x,lc[u]);
pushup(u);
}
int merge(int x,int y){//x<y
if(!x||!y)return x+y;
if(rnd[x]<rnd[y])return rc[x]=merge(rc[x],y),pushup(x),x;
else return lc[y]=merge(x,lc[y]),pushup(y),y;
}
void insert(const int pos,const T v){ // 插入 v
assert(pos);
int x,y,u=++tot;
sum[u]=val[u]=mn[u]=v,sz[u]=1,rnd[u]=rand();
split_by_sz(rt,pos-1,x,y);
rt=merge(merge(x,u),y);
}
void remove(const T v){
int x,y,z;
split_lower(rt,v,x,y);
split_upper(y,v,y,z);
if(!y)assert(0); // 删除不存在的元素
y=merge(lc[y],rc[y]);
rt=merge(x,merge(y,z));
}
int dfs(int *a,int l,int r){
if(l>r)return 0;
int u=++tot,mid=(l+r)>>1;
sum[u]=val[u]=mn[u]=a[mid],sz[u]=r-l+1,rnd[u]=rand();
lc[u]=dfs(a,l,mid-1);rc[u]=dfs(a,mid+1,r);
pushup(u);return u;
}
void build_from(int *a,int l,int r){rt=dfs(a,l,r);}
int rk(T v){ // 相同的数中,第一个数的排名
int x,y,res;
split_lower(rt,v,x,y);
assert(val[y]>=v);
res=sz[x]+1,rt=merge(x,y);
return res;
}
T kth(int k){ // 查询排名为 k 的数
int u=rt;
while(k!=sz[lc[u]]+1){
if(k<=sz[lc[u]])u=lc[u];
else k-=sz[lc[u]]+1,u=rc[u];
}
return val[u];
}
void dfs_seq(int u,T *p){
if(u==0)return;
dfs_seq(lc[u],p);
*(p+sz[lc[u]]+1)=val[u];
dfs_seq(rc[u],p+sz[lc[u]]+1);
}
void seq(T *p){dfs_seq(rt,p);}
void solve(){
int op,x,y;scanf("%d%d",&op,&x);
if(op==1){
scanf("%d",&y);
if(kth(x)<y) return (void)puts("0");
int L,R;split_by_sz(rt,x,L,R);
if(mn[L]>=y){
rt=merge(L,R);
return (void)puts("0");
}int l,r;
split_by_min(L,y,l,r);
ll ans=sum[r]-1ll*(y-1)*sz[r];
int l1,l2,r1,r2;
split_by_sz(l,sz[l]-1,l1,l2);
split_by_sz(r,1,r1,r2);
val[l2]+=val[r1]-(y-1);
sum[l2]=mn[l2]=val[l2];
val[r1]=sum[r1]=mn[r1]=y-1;
rt=merge(merge(merge(l1,l2),merge(r2,r1)),R);
printf("%lld\n",ans);
}else printf("%d\n",kth(x));
}
};
fhq_Treap<int> t;
int a[maxn];
void solve(){
int n,q;scanf("%d%d",&n,&q);
rep(i,1,n) scanf("%d",&a[i]);
t.clear();
rep(i,1,n) t.insert(i,a[i]);
while(q--) t.solve();
rep(i,1,n) printf(i==n?"%d\n":"%d ",t.kth(i));
}
int main(){
int T;cin>>T;
while(T--) solve();
}
H.Distance
题意
题解
代码
I.Yajilin
lmj 赛后
题意
给定网格图,将一些点涂成黑色,涂黑的点不能相邻,且涂完之后,白点可以形成曼哈顿回路,求黑色块的和的最大值。
题解
插头$dp$即可,加一个额外状态黑色块,注意转移的时候除非变成黑色状态,否则要变成普通状态。
如果不会插头$dp$建议学习洛谷插头$dp$模板题题解
代码
#include <bits/stdc++.h>
using namespace std;
#define paii pair<int,int>
#define fr first
#define sc second
typedef long long ll;
const int N=1e5+7;
const int p=1e9+7;
ll qpow(ll a,ll n){ll res=1;while(n){if(n&1)res=res*a%p;a=a*a%p;n>>=1;}return res;}
int dp[2][N];
int state[2][N];
int now;
int change(int k,int x) { return ((k)<<(2*(x))); }
int get(int k,int x) { return (((k)>>(2*(x)))&3); }
struct Hash
{
int fst[N],nxt[N];
int mark[N];
int mt=0;
int T;
void init()
{
mt++;
T=0;
}
void insert(int s,int v)
{
int S=s%N;
if(mark[S]!=mt)mark[S]=mt,fst[S]=-1;
for(int i=fst[S];i!=-1;i=nxt[i]){
if(state[now][i]==s){
dp[now][i]=max(dp[now][i],v);
return;
}
}
nxt[T]=fst[S];
fst[S]=T;
state[now][T]=s;
dp[now][T]=v;
T++;
}
}H;
int a[20][20];
void work()
{
int n,m;
scanf("%d",&n);
m=n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
}
}
int t;
state[0][(t=1)-1]=0;dp[0][0]=0;now=0;
int ans=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
now^=1;
H.init();
memset(dp[now],0,sizeof(dp[now]));
memset(state[now],0,sizeof(state[now]));
for(int k=0;k<t;k++){
int s=state[now^1][k];
int v=dp[now^1][k];
int k1=get(s,j-1),k2=get(s,j);
if(k1==0&&k2==0){
H.insert(s^change(3,j-1)^change(3,j),v+a[i][j]);
}
if(k1==3){
s^=change(3,j-1);k1=0;
}
if(k2==3){
s^=change(3,j);k2=0;
}
if(k1==0&&k2==0){
if(i<n&&j<m)H.insert(s^change(1,j-1)^change(2,j),v);
}else if(k1==0){
if(i<n)H.insert(s^change(k2,j-1)^change(k2,j),v);
if(j<m)H.insert(s,v);
}else if(k2==0){
if(i<n)H.insert(s,v);
if(j<m)H.insert(s^change(k1,j-1)^change(k1,j),v);
}else if(k1==2&&k2==1){
H.insert(s^change(k1,j-1)^change(k2,j),v);
}else if(k1==1&&k2==1){
int cnt=1;
for(int aaa=j+1;aaa<=m;aaa++){
if(get(s,aaa)==1)cnt++;
if(get(s,aaa)==2)cnt--;
if(!cnt){
H.insert(s^change(k1,j-1)^change(k2,j)^change(3,aaa),v);break;
}
}
}else if(k1==2&&k2==2){
int cnt=1;
for(int aaa=j-2;aaa>=1;aaa--){
if(get(s,aaa)==1)cnt--;
if(get(s,aaa)==2)cnt++;
if(!cnt){
H.insert(s^change(k1,j-1)^change(k2,j)^change(3,aaa),v);break;
}
}
}else{
if(i==n&&j==m){
ans=max(ans,v);
}else if(i==n&&j==m-1&&get(s,m)==0){
ans=max(ans,v+a[n][m]);
}
}
}
t=H.T;
}
for(int k=0;k<t;k++){
state[now][k]<<=2,state[now][k]&=change(1,m+1)-1;
}
}
printf("%d\n",ans);
}
int main()
{
//freopen("1.in","r",stdin);
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T=1;
scanf("%d",&T);
//cin>>T;
while(T--){
work();
}
}
J.Jump
题意
题解
代码
本文由 Edwiv 创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Aug 23, 2020 at 09:51 pm