「CF538X」Codeforces Round #300

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define linf 9000000000000000000LL
#define mp(a,b) make_pair(a,b)
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,K;
char a[105];
string b="CODEFORCES";
bool check(int l,int r)
{
    m=0;
    for(int i=1;i<=n;i++)
    {
        if(l<=i&&i<=r)continue;
        if(b[m]!=a[i])return 0;
        m++;
    }
    return 1;
}
int main()
{
    scanf("%s",a+1);
    n=strlen(a+1);
    if(n<10)
    {
        puts("NO");
        return 0;
    }
    for(int i=1;i<=n;i++)
        if(check(i,(n-10+i-1)))
        {
            puts("YES");
            return 0;
        }
    puts("NO");
    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

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define linf 9000000000000000000LL

#define mp(a,b) make_pair(a,b)

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,K;

char a[105];

string b="CODEFORCES";

bool check(int l,int r)

{

m=0;

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

{

if(l<=i&&i<=r)continue;

if(b[m]!=a[i])return 0;

m++;

}

return 1;

}

int main()

{

scanf("%s",a+1);

n=strlen(a+1);

if(n<10)

{

puts("NO");

return 0;

}

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

if(check(i,(n-10+i-1)))

{

puts("YES");

return 0;

}

puts("NO");

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define linf 9000000000000000000LL
#define mp(a,b) make_pair(a,b)
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,K;
char a[105],b[105];
int main()
{
    scanf("%s",a+1);
    n=strlen(a+1);
    for(int i=1;i<=n;i++)
        m=max(m,a[i]-'0');
    printf("%d\n",m);
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            if(a[j]-'0'!=0)
            {
                b[j]='1';a[j]--;
            }
            else b[j]='0';
        bool flag=0;
        for(int j=1;j<=n;j++)
            if(b[j]-'0'!=0)
            {
                flag=1;printf("%c",b[j]);
            }
            else if(flag)printf("%c",b[j]);
        printf(" ");
    }
    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

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define linf 9000000000000000000LL

#define mp(a,b) make_pair(a,b)

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,K;

char a[105],b[105];

int main()

{

scanf("%s",a+1);

n=strlen(a+1);

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

m=max(m,a[i]-'0');

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

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

{

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

if(a[j]-'0'!=0)

{

b[j]='1';a[j]--;

}

else b[j]='0';

bool flag=0;

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

if(b[j]-'0'!=0)

{

flag=1;printf("%c",b[j]);

}

else if(flag)printf("%c",b[j]);

printf(" ");

}

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define linf 9000000000000000000LL
#define mp(a,b) make_pair(a,b)
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,K;
int a[100005],b[100005],ans;
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        a[i]=read();b[i]=read();
        ans=max(b[i],ans);
    }
    for(int i=2;i<=m;i++)
        if(a[i]-a[i-1]<abs(b[i]-b[i-1]))
        {
            puts("IMPOSSIBLE");
            return 0;
        }
        else 
        {
            int d=a[i]-a[i-1]-abs(b[i]-b[i-1]);
            ans=max(ans,max(b[i],b[i-1])+d/2);
        }
    ans=max(ans,max(b[1]+a[1]-1,b[m]+n-a[m]));
    printf("%d\n",ans);
    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<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define linf 9000000000000000000LL

#define mp(a,b) make_pair(a,b)

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,K;

int a[100005],b[100005],ans;

int main()

{

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

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

{

a[i]=read();b[i]=read();

ans=max(b[i],ans);

}

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

if(a[i]-a[i-1]<abs(b[i]-b[i-1]))

{

puts("IMPOSSIBLE");

return 0;

}

else

{

int d=a[i]-a[i-1]-abs(b[i]-b[i-1]);

ans=max(ans,max(b[i],b[i-1])+d/2);

}

ans=max(ans,max(b[1]+a[1]-1,b[m]+n-a[m]));

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

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define linf 9000000000000000000LL
#define mp(a,b) make_pair(a,b)
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;
char a[105][105],b[105][105],c[105][105];
int sta(int x,int y)
{
    if(x<1||y<1||x>n||y>n)return -1;
    if(a[x][y]=='.')return 0;
    if(a[x][y]=='o')return 1;
    return 2;
}
bool check(int x,int y)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(sta(i,j)==1)
            {
                c[i][j]='o';
                if(sta(i+x,j+y)==0)return 0;
            }
    return 1;
}
void add(int x,int y)
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(sta(i,j)==1&&sta(i+x,j+y)!=-1)
                c[i+x][j+y]='x';
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
        scanf("%s",a[i]+1);
    for(int i=1;i<=2*n-1;i++)
    {
        for(int j=1;j<=2*n-1;j++)
            if(i==n&&j==n)b[i][j]='o';
            else if(check(i-n,j-n))
            {
                b[i][j]='x';
                add(i-n,j-n);
            }
            else b[i][j]='.';
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(a[i][j]=='x'&&a[i][j]!=c[i][j])
            {
                puts("NO");return 0;
            }
    puts("YES");
    for(int i=1;i<=2*n-1;i++)printf("%s\n",b[i]+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

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

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define linf 9000000000000000000LL

#define mp(a,b) make_pair(a,b)

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;

char a[105][105],b[105][105],c[105][105];

int sta(int x,int y)

{

if(x<1||y<1||x>n||y>n)return -1;

if(a[x][y]=='.')return 0;

if(a[x][y]=='o')return 1;

return 2;

}

bool check(int x,int y)

{

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

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

if(sta(i,j)==1)

{

c[i][j]='o';

if(sta(i+x,j+y)==0)return 0;

}

return 1;

}

void add(int x,int y)

{

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

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

if(sta(i,j)==1&&sta(i+x,j+y)!=-1)

c[i+x][j+y]='x';

}

int main()

{

n=read();

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

scanf("%s",a[i]+1);

for(int i=1;i<=2*n-1;i++)

{

for(int j=1;j<=2*n-1;j++)

if(i==n&&j==n)b[i][j]='o';

else if(check(i-n,j-n))

{

b[i][j]='x';

add(i-n,j-n);

}

else b[i][j]='.';

}

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

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

if(a[i][j]=='x'&&a[i][j]!=c[i][j])

{

puts("NO");return 0;

}

puts("YES");

for(int i=1;i<=2*n-1;i++)printf("%s\n",b[i]+1);

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define linf 9000000000000000000LL
#define mp(a,b) make_pair(a,b)
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,cnt;
int last[200005];
struct edge{
	int to,next;
}e[400005];
void insert(int u,int v)
{
	e[++cnt]=(edge){v,last[u]};last[u]=cnt;
}
int dfs(int x,bool f)
{
	if(!last[x])return 1;
	int t1=inf,t2=0;
	for(int i=last[x];i;i=e[i].next)
		if(f)t2+=dfs(e[i].to,!f);
		else t1=min(t1,dfs(e[i].to,!f));
	return f?t2:t1;
}
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		insert(u,v);
	}
	for(int i=1;i<=n;i++)if(!last[i])m++;
	printf("%d %d\n",m+1-dfs(1,0),dfs(1,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

46

47

48

49

50

51

52

53

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define linf 9000000000000000000LL

#define mp(a,b) make_pair(a,b)

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,cnt;

int last[200005];

struct edge{

int to,next;

}e[400005];

void insert(int u,int v)

{

e[++cnt]=(edge){v,last[u]};last[u]=cnt;

}

int dfs(int x,bool f)

{

if(!last[x])return 1;

int t1=inf,t2=0;

for(int i=last[x];i;i=e[i].next)

if(f)t2+=dfs(e[i].to,!f);

else t1=min(t1,dfs(e[i].to,!f));

return f?t2:t1;

}

int main()

{

n=read();

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

{

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

insert(u,v);

}

for(int i=1;i<=n;i++)if(!last[i])m++;

printf("%d %d\n",m+1-dfs(1,0),dfs(1,1));

return 0;

}

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1000000000
#define linf 9000000000000000000LL
#define mp(a,b) make_pair(a,b)
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,cnt;
int a[200005],rt[200005];
int c[8000005][2],sum[8000005];
int insert(int x,int val)
{
    int l=-inf,r=inf;
    int y=++cnt,tmp=y;
    sum[y]=sum[x]+1;
    while(l!=r)
    {
        int mid=(l+r)>>1,t=0;
        if(val<=mid)r=mid;
        else l=mid+1,t^=1;
        c[y][t]=++cnt;c[y][t^1]=c[x][t^1];
        x=c[x][t];y=c[y][t];
        sum[y]=sum[x]+1;
    }
    return tmp;
}
int query(int x,int y,int val)
{
    int l=-inf,r=inf,ans=0;
    while(l!=r)
    {
        int mid=(l+r)>>1,t=0;
        if(val<=mid)r=mid;
        else ans+=sum[c[y][0]]-sum[c[x][0]],l=mid+1,t^=1;
        x=c[x][t];y=c[y][t];
    }
    return ans;
}
int Q(int l,int r,int val)
{
    if(r>n)r=n;
    return query(rt[l-1],rt[r],val);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<=n;i++)rt[i]=insert(rt[i-1],a[i]);
    for(int k=1;k<n;k++)
    {
        ll ans=0;
        for(int i=1,j=1;j<=n;i++,j+=k)
            ans+=Q(j+1,j+k,a[i]);
        printf("%lld ",ans);
    }
    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

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define ll long long

#define inf 1000000000

#define linf 9000000000000000000LL

#define mp(a,b) make_pair(a,b)

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,cnt;

int a[200005],rt[200005];

int c[8000005][2],sum[8000005];

int insert(int x,int val)

{

int l=-inf,r=inf;

int y=++cnt,tmp=y;

sum[y]=sum[x]+1;

while(l!=r)

{

int mid=(l+r)>>1,t=0;

if(val<=mid)r=mid;

else l=mid+1,t^=1;

c[y][t]=++cnt;c[y][t^1]=c[x][t^1];

x=c[x][t];y=c[y][t];

sum[y]=sum[x]+1;

}

return tmp;

}

int query(int x,int y,int val)

{

int l=-inf,r=inf,ans=0;

while(l!=r)

{

int mid=(l+r)>>1,t=0;

if(val<=mid)r=mid;

else ans+=sum[c[y][0]]-sum[c[x][0]],l=mid+1,t^=1;

x=c[x][t];y=c[y][t];

}

return ans;

}

int Q(int l,int r,int val)

{

if(r>n)r=n;

return query(rt[l-1],rt[r],val);

}

int main()

{

n=read();

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

for(int i=1;i<=n;i++)rt[i]=insert(rt[i-1],a[i]);

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

{

ll ans=0;

for(int i=1,j=1;j<=n;i++,j+=k)

ans+=Q(j+1,j+k,a[i]);

printf("%lld ",ans);

}

return 0;

}

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

分类目录

热门文章

Myfriends

近期评论