CF Round #677 div3 post game summary

preface

Good luck AK (╯`□ ') ╯ (┻━┻)

I didn't understand the problem of celebration \ (E \) and found the rule (╯`□ ') ╯ (┻━┻)

A

Meaning:
That is to say, in the range of \ (1-10000 \), if each digit of a number is the same number, it is called boring number, and then it will be arranged in the order of \ (1,11111111,2,22... \), and then ask the boring number \ (x \) and the sum of the digits in front of it. For example, \ (11 \), there is \ (1 \) in front of it, and then the sum of digits is \ (2 + 1 = 3 \).

Violence simulation.

#include<cstdio>
#include<cstring>
using  namespace  std;
inline  int  solve(int  x)
{
	int  type=x%10;
	int  ans=(type-1)*10;
	int  y=0;
	while(x)
	{
		x/=10;
		y++;
		ans+=y;
	}
	printf("%d\n",ans);
}
int  main()
{
	int  T;scanf("%d",&T);
	for(int  i=1;i<=T;i++)
	{
		int  x;scanf("%d",&x);
		solve(x);
	}
	return  0;
}

B

Meaning:
If there is a book in position \ (i \), it is \ (1 \) and there is no book, it is \ (0 \).
For a continuous section of books \ ([l,r] \) on the shelf, if the position of \ (r+1 \) has no position, you can move the book of \ ([l,r] \) from right to \ ([l+1,r+1] \), which is similar to the left.
Then ask the minimum number of moves required to turn all books into a continuous section.

Practice:
At most one interval can be eliminated at a time. It is not difficult to find that the answer is the interval and between adjacent paragraphs of books.

#include<cstdio>
#include<cstring>
#define  N  60
using  namespace  std;
int  a[N],n;
void  solve()
{
	scanf("%d",&n);
	for(int  i=1;i<=n;i++)scanf("%d",&a[i]);
	bool  bk=0;int  ans=0,cnt=0;
	for(int  i=1;i<=n;i++)
	{
		if(!a[i])
		{
			if(bk)cnt++;
		}
		else
		{
			bk=1;
			ans+=cnt;
			cnt=0;
		}
	}
	printf("%d\n",ans);
}
int  main()
{
	int  T;scanf("%d",&T);
	while(T--)solve();
	return  0;
}

C

Meaning:
In other words, a fish \ (I \), if \ (a[i-1] < a[i] \) or \ (a[i+1] < a[i] \), can eat the position of \ (i-1 \) or \ (i+1 \), and then \ (a[i] + + + \). If a fish, assuming that only it can eat other fish in the whole world, and it can eat all the fish in the end, it is called the dominant fish, and then ask whether there is a dominant fish, and enter the number of one of the dominant fish.

First, consider the case of the largest weight. If the fish with the largest weight eats a fish, it will eat all the fish at will. Therefore, as long as there is a fish with the largest weight and one fish on the left and right sides is smaller than it, it is the dominant fish.

At that time, can we judge that there was no dominant fish? It is not difficult to find that the dominant fish found in this method must be correct, and if it cannot be found, if and only if all fish have the same weight, there is no dominant fish at this time, so this method is correct.

#include<cstdio>
#include<cstring>
#define  N  310000
using  namespace  std;
int  a[N],n;
inline  int  mymax(int  x,int  y){return  x>y?x:y;}
void  solve()
{
	scanf("%d",&n);
	int  mmax=1;
	for(int  i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		mmax=mymax(a[i],mmax);
	}
	a[0]=a[1];a[n+1]=a[n];
	for(int  i=1;i<=n;i++)
	{
		if(a[i]==mmax  &&  (a[i-1]!=a[i]  ||  a[i+1]!=a[i]))
		{
			printf("%d\n",i);
			return  ;
		}
	}
	printf("-1\n");
	return  ;
}
int  main()
{
	int  T;scanf("%d",&T);
	while(T--)solve();
	return  0;
}

The guy in the same computer room also thought of a similar stack, so I won't repeat it. Although the idea was wrong at first, it was later found that changing it could avoid the problem.

D

Meaning:
Each point has a weight, and then you can use the \ (n-1 \) edge to connect the \ (n \) points into a tree, and the weight of the points at both ends of the edge must not be the same.

Record the color of the first point, find the point with different color from the first point, and record it as \ (id \). If a point has different color from the first point, it will be connected to the first point. If it is the same as the first point, it will be connected to \ (id \).

The case of no solution is the case where \ (id \) cannot be found.

#include<cstdio>
#include<cstring>
#define  N  5100
using  namespace  std;
int  co[N],n;
void  solve()
{
	scanf("%d",&n);
	for(int  i=1;i<=n;i++)
	{
		scanf("%d",&co[i]);
	}
	int  shit=co[1];
	int  id=0;
	for(int  i=2;i<=n;i++)
	{
		if(co[i]!=shit)
		{
			id=i;
			break;
		}
	}
	if(!id)
	{
		printf("NO\n");
		return  ;
	}
	printf("YES\n");
	for(int  i=2;i<=n;i++)
	{
		if(co[i]!=shit)printf("1 %d\n",i);
		else  printf("%d %d\n",id,i);
	}
}
int  main()
{
	int  T;scanf("%d",&T);
	while(T--)solve();
	return  0;
 } 

E

Meaning:
I didn't know the meaning of the title until after the game
First of all, what is round dancing?
Have you seen the bonfire dinner? Dancing in a circle hand in hand is a round dance. Now divide the \ (n(n is an even number) \) person (the \ (i \) person number is \ (i \)) into two round dances.
It is recorded as a wheel dance scheme {\ (A,B \)}.
Two rounds \ (X,Y \) are the same. If and only if a point is selected as the beginning, the sequence formed from left to right is the same (that is to say, \ ([1,2,3] \) and \ ([3,2,1] \) are different).
The rotation schemes {\ (a {1}, B 1 \)} and {\ (a {2}, B 2 \)} are the same if and only if \ (a 1 = a 2, B 1 = B 2 \) or \ (a 1 = B 2, B 1 = a 2 \).
Ask how many different schemes there are, and the answer is guaranteed to be within the range of \ (long\) \(long \).

Practice:
Let \ (n=2m \), first select \ (m \) individuals to form the left circle, that is \ (C {n} ^ m \), but if \ (m \) individuals are selected, how many different circles are arranged? We might as well say in the title that fixing one person is in position one, and the others are all arranged, so it is \ ((n-1)! \), It is not difficult to find that this will not repeat and all schemes can be found (obviously correct, because everyone must be in the circle), and then \ (C {n} ^{m} * (m-1)* (m-1)!\), However, it is found that the left and right sides of a circle scheme will be selected, so \ (2 \) (in fact, there are ways to avoid it. Assuming that the person numbered \ (1 \) must be selected, it is \ (C {n-1} ^{M-1} \)).

Change the following formula:
\(\frac{C_{n}^{m}*(m-1)!*(m-1)!}{2}=\frac{n!*(m-1)!*(m-1)!}{2*m!*m!}=\frac{2n!}{n^2}=\frac{2(n-1)!}{n}\)

This formula is much simpler. This is the rule I found in the examination room.

Open the calculator and find that \ (19! \) won't explode \ (long\) \(long \) and mess with it directly.

#include<cstdio>
#include<cstring>
using  namespace  std;
int  main()
{
	int  n;scanf("%d",&n);
	if(n==2)printf("1\n");
	else
	{
		long  long  ans=1;
		for(int  i=1;i<n;i++)ans*=i;
		ans/=n/2;
		printf("%lld\n",ans);
	}
	return  0;
}

F

For a matrix of \ (n*m \), you can select \ (\ frac{m}{2} \) at most in each row, and then the sum of the selected numbers is required to be a multiple of \ (k \). Ask what is the maximum value of the sum.

Let \ (f[i][j][k] \) represent the \ (I \) number of each line, select \ (j \), and the remainder is the maximum value of \ (K \), so it is not difficult to think of the state transition equation.

Time complexity: \ (O(n^4) \)

#include<cstdio>
#include<cstring>
#define  N  90
using  namespace  std;
inline  int  mymax(int  x,int  y){return  x>y?x:y;}
int  a[N][N];
int  f[2][N][N];
int  n,m,K;
void  dp()
{
	memset(f[0],-20,sizeof(f[0]));
	f[0][0][0]=0;int  now=0,pre=1;
	int  limit=m/2;
	for(int  i=1;i<=n;i++)
	{
		now^=1;pre^=1;
		memset(f[now],-20,sizeof(f[now]));
		for(int  j=0;j<=limit;j++)
		{
			for(int  k=0;k<K;k++)f[now][0][k]=mymax(f[now][0][k],f[pre][j][k]);
		}
		for(int  j=1;j<=m;j++)
		{
			now^=1;pre^=1;
			memset(f[now],-20,sizeof(f[now]));
			for(int  k=1;k<=limit;k++)
			{
				for(int  t=0;t<K;t++)
				{
					int  shit=(t+a[i][j])%K;
					f[now][k][shit]=mymax(f[now][k][shit],f[pre][k-1][t]+a[i][j]);
				}
			}
			for(int  k=0;k<=limit;k++)
			{
				for(int  t=0;t<K;t++)f[now][k][t]=mymax(f[now][k][t],f[pre][k][t]);
			}
		}
	}
	now^=1;pre^=1;
	memset(f[now],-20,sizeof(f[now]));
	for(int  j=0;j<=limit;j++)
	{
		for(int  k=0;k<K;k++)f[now][0][k]=mymax(f[now][0][k],f[pre][j][k]);
	}
	printf("%d\n",f[now][0][0]);
}
int  main()
{
	scanf("%d%d%d",&n,&m,&K);
	for(int  i=1;i<=n;i++)
	{
		for(int  j=1;j<=m;j++)scanf("%d",&a[i][j]);
	}
	dp();
	return  0;
}

G

Meaning:
An undirected graph with \ (n \) points and \ (m \) edges has \ (k \) orders. Each order runs from \ (x \) to \ (y \), and the cost of each order is defined as the shortest path from \ (x \) to \ (y \), and the total cost is the sum of the costs of each order.

You can change one edge to \ (0 \) at most, and then ask you what the minimum total cost is.

Practice:
Run the shortest path for each point, because it is a sparse graph, \ (SPFA \) is very fast. In order not to be hack ed, another version of Dij was typed later

It must be a little less expensive to use opportunities than not to use them (at most unchanged).

Enumerate which side becomes \ (0 \). For the order \ (x - > y \), there are two operations: one is to follow the original path, and the other is to forcibly change the route in order to follow the \ (0 \). As for how to make \ (x - > y \) forcibly follow one side, you also understand. You can directly add the cost of \ (x \) walking to one end of the side and the cost of walking to \ (Y \) at the other end.

Dij time complexity: \ (O(nm\log{m}+mk) \)
SPFA:

#include<cstdio>
#include<cstring>
#define  N  1100
#define  M  2100
using  namespace  std;
typedef  long  long  LL;
inline  LL  mymin(LL  x,LL  y){return  x<y?x:y;}
LL  d[N][N];
int  list[N],head,tail,n,m,k;
bool  v[N];
struct  node
{
	int  y,next;
	LL  c;
}a[M];int  len,last[N];
inline  void  ins(int  x,int  y,LL  c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;} 
void  SPFA(int  st)
{
	memset(d[st],20,sizeof(d[st]));d[st][st]=0;
	list[head=1]=st;tail=2;v[st]=1;
	while(head!=tail)
	{
		int  x=list[head++];if(head==n+1)head=1;
		v[x]=0;
		for(int  k=last[x];k;k=a[k].next)
		{
			int  y=a[k].y;
			if(d[st][x]+a[k].c<d[st][y])
			{
				d[st][y]=d[st][x]+a[k].c;
				if(!v[y])
				{
					v[y]=1;
					list[tail++]=y;if(tail==n+1)tail=1;
				}
			}
		}
	}
}
struct  SHIT
{
	int  x,y;
	SHIT(int  xx=0,int  yy=0){x=xx;y=yy;}
}zjj1[N],zjj2[N];
int  main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int  i=1;i<=m;i++)
	{
		int  x,y;LL  c;scanf("%d%d%lld",&x,&y,&c);
		ins(x,y,c);ins(y,x,c);
		zjj2[i]=SHIT(x,y);
	}
	for(int  i=1;i<=k;i++)
	{
		int  x,y;
		scanf("%d%d",&x,&y);
		zjj1[i]=SHIT(x,y);
	}
	for(int  i=1;i<=n;i++)SPFA(i);
	LL  ans=(LL)99999999999999;
	for(int  i=1;i<=m;i++)
	{
		LL  sum=0;
		int  x=zjj2[i].x,y=zjj2[i].y;
		for(int  j=1;j<=k;j++)
		{
			int  ax=zjj1[j].x,ay=zjj1[j].y;
			sum+=mymin(mymin(d[ax][x]+d[y][ay],d[ax][y]+d[x][ay]),d[ax][ay]);
		}
		ans=mymin(ans,sum);
	}
	printf("%lld\n",ans);
	return  0;
}

Dij:

#include<cstdio>
#include<cstring>
#include<queue>
#define  N  1100
#define  M  2100
using  namespace  std;
typedef  long  long  LL;
inline  LL  mymin(LL  x,LL  y){return  x<y?x:y;}
LL  d[N][N];
int  n,m,k;
bool  v[N];
struct  node
{
	int  y,next;
	LL  c;
}a[M];int  len,last[N];
inline  void  ins(int  x,int  y,LL  c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
priority_queue<pair<LL,int>,vector<pair<LL,int> >,greater<pair<LL,int> > > fuck;
void  SPFA(int  st)
{
	memset(d[st],20,sizeof(d[st]));d[st][st]=0;
	memset(v,0,sizeof(v));
	while(!fuck.empty())fuck.pop();
	fuck.push(make_pair(0,st));
	for(int  i=1;i<=n;i++)
	{
		pair<LL,int>  zwq=fuck.top();fuck.pop();
		int  x=zwq.second;
		while(v[x])
		{
			zwq=fuck.top();fuck.pop();
			x=zwq.second;
		}
		v[x]=1;
		for(int  k=last[x];k;k=a[k].next)
		{
			int  y=a[k].y;
			if(!v[y]  &&  zwq.first+a[k].c<d[st][y])
			{
				d[st][y]=zwq.first+a[k].c;
				fuck.push(make_pair(d[st][y],y));
			}
		}
	}
}
struct  SHIT
{
	int  x,y;
	SHIT(int  xx=0,int  yy=0){x=xx;y=yy;}
}zjj1[N],zjj2[N];
int  main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int  i=1;i<=m;i++)
	{
		int  x,y;LL  c;scanf("%d%d%lld",&x,&y,&c);
		ins(x,y,c);ins(y,x,c);
		zjj2[i]=SHIT(x,y);
	}
	for(int  i=1;i<=k;i++)
	{
		int  x,y;
		scanf("%d%d",&x,&y);
		zjj1[i]=SHIT(x,y);
	}
	for(int  i=1;i<=n;i++)SPFA(i);
	LL  ans=(LL)99999999999999;
	for(int  i=1;i<=m;i++)
	{
		LL  sum=0;
		int  x=zjj2[i].x,y=zjj2[i].y;
		for(int  j=1;j<=k;j++)
		{
			int  ax=zjj1[j].x,ay=zjj1[j].y;
			sum+=mymin(mymin(d[ax][x]+d[y][ay],d[ax][y]+d[x][ay]),d[ax][ay]);
		}
		ans=mymin(ans,sum);
	}
	printf("%lld\n",ans);
	return  0;
}

Posted by love_php on Wed, 11 May 2022 02:18:36 +0300