「CF540X」Codeforces Round #301 (Div. 2)

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000007
#define inf 1000000000
#define eps 1e-9
#define sqr(x) x*x
#define pi acos(-1)
#define ll long long
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,ans;
char a[1005],b[1005];
int main()
{
    n=read();
    scanf("%s",a+1);
    scanf("%s",b+1);
    for(int i=1;i<=n;i++)
    {
        if(a[i]<b[i])swap(a[i],b[i]);
        ans+=min(a[i]-b[i],b[i]-a[i]+10);
    }
    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

#include<set>

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000007

#define inf 1000000000

#define eps 1e-9

#define sqr(x) x*x

#define pi acos(-1)

#define ll long long

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

char a[1005],b[1005];

int main()

{

n=read();

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

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

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

{

if(a[i]<b[i])swap(a[i],b[i]);

ans+=min(a[i]-b[i],b[i]-a[i]+10);

}

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

return 0;

}

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000007
#define inf 1000000000
#define eps 1e-9
#define sqr(x) x*x
#define pi acos(-1)
#define ll long long
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,k,p,x,y,tot,top;
int a[1005],b[1005];
int main()
{
    n=read();k=read();p=read();x=read();y=read();
    for(int i=1;i<=k;i++)a[i]=read();
    for(int i=1;i<=k;i++)tot+=a[i];
    if(tot+(n-k)>x)puts("-1");
    else 
    {
        int now=x-tot-(n-k);
        for(int i=k+1;i<=n;i++)
            if(now>=y-1)b[++top]=y,now-=y-1;
            else b[++top]=1;
        for(int i=1;i<=top;i++)a[k+i]=b[i];
        sort(a+1,a+n+1);
        if(a[n/2+1]<y||a[n]>p)puts("-1");
        else 
        {
            for(int i=1;i<=top;i++)
                printf("%d ",b[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

#include<set>

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000007

#define inf 1000000000

#define eps 1e-9

#define sqr(x) x*x

#define pi acos(-1)

#define ll long long

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,k,p,x,y,tot,top;

int a[1005],b[1005];

int main()

{

n=read();k=read();p=read();x=read();y=read();

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

for(int i=1;i<=k;i++)tot+=a[i];

if(tot+(n-k)>x)puts("-1");

else

{

int now=x-tot-(n-k);

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

if(now>=y-1)b[++top]=y,now-=y-1;

else b[++top]=1;

for(int i=1;i<=top;i++)a[k+i]=b[i];

sort(a+1,a+n+1);

if(a[n/2+1]<y||a[n]>p)puts("-1");

else

{

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

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

}

return 0;

}

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000007
#define inf 1000000000
#define eps 1e-9
#define sqr(x) x*x
#define pi acos(-1)
#define ll long long
#define p(i,j) (i-1)*m+j
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,xs,ys,xt,yt;
int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};
char a[505][505];
bool vis[505][505];
void dfs(int x,int y)
{
    if(x>n||y>m||x<1||y<1)return;
    if(a[x][y]=='X'&&(x!=xt||y!=yt))return;
    if(!vis[x][y])vis[x][y]=1;
    else return;
    for(int k=0;k<4;k++)
        dfs(x+xx[k],y+yy[k]);
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
        scanf("%s",a[i]+1);
    xs=read();ys=read();xt=read();yt=read();
    a[xs][ys]='.';
    dfs(xs,ys);
    if(!vis[xt][yt]){puts("NO");return 0;}
    int t=0;
    for(int i=0;i<4;i++)
        if(a[xt+xx[i]][yt+yy[i]]=='.')
            t++;
    if(xs==xt&&ys==yt)
    {
        if(t==0)puts("NO");
        else puts("YES");
        return 0;
    }
    if(a[xt][yt]!='X'&&t==1){puts("NO");return 0;}
    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

49

50

51

52

53

54

55

56

57

58

59

60

61

62

#include<set>

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000007

#define inf 1000000000

#define eps 1e-9

#define sqr(x) x*x

#define pi acos(-1)

#define ll long long

#define p(i,j) (i-1)*m+j

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,xs,ys,xt,yt;

int xx[4]={0,0,1,-1},yy[4]={1,-1,0,0};

char a[505][505];

bool vis[505][505];

void dfs(int x,int y)

{

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

if(a[x][y]=='X'&&(x!=xt||y!=yt))return;

if(!vis[x][y])vis[x][y]=1;

else return;

for(int k=0;k<4;k++)

dfs(x+xx[k],y+yy[k]);

}

int main()

{

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

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

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

xs=read();ys=read();xt=read();yt=read();

a[xs][ys]='.';

dfs(xs,ys);

if(!vis[xt][yt]){puts("NO");return 0;}

int t=0;

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

if(a[xt+xx[i]][yt+yy[i]]=='.')

t++;

if(xs==xt&&ys==yt)

{

if(t==0)puts("NO");

else puts("YES");

return 0;

}

if(a[xt][yt]!='X'&&t==1){puts("NO");return 0;}

puts("YES");

return 0;

}

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000007
#define inf 1000000000
#define eps 1e-9
#define sqr(x) x*x
#define pi acos(-1)
#define ll long long
#define p(i,j) (i-1)*m+j
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,s,p;
struct data{
    double p1,p2,p3;
    friend data operator+(data a,data b){
        return (data){a.p1+b.p1,a.p2+b.p2,a.p3+b.p3};
    }
    friend data operator*(data a,double b){
        return (data){a.p1*b,a.p2*b,a.p3*b};
    }
}f[105][105][105];
data dp(int a,int b,int c)
{
    data &t=f[a][b][c];
    if(t.p1+t.p2+t.p3>=eps)
        return t;
    t.p1=t.p2=t.p3=0;
    double tot=a+b+c,P=0,t1,t2,t3;
    if(a==tot){t.p1=1;return t;}
    if(b==tot){t.p2=1;return t;}
    if(c==tot){t.p3=1;return t;}
    t1=a/tot*b/tot,t2=b/tot*c/tot,t3=a/tot*c/tot;
    P=t1+t2+t3;
    if(a!=0&b!=0)t=t+dp(a,b-1,c)*(t1/P);
    if(a!=0&c!=0)t=t+dp(a-1,b,c)*(t3/P);
    if(b!=0&c!=0)t=t+dp(a,b,c-1)*(t2/P);
    return t;
}
int main()
{
    n=read();s=read();p=read();
    memset(&f,0,sizeof(f));
    data t=dp(n,s,p);
    printf("%.12lf %.12lf %.12lf",t.p1,t.p2,t.p3);
    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

#include<set>

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000007

#define inf 1000000000

#define eps 1e-9

#define sqr(x) x*x

#define pi acos(-1)

#define ll long long

#define p(i,j) (i-1)*m+j

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,s,p;

struct data{

double p1,p2,p3;

friend data operator+(data a,data b){

return (data){a.p1+b.p1,a.p2+b.p2,a.p3+b.p3};

}

friend data operator*(data a,double b){

return (data){a.p1*b,a.p2*b,a.p3*b};

}

}f[105][105][105];

data dp(int a,int b,int c)

{

data &t=f[a][b][c];

if(t.p1+t.p2+t.p3>=eps)

return t;

t.p1=t.p2=t.p3=0;

double tot=a+b+c,P=0,t1,t2,t3;

if(a==tot){t.p1=1;return t;}

if(b==tot){t.p2=1;return t;}

if(c==tot){t.p3=1;return t;}

t1=a/tot*b/tot,t2=b/tot*c/tot,t3=a/tot*c/tot;

P=t1+t2+t3;

if(a!=0&b!=0)t=t+dp(a,b-1,c)*(t1/P);

if(a!=0&c!=0)t=t+dp(a-1,b,c)*(t3/P);

if(b!=0&c!=0)t=t+dp(a,b,c-1)*(t2/P);

return t;

}

int main()

{

n=read();s=read();p=read();

memset(&f,0,sizeof(f));

data t=dp(n,s,p);

printf("%.12lf %.12lf %.12lf",t.p1,t.p2,t.p3);

return 0;

}

#include<set>
#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define mod 1000000007
#define inf 1000000000
#define eps 1e-9
#define sqr(x) x*x
#define pi acos(-1)
#define ll long long
#define p(i,j) (i-1)*m+j
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,top;
int v[100005],u[100005];
int q[200005],a[200005],pos[200005],t[200005];
void add(int x,int tmp)
{
    x++;
    for(int i=x;i<=2*n;i+=i&-i)
        t[i]+=tmp;
}
int query(int x)
{
    x++;
    int ans=0;
    for(int i=x;i;i-=i&-i)
        ans+=t[i];
    return ans;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        u[i]=read(),v[i]=read();
        q[++top]=u[i];
        q[++top]=v[i];
    }
    sort(q+1,q+top+1);
    top=unique(q+1,q+top+1)-q-1;
    for(int i=1;i<=n;i++)
    {
        u[i]=lower_bound(q+1,q+top+1,u[i])-q;
        v[i]=lower_bound(q+1,q+top+1,v[i])-q;
    }
    for(int i=1;i<=2*n;i++)pos[i]=i;
    for(int i=1;i<=n;i++)
        swap(pos[u[i]],pos[v[i]]);
    for(int i=1;i<=top;i++)
        a[pos[i]]=i;
    ll ans=0;
    ll sum=0;
    for(int i=1;i<=top;i++)
    {
        ans+=(sum-query(i-1))*(q[i]-q[i-1]-1);
        add(i-1,q[i]-q[i-1]-1);
        sum+=q[i]-q[i-1]-1;
        ans+=sum-query(a[i]-1);
        add(a[i],1);
        sum++;
    }
    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

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

#include<set>

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define mod 1000000007

#define inf 1000000000

#define eps 1e-9

#define sqr(x) x*x

#define pi acos(-1)

#define ll long long

#define p(i,j) (i-1)*m+j

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

int v[100005],u[100005];

int q[200005],a[200005],pos[200005],t[200005];

void add(int x,int tmp)

{

x++;

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

t[i]+=tmp;

}

int query(int x)

{

x++;

int ans=0;

for(int i=x;i;i-=i&-i)

ans+=t[i];

return ans;

}

int main()

{

n=read();

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

{

u[i]=read(),v[i]=read();

q[++top]=u[i];

q[++top]=v[i];

}

sort(q+1,q+top+1);

top=unique(q+1,q+top+1)-q-1;

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

{

u[i]=lower_bound(q+1,q+top+1,u[i])-q;

v[i]=lower_bound(q+1,q+top+1,v[i])-q;

}

for(int i=1;i<=2*n;i++)pos[i]=i;

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

swap(pos[u[i]],pos[v[i]]);

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

a[pos[i]]=i;

ll ans=0;

ll sum=0;

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

{

ans+=(sum-query(i-1))*(q[i]-q[i-1]-1);

add(i-1,q[i]-q[i-1]-1);

sum+=q[i]-q[i-1]-1;

ans+=sum-query(a[i]-1);

add(a[i],1);

sum++;

}

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

return 0;

}

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

分类目录

热门文章

Myfriends

近期评论