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

  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 的值。

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

#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。

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

#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加

#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);
}