8
7
2015
2

NOI(plus)模拟赛T1 程序自动分析

    在开头位置%%%nbdhhzh。正是他的出现使窝们陷入了万劫不复的境地。

    咦?有点偏了。。。

    好像自己有思路的就只有第一题哦~于是我们先来看一看我们的第一题。

程序自动分析(内存限制:512MB  时间限制:1s  代码长度限制:1024KB)

【问题描述】
    在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。
    考虑一个约束满足问题的简化版本:假设 x1,x2,x3,…代表程序中出现的变量,给定   n个形如 xi=xj或  xi≠xj的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x1=x2,x2=x3,x3=x4,x1≠x4,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。
    现在给出一些约束满足问题,请分别对它们进行判定。
    如果第i个约束与之前保留的约束可以共存,那么保留它,输出YES。
    如果第i个约束与之前保留的约束冲突,那么忽略他,输出NO。
 
【输入格式】
    第1行包含1个正整数n,表示该问题中需要被满足的约束条件个数。
    接下来n行,每行包括3个整数i,j,e,描述1个相等/不等的约束条件,相邻整数之间用单个空格隔开。若e=1,则该约束条件为xi=xj;若e=0,则该约束条件为xi≠xj。
 
【输出格式】
    输出文件包括n行。
    每行是一个字符串YES或NO,表示这个约束条件是否与之前保留的约束冲突。
 
【样例输入】
5
1 2 1
1 2 0
2 3 1
2 3 0
1 3 0
 
【样例输出】
YES
NO
YES
NO
NO
 
【数据规模与规定】
  n范围 i,j范围 约定
1
1≤n≤1000
1≤i,j≤10000
e∈{0,1}
2
3
4
1≤n≤100000
5
6
7
1≤i,j≤100000000
8
9
10

    看到这题可以发现这题的形式很像NOI2015中的一题。然而好像如果(和NOI2015的那题)用一样的算法必死无疑。所以窝们要再想想。

    看到题目之后的第一反应应该是并查集吧。窝们看到了这个数据范围之后会觉得i,j很大(但还是没有黈力大),这个时候记录Father节点似乎本蒟蒻不怎么会。。。

    于是就可以看到n。。。(不错不错十分美味)发现n只有少少的100000也就是说不重复的数字出现的最多为200000!于是似乎可以<li>乱<san>搞<hua>一下。然后就可以用裸的并查集来判断元素是否相同了。至于元素不同?直接在每个并查集的最终Father节点那里记录下与它不相等的集合的最终Father子节点离散化以后的序号。。

    似乎问题就解决了。。

    然而。。判着判着似乎TLE了

3400 mars_cat 时间超限36%
405216
2004
C++ 4075 B 2015-08-05 16:22:34

    这是怎么回事呢?听说是合并集合的时候爆掉了。。就像这样!

 

while(!N[gfy].empty())
{
    N[gfx].insert(GF(*N[gfy].begin()));
    N[gfy].erase(N[gfy].begin());
}

    然后被黈力骂了

    啊。。于是就启发式合并了一下A掉了。。

 

3403 mars_cat 正确
405480
204
C++/Edit 4131 B 2015-08-05 16:51:15

最终代码如下:(请无视那些长长的读入优化。。)

 

#include <fstream>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstring>
#include <ctime>
#include <cmath>
#include <string>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
 
using namespace std;
 
#define gch getchar
#define mp make_pair
 
char C_get;
void read(int &x)
{
    for(x=0,C_get=gch();(C_get<'0'||C_get>'9')&&C_get!='-'&&C_get!='+';C_get=gch());
    if(C_get=='-')
    {
        for(C_get=gch();C_get>='0'&&C_get<='9';C_get=gch())x=x*10-C_get+'0';
    }
    else
    {
        if(C_get=='+')C_get=gch();
        for(;C_get>='0'&&C_get<='9';C_get=gch())x=x*10+C_get-'0';
    }
}
 
void read(long long &x)
{
    for(x=0,C_get=gch();(C_get<'0'||C_get>'9')&&C_get!='-'&&C_get!='+';C_get=gch());
    if(C_get=='-')
    {
        for(C_get=gch();C_get>='0'&&C_get<='9';C_get=gch())x=x*10-C_get+'0';
    }
    else
    {
        if(C_get=='+')C_get=gch();
        for(;C_get>='0'&&C_get<='9';C_get=gch())x=x*10+C_get-'0';
    }
}
 
void read(double &x)
{
    for(x=0,C_get=gch();(C_get<'0'||C_get>'9')&&C_get!='-'&&C_get!='+';C_get=gch());
    if(C_get=='-')
    {
        for(C_get=gch();C_get>='0'&&C_get<='9';C_get=gch())x=x*10-C_get+'0';
        if(C_get=='.')
        {
            double n=1;
            for(C_get=gch();C_get>='0'&&C_get<='9';C_get=gch())n/=10,x=x-(C_get+'0')*n;
        }
    }
    else
    {
        if(C_get=='+')C_get=gch();
        for(;C_get>='0'&&C_get<='9';C_get=gch())x=x*10+C_get-'0';
        if(C_get=='.')
        {
            double n=1;
            for(C_get=gch();C_get>='0'&&C_get<='9';C_get=gch())n/=10,x=x+(C_get-'0')*n;
        }
    }
}
void read(char x){x=gch();}
void read(char x[]){gets(x);}
 
int MAP[100000010];
int tt=0;
 
int n,x,y,e;
set <int> N[200010];
int F[200010];
int gfx,gfy;
 
int GF(int xx)//Get_Father
{
    if(F[xx]!=xx)
    {
        F[xx]=GF(F[xx]);
    }
    return F[xx];
}
 
int main()
{
    memset(MAP,0,sizeof(MAP));
    memset(F,0,sizeof(F));
    read(n);
    for(int i=1;i<=n;++i)
    {
        read(x); read(y); read(e);
        if(MAP[x]==0)MAP[x]=++tt,N[tt].clear();
        if(MAP[y]==0)MAP[y]=++tt,N[tt].clear();
        x=MAP[x]; y=MAP[y];
        if(!F[x])F[x]=x;
        if(!F[y])F[y]=y;
        if(e)/*x==y*/
        {
            if(x==y)
            {
                puts("YES");
                continue;
            }
            gfx=GF(x);gfy=GF(y);
            if(N[gfx].count(gfy))
            {
                puts("NO");
                continue;
            }
            if(N[gfy].count(gfx))
            {
                puts("NO");
                continue;
            }
            puts("YES");
            if(gfx==gfy)continue;
            if(N[gfy].size()>N[gfx].size())swap(gfx,gfy);
            F[gfy]=gfx;
            while(!N[gfy].empty())
            {
                N[gfx].insert(GF(*N[gfy].begin()));
                N[gfy].erase(N[gfy].begin());
            }
        }
        else/*x!=y*/
        {
            gfx=GF(x);gfy=GF(y);
            if(gfx==gfy)
            {
                puts("NO");
                continue;
            }
            puts("YES");
            N[gfx].insert(gfy);
            N[gfy].insert(gfx);
        }
    }
    return 0;
}
 
/**************************************************************
    Problem: 1935
    User: mars_cat
    Language: C++
    Result: 正确
    Time:204 ms
    Memory:405480 kb
****************************************************************/

可接受。。除了内存比较蛤蛤。。

下表截至2015-8-7 15:54
名次 RunID 用户 内存 耗时 语言 代码长度 提交时间
1 3403 mars_cat 405480 KB 204 MS C++ 4131 B 2015-08-05 16:51:15
2 3385 ljx 17196 KB 272 MS C++ 1787 B 2015-08-05 15:27:58
3 3388 zhl 20344 KB 296 MS C++ 2042 B 2015-08-05 15:38:47
4 3354 maoxiaohan 16416 KB 300 MS C++ 1868 B 2015-08-05 13:26:51
5 3456 20141104 16420 KB 308 MS C++ 2783 B 2015-08-06 09:48:16
6 3398 zenith 20344 KB 320 MS C++ 1378 B 2015-08-05 16:12:24
7 3357 hhw 17832 KB 332 MS C++ 1754 B 2015-08-05 13:27:26
8 3430 mykk 21008 KB 348 MS C++ 1326 B 2015-08-05 20:46:42
9 3454 zhzxcool 9700 KB 492 MS C++ 1860 B 2015-08-06 08:28:56
10 3460 20141109 19180 KB 604 MS C++ 1812 B 2015-08-06 11:44:47
11 3353 lbn187 19604 KB 788 MS C++ 1062 B 2015-08-05 13:25:58
[TOP]  [STATUS]

 

Category: 比赛 | Tags: | Read Count: 339
Avatar_small
hhw 说:
2015年8月07日 19:13

咦n不是100000吗。。n要是10000直接n^2暴力不就好了。。
顺便跪rank1爷


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com