AtCoder Regular Contest 099

C - Minimization

题意

题意：给出一个n的排列。每次操作可以使一段长度为K的连续子序列变成该序列的最小数。求最少几次使得整个数列全部为1。

分析

可以发现每次操作都要包含1。所以我们的答案就应该是 \(\frac{n-k}{k-1}\)。

直接\(O(1)\)求就可以了。

#include <iostream>

#include <cstdlib>

#include <cmath>

#include <string>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

#define re register

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define MAXN 4000007

#define ll long long

#define mo 19930726

#define ls rt<<1

#define rs rt<<1|1

using namespace std;

typedef unsigned long long ull;

int n,k;

int main()

{

	cin>>n>>k;

	int ans=1;

	n-=k;

	ans+=n/(k-1);

	n%=(k-1);

	if(n) ans+=1;

	cout<<ans;

}

D - Snuke Numbers

题意

令S(n)表示n这个数各位之和。定义一个数n合法：所有m>n，都有n/S(n)<=m/S(m)。

输出前K个合法的数。

分析

发现所有的snuke数的尾数基本都是9。

所以我们直接暴力求就可以了。

#include <iostream>

#include <cstdlib>

#include <cmath>

#include <string>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

#define re register

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define MAXN 4000007

#define ll long long

#define mo 19930726

using namespace std;

typedef unsigned long long ull;

#define ms(arr) memset(arr, 0, sizeof(arr))

const int inf = 0x3f3f3f3f;

int n;

ll clac(ll x)

{

	ll cnt=0;

	while(x) cnt+=x%10,x/=10;

	return cnt;

}

int main()

{

	ll x=0,x1,x2,m=1;

	cin>>n;

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

		x1=x+m;x2=x+m*10;

		if(x1*clac(x2)<=x2*clac(x1))

			x=x1;

		else x=x2,m*=10;

		printf("%lld\n",x);

	}

}

E - Independence

题意

题意：给出一个无向图，让你将它分成两部分使得，每部分的点互相有边相连。

最小化边的数量。

分析

建立补图。

对补图进行二分图染色。

可以发现如果补图不是二分图的话，不合法。

然后对于每个联通块的两种颜色x和y，我们要通过交换一些x和y使\(\sum^n_{i=1}x[i]\)尽量接近于\(\frac N 2\)。

背包求一下就可以了。

#include <iostream>

#include <cstdlib>

#include <cmath>

#include <string>

#include <cstring>

#include <cstdio>

#include <algorithm>

#include <queue>

#include <set>

#include <map>

#define re register

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

#define MAXN 4000007

#define mo 19930726

using namespace std;

typedef unsigned long long ull;

#define ms(arr) memset(arr, 0, sizeof(arr))

const int inf = 0x3f3f3f3f;

int f[1001][1001],x[100001],y[10001],col[10001];

int n,m,a[1001][1001],cnt[100001],tot;

bool vis[100001];

struct po

{

	int nxt,to;

};

po edge[1000001];

inline int read()

{

    int x=0,c=1;

    char ch=' ';

    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

    while(ch=='-') c*=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-'0',ch=getchar();

    return x*c;

}

inline void put_color(int u)

{

	vis[u]=1;

	cnt[col[u]]++;

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

		if(a[u][i]==0){

			if(!vis[i]){

				col[i]=!col[u];

				put_color(i);

			} else if(col[u]==col[i]){

				cout<<-1;

				exit(0);

			}

		}

	}

}

int main()

{

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

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

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

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

		a[u][v]=a[v][u]=1;

	}

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

		if(!vis[i]){

			cnt[0]=cnt[1]=0;

			put_color(i);

			tot++;

			x[tot]=cnt[0];

			y[tot]=cnt[1];

		}

	}

	f[0][0]=1;

	for(re int i=1;i<=tot;i++){

		for(re int j=0;j<=n;j++){

			if(f[i-1][j]){

				f[i][j+x[i]]=1;

				f[i][j+y[i]]=1;

			}

		}

	}

	int ans=n*n;

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

		if(f[tot][i]) ans=min(ans,i*(i-1)/2+(n-i)*(n-i-1)/2);

	}

	cout<<ans;

}

巴特西

AtCoder Regular Contest 099

AtCoder Regular Contest 099

C - Minimization

题意

分析

D - Snuke Numbers

题意

分析

E - Independence

题意

分析

最新文章

热门文章