步骤

点击B2格 （第二行第一列）
	
按下Ctrl+Shift+End
	
所有数据行已选（除了首行）
 



 

快捷键Ctrl+Shift+End的作用：从当前选定的行开始，选择到本表的最后一行。

 

 

参考： http://www.winwin7.com/jc/8714.html

题目意思是给一个m*n的01矩阵，将剩余的n-m行01矩阵填满，并保证最后的n*n的矩阵每一行和每一列都有且仅有两个1，问有多少种填法。 

对于每一行，我们都可以从上一行的所有状态中推出当前这一行填01的方法种数。对于填哪两列其实我们并不用关心，只需要记录到当前行由几个列选了0个1和1个1即可。这样配合组合数就可以进行O(n3)的dp转移。 

但是实际上我们知道了当前行有多少个“0”（即0个1），我们便可以求出有多少个“1”，因为01矩阵1的总个数是确定的。这样dp的时间复杂度就变成了O(n2).



#include <bits/stdc++.h>
using namespace std;
int n, m, mod;
typedef long long ll;
const int maxn = 1000 + 5;
char s[maxn][maxn];
ll d[2][500+5][500+5];
ll C[maxn][maxn];
int main(int argc, char const *argv[])
{
    scanf("%d%d%d", &n, &m ,&mod);
    C[1][0] = C[1][1] = 1;
    for(int i = 2; i < 600; ++i) {
        C[i][0] = 1;
        for(int j = 1; j < 600; ++j) {
            C[i][j] = (C[i-1][j]+C[i-1][j-1])%mod;
        }
    }
    for(int i = 1; i <= m; ++i) {
        scanf("%s", s[i] + 1);
    }
    int a  = 0 ,b = 0, c = 0;
    for(int j = 1; j <= n; ++j) {
        int cnt = 0;
        for(int i = 1; i <= m; ++i) {
            if(s[i][j] == '1') cnt++;
        }
        if(cnt == 0) a++;
        else if(cnt == 1) b++;
        else c++;
    }
    d[0][a][b] = 1;
    int x = 0;
    for(int i = m+1; i <= n; ++i) {
        x ^= 1;
        for(int j = 0; j <= n; ++j) {
            int k = ((n-i+1) << 1) - (j << 1);
            if(k < 0 || k > n) continue;
            if(j >= 2){
                (d[x][j-2][k+2] += d[x^1][j][k] * C[j][2] % mod) %= mod;
            }
            if(j >= 1 && k >= 1) {
                (d[x][j-1][k] += d[x^1][j][k] * j * k % mod) %= mod; 
            }
            if(k >= 2){
                (d[x][j][k-2] += d[x^1][j][k] * C[k][2] % mod) %= mod;
            }
        }
    }
    cout << d[x][0][0] << endl;
    return 0;
}

8*8的棋盘，8个皇后放入其中，要求所有任何皇后不能在同一行同一列，也不能都在对角线线上
对每一个皇后的候选位置进行探测，（每个皇后的候选位置都是从第一个到最后一个），如果当前位置不和之前的皇后冲突，则选下一个皇后的，否则就要向前回溯，把上一个选好位置皇后的位置往后移一个
代码如下



#include <iostream>
#include <vector>
#include <set>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int n = 8;
int sum = 1;
bool flag;
vector<int> vec(n,0);
vector<int> result(n,0);

void QUEEN(int k)
{
	for(int i=1;i<=n;++i)  
	{
		flag = true;
		for(int b=0; b<k; ++b)
		{
			if((b-k)==(i-vec[b]) || (k-b)==(i-vec[b]) || (i==vec[b]))
			{
				flag = false;
				break;
			}
		}
		if(flag) //部分的解，当前位置合法
		{
			vec[k] = i;
			if(k==n-1)    //所有皇后已经放完 
			{
				cout<<"第 "<<sum++<<" 种方案 ";
				for(size_t i=0;i<n;++i)
					cout<<vec[i]<<" ";
				cout<<endl;
				return;
			}
			QUEEN(k+1);
		}
	}
	return;
}
void queen()
{
	sum = 1;
	QUEEN(0);  //从第一个皇后开始放 
	if(sum==1)
		cout<<"无解"<<endl;
}
void Queen()
{
	int k = 0;
	while( k>=0 )
	{
		while(vec[k]<=n-1)   //每一个皇后的候选位置从 0 到 7 
		{
			vec[k] += 1;    
			flag = true;
			for(int b=0; b<k; ++b)   // 检测当前位置是否合法，就是不和之前已经放完的皇后位置冲突 
			{
				if((b-k)==(vec[k]-vec[b]) || (k-b)==(vec[k]-vec[b]) || (vec[k]==vec[b]))  
				{
					flag = false;
					break;
				}
			}
			if(flag) //部分的解，当前位置合法 ,不合法则继续向后探测，看这个皇后还有没有候选的位置 
			{
				result[k]=vec[k];  //记录这个皇后选出来的位置 
				if(k==n-1)    //所有皇后已经放完 
				{
					cout<<"第 "<<sum++<<" 种方案 ";
					for(size_t i=0;i<n;++i)
						cout<<result[i]<<" ";
					cout<<endl;
					break;
				}
				++k;
			}
		}
		vec[k] = 0;  //当前皇后的所有位置都已探测完毕，没有候选的位置了，
		--k;   //   回溯，只能把前一个选完的皇后的位置向后移一个  
	}
	if(sum==1)
		cout<<"无解"<<endl;
	return;
} 
int main(int argc, char** argv) 
{
	Queen();  //非递归，迭代 
	cout<<endl;
	//queen();  //递归 
	return 0;
}


运行结果

题目大意：

对于任意的2*2的正方形，可以选择其中的任意三个（0–>1,1–>0），使得进行若干次操作之后让所有的元素变成0.
Easy版本：操作次数不超过3nm
Hard版本：操作次数不超过nm
思路：
直接写nm的方法吧（比赛的时候觉得不可能麻烦到去讨论2 * 2的内部单独情况，于是就换思路了，结果今早还是换成了一开始的办法）。从上到下，从左到右（不包括最后两行，和最后一列），一旦当前的a[i][j]==1,那么就选择(i,j),(i,j+1),(i+1,j+1)进行变化。对于最后一列的选择(i,m),(i+1,m),(i+1,m-1)进行变化。对于最后两行的，从左到右，如果a[n-1]][j]==1就选择(n-1,j),(n-1,j+1),(n,j+1)；如果a[n][j]==1就选择(n,j),(n,j+1),(n-1,j+1),这样就只剩下右下角的 2 * 2的小方格了，比赛的时候就这里出问题了。今天早上想的方法是分别讨论1的个数为0，1，2，3，4的情况：
0：不需要变换，直接输出；
3：变换那3个1的位置，操作次数为1；
2：变换2个0的位置+任意一个1的位置，转换成了1的个数为3的情况，操作次数共为2；
1：变换1的位置+任意2个0的位置，转换成了1的个数为2个情况，操作次数为3；
4：变换任意3个1的位置，操作次数为4.
代码：
#include<bits/stdc++.h>
using namespace std;
const int maxn=200+5;
int a[maxn][maxn],T,n,m;char s[maxn][maxn];
struct Node{
	int x1,Y1,x2,Y2,x3,Y3;
}ans[maxn*maxn];
int main(){
	cin>>T;
	while(T--){
		cin>>n>>m;int tot=0;
		for(int i=1;i<=n;i++)cin>>s[i]+1;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=m;j++)a[i][j]=s[i][j]-'0';
		for(int i=1;i<=n-2;i++){
			for(int j=1;j<=m-1;j++){
				if(a[i][j]==0)continue;
				tot++;
				ans[tot].x1=i;ans[tot].Y1=j;ans[tot].x2=i;ans[tot].Y2=j+1;ans[tot].x3=i+1;ans[tot].Y3=j+1;
				a[i][j]=0;a[i][j+1]=1-a[i][j+1];a[i+1][j+1]=1-a[i+1][j+1];
			}
			if(a[i][m]){
				tot++;
				ans[tot].x1=i;ans[tot].Y1=m;ans[tot].x2=i+1;ans[tot].Y2=m;ans[tot].x3=i+1;ans[tot].Y3=m-1;
				a[i][m]=0;a[i+1][m]=1-a[i+1][m];a[i+1][m-1]=1-a[i+1][m-1];
			}
		}
		for(int i=1;i<=m-2;i++){
			if(a[n-1][i]){
				tot++;
				ans[tot].x1=n-1;ans[tot].Y1=i;ans[tot].x2=n-1;ans[tot].Y2=i+1;ans[tot].x3=n;ans[tot].Y3=i+1;
				a[n-1][i]=0;a[n-1][i+1]=1-a[n-1][i+1];a[n][i+1]=1-a[n][i+1];
			}
			if(a[n][i]){
				tot++;
				ans[tot].x1=n;ans[tot].Y1=i;ans[tot].x2=n;ans[tot].Y2=i+1;ans[tot].x3=n-1;ans[tot].Y3=i+1;
				a[n][i]=0;a[n][i+1]=1-a[n][i+1];a[n-1][i+1]=1-a[n-1][i+1];
			}
		}
		int cnt=a[n][m]+a[n-1][m-1]+a[n-1][m]+a[n][m-1];
		int t[6][10]={0};
		if(cnt==1){
			tot++;int cnt=0,sign=0;
			for(int i=n-1;i<=n;i++){
				for(int j=m-1;j<=m;j++){
					if(a[i][j]){
						t[1][++cnt]=i;t[1][++cnt]=j;a[i][j]=0;
					}
					else{
						if(sign>=2)continue;
						sign++;
						t[1][++cnt]=i;t[1][++cnt]=j;a[i][j]=1;
					}
					if(cnt==6)break;
				}
			}
			sign=0;cnt=0;tot++;
			for(int i=n-1;i<=n;i++){
				for(int j=m-1;j<=m;j++){
					if(a[i][j]){
						if(!sign){
							sign=1;t[2][++cnt]=i;t[2][++cnt]=j;a[i][j]=0;
						}
						continue;
					}
					t[2][++cnt]=i;t[2][++cnt]=j;a[i][j]=1;
					if(cnt==6)break;
				}
			}
			tot++;cnt=0;
			for(int i=n-1;i<=n;i++){
				for(int j=m-1;j<=m;j++){
					if(!a[i][j])continue;
					t[3][++cnt]=i;t[3][++cnt]=j;
				}
			}
			cout<<tot<<endl;
			for(int i=1;i<=tot-3;i++)cout<<ans[i].x1<<' '<<ans[i].Y1<<' '<<ans[i].x2<<' '<<ans[i].Y2<<' '<<ans[i].x3<<' '<<ans[i].Y3<<endl;
			for(int i=1;i<=3;i++)cout<<t[i][1]<<' '<<t[i][2]<<' '<<t[i][3]<<' '<<t[i][4]<<' '<<t[i][5]<<' '<<t[i][6]<<endl; 
		}
		else if(cnt==2){
			tot++;int sign=0,cnt=0;
			for(int i=n-1;i<=n;i++){
				for(int j=m-1;j<=m;j++){
					if(a[i][j]){
						if(!sign){
							sign=1;t[1][++cnt]=i;t[1][++cnt]=j;a[i][j]=0;
						}
						continue;
					}
					t[1][++cnt]=i;t[1][++cnt]=j;a[i][j]=1;
					if(cnt==6)break;
				}
			}
			tot++;cnt=0;
			for(int i=n-1;i<=n;i++){
				for(int j=m-1;j<=m;j++){
					if(!a[i][j])continue;
					t[2][++cnt]=i;t[2][++cnt]=j;
				}
			}
			cout<<tot<<endl;
			for(int i=1;i<=tot-2;i++)cout<<ans[i].x1<<' '<<ans[i].Y1<<' '<<ans[i].x2<<' '<<ans[i].Y2<<' '<<ans[i].x3<<' '<<ans[i].Y3<<endl;
			for(int i=1;i<=2;i++)cout<<t[i][1]<<' '<<t[i][2]<<' '<<t[i][3]<<' '<<t[i][4]<<' '<<t[i][5]<<' '<<t[i][6]<<endl; 
		}
		else if(cnt==3){
			tot++;int cnt=0;
			for(int i=n-1;i<=n;i++){
				for(int j=m-1;j<=m;j++){
					if(!a[i][j])continue;
					t[1][++cnt]=i;t[1][++cnt]=j;
				}
			}
			cout<<tot<<endl;
			for(int i=1;i<=tot-1;i++)cout<<ans[i].x1<<' '<<ans[i].Y1<<' '<<ans[i].x2<<' '<<ans[i].Y2<<' '<<ans[i].x3<<' '<<ans[i].Y3<<endl;
			for(int i=1;i<=1;i++)cout<<t[i][1]<<' '<<t[i][2]<<' '<<t[i][3]<<' '<<t[i][4]<<' '<<t[i][5]<<' '<<t[i][6]<<endl; 
		}
		else if(cnt==4){
			cout<<tot+4<<endl;
			for(int i=1;i<=tot;i++)cout<<ans[i].x1<<' '<<ans[i].Y1<<' '<<ans[i].x2<<' '<<ans[i].Y2<<' '<<ans[i].x3<<' '<<ans[i].Y3<<endl;
			cout<<n-1<<' '<<m-1<<' '<<n<<' '<<m-1<<' '<<n<<' '<<m<<endl;
			cout<<n-1<<' '<<m-1<<' '<<n-1<<' '<<m<<' '<<n<<' '<<m<<endl;
			cout<<n-1<<' '<<m-1<<' '<<n-1<<' '<<m<<' '<<n<<' '<<m-1<<endl;
			cout<<n-1<<' '<<m<<' '<<n<<' '<<m-1<<' '<<n<<' '<<m<<endl;
		}
		else{
			cout<<tot<<endl;
			for(int i=1;i<=tot;i++)cout<<ans[i].x1<<' '<<ans[i].Y1<<' '<<ans[i].x2<<' '<<ans[i].Y2<<' '<<ans[i].x3<<' '<<ans[i].Y3<<endl;
		}
	}
	return 0;
}