Location>code7788 >text

2025/3/1 Class Record

Popularity：766 ℃/2025-03-08 21:49:26

Table of contents

  1. The arrangement of the ranch (Beast Legion 2)
  2. Turn off the light problemⅡ

  • Ranking of ranch(Beast Legion 2)

Beast Legion 1 is an eight-way

This question only has four directions

But there are terrain restrictions on this question

Therefore, when you find the legal status of each line, you will find that the legal status of almost every line is different

Therefore, we need to set a new array: num is used to store the binary corresponding to the legal status of each row.

It is worth noting that: map[i]=(map[i]<<1)+1-x;

Here we did not store the input directly into the map, but instead took the inverse, that is, 1->0, 0->1

Why do you need to reverse it?

Because when judging whether a state is legal, you need to use "&"

This & can only tell whether there is a overlapping 1, but not 0

Then, imagine the barren land as if there are obstacles placed on the land (building a house), which is expressed as 1

The one who has not built a house is 0

If the position of a cow coincides with the house or overlaps with another cow that moves left and moves to the left

Then this state is illegal

The rest is almost the same as the Beast Legion 1

This is the code I wrote myself and submitted the AC
#include<iostream>
using namespace std;
int map[15],sum[15],num[15][250],f[15][250];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			{
				int x;
				cin>>x;
				map[i]=(map[i]<<1)+1-x;	
			}
	for(int i=1;i<=n;i++)
		for(int j=0;j<(1<<m);j++)
		{
			if(j&(j<<1)||j&(j>>1)||j&map[i])continue;
			sum[i]++;
			num[i][sum[i]]=j;
		}
	num[0][1]=0;
	sum[0]=1;
	f[0][1]=1;
	long long int ans=0;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=sum[i];j++)
		{
			int a=num[i][j];
			for(int k=1;k<=sum[i-1];k++)
			{
				int b=num[i-1][k];
				if(a&b)continue;
				f[i][j]+=f[i-1][k];
			}
			if(i==n)ans+=f[i][j];
		}
	cout<<ans%100000000<<"\n";
/*	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=1<<m;j++)
			cout<<f[i][j];
		cout<<"\n";
	}
	for(int i=1;i<=15;i++)cout<<sum[i];*/
	return 0;
}

  • Turn off the light problemⅡ

Can't understand a little

The example is to first press the second button and turn off the middle light.

Then press the first button and turn off the first and third lights

Just put the code
#include<bits/stdc++.h>
 #define IL inline
 #define RI register int
 IL void in(int &x)
 {
     int f=1;x=0;char s=getchar();
     while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
     while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
     x*=f;
 }
 int a[108][18],f[2048],n,m;
 int main()
 {
     in(n); // cin
	 in(m);
     memset(f,0x3f,sizeof f);
    
     for(RI i=1;i<=m;i++) // Read in
         for(RI j=1;j<=n;j++)
             in(a[i][j]);
            
     f[(1<<n)-1]=0; // f[s]= Min. times
     //1 means on; 0 means off;
     for(RI i=(1<<n)-1;i>=0;i--) // Enumerate all states
     {
         for(RI j=1;j<=m;j++) // Enumerate all switches
         {
             int now=i;
             for(RI l=1;l<=n;l++) // Enumerate all bulbs
             {
                 if(a[j][l]==0) // If it is 0, no matter whether the light is on or not, don't worry.
				     continue;
                 if(a[j][l]==1 && (i&(1<<(l-1)))) // If a[i][j] is 1, then turn it off when the light is on, otherwise don't worry
				     now^=(1<<(l-1)); // l bit 0 of now
				     //now=i-(1<<(l-1));
                 if(a[j][l]==-1 && !(i&(1<<(l-1)))) //If it is -1, if the light is off, turn it on, otherwise don't worry
				     now^=(1<<(l-1)); // l bit 1 of now
             }
             f[now]=std::min(f[now],f[i]+1); // At least a few buttons are required to turn them all off
         }
     }
     printf("%d",f[0]==1061109567?-1:f[0]);
 }

 

<Previous Next>