CXJY-Day 1

Author Avatar
Axell 7月 29, 2019
  • 在其它设备中阅读本文章

写在前面

诚享教育培训第一天，考题据大佬说很简单。然而我2，3题都打暴力水了210…大哭，被小学大佬虐爆啦
还是好好整理下吧

连连看（link）

【题目描述】

小A玩连连看的水平已经登峰造极了，所以他想要挑战一下自己的极限，于是他决定玩一种新的规则的连连看。这种连连看只有一种棋子，但是两个棋子只有满足一定条件才能够被消除。设棋子的坐标为(Xi,Yi)，那么只有 $|X_i-X_j|+|Y_i-Y_j|=\sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2}$ 时这两个棋子才能被一起消除（消除并不需要考虑传统的连连看的规则，如果两个棋子之间有其他棋子，他们也是可以被一起消除的）。
现在小A有一个初始局面，他想要知道他需要多少步才能把这个局面全部消完。
但是这个问题太简单了，显然是n/2（n为棋子个数）或者消不完，所以他想要问问你，他能够选择的第一步有几种方法？

【输入数据】

第一行一个整数n表示棋子个数。
接下来n行每行两个整数Xi，Yi表示棋子的坐标。

【输出数据】

一个整数，表示小A的第一步有多少种方案。

【样例输入】

3
1 1
7 5
1 5

【样例输出】

2

【数据范围】

对于30%的数据，$n≤10$。
对于60%的数据，$n≤5000$。
对于100%的数据，$n≤200000$。
不会有两个棋子在同一个位置。

题解

这题还是比较水的，直接找x相同的对数或y相同的对数即可

开心农场（farm）

【题目描述】

小A在发现他在连连看的领域确实已经找不到任何挑战了之后，决定退隐江湖，把机会留给年轻人们，于是他开始去养老玩起了开心农场。
但是有一天开心农场更新了之后，就不再是小A以前的那个开心农场了。
农场的一片片田地，被摆成了树的样子，每两块田间有且仅有一条路径了。
而且农作物的种类也大大增多，搞得小A这个开心农场的新手眼花缭乱，不知道自己应该种什么，而收菜时也不知道自己哪里的菜好了，记得的熟了的菜也忘了种在哪里。
为了帮助自己增强记忆力，小A决定考考自己，问问自己每棵子树内部分别有多少种蔬菜，因为是考试性质的检验，所以肯定是不按照顺序问的。

【输入数据】

第一行三个整数n，q，type表示田地的块数，询问个数和数据种类。
第二行n个整数表示每块田内种的蔬菜的种类。
接下来n-1行两个整数x，y表示x与y之间有一条边。
接下来q行每行一个整数x，表示询问x的子树内有多少种蔬菜，若$type=0$，则x需异或上上一问的答案（第一次默认上一次答案为0）。

【输出数据】

输出q行每行一个数字表示x子树内蔬菜的种类。

【样例输入】

10 10 1
10 3 1 7 8 1 7 5 9 10 
4 5
8 5
9 5
2 5
6 5
10 4
3 8
1 5
7 10
6
1
10
9
6
8
1
6
1
10

【样例输出】

1
7
2
1
1
2
7
1
7
2

【数据范围】

C为蔬菜的种类。 有20%的数据，$n,q≤20$。
有20%的数据，$n,q≤1000$。
有20%的数据，树是一条链（并不一定以1为链的一个端点）。
有20%的数据，树是随机的。
对于100%的数据，$n,q≤100000,c≤1000000000$。
有50%的数据$type=1$，即x不需要异或上一问的答案。
且这50%每20%的数据中都有一半。
默认以1为树的根。

题解

考场上想了半天，很接近正解了，，，
主要思路是一个节点的颜色只对它的父亲们生效，因此一旦他的父亲已经回溯了，这个点存在的意义便没有了（如果有其它一样颜色的点可以直接接管他）
因此只要在dfs中，节点回溯时

  1. 用该节点替换前一个一样颜色的节点（前一个节点剩余价值没有了，直接用该节点替换可以防止重复统计），即该点权值=1，前一个点权值=0
  2. 计算此节点的子树和，即为该点答案
  3. 计算子树和时，可以用节点的dfs序作为下标，建立线段树，x的子树就是$[dfn_x,dfn_x+size_x-1]$，同样前面的更改操作也是在线段树上完成的（树状数组也可）
#include <bits/stdc++.h>
using namespace std;
#define lc (rt<<1)
#define rc ((rt<<1)|1)
struct node{
    int Next,y;
}Pth[200005];
int head[100005],cnt;

inline void add(int x,int y){
    cnt++;
    Pth[cnt]={head[x],y};
    head[x]=cnt;
}

int n,q,ty,m,raw[100005],a[100005],tr[400005];
void update(int wt,int v,int rt,int l,int r){
    if (l==r){
        tr[rt]+=v;
        return;
    }
    int mid=(l+r)>>1;
    if (wt<=mid) update(wt,v,lc,l,mid);
    else update(wt,v,rc,mid+1,r);
    tr[rt]=tr[lc]+tr[rc];
}
int query(int wl,int wr,int rt,int l,int r){
    if (l==wl && r==wr){
        return tr[rt];
    }
    int mid=(l+r)>>1;
    if (wr<=mid) return query(wl,wr,lc,l,mid);
    else if (wl>mid) return query(wl,wr,rc,mid+1,r);
    else return query(wl,mid,lc,l,mid)+query(mid+1,wr,rc,mid+1,r);
}

int last[100005];
int num,dfn[100005],size[100005],ans[100005];
void dfs(int x,int pr){
    dfn[x]=++num; size[x]=1;
    for (int i=head[x];i;i=Pth[i].Next){
        int y=Pth[i].y;
        if (y==pr) continue;
        dfs(y,x);
        size[x]+=size[y];
    }
    update(dfn[x],1,1,1,n);
    if (last[a[x]]) update(last[a[x]],-1,1,1,n);
    last[a[x]]=dfn[x];
    ans[x]=query(dfn[x],dfn[x]+size[x]-1,1,1,n);
}

int main(){
    freopen("farm.in","r",stdin);
    freopen("farm.out","w",stdout);
    cin>>n>>q>>ty;
    for (int i=1;i<=n;++i){
        scanf("%d",&raw[i]);
        a[i]=raw[i];
    }
    sort(raw+1,raw+n+1);
    m=unique(raw+1,raw+n+1)-raw-1;
    for (int i=1;i<=n;++i){
        a[i]=lower_bound(raw+1,raw+m+1,a[i])-raw;
    }
    for (int i=1;i<n;++i){
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y); add(y,x);
    }
    dfs(1,0);
    int la=0;
    for (int i=1;i<=q;++i){
        int x; scanf("%d",&x);
        if (ty==0) x^=la;
        printf("%d\n",ans[x]);
        la=ans[x];
    }
    return 0;
}

祖玛（zuma）

【题目描述】

小A在玩开心农场时，发现很多时间他都在等待菜熟而不是在收菜，于是他决定把这些时间利用起来，他找到了另外一个游戏，祖玛。
通过他的游戏天赋，很快，他又精通了这个游戏，想要寻求挑战的他又开始研究起了这个游戏的变种。
然而因为祖玛这个游戏规则太过于简单，所以没有什么好变的，所以小A就只能在祖玛这个游戏上下功夫了。
小A女朋友生日前，小A想弄一条珠子序列来给他女朋友做生日礼物，但是因为他的要求中既有颜色又有顺序，所以实现难度很高，竟然达到了小A都无法完成的地步，所以心里有着一股执念的小A决定开挂来调出这个序列。
然而小A因为游戏能力过于高超导致了他开挂的能力很差，竟然只能改变珠子的顺序，还只能把一样颜色的放一起，颜色之间还有一定的大小顺序，现在有他当前的序列，以及他想要的序列，请问小A有机会得到他想要的序列吗？
简单题意：你有两个序列A，B，一个操作是将你选择的一个区间递增排序，请问是否能将A序列用若干个操作修改为B序列。

【输入数据】

第一行一个整数T，表示数据组数。
每一组数据第一行一个整数n，表示序列长度。
第二行n个整数，表示序列A。
第三行n个整数，表示序列B。

【输出数据】

每组数据输出”Yes”或”No”，每组数据占一行。

【样例输入】

3
8
4 6 3 3 3 2 1 6 
4 6 3 3 2 3 1 6 
8
2 3 5 3 5 8 6 8 
3 3 5 5 8 8 6 2 
8
8 1 6 8 4 3 1 5 
8 1 6 8 1 4 3 5

【样例输出】

Yes
No
Yes

【数据范围】

对于100%的数据，$1≤T≤3$。
对于20%的数据，$1≤n≤8$。
对于另20%的数据，$1≤n≤1000$。
对于另20%的数据，数字仅有$1,2$两种。
对于另20%的数据，数字范围为$[1,100]$。
对于100%的数据，$1≤n≤100000$,数字范围为$[1,n]$。

题解

这题的思路挺重要的
首先看小数据（只有1，2时），可以发现只能1往前，因此记一下前缀和，只有当a的前缀和始终小于等于b的前缀和序列时才可行
由此可以发现，所有移动的操作都可以单独进行，即类似于冒泡排序，每次相邻两个之间排序，完成调换
例如要把$a_i$移到$j,j \lt i$，可以依次如下调换$(i,i-1),(i-1,i-2)…,(j+1,j)$，前提是$min[a_{j},a_{i}]=a_i$即$a_i$是最小值，否则一定过不去
首先考虑$b_1$，必须是由$a_x=b_1$且x最小移过来的，所以检查$a[1,x]$的最大值是否为$a_x$，如果不是就判否
然后把$a_x$置为无穷，即删除该元素，再找和$b_2$相等的，以此类推，反复检查
其中找最小值可以直接用线段树，查找相同值可以用set（其实两者合起来可以用权值线段树+multiset，判断改为检查权值$[1,a_x-1]$中最小下标是不是在$1,x$之间即可）

#include <bits/stdc++.h>
using namespace std;
#define lc (rt<<1)
#define rc ((rt<<1)|1)

int n,a[100005],b[100005],tr[400005];
set <int> s[100005];

void build(int rt,int l,int r){
    if (l==r){
        tr[rt]=a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(lc,l,mid);
    build(rc,mid+1,r);
    tr[rt]=min(tr[lc],tr[rc]);
}

int query(int wl,int wr,int rt,int l,int r){
    if (wl==l && wr==r){
        return rt[tr];
    }
    int mid=(l+r)>>1;
    if (wr<=mid) return query(wl,wr,lc,l,mid);
    else if (wl>mid) return query(wl,wr,rc,mid+1,r);
    else return min(query(wl,mid,lc,l,mid),query(mid+1,wr,rc,mid+1,r));
}

void update(int p,int rt,int l,int r){
    if (l==r){
        tr[rt]=0x3f3f3f3f;
        return;
    }
    int mid=(l+r)>>1;
    if (p<=mid) update(p,lc,l,mid);
    else update(p,rc,mid+1,r);
    tr[rt]=min(tr[lc],tr[rc]);
}

void solve(){
    cin>>n;
    for (int i=1;i<=n;++i) s[i].clear();
    for (int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        s[a[i]].insert(i);
    }
    for (int i=1;i<=n;++i){
        scanf("%d",&b[i]);
    }
    memset(tr,0x3f,sizeof tr);
    build(1,1,n);
    for (int i=1;i<=n;++i){
        int index=*s[b[i]].begin();
        s[b[i]].erase(s[b[i]].begin());
        int c=query(1,index,1,1,n);
        if (c!=b[i]){
            puts("No");
            return;
        }
        update(index,1,1,n);
    }
    puts("Yes");
}

int main(){
    freopen("zuma.in","r",stdin);
    freopen("zuma.out","w",stdout);
    int t; cin>>t;
    while (t--) solve();
    return 0;
}

其他

剩下一些没有消化的知识回去慢慢消化，主要是数据结构一类的，联赛可能没用，先记下来再说吧

  1. 队列，栈，优先队列，线段树，树状数组（已学过）
  2. 主席树
  3. 可持久化线段树
  4. 可持久化并查集
  5. 权值线段树
  6. 树套树
  7. 动态开点线段树&线段树合并
  8. 分块&莫队优化
  9. Manacher（回顾）
  10. 线性表，RMQ（回顾）

以及要做的题，都是黑题啊…

  • BZOJ4777 Switch Crass
  • BZOJ3932 任务查询系统
  • TJO2016 序列
  • BZOJ3674
  • BZOJ1104 POI2007
  • BZOJ2002 HNOI2010 弹飞绵羊
  • BZOJ3289 Mato的文件管理
  • BZOJ3790 神奇项链
  • 区间第k值

知识共享许可协议
本作品采用知识共享署名-非商业性使用-相同方式共享 3.0 未本地化版本许可协议进行许可。
本文链接：https://hs-blog.axell.top/archives/cxjy-day-1/