15.10.06【矩阵乘法、枚举、贪心+二分查找】

OI&ACM, OI训练
  1. 1.斐波那契数列 (fibonacci)
  2. 2.翻转棋 (fliptile)
  3. 3.集合 (set)

100+100+30

1.斐波那契数列 (fibonacci)

【问题描述】 大家都知道，斐波那契数列是满足如下性质的一个数列： • f(1) = 1 • f(2) = 1 • f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数) 请你求出 f(n) mod 1000000007 的值。

矩阵乘法+快速幂 这题比较水

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include<cstring>
#include<cstdio>
using namespace std;
int m=1000000007;
long long n,ans;
long long X[3][3],A[3][3]={{0,0,0},{0,0,1},{0,1,1}},
                  N[3][3]={{0,0,0},{0,0,1},{0,1,1}};
void cheng(int x)
{
	memset(X,0,sizeof(X));
	if(!x)
	{
		for(int i=1;i<=2;i++)
		  for(int j=1;j<=2;j++)
		    for(int k=1;k<=2;k++)
		    X[i][j]=(X[i][j]+A[i][k]*N[k][j])%m;
		memcpy(N,X,sizeof(X));
	}
	else
	{
		for(int i=1;i<=2;i++)
		  for(int j=1;j<=2;j++)
		    for(int k=1;k<=2;k++)
		    X[i][j]=(X[i][j]+N[i][k]*N[k][j])%m;
		memcpy(N,X,sizeof(X));
	}
}
void mi(long long n)
{
	if(n==1) return;
	mi(n/2);
	cheng(1);//N*N
	if(n%2) cheng(0);//N*A
}
int main()
{
	freopen("fibonacci.in","r",stdin);
	freopen("fibonacci.out","w",stdout);
	scanf("%lld",&n);
	if(n==1||n==2) {printf("1");return 0;}
	mi(n-2);
	ans=(N[2][1]+N[2][2])%m;
	printf("%d",ans);
}

2.翻转棋 (fliptile)

【题目描述】 农夫约翰知道，聪明的奶牛可以产更多的牛奶。他为奶牛设计了一种智力游戏，名叫翻转棋。 翻转棋可以分成 M × N 个格子，每个格子有两种颜色，一面是黑的，一面是白的。 一旦翻转某个格子，这个格子的颜色就会颠倒。如果把所有的格子都翻成白的，就算奶牛赢了。然而，奶牛的蹄子很大，一旦它们打算翻转某个格子，这个格子附近（即和这个格子有公共边）的格子也会被翻转。一直翻来翻去也很无聊，奶牛们想最小化必须翻动的次数。 请帮助奶牛确定翻动的最少次数和具体的翻法。如果最小解有多个，则输出在字典序意义下最小的那个，如果不可能完成任务，则只要输出一行单词：IMPOSSIBLE。

如果第一行定了，那么后面都定了，所以状压枚举第一行就行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<cstring>
#include<cstdio>
using namespace std;
int f[5][2]={{1,0},{0,-1},{0,0},{0,1},{-1,0}};
int a[16][16],b[16][16],c[16][16],ans[16][16];
int m,n,x,inf,yes;
int main()
{
	freopen("fliptile.in","r",stdin);
	freopen("fliptile.out","w",stdout);
	scanf("%d%d",&m,&n);
	memset(ans,0x7f,sizeof(ans));inf=ans[0][0];
	for(int i=1;i<=m;i++)
	  for(int j=1;j<=n;j++)
	    scanf("%d",&a[i][j]);
	memcpy(b,a,sizeof(a));
	for(int i=0;i<(1<<n);i++)
	{
		x=0;
		memset(c,0,sizeof(c));
		for(int j=0;j<n;j++)  if((i&(1<<j)))  c[1][n-j]=1,x++;
		for(int j=1;j<=n;j++)
		if(c[1][j])
		{
			for(int k=0;k<5;k++)
			if(1+f[k][0]>=1&&1+f[k][0]<=m&&j+f[k][1]>=1&&j+f[k][1]<=n)
			a[1+f[k][0]][j+f[k][1]]=a[1+f[k][0]][j+f[k][1]]^1;
		}
		for(int num=2;num<=m;num++)
		{
			for(int j=1;j<=n;j++)
	        if(a[num-1][j])
	        {
	        	c[num][j]=1;x++;
	  	        for(int k=0;k<5;k++)
		        if(num+f[k][0]>=1&&num+f[k][0]<=m&&j+f[k][1]>=1&&j+f[k][1]<=n)
		        a[num+f[k][0]][j+f[k][1]]=a[num+f[k][0]][j+f[k][1]]^1;
	        }
		}
		yes=1;
		for(int j=1;j<=n;j++)
		  if(a[m][j]) {yes=0;break;}
		if(yes&&x<ans[0][0])
		{
			memcpy(ans,c,sizeof(c));
			ans[0][0]=x;
		}
		memcpy(a,b,sizeof(b));
	}
	if(ans[0][0]==inf) printf("IMPOSSIBLE");
	else
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=n;j++)
	      printf("%d ",ans[i][j]);
	    printf("\n");
	}
}

3.集合 (set)

【题目描述】 集合是数学中的一个概念，用通俗的话来讲就是：一大堆数在一起就构成了集合。集合有如下的特性： • 无序性：任一个集合中，每个元素的地位都是相同的，元素之间是无序的。 • 互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。 • 确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。 例如 A = {1, 2, 3} 就是一个集合。我们可以知道， 1 属于 A ，即 1 ∈ A ； 4 不属于 A ，即 4 ∉ A 。一个集合的大小，就是其中元素的个数。 现在定义一个特殊的 k-集合，要求满足： • 集合的所有特性 • 对任意一个该集合内的元素 x ，不存在一个数 y ，使得 y = kx 并且 y 属于该集合。即集合中的任意一个数，它乘以 k 之后的数都不在这个集合内给你一个由 n 个不同的数组成的集合，请你从这个集合中找出一个最大的 k-集合。

如果是k=2时，1 2 4 8 16 最多可以有5个，隔一个加一个 然而我之前想的是只有1个，只拿了30，不知道哪根筋抽了 所以用一个数组，如果x/k加的话，x不加；x/k不加的话，x加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<algorithm>
#include<cstdio>
using namespace std;
int n,k,l,r,mid,ans;
long long a[100001],minn,maxx,x;
bool no[100001];
int main()
{
	freopen("set.in","r",stdin);
	freopen("set.out","w",stdout);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
	  {
	  	scanf("%lld",&a[i]);
	  	if(!a[i]) i--,n--;
	  }
	sort(a+1,a+n+1);
	if(k==0)
	{
		if(0>=minn||0<=maxx)
		{
			l=1;r=n;
		    while(l!=r)
		    {
			    mid=(l+r)/2;
			    if(a[mid]>=0) r=mid;
			    else l=mid+1;
		    }
		    if(a[l]==0) x=1;
		}
		printf("%d",n-x);return 0;
	}
	minn=a[1];maxx=a[n];
	for(int i=1;i<=n;i++)
	if(!(a[i]%k))
	{
		x=a[i]/k;
		if(x<minn||x>maxx) continue;
		l=1;r=n;
		while(l!=r)
		{
			mid=(l+r)/2;
			if(a[mid]>=x) r=mid;
			else l=mid+1;
		}
		if(a[l]==x) no[i]=!no[l];
	}
	for(int i=1;i<=n;i++)
	  if(!no[i]) ans++;
	printf("%d",ans);
}