赛后——1.25 寒假模拟3
\(T1\ \text{Scape}\)
题意
一条街上有 \(n\) 家店，第 \(i\) 家店提供 \(w_i\) 单位的食物。
\(\text{Scape}\) 喜欢吃吃吃，但 \(\text{Scape}\) 肚子的最大容量只有 \(c\) 单位。
\(\text{Scape}\) 可以选择任意一家点作为起点开始向右走（吃），每经过一家店（假设是第 \(i\) 家），只要他的肚子里还有剩余容量，就会忍不住吃掉 \(w_i\) 单位的事物（如果没有剩余容量就不会吃而是继续向右走）。
\(\text{Scape}\) 想最大化吃过店的数量，求这个数量。
数据范围：\(n \le {10}^3,1\le c\le {10}^6\)
思路
发现吃与不吃是没有选择的，考虑贪心，暴力扫一遍即可。
代码
int n,c;
int w[1005];
int ans,maxx;
int main(){
n=read(),c=read();
for(int i=1;i<=n;i++){
w[i]=read();
}
for(int i=1;i<=n;i++){
maxx=0;
for(int j=i,k=c;j<=n&&k;j++){
if(k>=w[j]){
k-=w[j];
maxx++;
}
}
ans=max(ans,maxx);
}
printf("%d\n",ans);
return 0;
}
\(T2\ \text{And}\)
题意
给出一个 \(n\times n\) 的表格 \(X_{i,j}\)，\(X_{i,j}=A_i \operatorname{and} A_j\)，\(A\)是是一个长度为 \(n\) 的未知数列。
但是不幸的是 \(X_{i,i}\) 的值全部丢失了（因此读入的 \(X_{i,i}\) 没有任何意义），你需要求一个合法的 \(A\)。
数据范围：\(n\le {10}^3\)
提示：本题 \(\operatorname{SPJ}\)
思路
因为与运算没有逆运算，考虑构造任意一组合法数据。将每一个与运算的结果二进制拆分后若与第 \(i\) 个数相关的第 \(j\) 位数与运算结果中有一个 \(1\)，则该数在第 \(j\) 位一定为 \(1\)，以此类推构造即可。
代码
int n;
int x[1005][1005];
int a[1005];
int main(){
n=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
x[i][j]=read();
}
}
for(int k=0;k<=30;k++){
for(int i=1;i<=n;i++){
bool pd=0;
for(int j=1;j<=n;j++){
int sit=x[i][j]&(1<\(T3\ \text{Dist}\)
题面
有一棵 \(n\) 个点的 \(k\) 叉树，点的编号 \(1\cdots n\)，它的结构描述如下：
- \(1\) 号点为根节点，如果一个点到 \(1\) 号点经过的最少边数为 \(i\) 则称它在第 \(i\) 层里。
- 第 \(i\) 层的第 \(j\) 个点的父亲是第 \(i-1\) 层的第 \(\lfloor(j-1)/k\rfloor+1\) 个点。
- 第 \(i\) 层的第 \(j\) 个点的编号是 \(\sum_{p=0}^{i-1} (k^p) +j\)。
- 从第三条性质可以看出，这是一个完全 \(k\) 叉树。
\(q\) 次询问，每次询问树上点 \(x\) 到点 \(y\) 的距离（经过的最少边数）。
思路
一眼树链剖分（大雾）。
只需要跳祖先即可，这里可以将编号全部 \(-1\)，这样在操作时，编号为 \(i\) 的点的父亲编号为 \((i-1)/k\)，直到跳到公共祖先为止。
代码
ll n,k,q;
int main(){
n=read(),k=read(),q=read();
while(q--){
ll x=read()-1,y=read()-1;
int cnt=0;
while(x!=y){
if(x>y){
x=(x-1)/k;
}
else{
y=(y-1)/k;
}
cnt++;
}
printf("%d\n",cnt);
}
return 0;
}
\(T4\ \text{Path}\)
题面
有一棵 \(n\) 个点的树，数的边上有权值，定义一个路径是好的，当且仅当这条路径上所有边的权值异或和等于 \(0\)，（\(u\) 到 \(v\) 的路径与 \(v\) 到 \(u\) 的路径被视作是相同的路径）。
现在要按照一个次序把这颗树里的所有边删掉，请输出所有删除操作开始前这棵树的好路径数以及每次删除操作后的好路径数。
思路
正序删边等价于方向删边。—— by APJ
可以发现的是，维护出到根结点的异或和，就能得到任意路径的异或和。
用 \(map\) 作为桶维护即可。
代码
int n;
struct edge{
int to,nxt,w;
}e[maxn];
struct node{
int from,to,w;
}E[maxn];
int head[maxn],cnt;
int xorsum[maxn];
inline void add_edge(int u,int v,int w){
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].nxt=head[u];
head[u]=cnt;
}
inline void dfs(int u,int fa){
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(v==fa) continue;
xorsum[v]=xorsum[u]^e[i].w;
dfs(v,u);
}
}
int del[maxn],fa[maxn];
map mp[maxn];
inline int find(int x){
if(fa[x]==x) return fa[x];
return fa[x]=find(fa[x]);
}
ll ans[maxn],ansx;
int main(){
n=read();
for(int i=1;i=0;i--){
int u=E[del[i]].from,v=E[del[i]].to,w=E[del[i]].w;
u=find(u),v=find(v);
if(mp[u].size()>mp[v].size()) swap(u,v);
fa[u]=v;
for(map::iterator j=mp[u].begin();j!=mp[u].end();j++){
ansx+=(ll)(mp[v][j->first]*j->second);
mp[v][j->first]+=j->second;
}
ans[i]=ansx;
}
for(int i=1;i<=n;i++){
printf("%lld\n",ans[i]);
}
return 0;
}