# [【LGR-150-Div.2】洛谷 8 月月赛 I & RiOI Round 2](https://www.luogu.com.cn/contest/122184)
## T1 [P9496 「RiOI-2」hacker](https://www.luogu.com.cn/problem/P9496?contestId=122184)
$100pts$
### 题目描述
有两种操作，$「ACCEPT」$与$「BOTH」$，均花费 $1$ 代价。$「ACCEPT」$将 $n$ 二进制 按位或 一个正整数。$「BOTH」$将 $n$ 二进制 按位与 一个正整数。两种操作均可使用多次（或不用），请求出将 $n$ 变为 $m$ 最小的代价。
[帮助：什么是按位与和按位或](https://oi-wiki.org/math/bit)
- 水题，但是本蒟蒻一开始用 $scanf$ 输入 $long long$ 没有用 $"\%ld"$ 然后 $WA$ 了两个点。
- 将 $n$ 和 $m$ 转化为二进制，用两个数组分别存起来，再枚举。
- 若 $n$ 表示为 $0$，$b$ 表示为1，则进行$「ACCEPT」$操作。
- 若 $m$ 表示为 $1$，$b$ 表示为0，则进行$「BOTH」$操作。
```cpp
#include<bits/stdc++.h>
using namespace std;
long long int n,sum=0;
long long int x,y;
long long int a[100],b[100];
int main()
{
long long int i,j,m,t;
scanf("%ld",&t);
while(t--)
{
sum=0;
scanf("%ld%ld",&n,&m);//scanf输入long long需要 "%ld"
if(n==m)
{
printf("%d\n",0);
continue;
}
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
int cnt=0,res=0;
int cn=0,cm=0;
x=n,y=m;
while(x)
{
a[++cnt]=x%2;
x/=2;
}
while(y)
{
b[++res]=y%2;
y/=2;
}
for(i=1;i<=max(cnt,res);i++)
{
if(a[i]==1&&b[i]==0)cn=1;
if(a[i]==0&&b[i]==1)cm=1;
}
printf("%d\n",cn+cm);
}
}
```
## T2 [P9497 「RiOI-2」weight](https://www.luogu.com.cn/problem/P9497?contestId=122184)
$100pts$
### 题目描述
给定一个 $n$ 行 $n$ 列 的矩阵 $a$。
有 $q$ 组询问，每次给定一个 $v$，请将矩阵每一行任意重排（可以不重排），最大化最大值不小于 $v$（也就是说，至少有一个不小于 $v$ 的数）的列数。请输出这个列数。
询问之间相互独立。换言之，每次询问前可以重新排列。
- 还是水题，将二维矩阵压成一位数组，输入后再从大到小 $sort$ 一遍，每次询问时，从 $1$ 到 $n$ 中寻找第一个小于 $v$ 的数，如果都大于等于 $v$ 则，输出 $n$ 。
- 一开始没看懂题目，以为是把每行从大到小排列。
- 改过来之后，发现输出都是 $0$ ，但本蒟蒻没想太多就交上去了，但是竟然 $AC$ 了，才想起来电脑是$32$位，$long long$ 显示为$0$。
```cpp
#include<bits/stdc++.h>
using namespace std;
long long int n,q,a[1010001];
long long int maxx[1001];
bool cmp(long long int x,long long int y)
{
return x>y;
}
int main()
{
int i,j;
cin>>n>>q;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%ld",&a[(i-1)*n+j]);
stable_sort(a+1,a+1+n*n,cmp);
for(i=1;i<=n;i++)maxx[i]=a[i];
long long int w;
for(i=1;i<=q;i++)
{
int flag=0;
scanf("%ld",&w);
for(j=1;j<=n;j++)
{
if(maxx[j]<w)
{
printf("%ld\n",j-1);
flag=1;
break;
}
}
if(!flag)printf("%ld\n",n);
}
}
```
## T3 [P9498 「RiOI-2」equals](https://www.luogu.com.cn/problem/P9498?contestId=122184)
$100pts$
### 题目描述
给定一棵 $n$ 个结点，以 $1$ 为根的树，定义一个结点的深度 $d_i$ 表示它到根结点的简单路径上的结点个数。
你需要给每个结点黑白染色，满足黑色结点的深度和等于白色结点的深度和。设 $c_i = \{0, 1\}$ 分别代表编号为 $i$ 的结点为黑色或白色，那么这即 $\displaystyle\sum_{c_i=0}d_i=\sum_{c_i=1}d_i$。
若无解，仅输出一行一个整数 $-1$。
- 本蒟蒻一开始打算用邻接矩阵存边，但是...
### 数据规模与约定
| $\rm Subtask$ | 分值 | $n\le $ | 特殊性质 |
| :-----------: | :--: | :-----: | :------: |
| $0$ | $5$ | $20$ | / |
| $1$ | $15$ | $500$ | / |
| $2$ | $20$ | $5\times 10^3$ | / |
| $3$ | $10$ | / | $n$ 为偶数 |
| $4$ | $5$ | / | 树为菊花图（不保证根为菊花中心） |
| $5$ | $5$ | / | 树为一条链（不保证根为链的端点） |
| $6$ | $40$ | / | / |
斜杠表示这一栏无特殊限制。
对于 $100\%$ 的数据，$1\le n\le 10^6$，$1\le u_i,v_i\le n$，输入数据构成一棵树。
- 由于$1\le n\le 10^6$，所以改用链式前向星存边。
- $dfs$ 一遍得出深度，由于黑点、白点的深度和要相等，所以想到前几天做的分钱，于是用$dp$判断是否有解。
- 但是如果有解需要输出点的状态，而本蒟蒻不会记录路径，因此放弃了$dp$。
- 放弃了$dp$，考虑爆搜，打搜索。因为爆搜超时，开始一分没骗到，然后剪枝得了$85$
之后想到折半搜索，但是本蒟蒻只会折半，因此分了两个$for$循环，第一个从$1$循环到$(n+1)/2$
第二个从$(n+1)/2$循环到$n$。(~~但应该不是正解~~)。然后$AC$......
### (~~出题人的数据怎么如此之氵，把爆搜都放过去了~~)...
[测评记录](https://www.luogu.com.cn/record/119207366)
```cpp
#include<bits/stdc++.h>
using namespace std;
long long int dep[6000001],vis[6000001];
long long int n,sum=0;
struct ee
{
int next,to;
}e[6000001];
int head[6000001],cnt=0;
void add(int u,int v)
{
e[++cnt]={head[u],v};
head[u]=cnt;
}
void dfs(int x)
{
int i;
vis[x]=1;
for(i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(!vis[v])
dep[v]=dep[x]+1,dfs(v);
}
}
bool pd[6000001];
void search(int x,long long int s)
{
int i,j;
if(s==(sum/2))
{
for(j=1;j<=n;j++)
{
if(pd[j])printf("%d ",1);
else printf("%d ",0);
}
exit(0);
}
for(i=x;i<=(n+1)/2;++i)
{
if(!pd[i]&&s+dep[i]<=(sum/2))
{
pd[i]=1;
if(s+dep[i]==(sum/2))
{
for(j=1;j<=n;j++)
{
if(pd[j])printf("%d ",1);
else printf("%d ",0);
}
exit(0);
}
if(s+dep[i]<(sum/2))
search(i+1,s+dep[i]);
pd[i]=0;
}
}
for(i=(n+1)/2;i<=n;++i)
{
if(!pd[i]&&s+dep[i]<=(sum/2))
{
pd[i]=1;
if(s+dep[i]==(sum/2))
{
for(j=1;j<=n;j++)
{
if(pd[j])printf("%d ",1);
else printf("%d ",0);
}
exit(0);
}
if(s+dep[i]<(sum/2))
search(i+1,s+dep[i]);
pd[i]=0;
}
}
}
int main()
{
int i,j,m,x,y;
scanf("%d",&n);
for(i=1;i<n;i++)scanf("%d%d",&x,&y),add(x,y),add(y,x);
dep[1]=1;
dfs(1);
for(i=1;i<=n;++i)sum+=dep[i];
if(sum%2==1)
{
printf("%d",-1);
return 0;
}
search(1,0);
printf("%d",-1);
}
```
## T4 [P9499 「RiOI-2」change](https://www.luogu.com.cn/problem/P9499?contestId=122184)
$20pts$
- 本蒟蒻不会打，骗了20分。。。