「CF519X」Codeforces Round #294 (Div. 2)

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#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;
}
char ch[10][10];
int t1,t2;
int main()
{
    for(int i=1;i<=8;i++)
        scanf("%s",ch[i]+1);
    for(int i=1;i<=8;i++)
        for(int j=1;j<=8;j++)
        {
            bool f=0;
            if(ch[i][j]>='a'&&ch[i][j]<='z')
                ch[i][j]=ch[i][j]-'a'+'A',f=1;
            int tmp=0;
            if(ch[i][j]=='Q')tmp=9;
            if(ch[i][j]=='R')tmp=5;
            if(ch[i][j]=='B')tmp=3;
            if(ch[i][j]=='N')tmp=3;
            if(ch[i][j]=='P')tmp=1;
            if(f)t1+=tmp;
            else t2+=tmp;
        }
    if(t1==t2)puts("Draw");
    else if(t1>t2)puts("Black");
    else puts("White");
    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<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

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

}

char ch[10][10];

int t1,t2;

int main()

{

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

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

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

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

{

bool f=0;

if(ch[i][j]>='a'&&ch[i][j]<='z')

ch[i][j]=ch[i][j]-'a'+'A',f=1;

int tmp=0;

if(ch[i][j]=='Q')tmp=9;

if(ch[i][j]=='R')tmp=5;

if(ch[i][j]=='B')tmp=3;

if(ch[i][j]=='N')tmp=3;

if(ch[i][j]=='P')tmp=1;

if(f)t1+=tmp;

else t2+=tmp;

}

if(t1==t2)puts("Draw");

else if(t1>t2)puts("Black");

else puts("White");

return 0;

}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#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;
}
int n;
int a[100005],b[100005],c[100005];
map<int,int> mp;
void solve(int *a,int na,int *b,int nb)
{
    mp.clear();
    for(int i=1;i<=nb;i++)
        mp[b[i]]++;
    for(int i=1;i<=na;i++)
    {
        mp[a[i]]--;
        if(mp[a[i]]==-1){printf("%d\n",a[i]);break;}
    }
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
    for(int i=1;i<n;i++)b[i]=read();
    for(int i=1;i<n-1;i++)c[i]=read();
    solve(a,n,b,n-1);
    solve(b,n-1,c,n-2);
    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

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

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

}

int n;

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

map<int,int> mp;

void solve(int *a,int na,int *b,int nb)

{

mp.clear();

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

mp[b[i]]++;

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

{

mp[a[i]]--;

if(mp[a[i]]==-1){printf("%d\n",a[i]);break;}

}

int main()

{

n=read();

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

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

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

solve(a,n,b,n-1);

solve(b,n-1,c,n-2);

return 0;

}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#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;
}
int n,m;
int solve(int n,int m)
{
    if(m>=2*n)return n;
    int t=m-n;
    m-=2*t;n-=t;
    t+=n/3*2;
    if(n%3==2)return t+1;
    else return t;
}
int main()
{
    n=read();m=read();
    if(n>m)swap(n,m);
    printf("%d\n",solve(n,m));
    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

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

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

}

int n,m;

int solve(int n,int m)

{

if(m>=2*n)return n;

int t=m-n;

m-=2*t;n-=t;

t+=n/3*2;

if(n%3==2)return t+1;

else return t;

}

int main()

{

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

if(n>m)swap(n,m);

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

return 0;

}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#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;
}
int l,x[30],num[100005],a[100005];
char ch[100005];
ll s[100005],ans;
map<pair<ll,int>,int>mp;
int main()
{
    for(int i=1;i<=26;i++)x[i]=read();
    scanf("%s",ch+1);
    l=strlen(ch+1);
    for(int i=1;i<=l;i++)
    {
        num[i]=ch[i]-'a'+1;
        a[i]=x[num[i]];
    }
    for(int i=1;i<=l;i++)
        s[i]=s[i-1]+a[i];
    for(int i=1;i<=l;i++)
    {
        ans+=mp[make_pair(s[i]-a[i],num[i])];
        mp[make_pair(s[i],num[i])]++;
    }
    printf("%I64d\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

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

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

}

int l,x[30],num[100005],a[100005];

char ch[100005];

ll s[100005],ans;

map<pair<ll,int>,int>mp;

int main()

{

for(int i=1;i<=26;i++)x[i]=read();

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

l=strlen(ch+1);

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

{

num[i]=ch[i]-'a'+1;

a[i]=x[num[i]];

}

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

s[i]=s[i-1]+a[i];

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

{

ans+=mp[make_pair(s[i]-a[i],num[i])];

mp[make_pair(s[i],num[i])]++;

}

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

return 0;

}

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#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;
}
int bin[20];
int n,m,cnt;
int deep[100005],size[100005],fa[100005][20],last[100005];
struct edge{
    int to,next;
}e[200005];
void insert(int u,int v)
{
    e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
    e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;
}
void dp(int x)
{
    size[x]=1;
    for(int i=1;bin[i]<=deep[x];i++)
        fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int i=last[x];i;i=e[i].next)
        if(e[i].to!=fa[x][0])
        {
            deep[e[i].to]=deep[x]+1;
            fa[e[i].to][0]=x;
            dp(e[i].to);
            size[x]+=size[e[i].to];
        }
}
int lca(int x,int y)
{
    int t=deep[x]-deep[y];
    for(int i=0;bin[i]<=t;i++)
        if(t&bin[i])x=fa[x][i];
    for(int i=19;i>=0;i--)
        if(fa[x][i]!=fa[y][i])
            x=fa[x][i],y=fa[y][i];
    if(x==y)return x;
    return fa[x][0];
}
int solve(int x,int y)
{
    if(x==y)return n;
    int t=lca(x,y),l;
    if(t!=y)l=deep[x]+deep[y]-2*deep[t];
    else l=deep[x]-deep[y];
    if(l&1)return 0;
    l/=2;
    for(int i=0;bin[i]<=l-1;i++)
        if((l-1)&bin[i])x=fa[x][i];
    int f=fa[x][0];
    if(f==t)
    {
        int l=deep[y]-deep[t];
        for(int i=0;bin[i]<=l-1;i++)
            if((l-1)&bin[i])y=fa[y][i];
        return n-size[x]-size[y];
    }
    return size[f]-size[x];
}
int main()
{
    bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;
    n=read();
    for(int i=1;i<n;i++)
    {
        int u=read(),v=read();
        insert(u,v);
    }
    dp(1);
    m=read();
    while(m--)
    {
        int u=read(),v=read();
        if(deep[u]<deep[v])swap(u,v);
        printf("%d\n",solve(u,v));
    }
    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

85

86

87

88

89

90

91

92

93

94

#include<iostream>

#include<cstring>

#include<cstdio>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#include<vector>

#include<set>

#include<map>

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

}

int bin[20];

int n,m,cnt;

int deep[100005],size[100005],fa[100005][20],last[100005];

struct edge{

int to,next;

}e[200005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;

}

void dp(int x)

{

size[x]=1;

for(int i=1;bin[i]<=deep[x];i++)

fa[x][i]=fa[fa[x][i-1]][i-1];

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

if(e[i].to!=fa[x][0])

{

deep[e[i].to]=deep[x]+1;

fa[e[i].to][0]=x;

dp(e[i].to);

size[x]+=size[e[i].to];

}

int lca(int x,int y)

{

int t=deep[x]-deep[y];

for(int i=0;bin[i]<=t;i++)

if(t&bin[i])x=fa[x][i];

for(int i=19;i>=0;i--)

if(fa[x][i]!=fa[y][i])

x=fa[x][i],y=fa[y][i];

if(x==y)return x;

return fa[x][0];

}

int solve(int x,int y)

{

if(x==y)return n;

int t=lca(x,y),l;

if(t!=y)l=deep[x]+deep[y]-2*deep[t];

else l=deep[x]-deep[y];

if(l&1)return 0;

l/=2;

for(int i=0;bin[i]<=l-1;i++)

if((l-1)&bin[i])x=fa[x][i];

int f=fa[x][0];

if(f==t)

{

int l=deep[y]-deep[t];

for(int i=0;bin[i]<=l-1;i++)

if((l-1)&bin[i])y=fa[y][i];

return n-size[x]-size[y];

}

return size[f]-size[x];

}

int main()

{

bin[0]=1;for(int i=1;i<20;i++)bin[i]=bin[i-1]<<1;

n=read();

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

{

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

insert(u,v);

}

dp(1);

m=read();

while(m--)

{

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

if(deep[u]<deep[v])swap(u,v);

printf("%d\n",solve(u,v));

}

return 0;

}

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

分类目录

热门文章

Myfriends

近期评论