「CF685X」Codeforces Round #360 (Div. 1)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
bool flag;
int n,m;
int c[100005];
vector<int>a[2],e[100005];
void dfs(int x,int t)
{
    if(c[x]!=-1)
    {
        if(c[x]!=t)flag=1;
        return;
    }
    c[x]=t;
    a[t].push_back(x);
    for(int i=0;i<e[x].size();i++)
        dfs(e[x][i],t^1);
}
int main()
{
    memset(c,-1,sizeof(c));
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read();
        e[u].push_back(v);
        e[v].push_back(u);
    }
    for(int i=1;i<=n;i++)
        if(c[i]==-1)dfs(i,1);
    if(flag)puts("-1");
    else 
    {
        for(int x=0;x<=1;x++)
        {
            printf("%d\n",a[x].size());
            for(int i=0;i<a[x].size();i++)                
                printf("%d ",a[x][i]);
            puts("");
        }
    }
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<vector>

#include<algorithm>

#include<map>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

bool flag;

int n,m;

int c[100005];

vector<int>a[2],e[100005];

void dfs(int x,int t)

{

if(c[x]!=-1)

{

if(c[x]!=t)flag=1;

return;

}

c[x]=t;

a[t].push_back(x);

for(int i=0;i<e[x].size();i++)

dfs(e[x][i],t^1);

}

int main()

{

memset(c,-1,sizeof(c));

n=read();m=read();

for(int i=1;i<=m;i++)

{

int u=read(),v=read();

e[u].push_back(v);

e[v].push_back(u);

}

for(int i=1;i<=n;i++)

if(c[i]==-1)dfs(i,1);

if(flag)puts("-1");

else

{

for(int x=0;x<=1;x++)

{

printf("%d\n",a[x].size());

for(int i=0;i<a[x].size();i++)

printf("%d ",a[x][i]);

puts("");

}

return 0;

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,K;
int c[1000005];
bool check(int t)
{
    for(int i=1;i<=n;i++)
        if(c[i]%t==0)return 1;
    return 0;
}
int main()
{
    n=read();K=read();
    for(int i=1;i<=n;i++)c[i]=read();
    for(int i=2;i<=K;i++)
    {
        int t=1;
        while(K%(t*i)==0)t*=i;
        if(t!=1)
            if(!check(t))
            {
                puts("No");
                return 0;
            }
        K/=t;
    }
    puts("Yes");
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<vector>

#include<algorithm>

#include<map>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,K;

int c[1000005];

bool check(int t)

{

for(int i=1;i<=n;i++)

if(c[i]%t==0)return 1;

return 0;

}

int main()

{

n=read();K=read();

for(int i=1;i<=n;i++)c[i]=read();

for(int i=2;i<=K;i++)

{

int t=1;

while(K%(t*i)==0)t*=i;

if(t!=1)

if(!check(t))

{

puts("No");

return 0;

}

K/=t;

}

puts("Yes");

return 0;

}

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<set>
#include<ctime>
#include<queue>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#define ll long long
#define inf 1000000000
using namespace std;
int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,K,ans;
int f[505][505];
int main()
{
    n=read();K=read();
    f[0][0]=1;
    for(int i=1;i<=n;i++)
    {
        int x=read();
        for(int j=K;j>=0;j--)
            for(int k=K;k>=0;k--)
            {
                if(j>=x)f[j][k]|=f[j-x][k];
                if(k>=x)f[j][k]|=f[j][k-x];
            }
    }
    for(int i=0;i<=K;i++)
        if(f[i][K-i])ans++;
    printf("%d\n",ans);
    for(int i=0;i<=K;i++)
        if(f[i][K-i])printf("%d ",i);
    return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>

#include<ctime>

#include<queue>

#include<cmath>

#include<vector>

#include<algorithm>

#include<map>

#define ll long long

#define inf 1000000000

using namespace std;

int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int n,K,ans;

int f[505][505];

int main()

{

n=read();K=read();

f[0][0]=1;

for(int i=1;i<=n;i++)

{

int x=read();

for(int j=K;j>=0;j--)

for(int k=K;k>=0;k--)

{

if(j>=x)f[j][k]|=f[j-x][k];

if(k>=x)f[j][k]|=f[j][k-x];

}

for(int i=0;i<=K;i++)

if(f[i][K-i])ans++;

printf("%d\n",ans);

for(int i=0;i<=K;i++)

if(f[i][K-i])printf("%d ",i);

return 0;

}

hzwer.com _ Home | http://hzwer.com

分类目录

热门文章

Myfriends

近期评论