考试策略

T1->T2->T5->T4->T3这样的吧,除了T3以外的题目都还是很水滴!只不过忽然对T4的32M空间表示疑惑了一下子而已。
经验和教训
这次考试没有什么特别的感悟,就是平时练好就行了,考试的时候发散思维,难题能想到就想到,不能想到就拿稳暴力分。
这次考试总之还是很水滴,boshi大佬早早做完题就开始写作业了QAQ

T1

期望得分:100 实际得分:100
题目描述
若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。
规定:x和y是亲戚,y和z是亲戚,那么x和z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。
数据输入:
第一行:三个整数n,m,p,(n小于等于5000,m小于等于5000,p小于等于5000),分别表示有n个人,m个亲戚关系,询问p对亲戚关系。
以下m行:每行两个数Mi,Mj,1<=Mi,Mj<=N,表示Ai和Bi具有亲戚关系。
接下来p行:每行两个数Pi,Pj,询问Pi和Pj是否具有亲戚关系。
解题思路
并查集裸题。
代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m,p;
int f[5005];
int find(int x){
    if(x==f[x])return x;
    f[x]=find(f[x]);return f[x];
}
int main()
{
    freopen("relation.in","r",stdin);
    freopen("relation.out","w",stdout);
    int x,y,i,r1,r2;
    n=read(),m=read(),p=read();
    for(i=1;i<=n;++i)f[i]=i;
    for(i=1;i<=m;++i){
        x=read(),y=read();
        r1=find(x),r2=find(y);
        if(r1!=r2)f[r1]=r2;
    }
    for(i=1;i<=p;++i){
        x=read(),y=read();
        if(find(x)==find(y))printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

T2

期望得分:100 实际得分:100
题目描述
众所周知,香港的黑社会组织猖獗,警方希望能摸清他们的内部构成情况,特派小生前往调查。经过长期的卧底,小生初步获得了一些资料:整个组织有n个人,任何两个认识的人不是朋友就是敌人,而且满足:①我朋友的朋友是我的朋友;②我敌人的敌人是我的朋友。所有是朋友的人组成一个团伙。现在,警方委派你协助调查,拥有关于这n个人的m条信息(即某两个人是朋友,或某两个人是敌人),请你计算出这个城市最多可能有多少个团伙。
数据范围:2≤N≤2000,1≤M≤5000。
输入数据:第一行包含一个整数N,第二行包含一个整数M,接下来M行描述M条信息,内容为以下两者之一:“F x y”表示x与y是朋友;“E x y”表示x与y是敌人(1≤x≤y≤N)。
输出数据:包含一个整数,即可能的最大团伙数。
题目分析
补集思想,每个人有两个并查集,一个代表其朋友集,一个代表其敌人集。如果两个人A和B是敌人,则把A的朋友集和B的敌人集合并,把B的敌人集和A的朋友集合并。如果两个人是朋友,就合并他们的朋友集。最后数一数一共有多少个集合即可。
代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
int read(){
    int q=0;char ch=' ';
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
    return q;
}
int n,m,ans;
int f[4005],vis[4005];
int find(int x){
    if(x==f[x])return x;
    f[x]=find(f[x]);return f[x];
}
int main()
{
    freopen("gangs.in","r",stdin);
    freopen("gangs.out","w",stdout);
    int i,r1,r2,x,y;char ch[5];
    n=read(),m=read();
    for(i=1;i<=n*2;++i)f[i]=i;
    for(i=1;i<=m;++i){
        scanf("%s",ch);x=read(),y=read();
        if(ch[0]=='E'){
            r1=find(x),r2=find(y+n);
            if(r1!=r2)f[r1]=r2;
            r1=find(x+n),r2=find(y);
            if(r1!=r2)f[r1]=r2;
        }
        else {
            r1=find(x),r2=find(y);
            if(r1!=r2)f[r1]=r2;
        }
    }
    for(i=1;i<=n;++i){
        r1=find(i);
        if(!vis[r1])vis[r1]=1,++ans;
    }
    printf("%d",ans);
    return 0;
}

T3

期望得分:30 实际得分:55
错误原因:因为太蠢了没有想到怎么做,虽然与点连接坐标的并查集这样的思路擦边,但是没有细想。于是写了个离散化+哈希,暴力查找可以获得的新点,哈希确定能否添加。本来只想拿30分暴力分,结果因为哈希复杂度与数据强度有关,迷一般的拿了55…
题目描述
给定平面 n 个黑点,如果平面一个边平行于坐标轴的矩形 3 个角是黑色的那么就把那个矩形的第 4 个角改成黑色,最后平面上将会有多少个黑点
30%的数据 n小于等于100,100%的数据 n小于等于$2*10^5$
坐标绝对值小于等于1e9
题目分析
首先离散化。
然后对于每一个点,将其横坐标和纵坐标加入并查集,最后答案就是所有并查集中横坐标数量*纵坐标数量。
为什么呢?画个图搞一搞应该可以明白,每个并查集的横坐标和纵坐标搭配出的点都是黑的。
汗!这种题目讲不清楚啊!
代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<climits>
using namespace std;
#define LL long long
const int N=400005;
int f[N<<1],s1[N],s2[N];
int xx[N],yy[N],a[N],b[N];
int n,t1=1,t2=1;LL ans;
int find(int x){
    if(x==f[x])return x;
    f[x]=find(f[x]);return f[x];
}
void work(){
    int i,r1,r2;
    for(i=1;i<=t1;++i)f[i]=i,s1[i]=1;
    for(i=1;i<=t2;++i)f[i+t1]=i+t1,s2[i+t1]=1;
    for(i=1;i<=n;++i){
        xx[i]=lower_bound(a+1,a+1+t1,xx[i])-a;
        yy[i]=lower_bound(b+1,b+1+t2,yy[i])-b;
        r1=find(xx[i]),r2=find(yy[i]+t1);
        if(r1!=r2)f[r1]=r2,s1[r2]+=s1[r1],s2[r2]+=s2[r1],s1[r1]=0,s2[r1]=0;
    }
    for(i=1;i<=t1+t2;++i)
        if(find(i)==i)ans+=(LL)s1[i]*s2[i];
}
int main()
{
    freopen("filling.in","r",stdin);
    freopen("filling.out","w",stdout);
    int i;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d%d",&xx[i],&yy[i]);
        a[i]=xx[i],b[i]=yy[i];
    }
    sort(a+1,a+1+n),sort(b+1,b+1+n);
    for(i=2;i<=n;++i)
        if(a[i]!=a[t1])a[++t1]=a[i];
    for(i=2;i<=n;++i)
        if(b[i]!=b[t2])b[++t2]=b[i];
    work();printf("%lld",ans);
    return 0;
}

T4

期望得分:100 实际得分:100
题目描述
由于机器人工作速度惊人,基地很快竣工,科学家来到Smauel星上玩起了格字游戏,这是有两人队战的游戏:
两人轮流在一个n*n (n 小于等于1000)的棋盘上连边(每次只能连两条相邻的边),谁先连出一个连通的图形谁就赢了,此时游戏结束。
由于图形太大科学家下了很久以后不知道到底是谁赢了,于是他们又需要你的帮助。
现在给你他们连边的次数m(m小于等于100000)和位置,你需要判断游戏什么时候结束。
题目分析
一次连线相当于把两个格点加入一个并查集,如果要连的两个格点已经处于同一个并查集了,则连出了连通图形,游戏结束。
代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
const int N=1000005;
int n,m;
int f[N];
int find(int x){
    if(f[x]==x)return x;
    f[x]=find(f[x]);return f[x];
}
int main()
{
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int i,r1,r2,x,y,xx,yy;char ch[5];
    scanf("%d%d",&n,&m);
    for(i=1;i<=n*n;++i)f[i]=i;
    for(i=1;i<=m;++i){
        scanf("%d%d%s",&xx,&yy,ch);
        x=(xx-1)*n+yy;
        if(ch[0]=='R')y=x+1;
        else y=xx*n+yy;
        r1=find(x),r2=find(y);
        if(r1!=r2)f[r1]=r2;
        else {printf("%d",i);return 0;}
    }
    printf("-1");
    return 0;
}

T5

期望得分:100 实际得分:100
题目描述
众所周知,我们的lyp神犇外号叫Altman,的确,在另一个平行宇宙,lyp神犇就是一个——Altman。
有一天,lyp神犇遇到了另一个平行宇宙中的他,得知了在其他的宇宙中,Altman是存在的,那么,怪兽也是存在的咯。
作为一个有名的oier,lyp神犇想要统计一下各个宇宙中怪兽的战斗力,他发现,一些怪兽在不同的宇宙都出现过(!. !,难不成怪兽不穿越,算了,不管了),每一个Altman都提供给lyp一些信息,告诉他一个怪兽比另一个怪兽的战斗力大多少(这个数可以是负数)。
Altman神犇为了给你以表现机会,将这些信息都给你,并会时不时地问你两个怪兽之间谁更强。
假设Altman们提到了怪兽都按1~n编号。
Altman们的信息的格式是 X A B C
其中x固定为1,A,B是两个1~n的整数,表示怪兽编号,A怪兽的战斗力比B怪兽的战斗力大C(C为整数),保证信息之间不矛盾。
Lyp的询问的格式是:Y A B
Y 固定为2,A,B是怪兽编号,属于1~n,如果A比B 强,输出A;如果B比A强,输出B,如果无法判断或怪兽们一样强,输出0
题目分析
带权并查集,如果B的战斗力比A大3,那么就连成如图所示:

然后路径压缩,比较两个怪兽代表的节点距离根节点的长度即可判断谁比较强,不在同一并查集则无法判断。
代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cstring>
using namespace std;
const int N=30005;
int n,m;
int f[N],d[N];
int find(int x){
    if(f[x]==x)return x;
    int t=f[x];
    f[x]=find(f[x]),d[x]+=d[t];
    return f[x];
}
int main()
{
    freopen("lyp.in","r",stdin);
    freopen("lyp.out","w",stdout);
    int i,bj,x,y,w,r1,r2;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;++i)f[i]=i;
    for(i=1;i<=m;++i){
        scanf("%d",&bj);
        if(bj==1){
            scanf("%d%d%d",&x,&y,&w);
            r1=find(x),r2=find(y);
            if(r1!=r2)f[r1]=r2,d[r1]=d[y]-d[x]+w;
        }
        else {
            scanf("%d%d",&x,&y);
            r1=find(x),r2=find(y);
            if(r1!=r2)printf("0\n");
            else if(d[x]==d[y])printf("0\n");
            else if(d[x]>d[y])printf("%d\n",x);
            else if(d[x]<d[y])printf("%d\n",y);
        }
    }
    return 0;
}
分类: 文章

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *