这一场打得还算可以,团队合力共A五题，凭借罚时优势排列在前面。
比赛链接：牛客多校第六场
J.Number Game（签到）
题意：给你三个数$a,b,c$以及$x$，你可以对下列两个操作进行任意次操作，请问最后是否能够达到$c=x$。
- 1) $B = A - B$
- 2) $C = B-C$
思路：自己模拟几遍发现其实就只有几种情况，比如$b$只有$a-b,b$两种，但是$c$能够造出很多种，为什么呢？我可以对于$b$的两种形态对$c$进行第二个操作。例如：
$$
c\Rightarrow (a-b)-c \Rightarrow b-(a-b)+c \Rightarrow (a-b)-b+(a-b)-c \Rightarrow \cdots
$$
就这么几种情况，最后找到规律就if即可。
代码：
#define No cout<<"No"<<endl
#define Yes {cout<<"Yes"<<endl;return;}
inline void Case_Test()
{
cin>>a>>b>>c>>x;
if (c==x||b-c==x) Yes;
if ((a-2*b!=0)&&((x-c)%(a-2*b)==0||(x+c-b)%(a-2*b)==0)) Yes;
if ((2*b-a!=0)&&((x+c-b)%(2*b-a)==0||(x-c)%(2*b-a)==0)) Yes;
No;
}
B.Eezie and Pie（树上差分）
题意：给你一颗$n$边根为$1$的树，每个点都有一个权值$a_i$，可以往跟派送$a_i$次，求每个点最多能被访问多少次。
思路：这个题一眼树上差分，具体操作请看这篇文章（填坑）。
然后需要从下往上扫，就像bfs/拓扑排序一样，当下面的点扫完之后才轮到它，进行类似前缀和的操作即可。
代码：
void Build(int x,int pre)
{
dep[x]=dep[pre]+1;
f[x][0]=pre;
for (int i=1;i<=20;i++)
f[x][i]=f[ f[x][i-1] ][i-1];
for (int i=head[x];i;i=edge[i].next)
if (edge[i].to!=pre)
Build(edge[i].to,x);
}
inline int find(int x)
{
int p = a[x];
for (int i=20;i>=0;i--)
if ((p>>i)&1) x = f[x][i];
return Max(x,1);
}//二进制拆位找祖先
inline void Case_Test()
{
for (int i=2;i<N-2;i++) lg2[i] = lg2[i>>1]+1;
n = read();
for (int i=1;i<n;i++)
{
int u,v;
u =read(); v = read();
add(u,v);add(v,u);
in[u]++;in[v]++;
}
Build(1,0);
for (int i=1;i<=n;i++)
a[i] = read();
for (int i=1;i<=n;i++)
{
int o = find(i);//找祖先
ans[i]++;
ans[f[o][0]]--;
}
queue<int> q;
for (int i=1;i<=n;i++)
if (in[i]==1) q.push(i);
while (!q.empty())
{
int x = q.front();q.pop();
ans[f[x][0]] += ans[x];
in[f[x][0]]--;
if (in[f[x][0]]==1) q.push(f[x][0]);
}
for (int i=1;i<=n;i++) cout<<ans[i]<<" ";
}
G.Icon Design（签到）
题意：输出logo...
M.Z-Game on grid（思维）
题意：给你一个$n\times m$的棋盘，由A,B,.构成，一开始棋子$(1,1)$在左上角，Alice（先）和Bob（后）进行操作。每次可以选择$(x,y)\to (x+1,y)$或者$(x,y)\to (x,y+1)$，如果当前的点是A则Alice赢，B则Bob赢，最后大家都无棋可走（到达$(n,m)$）则游戏平局。
请问Alice是否能找到一条路一定使得自己Win,Lose,Draw？他并不知道Bob如何想的。
思路：这个题的坑点主要是：如果Alice想赢，那么Bob思考的是不想让Alice赢；如果Alice想平，那么Bob思考的是不想让Alice平；如果Alice想输，那么Bob思考的是不想让Alice输。
这跟平时的博弈不同，题目问的是能否找到一条路使得一定能够，所以如果有必输的方案，那么Bob可以选择让你赢。
所以我们想到一个染色方法，这里举想赢的例子。对于当前点$(x,y)$只有$(x+1,y),(x,y+1)$能够影响到它，那么我们就从下往上，从右往左开始扫，这样保证每一个点的时候他的右边和下面都是有的。
那么如何染呢？如果当前点的两边都同为A或者B，那么该点也是这个，如何理解呢，例如两边都是A，那么到达该点之后无论是Alice动还是Bob动都是Alice赢，这个点的A的意义是这样的。
那么如果不同怎么办，两边分别各有一个？那么就需要看曼哈顿距离的奇偶。看哪个能影响的。
最后看$(1,1)$被哪个颜色染了。
那么想输的时候怎么办呢？则需要全局的A,B对调一下即可，这时候就不想让你输。
平局的时候呢？都看成一个字母就行了，因为Alice这些都不想碰到。
代码：
inline void Case_Test()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
cin>>c[i][j];
ch[i][j] = c[i][j];
}
c[n+1][m] = '.';
c[n][m+1] = '.';
for (int i=n;i>=1;i--)
{
for (int j=m;j>=1;j--)
{
if (c[i][j]!='.') continue;
int d = i+j-2;
if (i==n)
c[i][j] = c[i][j+1];
else if (j==m)
c[i][j] = c[i+1][j];
else
{
if (c[i+1][j]=='A'&&c[i][j+1]=='A')
c[i][j] = 'A';
else if (c[i+1][j]=='B'&&c[i][j+1]=='B')
c[i][j] = 'B';
else
{
if ((c[i+1][j]=='A'||c[i][j+1]=='A')&&d%2==0)
c[i][j] = 'A';
if ((c[i+1][j]=='B'||c[i][j+1]=='B')&&d%2==1)
c[i][j] = 'B';
}
}
}
}
if (c[1][1]=='A') cout<<"yes ";
else cout<<"no ";
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (ch[i][j]=='.') c[i][j] = '.';
else c[i][j] = 'B';
for (int i=n;i>=1;i--)
{
for (int j=m;j>=1;j--)
{
if (c[i][j]!='.') continue;
int d = i+j-2;
if (i==n)
c[i][j] = c[i][j+1];
else if (j==m)
c[i][j] = c[i+1][j];
else
{
if (c[i+1][j]=='A'&&c[i][j+1]=='A')
c[i][j] = 'A';
else if (c[i+1][j]=='B'&&c[i][j+1]=='B')
c[i][j] = 'B';
else
{
if ((c[i+1][j]=='A'||c[i][j+1]=='A')&&d%2==0)
c[i][j] = 'A';
if ((c[i+1][j]=='B'||c[i][j+1]=='B')&&d%2==1)
c[i][j] = 'B';
}
}
}
}
if (c[1][1]=='.') cout<<"yes ";
else cout<<"no ";
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
if (ch[i][j]=='.') c[i][j] = '.';
else if (ch[i][j]=='A') c[i][j] = 'B';
else c[i][j] = 'A';
for (int i=n;i>=1;i--)
{
for (int j=m;j>=1;j--)
{
if (c[i][j]!='.') continue;
int d = i+j-2;
if (i==n)
c[i][j] = c[i][j+1];
else if (j==m)
c[i][j] = c[i+1][j];
else
{
if (c[i+1][j]=='A'&&c[i][j+1]=='A')
c[i][j] = 'A';
else if (c[i+1][j]=='B'&&c[i][j+1]=='B')
c[i][j] = 'B';
else
{
if ((c[i+1][j]=='A'||c[i][j+1]=='A')&&d%2==0)
c[i][j] = 'A';
if ((c[i+1][j]=='B'||c[i][j+1]=='B')&&d%2==1)
c[i][j] = 'B';
}
}
}
}
if (c[1][1]=='A') cout<<"yes\n";
else cout<<"no\n";
}
A.Array（构造）
题意：这是一个有趣的构造题.
给你一个长度为$n(n\leq 10^5)$的数组$a$，满足$\Sigma _{i=1}^{n}\frac{1}{a[i]} \leq \frac{1}{2}$。需要构造出一个$b$数组，必须满足在$ b$ 的每个连续的$ a[i] $个数中存在一个等于$i$的数
思路：
先来看例如$a[1]=3$的时候
a[1] = 3的时候
构造的方式是我们找到一个最大的$x$满足，$2^x\leq a_i$，也就是不大于$a_i$的最大的二的幂。例如$7\to 4,\ 8\to 8,\ 9\to 8$。那么我们按照这个构造，例如$a[1]=3$，那么我就是变成$a[1]=2$使得其每两个则放置一个$1$。这样构造的倒数之和小于$1$。
寻找最大的这个$x$可以通过内置函数一行写出，即1 << 31 - __builtin_clz(a[i])。
然后我们得到新的$a_i$进行从小到大的排序之后,暴力放置即可。
例如现在得到的是$a[]=\lbrace 4,8,8,8,8\rbrace $。我们按顺序依次放置，如果当前有了则往下放即可，例如$5$，每次加上自己的$a[i]$即可。最后随便填写即可。
依次放置4,8,8,8,8
代码：
PII p[N];
inline void Case_Test()
{
cin>>n;
for (int i=1;i<=n;i++)
{
cin>>a[i];
p[i] = make_pair(1ll<<31 - __builtin_clz(a[i]),i);
}
sort(p+1,p+1+n);
int t = 1, maxn = 1<<18;
for (int i=1;i<=n;i++)
{
while (ans[t]) t++;//往下枚举，不回头所以O(n)
for (int j = t;j<=maxn;j+=p[i].first) ans[j] = p[i].second;//每次加上新的a[i]
}
cout<<maxn<<endl;
for (int i=1;i<=maxn;i++) cout<<Max(1,ans[i])<<" ";//0就填1
}