「CF1228X」Codeforces Round #589

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
using namespace std;
ll read()
{
    ll 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 check(int x)
{
    bool mark[10] = {};
    while(x)
    {
        int y = x % 10;
        if(mark[y])return 0;
        mark[y] = 1;
        x /= 10;
    }
    return 1;
}
int main()
{
    int l = read(), r = read();
    for(int i = l; i <= r; i++)
        if(check(i))
        {
            cout << i << endl;
            return 0;
        }
    puts("-1");
    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

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

using namespace std;

ll read()

{

ll 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 check(int x)

{

bool mark[10] = {};

while(x)

{

int y = x % 10;

if(mark[y])return 0;

mark[y] = 1;

x /= 10;

}

return 1;

}

int main()

{

int l = read(), r = read();

for(int i = l; i <= r; i++)

if(check(i))

{

cout << i << endl;

return 0;

}

puts("-1");

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll 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, m;
int r[1005], c[1005], tr[1005], tc[1005];
int a[1005][1005];
ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(ll i = b; i; i >>= 1, a = a * a % mod)
        if(i & 1)
            ans = (ans * a) % mod;
    return ans;
}
int main()
{
    n = read(), m = read();
    for(int i = 1; i <= n; i++)
        r[i] = read();
    for(int j = 1; j <= m; j++)
        c[j] = read();
    int ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(i <= c[j] || j <= r[i])
                a[i][j] = 1;
    for(int i = 1; i <= n; i++)
    {
        int j = 1;
        while(a[i][j] && j <= m)
            tr[i]++, j++;
        if(tr[i] > r[i])ans = -1;
    }
    for(int i = 1; i <= m; i++)
    {
        int j = 1;
        while(a[j][i] && j <= n)
            tc[i]++, j++;
        if(tc[i] > c[i])ans = -1;
    }
    if(ans == -1)
    {
        puts("0");
        return 0;
    }
    ans = 0;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(i > (c[j] + 1) && j > (r[i] + 1))
                ans++;
    cout << qpow(2, ans) << endl;
    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

63

64

65

66

67

68

69

70

71

72

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll 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, m;

int r[1005], c[1005], tr[1005], tc[1005];

int a[1005][1005];

ll qpow(ll a, ll b)

{

ll ans = 1;

for(ll i = b; i; i >>= 1, a = a * a % mod)

if(i & 1)

ans = (ans * a) % mod;

return ans;

}

int main()

{

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

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

r[i] = read();

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

c[j] = read();

int ans = 0;

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

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

if(i <= c[j] || j <= r[i])

a[i][j] = 1;

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

{

int j = 1;

while(a[i][j] && j <= m)

tr[i]++, j++;

if(tr[i] > r[i])ans = -1;

}

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

{

int j = 1;

while(a[j][i] && j <= n)

tc[i]++, j++;

if(tc[i] > c[i])ans = -1;

}

if(ans == -1)

{

puts("0");

return 0;

}

ans = 0;

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

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

if(i > (c[j] + 1) && j > (r[i] + 1))

ans++;

cout << qpow(2, ans) << endl;

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll 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;
}
ll x, n, ans;
ll p[10005], cnt, m[10005];
ll qpow(ll a, ll b)
{
    ll ans = 1;
    for(ll i = b; i; i >>= 1, a = a * a % mod)
        if(i & 1)
            ans = (ans * a) % mod;
    return ans;
}
int main()
{
    x = read(); n = read();
    for(int i = 2; i <= sqrt(x); i++)
        if(x % i == 0)
        {
            p[++cnt] = i;
            while(x % i == 0)
                x = x / i;
        }
    if(x != 1)
        p[++cnt] = x;
    //for(int i = 1; i <= cnt; i++)
    //    cout << p[i];
    for(int i = 1; i <= cnt; i++)
    {
        ll t = p[i], q = n / t;
        while(q)
        {
            m[i] += q % (mod - 1);
            q = q / t;
            m[i] = m[i] % (mod - 1);
        }
    }
    ans = 1;
    for(int i = 1; i <= cnt; i++)
    {
        // cout << p[i] << ' ' << m[i] << endl;
        ans = ans * qpow(p[i], m[i]) % mod;
    }
    cout << ans << endl;
    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

63

64

65

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll 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;

}

ll x, n, ans;

ll p[10005], cnt, m[10005];

ll qpow(ll a, ll b)

{

ll ans = 1;

for(ll i = b; i; i >>= 1, a = a * a % mod)

if(i & 1)

ans = (ans * a) % mod;

return ans;

}

int main()

{

x = read(); n = read();

for(int i = 2; i <= sqrt(x); i++)

if(x % i == 0)

{

p[++cnt] = i;

while(x % i == 0)

x = x / i;

}

if(x != 1)

p[++cnt] = x;

//for(int i = 1; i <= cnt; i++)

// cout << p[i];

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

{

ll t = p[i], q = n / t;

while(q)

{

m[i] += q % (mod - 1);

q = q / t;

m[i] = m[i] % (mod - 1);

}

ans = 1;

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

{

// cout << p[i] << ' ' << m[i] << endl;

ans = ans * qpow(p[i], m[i]) % mod;

}

cout << ans << endl;

return 0;

}

#include<map>
#include<set>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pa pair<int,int>
#define ll long long
#define inf 1000000000
#define mod 1000000007
using namespace std;
ll read()
{
    ll 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, m;
vector<int> v[100005];
int c[100005], x[300005], y[300005], cnt[4];
vector<int> q[3];
int main()
{
    n = read(); m = read();
    for(int i = 1; i <= m; i++)
    {
        x[i] = read(), y[i] = read();
        v[x[i]].push_back(y[i]);
        v[y[i]].push_back(x[i]);
    }
    int t = 0;
    bool mark[4] = {0};
    c[1] = 1;
    for(int i = 0; i < v[1].size(); i++)
    {
        int y = v[1][i];
        c[y] = 2;
        mark[2] = 1;
        t = y;
    }
    for(int i = 0; i < v[t].size(); i++)
    {
        int y = v[t][i];
        if(c[y] == 2)
        {
            c[y] = 3;
            mark[3] = 1;
        }
    }
    for(int i = 1; i <= n; i++)
        if(!c[i])
            c[i] = 1;
    if(!mark[2] || !mark[3])
    {
        puts("-1");
        return 0;
    }
    for(int i = 1; i <= n; i++)
        cnt[c[i]]++;
    for(int i = 1; i <= n; i++)
    {
        int tmp = n - cnt[c[i]];
        if(v[i].size() != tmp)
        {
            puts("-1");
            return 0;
        }
    }
    for(int i = 1; i <= m; i++)
        if(c[x[i]] == c[y[i]])
        {
            puts("-1");
            return 0;
        }
    for(int i = 1; i <= n; i++)
        printf("%d ", c[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

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

#include<map>

#include<set>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define pa pair<int,int>

#define ll long long

#define inf 1000000000

#define mod 1000000007

using namespace std;

ll read()

{

ll 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, m;

vector<int> v[100005];

int c[100005], x[300005], y[300005], cnt[4];

vector<int> q[3];

int main()

{

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

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

{

x[i] = read(), y[i] = read();

v[x[i]].push_back(y[i]);

v[y[i]].push_back(x[i]);

}

int t = 0;

bool mark[4] = {0};

c[1] = 1;

for(int i = 0; i < v[1].size(); i++)

{

int y = v[1][i];

c[y] = 2;

mark[2] = 1;

t = y;

}

for(int i = 0; i < v[t].size(); i++)

{

int y = v[t][i];

if(c[y] == 2)

{

c[y] = 3;

mark[3] = 1;

}

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

if(!c[i])

c[i] = 1;

if(!mark[2] || !mark[3])

{

puts("-1");

return 0;

}

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

cnt[c[i]]++;

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

{

int tmp = n - cnt[c[i]];

if(v[i].size() != tmp)

{

puts("-1");

return 0;

}

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

if(c[x[i]] == c[y[i]])

{

puts("-1");

return 0;

}

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

printf("%d ", c[i]);

return 0;

}

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

分类目录

热门文章

Myfriends

近期评论