「CF507X」Codeforces Round #287 (Div. 2)

#include<map>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
#define mod 1000000009
#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;
struct data{
    int v,id;
}a[105];
vector<int>ans;
bool operator<(data a,data b)
{
    return a.v<b.v;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=n;i++)
    {
        a[i].v=read();
        a[i].id=i;
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        if(m>=a[i].v)
        {
            m-=a[i].v;ans.push_back(a[i].id);
        }
    printf("%lu\n",ans.size());
    for(int i=0;i<ans.size();i++)
        printf("%d ",ans[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

#include<map>

#include<cmath>

#include<ctime>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define mod 1000000009

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

struct data{

int v,id;

}a[105];

vector<int>ans;

bool operator<(data a,data b)

{

return a.v<b.v;

}

int main()

{

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

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

{

a[i].v=read();

a[i].id=i;

}

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

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

if(m>=a[i].v)

{

m-=a[i].v;ans.push_back(a[i].id);

}

printf("%lu\n",ans.size());

for(int i=0;i<ans.size();i++)

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

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
#define mod 1000000009
#define inf 1000000000
#define eps 1e-8
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 r,x,y,x_,y_;
int main()
{
    r=read();x=read();y=read();x_=read();y_=read();
    x-=x_;y-=y_;
    double d=sqrt(x*x+y*y);
    int ans=d/(2*r);
    if(ans*r*2<d-eps)ans++;
    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

#include<map>

#include<cmath>

#include<ctime>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define mod 1000000009

#define inf 1000000000

#define eps 1e-8

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 r,x,y,x_,y_;

int main()

{

r=read();x=read();y=read();x_=read();y_=read();

x-=x_;y-=y_;

double d=sqrt(x*x+y*y);

int ans=d/(2*r);

if(ans*r*2<d-eps)ans++;

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

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
#define mod 1000000009
#define inf 1000000000
#define eps 1e-8
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 h;
ll n,bin[55],ans;
int main()
{
    bin[0]=1;for(int i=1;i<=50;i++)bin[i]=bin[i-1]<<1;
    h=read();n=read();n--;
    int f=0;
    for(int i=h-1;i>=0;i--)
    {
        if(((n>>i)&1)!=f)
            ans+=bin[i+1];
        else ans++,f^=1;
    }
    cout<<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

#include<map>

#include<cmath>

#include<ctime>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define mod 1000000009

#define inf 1000000000

#define eps 1e-8

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

ll n,bin[55],ans;

int main()

{

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

h=read();n=read();n--;

int f=0;

for(int i=h-1;i>=0;i--)

{

if(((n>>i)&1)!=f)

ans+=bin[i+1];

else ans++,f^=1;

}

cout<<ans;

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
#define mod 1000000009
#define inf 1000000000
#define eps 1e-8
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,m,ans;
int a[1005],f[1005][1005][2];
int main()
{
    n=read();K=read();m=read();
    a[0]=1%K;for(int i=1;i<=n;i++)a[i]=a[i-1]*10%K;
    f[0][0][0]=1;
    for(int i=0;i<n;i++)
        for(int j=0;j<K;j++)
            for(int p=0;p<=9;p++)
            {
                if(i==n-1&&p==0)continue;
                int t=(j+a[i]*p)%K;

                if(t||!p)f[i+1][t][0]=(f[i+1][t][0]+f[i][j][0])%m;
                else f[i+1][t][1]=(f[i+1][t][1]+f[i][j][0])%m;
                
                f[i+1][t][1]=(f[i+1][t][1]+f[i][j][1])%m;
            }
    for(int i=0;i<K;i++)
        ans=(ans+f[n][i][1])%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

#include<map>

#include<cmath>

#include<ctime>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define mod 1000000009

#define inf 1000000000

#define eps 1e-8

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

int a[1005],f[1005][1005][2];

int main()

{

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

a[0]=1%K;for(int i=1;i<=n;i++)a[i]=a[i-1]*10%K;

f[0][0][0]=1;

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

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

for(int p=0;p<=9;p++)

{

if(i==n-1&&p==0)continue;

int t=(j+a[i]*p)%K;

if(t||!p)f[i+1][t][0]=(f[i+1][t][0]+f[i][j][0])%m;

else f[i+1][t][1]=(f[i+1][t][1]+f[i][j][0])%m;

f[i+1][t][1]=(f[i+1][t][1]+f[i][j][1])%m;

}

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

ans=(ans+f[n][i][1])%m;

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

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ll long long 
#define mod 1000000009
#define inf 1000000000
#define eps 1e-8
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=1,ans;
struct edge{
    int from,to,next,v;
}e[200005];
int dis[100005],f[100005],g[100005],last[100005],q[100005];
bool mark[200005];
void insert(int u,int v,int w)
{
    e[++cnt]=(edge){u,v,last[u],w};last[u]=cnt;
    e[++cnt]=(edge){v,u,last[v],w};last[v]=cnt;
}
void bfs()
{
    int head=0,tail=1;
    dis[1]=0;q[0]=1;f[1]=0;
    while(head!=tail)
    {
        int now=q[head];head++;
        for(int i=last[now];i;i=e[i].next)
            if(dis[e[i].to]==-1||dis[now]+1==dis[e[i].to])
            {
                if(dis[e[i].to]==-1)
                    q[tail++]=e[i].to;
                dis[e[i].to]=dis[now]+1;
                if(f[e[i].to]<f[now]+e[i].v)
                {
                    f[e[i].to]=f[now]+e[i].v;
                    g[e[i].to]=i;
                }
            }
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        if(w==1)ans++;
        insert(u,v,w);
    }
    memset(dis,-1,sizeof(dis));
    memset(f,-1,sizeof(f));
    bfs();
    int x=n;
    while(x!=1)
    {
        mark[g[x]]=1;
        if(e[g[x]].v==1)ans--;
        else ans++;
        x=e[g[x]].from;
    }
    printf("%d\n",ans);
    for(int i=2;i<=cnt;i+=2)
        if(mark[i]+mark[i^1]&&!e[i].v)
            printf("%d %d %d\n",e[i].from,e[i].to,e[i].v^1);
        else if(!(mark[i]+mark[i^1])&&e[i].v)
            printf("%d %d %d\n",e[i].from,e[i].to,e[i].v^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

77

78

79

80

81

#include<map>

#include<cmath>

#include<ctime>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define ll long long

#define mod 1000000009

#define inf 1000000000

#define eps 1e-8

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

struct edge{

int from,to,next,v;

}e[200005];

int dis[100005],f[100005],g[100005],last[100005],q[100005];

bool mark[200005];

void insert(int u,int v,int w)

{

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

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

}

void bfs()

{

int head=0,tail=1;

dis[1]=0;q[0]=1;f[1]=0;

while(head!=tail)

{

int now=q[head];head++;

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

if(dis[e[i].to]==-1||dis[now]+1==dis[e[i].to])

{

if(dis[e[i].to]==-1)

q[tail++]=e[i].to;

dis[e[i].to]=dis[now]+1;

if(f[e[i].to]<f[now]+e[i].v)

{

f[e[i].to]=f[now]+e[i].v;

g[e[i].to]=i;

}

int main()

{

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

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

{

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

if(w==1)ans++;

insert(u,v,w);

}

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

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

bfs();

int x=n;

while(x!=1)

{

mark[g[x]]=1;

if(e[g[x]].v==1)ans--;

else ans++;

x=e[g[x]].from;

}

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

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

if(mark[i]+mark[i^1]&&!e[i].v)

printf("%d %d %d\n",e[i].from,e[i].to,e[i].v^1);

else if(!(mark[i]+mark[i^1])&&e[i].v)

printf("%d %d %d\n",e[i].from,e[i].to,e[i].v^1);

return 0;

}

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

分类目录

热门文章

Myfriends

近期评论