B
一个数字三角形，最下层的值是 $1\sim 2n-1$ 的排列，其余的值是正下，左下，右下方三个值的中位数，给定 $n,x$ ， 求能构造出顶端是 $x$ 的最下层排列
先考虑无解：即 $x=1 或 x=2n-1$ 时无解
其次可以发现，对于两个相邻的相同数字，该数字会一直向上延伸
而 $x$ 就是离对称轴最近且满足条件的数
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| const int N=2e5+100;
int n,x,p[N],vis[N];
int main(){
scanf("%d%d",&n,&x);
if(x==1 || x==2*n-1) return puts("No"),0;
puts("Yes");
p[n]=x;
p[n-1]=x==2 ? x+1 : x-1,p[n+1]=x==2 ? x-1 : x+1,p[n+2]=x==2 ? x+2 : x-2;
vis[x]=vis[x+1]=vis[x-1]=vis[x==2 ? x+2 : x-2]=1;
for(rei i=1,j=1;i<=2*n-1;++i){
if(p[i]) continue;
while(vis[j]) ++j;
p[i]=j,vis[j]=1;
}
for(rei i=1;i<=2*n-1;++i) printf("%d\n", p[i]);
getchar(),getchar();
return 0;
}
|
C
数轴上有 $n$ 只兔子，第 $i$ 只位于 $a_i$ ，做 $k$ 次移动，每次由 $m$ 次跳跃，对于第 $j$ 次跳跃，第 $c_j$ 只兔子等概率选取 $c_{j-1}$ 或 $c_{j+1}$ 的兔子并跳到其对称点，求每一只兔子最终位置的期望
对于兔子 $c_j$ ，跳跃后会转移到 $2\times c_{j-1}-c_j$ 或 $2\times c_{j+1}-c_j$
所以有 $f’_{c_j}=\frac{2\times f_{c_{j-1}}-f_{c_j}+2\times f_{c_{j+1}}-f_{c_j}}{2}=f_{c_{j-1}}+f_{c_{j+1}}-f_{c_j}$
而进行 $k\leq 10^{18}$ 轮，时间复杂度显然会爆
$\text{ctp_314}$ 告诉我们，遇到转移问题难以转移就想一想差分，即， $d_i=f_i-f_{i-1}$
差分的转移为:
恰好是交换，那么求出循环节即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| const int N=1e5+100;
int n,m,a[N],f[N],s[N],top,vis[N];
ll ans[N],k;
int main(){
scanf("%d",&n);
for(rei i=1;i<=n;++i) scanf("%d",&a[i]);
for(rei i=n;i;--i) a[i]-=a[i-1],f[i]=i;
scanf("%d%lld",&m,&k);
for(rei i=1,p;i<=m;++i) scanf("%d",&p),swap(f[p],f[p+1]);
for(rei i=1;i<=n;++i,top=0)
if(!vis[i]){
for(rei j=i;!vis[j];j=f[j]) vis[j]=1,s[++top]=j;
for(rei j=1;j<=top;++j) ans[ s[j] ]=a[ s[(j+k-1)%top+1] ];
}
for(rei i=1;i<=n;++i) printf("%lld\n",ans[i]+=ans[i-1]);
getchar(),getchar();
return 0;
}
|
D
数字三角形，生成规则与 $B$ 相同，给定第 $n$ 行的数列，求第 $1$ 行的
不会的二分贪心思维题
二分顶端的数，由于用中位数生成，所以数列中只需要保留与顶端数的大小关系，即将原数列转化为 $01$ 串
由 $B$ 推出的性质推广得：当存在两个相邻的 $0/1$，且不与边界相邻，那么可以一直向上走
即，离对称轴最近且长度至少为 $2$ 的连续段就是顶端答案
最后特判不存在该连续段的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| const int N=2e5+100;
int n,ans=2,p[N];
inline bool valid(int mid){
for(rei i=0;i<n-1;++i)
if(max(p[n-i],p[n-i-1])<=mid || max(p[n+i],p[n+i+1])<=mid) return true;
else if(min(p[n-i],p[n-i-1])>mid || min(p[n+i],p[n+i+1])>mid) return false;
return p[1]<=mid;
}
int main(){
scanf("%d",&n); for(rei i=2*n-1;i;--i) scanf("%d",&p[i]);
rei l=2,r=2*n-2;
while(l<=r){
rei mid=l+r>>1;
valid(mid) ? r=mid-1,ans=mid : l=mid+1;
}
printf("%d\n",ans);
getchar(),getchar();
return 0;
}
|
E
给定 $3\times N$ 的矩阵，点 $(i,j)$ 的数为 $i+3j-3$ 。有操作：选择 $3\times 3$ 的矩阵，并将其旋转 $180^。$ 。给定目标矩阵，询问是否可以转化
首先考虑无解：
- 将每一列看为一个整体，整体内部的元素组成不变
- 所有模 $3$ 余 $2$ 的数一定在第二行
再考虑性质：每次以 $(i,2)$ 为中心旋转实际是交换 $i-1,i+1$ 列，并将 $[i-1,i+1]$ 上下颠倒 —— 将上下颠倒看作奇偶性，奇数时要上下颠倒
将每一列当成字母，小写为颠倒前，大写为颠倒后，设 $abcde$ 为原矩形的部分
其次可以推出结论：
可以将隔着一列的两列数同时颠倒
可以同时改变相邻 $4$ 列的奇偶性
$\therefore$ 可以成对改变边的奇偶性，那么只需要考虑最终状态 奇数列 与 偶数列上下颠倒个数 的奇偶性，若都为偶则合法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| const int N=1e5+100;
int w[3][N],f[N],h[2],n;
int main(){
scanf("%d",&n);
for(rei i=0;i<3;++i) for(rei j=1;j<=n;++j) scanf("%d",&w[i][j]);
for(rei i=1;i<=n;++i){
rei a=w[0][i],b=w[1][i],c=w[2][i];
if(abs(a-b)>1 || abs(b-c)>1 || b%3!=2 || (b%6 & i&1)) return puts("No"),0;
f[i]=b/3+1,h[i&1]^=a>c;
}
for(rei i=1;i<=n;++i) while(f[i]!=i) h[ i&1^1 ]^=1,swap(f[i],f[ f[i] ]);
h[0]||h[1] ? puts("No") : puts("Yes");
getchar(),getchar();
return 0;
}
|
F
给定 $n\times n$ 的网格，给定黑点坐标，其余白色，若存在 $(x,y)$ 和 $(y,z)$ 则会出现一个 $(z,x)$ 的黑点，求最终黑点数
若 $(x,y)$ 为黑色，则连 $x\rightarrow y$ 的边，将题目等价于：若有 $x\rightarrow y 且 y\rightarrow z$ ，则有 $z\rightarrow x$
如此连边不会影响连通性，只需考虑一个连通块内的情况并累加即可
由连边方式构成的三元环结构引导我们对图染色
连边方式自然定为：若 $x\rightarrow y$ , 则有 $col(x)+1\equiv col(y) \pmod 3$
对染色情况分类：
所有点只用 $\leq 2$ 中颜色且成功
即没有出现新边，最终边数 $|E’|$ 等于原边数 $|E|$
所有点用 $3$ 种颜色且成功
可以证明此时图 $G$ 具有完全三分图的结构
在此情况下，总边数等于各个部分大小的两两乘积和
染色失败
设加入边 $(u,v)$ 时失败，即，加入该边前 $u,v$ 已经连通，此时他们所在的连通分量是一个完全三分图
考虑失败原因
对于自环 $s\rightarrow s$ ,可以证明所有与 $s$ 相连的点 $u$ ,都有重边； 而对于 $\forall v,u$ 都有 $v\rightarrow s\rightarrow u \rightarrow v$
即，图 $G$ 完全图
该情况下总边数时连通分量大小的平方
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| const int N=1e5+100;
int head[N],Next[N<<1],ver[N<<1],tot;
int col[N],c[3],n,m,ce;
ll ans;
inline void add(int u,int v){ ver[++tot]=v,Next[tot]=head[u],head[u]=tot;}
bool dfs(int x){
bool result=true; ++c[ col[x] ];
for(rei i=head[x];i;i=Next[i]){
rei y=ver[i];
rei c=(col[x]+2-(i&1))%3; ++ce;
result&=(~col[y] ? col[y]==c : (col[y]=c,dfs(y)));
}
return result;
}
int main(){
scanf("%d%d",&n,&m);
for(rei i=1,u,v;i<=m;++i) scanf("%d%d",&u,&v),add(u,v),add(v,u);
memset(col,-1,sizeof col);
for(rei i=1;i<=n;++i)
if(!~col[i]){
c[0]=c[1]=c[2]=ce=col[i]=0;
if(!dfs(i)) ans+=(ll) (c[0]+c[1]+c[2])*(c[0]+c[1]+c[2]);
else if(c[0] && c[1] && c[2]) ans+=(ll) c[0]*c[1]+(ll) (c[0]+c[1])*c[2];
else ans+=ce>>1;
}
printf("%lld\n",ans);
getchar(),getchar();
return 0;
}
|