牛客周赛 Round 57（A,B,C,D,E,F,G）
比赛链接
官方题解
这场的题还不错，D是一个计算几何，考察到了一些线性代数里叉积的知识，E是爆搜+打表，不太常规，所以做起来感觉还不错？FG偏简单，F是multiset+线段树，G是很简单的构造题。DE挺值得一做的。
A 小红喜欢1
思路：
签到
code：
#include <iostream>
#include <cstdio>
using namespace std;
int a,b;
int main(){
for(int i=1;i<=5;i++){
cin>>a;
if(a==1)b=i;
}
cout<<b<<endl;
return 0;
}
B 小红的树切割
思路：
只要有两个同色点被一条边相连，那不管怎么放都不满足要求，因此一定得从中间断开。全都断开之后一定不存在两个同色点相邻了。
所以看每条边两个端点是否同色，同色就断，否则就不用断。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e5+5;
int n;
string s;
int head[maxn],ent;
struct edge{
int v,nxt;
}e[maxn<<1];
void add(int u,int v){
e[++ent]={v,head[u]};
head[u]=ent;
}
int ans=0;
void dfs(int u,int fa){
for(int i=head[u],v;i;i=e[i].nxt){
v=e[i].v;
if(v==fa)continue;
if(s[u]==s[v])ans++;
dfs(v,u);
}
}
int main(){
cin>>n>>s;s=" "+s;
for(int i=1,u,v;i<n;i++){
cin>>u>>v;
add(u,v);
add(v,u);
}
dfs(1,-1);
cout<<ans<<endl;
return 0;
}
C 小红的双好数（easy）
思路：
只要是二进制那每一位不就一定不大于 1 1 1 了？所以 k = 2 k=2 k=2 就是一种答案。
另外如果是 k = n k=n k=n 进制数那么表示出来就一定是 ( 10 ) n (10)_{n} (10)n，也一定是满足条件的。
类似的还有 k = n − 1 k=n-1 k=n−1 进制数，表示出来就是 ( 11 ) n − 1 (11)_{n-1} (11)n−1，也是满足的。
不过要注意当 n ≤ 2 n\le 2 n≤2 时，得满足 k ≥ 2 k\ge2 k≥2。这时 n = 2 n=2 n=2 时无解，而 n = 1 n=1 n=1 时 k k k 不管取什么都可以。
code：
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll n;
int main(){
cin>>n;
if(n==1)puts("YES\n2 3");
else if(n==2)puts("NO");
else {
puts("YES");
printf("%lld %lld\n",n-1,n);
}
return 0;
}
D 小红的线段
思路：
计算几何好题，主要考察叉积的性质。我写的感觉很神秘但是很简洁，看了看别人的感觉都做麻烦了，讲讲我的。
稍微讲讲前置知识，可能字有点多，不过请耐心看完，一定会有所收获的。
一：
先说说叉积的运算和性质。叉积一般是两个三维向量相乘得到第三个三维向量，假设 a ⃗ = ( x 1 , y 1 , z 1 ) , b ⃗ = ( x 2 , y 2 , z 2 ) \vec{a}=(x1,y1,z1),\vec{b}=(x2,y2,z2) a=(x1,y1,z1),b=(x2,y2,z2) ，则 a ⃗ × b ⃗ = ∣ i ⃗ j ⃗ k ⃗ x 1 y 1 z 1 x 2 y 2 z 2 ∣ = ( y 1 ∗ z 2 − y 2 ∗ z 1 ) i ⃗ + ( x 1 ∗ z 2 − x 2 ∗ z 1 ) j ⃗ + ( x 1 ∗ y 2 − x 2 ∗ y 1 ) k ⃗ \vec{a}\times\vec{b}=\left | \begin{matrix} \vec{i} & \vec{j} & \vec{k} \\ x1 &y1 & z1 \\ x2 & y2 &z2 \\ \end{matrix} \right | \\=(y1*z2-y2*z1)\vec{i}+(x1*z2-x2*z1)\vec{j}+(x1*y2-x2*y1)\vec{k} a×b= ix1x2jy1y2kz1z2 =(y1∗z2−y2∗z1)i+(x1∗z2−x2∗z1)j+(x1∗y2−x2∗y1)k也就是说 a ⃗ × b ⃗ = c ⃗ = ( y 1 ∗ z 2 − y 2 ∗ z 1 , x 1 ∗ z 2 − x 2 ∗ z 1 , x 1 ∗ y 2 − x 2 ∗ y 1 ) \vec{a}\times\vec{b}=\vec{c}=(y1*z2-y2*z1,x1*z2-x2*z1,x1*y2-x2*y1) a×b=c=(y1∗z2−y2∗z1,x1∗z2−x2∗z1,x1∗y2−x2∗y1)。这是高一公修课《线性代数》的内容，理解线性代数的本质我强推3b1b。这里的公式更多地是作为一种经验公式，而并不能说明叉积的本质。
这里是二维的向量，但它可以通过拓展一维来进行运算。我们把这个二维平面平铺在地上，向上引出第三维，假设原本 a ⃗ = ( x 1 , y 1 ) , b ⃗ = ( x 2 , y 2 ) \vec{a}=(x1,y1),\vec{b}=(x2,y2) a=(x1,y1),b=(x2,y2)，拓展后变成 a ⃗ = ( x 1 , y 1 , 0 ) , b ⃗ = ( x 2 , y 2 , 0 ) \vec{a}=(x1,y1,0),\vec{b}=(x2,y2,0) a=(x1,y1,0),b=(x2,y2,0)，就可以做叉积了。而结果是 a ⃗ × b ⃗ = c ⃗ = ( 0 , 0 , x 1 ∗ y 2 − x 2 ∗ y 1 ) \vec{a}\times\vec{b}=\vec{c}=(0,0,x1*y2-x2*y1) a×b=c=(0,0,x1∗y2−x2∗y1)，这个 x 1 ∗ y 2 − x 2 ∗ y 1 x1*y2-x2*y1 x1∗y2−x2∗y1 就是 a ⃗ , b ⃗ \vec{a},\vec{b} a,b 所成平行四边形的面积，正负指示了两个向量的相对位置（叉积的性质，叉积作出的第三个向量的长度就是以两个向量为两临边所成平行四边形的面积，三个向量指向的方向满足右手定则，这里由于第三个向量的 x y xy xy 值为 0 0 0。因此向量长度（又称向量的模）就是 z z z 值绝对值，方向就是 z z z 值正负性。 z z z 为正，向上时说明 b ⃗ \vec b b 在 a ⃗ \vec a a 的逆时针方向上，否则说明在顺时针方向上）
二：
再说一下直线解析式和直线的方向向量。初中一般把直线描述为 y = k x + b y=kx+b y=kx+b 的形式，表示这个解析式包含 所有满足 y = k x + b y=kx+b y=kx+b 的有序数对（也就是点坐标），这些点一个一个一个画在平面直角坐标系中，就是一条直线的样式。在高中阶段，更多是用 a x + b y + z = 0 ax+by+z=0 ax+by+z=0 的形式来描述一条直线（也称一般式），这样的好处是可以表示竖线（ y = k x + b y=kx+b y=kx+b 不能表示竖线，因为斜率 k k k 不存在），更通用。
而直线的方向向量就是和直线方向平行的向量，当解析式为 a x + b y + z = 0 ax+by+z=0 ax+by+z=0 时，一个方向向量可以写成 v ⃗ = ( − b , a ) \vec v=(-b,a) v=(−b,a) 的形式。同理 y = k x + b y=kx+b y=kx+b 转化成一般式后写出方向向量可以是 v ⃗ = ( 1 , k ) \vec v=(1,k) v=(1,k)。
三：
平面上有若干个点和一个固定的向量 v ⃗ \vec v v，我们从原点向每个点上连箭头，用这个箭头表示向量，用每个点的向量分别与那个固定的向量 v ⃗ \vec v v 做叉积，并用向量的模的大小作为排序依据进行排序，会怎么样呢？
先拿两个点和它们的向量举例：
平行四边形OABC的面积就是
O
A
→
\overrightarrow{OA}
OA 和
O
C
→
\overrightarrow{OC}
OC 叉积向量的模，它的面积又可以看作是
A
B
∗
O
D
=
O
C
∗
O
D
AB*OD=OC*OD
AB∗OD=OC∗OD，同理另一个向量与
O
C
→
\overrightarrow{OC}
OC 所成平行四边形的面积为
O
C
∗
O
E
OC*OE
OC∗OE。我们发现任意一个向量与
O
C
→
\overrightarrow{OC}
OC 所成四边形的面积一定包含
O
C
OC
OC 这个底边，我们按四边形面积排序，本质上是按照点到直线
O
C
OC
OC 的距离来排序的。
而且最神奇的是由于向量叉积存在顺序，所以在直线上面的点乘出来的四边形面积是正值，反之在直线下面的点乘出来的四边形面积是负值。我们按叉积的模来排序，就相当于按照点到直线
O
C
OC
OC 的距离从上到下排序。
比如下图，假设方向向量坐标为
(
x
,
y
)
(x,y)
(x,y)，每个点的坐标为
(
x
i
,
y
i
)
(x_i,y_i)
(xi,yi)，那么按照叉积的模
x
∗
y
i
−
x
i
∗
y
x*y_i-x_i*y
x∗yi−xi∗y 来排序的话。从图上从上到下看，排序后的顺序应该是
C
,
A
,
B
,
E
,
D
C,A,B,E,D
C,A,B,E,D。
这个题我们要连接两点，使得两点连线经过直线。我们可以把点分成三类：在直线上方，在直线上，在直线下方。不难看出在直线上的点不管怎么连都一定会产生交点，非常万金油，所以我们要省着点用。另外就是在直线上方和下方的点相连会产生交点。除此之外，上方的点互相相连一定不会产生交点，同理下方的点互连。
所以这个题我们可以对点 用叉积的方法排一下序，这样上方的点都排在前面，在直线上的点排在中间，在直线下方的点都排在后面。这时开头和末尾的点两两配对就行了。
处理的时候可以把所有点和直线都向下移动 b b b 格，让直线经过原点。
code：
#include <iostream>
#include <cstdio>
#include <array>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const int maxn=1005;
ll n,k,b,X,Y;//(X,Y)=(1,k)是y=kx+b的方向向量
array<ll,3> nd[maxn<<1];
bool cmp(array<ll,3> a,array<ll,3> b){
auto [x1,y1,id1]=a;
auto [x2,y2,id2]=b;
return x1*Y-y1*X<x2*Y-y2*X;//向量叉乘
}
bool check(array<ll,3> a,array<ll,3> b){//检查是否在两边
auto [x1,y1,id1]=a;
auto [x2,y2,id2]=b;
if(x1*Y-y1*X==0)return true;
return (x1*Y-y1*X)/abs(x1*Y-y1*X)*(x2*Y-y2*X)<=0;//相乘为负说明正负性相反，在两边
}
int main(){
cin>>n>>k>>b;
X=1;Y=k;
for(int i=1;i<=2*n;i++){
auto &[x,y,id]=nd[i];
cin>>x>>y;
y-=b;
id=i;
}
sort(nd+1,nd+2*n+1,cmp);
ll ans=0;
for(int i=1;i<=n;i++)ans+=check(nd[i],nd[i+n]);
cout<<ans<<endl;
for(int i=1;i<=n;i++)
printf("%lld %lld %c\n",nd[i][2],nd[i+n][2],"NY"[check(nd[i],nd[i+n])]);
return 0;
}
E 小红的双好数（hard）
思路：
分治。爆搜+打表
做法太超出常理了导致没人敢做，导致赛时过题人数甚至比 G G G 题还少一半，建议 E G EG EG 换一下位置。
这里保证 k 1 < k 2 k1<k2 k1<k2，先讨论大的 k 2 k2 k2，可以发现当 k 2 k2 k2 比较大的时候， n n n 写成 k 2 k2 k2 进制数其实根本没有几位，比如当 k 2 = 1000 k2=1000 k2=1000 时， n n n 写成 k 2 k2 k2 进制数一共最多也就才 6 6 6 位（ n n n 最大不超过 1 0 18 10^{18} 1018），直接爆搜所有可能的数就行（也就 2 6 − 2 = 30 2^6-2=30 26−2=30 个），然后验证写成 k 1 k1 k1 进制数是否满足条件。
这个爆搜的时间复杂度大概是 2 log k 2 1 0 18 ∗ log k 1 1 0 18 ≈ 18 ∗ 2 log k 2 1 0 18 2^{\log_{k2}10^{18}}*\log_{k1}10^{18}\approx18*2^{\log_{k2}10^{18}} 2logk21018∗logk11018≈18∗2logk21018，嗯。发现当 k 2 ≥ 7 k2\ge7 k2≥7 的时候比较能搜的动，而对于 k 1 < k 2 < 7 k1<k2<7 k1<k2<7 的部分，因为很少，所以直接打表查表特判输出即可。
code：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
typedef __int128 i128;
const ll linf=1e18;
ll k1,k2;
vector<ll> a;//k2在1e18内的所有次幂
void init(){
i128 tot=1;
while(true){
a.push_back(tot);
if(tot*k2<=linf)tot*=k2;
else break;
}
}
vector<i128> val;//k2所有满足的值
void dfs(int i,i128 cur){
if(i>=a.size()){
val.push_back(cur);
return;
}
dfs(i+1,cur);
dfs(i+1,cur+a[i]);
}
bool check(i128 x){
while(x){
if(x%k1>1)return false;
x/=k1;
}
return true;
}
void solve(){
for(auto x:val){
if(x<2 || x>linf)continue;
if(check(x)){
printf("YES\n%lld\n",ll(x));
return;
}
}
printf("NO");
return;
}
ll ans[15][15];
void hh(){
ans[2][3]=3;
ans[2][4]=4;
ans[2][5]=5;
ans[2][6]=6;
ans[2][7]=7;
ans[3][4]=4;
ans[3][5]=30;
ans[3][6]=36;
ans[3][7]=351;
ans[4][5]=5;
ans[4][6]=1296;
ans[4][7]=0;
ans[5][6]=6;
ans[5][7]=0;
ans[6][7]=7;
}
int main(){
hh();
cin>>k1>>k2;
if(k2>7){
init();
reverse(a.begin(),a.end());
dfs(0,0);
solve();
}
else {
if(ans[k1][k2])printf("YES\n%lld\n",ans[k1][k2]);
else printf("NO\n");
}
return 0;
}
F 小红的数组操作
思路：
其实一开始感觉有点像二维线段树的感觉，就是对每个数组用一个线段树维护一下最小值，然后得到 n n n 个最小值，再对这些最小值开一个线段树，维护最小值的最小值。
但是其实发现维护数组的最小值其实没必要用线段树，用 m u l t i s e t multiset multiset 就可以了，每次修改新值后，最小值和原本的最小值比较一下，如果变化了就在线段树上修改一下，否则就不变就行了。
code：
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
const int maxn=1e5+5;
int n,q;
vector<int> a[maxn];
multiset<int> S[maxn];
struct segment_tree{
#define ls (p<<1)
#define rs (p<<1|1)
int tr[maxn<<3],n;
void push_up(int p){
tr[p]=min(tr[ls],tr[rs]);
}
void build(int p,int l,int r){
if(l==r){
tr[p]=*S[l].begin();
return;
}
int mid=(l+r)>>1;
build(ls,l,mid);
build(rs,mid+1,r);
push_up(p);
}
void build(int _n){
n=_n;
build(1,1,n);
}
void print(int p,int l,int r){
printf("%d[%d,%d] %d\n",p,l,r,tr[p]);
if(l==r)return;
int mid=(l+r)>>1;
print(ls,l,mid);
print(rs,mid+1,r);
}
void print(){print(1,1,n);}
void modify(int p,int l,int r,int id,int x){
if(l==r){
tr[p]=x;
return;
}
int mid=(l+r)>>1;
if(id<=mid)modify(ls,l,mid,id,x);
else modify(rs,mid+1,r,id,x);
push_up(p);
}
int query(int p,int l,int r,int L,int R){
if(L<=l && r<=R){
return tr[p];
}
int mid=(l+r)>>1,ans=1e9;
if(mid>=L)ans=min(ans,query(ls,l,mid,L,R));
if(mid+1<=R)ans=min(ans,query(rs,mid+1,r,L,R));
return ans;
}
#undef ls
#undef rs
}tr;
int main(){
cin.tie(0)->sync_with_stdio(false);
cin>>n;
for(int i=1,m;i<=n;i++){
cin>>m;
a[i].resize(m);
for(int j=0;j<m;j++){
cin>>a[i][j];
S[i].insert(a[i][j]);
}
}
tr.build(n);
cin>>q;
while(q--){
int op;
cin>>op;
if(op==1){
int i,j,x;
cin>>i>>j>>x;j--;
int lst=*S[i].begin();
S[i].erase(S[i].find(a[i][j]));
S[i].insert(x);
a[i][j]=x;
if(lst!=*S[i].begin())tr.modify(1,1,n,i,*S[i].begin());
}
else {
int id;
cin>>id;
cout<<tr.query(1,1,n,1,id)<<'\n';
}
}
return 0;
}
G 小红的双排列构造
思路：
这题不难，而且很简单，构造方法很多，我用的是官方题解的构造方法。
先看怎么构造排列数最多。显然是 1 , 2 , … , n , 1 , 2 , … , n 1,2,\dots,n,1,2,\dots,n 1,2,…,n,1,2,…,n 的时候。这时任意连续的 n n n 个位置都是一个满足情况的排列，一共有 n + 1 n+1 n+1 个。
当我们给前 t t t 个位置的数翻转一下的话，变成 t , t − 1 , … , 2 , 1 , t + 1 , t + 2 , … , n , 1 , 2 , … , n t,t-1,\dots,2,1,t+1,t+2,\dots,n,1,2,\dots,n t,t−1,…,2,1,t+1,t+2,…,n,1,2,…,n，会发现 2 ∼ n + 2 2\sim n+2 2∼n+2 到 t ∼ n + t t\sim n+t t∼n+t 这 t − 1 t-1 t−1 个连续的 n n n 个数就无法组成排列了，剩余 n − t + 2 n-t+2 n−t+2 个排列。
换句话说，我们想要 k = n − t + 2 k=n-t+2 k=n−t+2 个排列，就需要把前 t = n − k + 2 t=n-k+2 t=n−k+2 个数翻转一下即可。注意 t t t 的取值范围是 1 ∼ n 1\sim n 1∼n，因此只能做出 k ∈ [ 2 , n + 1 ] k\in[2,n+1] k∈[2,n+1] 的情况。当 k = 0 , 1 k=0,1 k=0,1 的情况需要单独讨论。
当 k = 0 k=0 k=0 时，发现 n = 1 , 2 n=1,2 n=1,2 时无解，因为不管怎么排都一定会出现排列，当 n ≥ 3 n\ge3 n≥3 时可以用 1 , 1 , 2 , 2 , 3 , 3 , … , n , n 1,1,2,2,3,3,\dots,n,n 1,1,2,2,3,3,…,n,n 的方式来排列。
当 k = 1 k=1 k=1 时，可以用 1 , 1 , 2 , 3 , … , n , n , n − 1 , n − 2 , … , 2 1,1,2,3,\dots,n,n,n-1,n-2,\dots,2 1,1,2,3,…,n,n,n−1,n−2,…,2 的方式来排列。
code：
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
int n,k;
int main(){
cin>>n>>k;
if(k==0){
if(n==1 || n==2)cout<<-1;
else {
for(int i=1;i<=n;i++)
cout<<i<<" "<<i<<" ";
}
}
else if(k==1){
if(n==1)cout<<-1;
else {
cout<<1<<" ";
for(int i=1;i<=n;i++)
cout<<i<<" ";
for(int i=n;i>=2;i--)
cout<<i<<" ";
}
}
else {
int t=n+2-k;
vector<int> a;
for(int i=1;i<=n;i++)a.push_back(i);
for(int i=1;i<=n;i++)a.push_back(i);
reverse(a.begin(),a.begin()+t);
for(auto x:a)cout<<x<<" ";
}
return 0;
}