今日新闻 最新消息 大事/seo网络营销推广公司

1.AcWing 327. 玉米田

AcWing 327. 玉米田 - AcWing

无脑状态表示：考虑前i行，第i行状态是j。为了方便，遍历到n+1行，答案是f(n+1,0)；

满足的要求：上一行状态k。k&j==0，每一层不能有相邻两个1

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N =13,M=1<<N;int n,m;
int f[N][M];
int g[N];
vector<int> state;
vector<int> head[M];
const int mod=1e8;bool check(int state)
{for(int i=0;i<m;i++){if((state>>i&1) && (state>>i+1&1)) return false;}return true;
}void get_state()
{for(int i=0;i<1<<m;i++) if(check(i)) state.push_back(i);for(int i=0;i<state.size();i++){for(int j=0;j<state.size();j++){int a=state[i],b=state[j];if((a&b)==0) head[i].push_back(j);}}
}int main()
{cin>>n>>m;for(int i=1;i<=n;i++){for(int j=0;j<m;j++){int t;cin>>t;g[i]+=!t<<j;}}get_state();f[0][0]=1;for(int i=1;i<=n+1;i++){for(int a=0;a<state.size();a++){if(g[i]&state[a]) continue;for(int b:head[a]){f[i][a]=(f[i][a]+f[i-1][b])%mod;}}}cout<<f[n+1][0]<<endl;
}作者：yankai
链接：https://www.acwing.com/activity/content/code/content/6087799/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

2.1194. 岛和桥

1194. 岛和桥 - AcWing题库

 这怎么能是个简单题呢，，虽然思路不难www。

1.预处理sum=权值之和。然后不用管它，最后记得加上

2.预处理边权为两点权值乘积即可。

3.存在哈密顿路径中相邻三点成环，额外加上三点权值乘积。因此需要记录当前点，还要多一维状态记录从哪个点转移过来。

4.求条数。初始化为1，如果状态更新就等于更新来的方案数，如果相等就加上。

其他tips：

1.正反两条路径被视为同一条路径，所以方案数要除以2

2.最后在计算方案数的时候不要忘记加上相等状态的方案数

3.状压dp，节点下标从0开始。

3.是哈密顿路径而不是哈密顿环，因此路径起点的选择对问题求解有影响。所以建立超级原点n，因此初始时合法状态为，从n点到i点，状态为1<<i。此外，求解时，当前点和上一个点时从0到n-1，因为从n到某点的状态已经被初始化。但是遍历上上个点的时候，会存在从n号点转移到上一个点的情况，因此，上上个点遍历到n号点。于此同时，处理上一个点时整体状态是否包含上上个点时要对n号点特判。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N =14,M=1<<14;int edge[N][N];
int f[N][N][M];//当前所在，上一步所在，当前状态
int w[N];
int n;
int m;
int g[N][N][M];//方案数
//wa总结：起点有影响，因此应该建立超级原点处理起点。设超级原点为n。所以初始化f应该初始化所有n到0-n-1起点的状态
//状压dp 下标从0开始pair<int,int> ans;void solve()
{cin>>n>>m;int sum = 0;for(int i=0;i<n;i++) cin>>w[i],sum+=w[i];memset(edge,0,sizeof edge);for(int i=0;i<m;i++){int a,b;cin>>a>>b;a--,b--;edge[a][b]=edge[b][a]=w[a]*w[b];}memset(f,-0x3f,sizeof f);memset(g,0,sizeof g);for(int i=0;i<n;i++){f[i][n][1<<i]=0;g[i][n][1<<i]=1;}for(int i=0;i<1<<n;i++){for(int j=0;j<n;j++)//状态i 当前点{if((i>>j)&1==0) continue;int s1=i^(1<<j);//i-j   上一步状态for(int k=0;k<n;k++)//状态i上一个点{if(!edge[k][j]) continue;//k到j没有边 if((s1>>k)&1==0) continue;int s2=s1^(1<<k)^(1<<n);//注意上上个点可能是n   上上步状态+nfor(int u=0;u<=n;u++)//上上个点  注意上上个点可能是n{if((u!=n&&edge[u][k]==0)) continue;if((s2>>u)&1==0) continue;int t=f[k][u][s1]+edge[k][j]+(edge[j][u]?edge[j][u]*w[k]:0);if(f[j][k][i]<t){f[j][k][i]=t;g[j][k][i]=g[k][u][s1];}else if(f[j][k][i]==t)g[j][k][i] += g[k][u][s1];}}            }}ans={0,0};for(int j=0;j<n;j++){for(int k=0;k<n;k++){if(ans.first<f[j][k][(1<<n)-1])ans.first=f[j][k][(1<<n)-1],ans.second=g[j][k][(1<<n)-1];else if(ans.first==f[j][k][(1<<n)-1]) ans.second+=g[j][k][(1<<n)-1];}}if(ans.second>0)printf("%d %d\n",ans.first+sum,ans.second/2);//正反相等else puts("0 0");}
int main()
{int T;cin>>T;while(T--){solve();}return 0;
}

3.183. 靶形数独

183. 靶形数独 - AcWing题库

解决数独问题，同时求解最大分值。

其实和之前做过的数独基本相似，这里回忆几个要处理的点

1.每个行列，区域，有一个二进制数表示哪些数可填。

2.需要一个map，能根据二进制数判断哪些数可取。

3.lowbit可以处理每一位。

4.ones数组存储有多少位数字可填。

5.draw函数，表示在x，y位置填t，如果t是负数就把该位置置零

6.dfs函数。每次找出可填数字最少的点，接着dfs可填数。

7.dfs中显然需要存储状态：还需要填几个数，当前填法得了多少分。当剩0个数时，记录答案，return

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N =9,M=1<<N;int row[N],col[N],cell[N/3][N/3];
int ones[M], map[M];
int  g[N][N];
int ans=-1;inline int lowbit(int x)
{return x&-x;
}inline int get_score(int x,int y,int t)
{return (min(min(x, 8 - x), min(y, 8 - y)) + 6) * t;
}void init()
{for(int i=0;i<N;i++) map[1<<i]=i;for(int i=0;i<M;i++)for(int j=i;j;j-=lowbit(j)){ones[i]++;}for(int i=0;i<9;i++)  row[i]=col[i]=cell[i / 3][i%3]=M-1;
}inline void draw(int x,int y,int t)
{int s=1;if(t>0){s=1;g[x][y]=t;}else s=-1,g[x][y]=0,t=-t;t--;row[x]-=(1<<t)*s;col[y]-=(1<<t)*s;cell[x/3][y/3]-=(1<<t)*s;}inline int get(int x,int y) //获得该点可填数字状态
{return row[x]&col[y]&cell[x/3][y/3];
}void dfs(int cnt,int score)
{if(cnt==0) {ans=max(ans,score);}int minv=10;int x,y;//找出可填数字最少的位置.for(int i=0;i<N;i++)for(int j=0;j<N;j++){if(!g[i][j]){int t=ones[get(i,j)];if(t<minv){minv=t;x=i,y=j;}}}for(int i=get(x,y);i;i-=lowbit(i)){int t=map[lowbit(i)] +1;draw(x,y,t);dfs(cnt-1,score+get_score(x,y,t));draw(x,y,-t);}}int main()
{init();int cnt=0,score=0;for(int i=0;i<N;i++)for(int j=0;j<N;j++){int x;cin>>x;if(x){draw(i,j,x);score+=get_score(i,j,x);}else cnt++;}dfs(cnt,score);cout<<ans;
}

4.虫食算

184. 虫食算 - AcWing题库

晚上脑子晕了，思路混乱。第一眼感觉从右往左枚举，枚举该列算式上出现的字母，如果没有被赋值就遍历赋值，然后继续搜。如果被赋值了，那么就可以判断。

但是如果有的被赋值，有的没被赋值，那这个搜索框架就很难处理。

然后又想从A到Z枚举每个字母代表的值，然后从右往左枚举算式。这样搜索框架好写了，但是搜不出来，从右往左一开始遇到的不一定就是A，状态更新非常之玄学。

最后才发现，结合两个思路就能写了。从右往左枚举，搜索框架里，枚举的是从右往左从上往下出现的字母。

接着是判断合不合法。如此搜索，如果一列上三个字母都已确定，那么看上一位的进位如何。如果有不确定的，进位就不能确定。一开始以为出现不确定的还需要进行什么奇怪的方法判断有没有问题。最后发现，如果有不确定的字母，直接摆烂，把进位设置为不确定即可。

如果三个确定，且进位确定，那直接判断即可。如果进位不确定，则判断在进位为0或者为1的时候是否有成立的状态。

最后要注意，最高位加完以后不能有进位。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N =30;int num[N];
int n;
char eq[3][N];
int q[N],cnt;
bool st[N];bool check()
{int t=0;for(int i=n-1;i>=0;i--){int x = num[eq[0][i] - 'A'], y = num[eq[1][i] - 'A'], z = num[eq[2][i] - 'A'];if ( x!= -1 && y != -1 && z != -1){if(t==-1){if((x+y+1)%n!=z&&(x+y)%n!=z) return false;if(!i&&x+y>=n) return false;                }else {if((x+y+t)%n!=z) return false;if(!i&&x+y+t>=n) return false;t=(x+y+t)/n;}}else t=-1;}return true;
}bool dfs(int u)//搜索第i个字母 代表的数
{if(u==n) return true;//所有都搜完了，没出现问题，truefor(int i=0;i<n;i++){if(!st[i]){num[q[u]]=i;st[i]=true;if(check()&&dfs(u+1)) return true;num[q[u]]=-1;st[i]=false;}}return false;}int main()
{cin >> n >> eq[0] >> eq[1] >> eq[2];for (int i = n - 1, k = 0; i >= 0; i -- )for (int j = 0; j < 3; j ++ ){int c = eq[j][i] - 'A';if (!st[c]){st[c] = true;q[k ++ ] = c;}}memset(st,0,sizeof st);memset(num,-1,sizeof num);dfs(0);for(int i=0;i<n;i++) cout<<num[i]<<" ";
}