「CF545X」Codeforces Round #303 (Div. 2)

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#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;
int a[105][105];
int main()
{
	n=read();
	vector<int>ans;
	for(int i=1;i<=n;i++)
	{
		bool flag=0;
		for(int j=1;j<=n;j++)
		{
			a[i][j]=read();
			if(a[i][j]==1||a[i][j]==3)flag=1;
		}
		if(!flag)ans.push_back(i);
	}
	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

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

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

int a[105][105];

int main()

{

n=read();

vector<int>ans;

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

{

bool flag=0;

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

{

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

if(a[i][j]==1||a[i][j]==3)flag=1;

}

if(!flag)ans.push_back(i);

}

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<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#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,tot;
char a[100005],b[100005];
int main()
{
    scanf("%s%s",a+1,b+1);
    n=strlen(a+1);
    for(int i=1;i<=n;i++)
        if(a[i]!=b[i])tot++;
    if(tot&1)puts("impossible");
    else 
    {
        int t=0;
        for(int i=1;i<=n;i++)
            if(a[i]!=b[i])
            {
                if(t<tot/2)t++,printf("%c",a[i]);
                else printf("%c",b[i]);
            }
            else printf("%c",a[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

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

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

char a[100005],b[100005];

int main()

{

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

n=strlen(a+1);

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

if(a[i]!=b[i])tot++;

if(tot&1)puts("impossible");

else

{

int t=0;

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

if(a[i]!=b[i])

{

if(t<tot/2)t++,printf("%c",a[i]);

else printf("%c",b[i]);

}

else printf("%c",a[i]);

}

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#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;
int x[100005],h[100005];
int main()
{
    n=read();
    if(n==1)
    {
        puts("1");
        return 0;
    }
    for(int i=1;i<=n;i++)
        x[i]=read(),h[i]=read();
    int ans=2;
    for(int i=2;i<=n-1;i++)
        if(abs(x[i]-x[i-1])>h[i])ans++;
        else if(abs(x[i]-x[i+1])>h[i])
            ans++,x[i]+=h[i];
    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<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

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

int x[100005],h[100005];

int main()

{

n=read();

if(n==1)

{

puts("1");

return 0;

}

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

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

int ans=2;

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

if(abs(x[i]-x[i-1])>h[i])ans++;

else if(abs(x[i]-x[i+1])>h[i])

ans++,x[i]+=h[i];

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

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#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;
int t[100005];
int main()
{
    n=read();
    for(int i=1;i<=n;i++)t[i]=read();
    sort(t+1,t+n+1);
    ll tot=0;
    for(int i=1;i<=n;i++)
        if(tot<=t[i])tot+=t[i],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<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

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

int t[100005];

int main()

{

n=read();

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

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

ll tot=0;

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

if(tot<=t[i])tot+=t[i],ans++;

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

return 0;

}

#include<map>
#include<cmath>
#include<ctime>
#include<queue>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define ll long long
#define pa pair<ll,int>
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;
int last[300005],pre[300005];
bool mark[600005],vis[300005];
ll dis[300005];
struct edge{
    int to,next,v;
}e[600005];
void insert(int u,int v,int w)
{
    e[++cnt]=(edge){v,last[u],w};last[u]=cnt;
    e[++cnt]=(edge){u,last[v],w};last[v]=cnt;
}
priority_queue<pa,vector<pa>,greater<pa> >q;
void dijkstra(int x)
{   
    for(int i=1;i<=n;i++)dis[i]=1e60;
    dis[x]=0;q.push(make_pair(0,x));
    while(!q.empty())
    {
        int now=q.top().second;q.pop();
        if(vis[now])continue;vis[now]=1;
        for(int i=last[now];i;i=e[i].next)
            if(!vis[e[i].to]&&dis[now]+e[i].v<=dis[e[i].to])
            {
                if(dis[now]+e[i].v<dis[e[i].to])pre[e[i].to]=i;
                else if(e[i].v<e[pre[e[i].to]].v)pre[e[i].to]=i;
                dis[e[i].to]=dis[now]+e[i].v;
                q.push(make_pair(dis[e[i].to],e[i].to));
            }
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        int u=read(),v=read(),w=read();
        insert(u,v,w);
    }
    int t=read();
    dijkstra(t);
    for(int i=1;i<=n;i++)
        mark[pre[i]]=1;
    vector<int>ans;
    ll tot=0;
    for(int i=2;i<=cnt;i+=2)
        if(mark[i]||mark[i+1])
        {
            ans.push_back(i/2);
            tot+=e[i].v;
        }
    printf("%I64d\n",tot);
    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

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

#include<map>

#include<cmath>

#include<ctime>

#include<queue>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define ll long long

#define pa pair<ll,int>

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;

int last[300005],pre[300005];

bool mark[600005],vis[300005];

ll dis[300005];

struct edge{

int to,next,v;

}e[600005];

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

{

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

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

}

priority_queue<pa,vector<pa>,greater<pa> >q;

void dijkstra(int x)

{

for(int i=1;i<=n;i++)dis[i]=1e60;

dis[x]=0;q.push(make_pair(0,x));

while(!q.empty())

{

int now=q.top().second;q.pop();

if(vis[now])continue;vis[now]=1;

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

if(!vis[e[i].to]&&dis[now]+e[i].v<=dis[e[i].to])

{

if(dis[now]+e[i].v<dis[e[i].to])pre[e[i].to]=i;

else if(e[i].v<e[pre[e[i].to]].v)pre[e[i].to]=i;

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

q.push(make_pair(dis[e[i].to],e[i].to));

}

int main()

{

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

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

{

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

insert(u,v,w);

}

int t=read();

dijkstra(t);

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

mark[pre[i]]=1;

vector<int>ans;

ll tot=0;

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

if(mark[i]||mark[i+1])

{

ans.push_back(i/2);

tot+=e[i].v;

}

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

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

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

return 0;

}

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

分类目录

热门文章

Myfriends

近期评论