又写次矩阵模乘,表示看了解题报告后,才知道是矩阵题。练得题少的缘故。应该看懂题就能分析出是什么题。勤加练习,加油!吖飒~~~~
hdu2276,数据比较水,很快就AC了,nyoj一直TLE,后来用结构体写AC啦。大概是初始化和函数的调用浪费的时间。
题意:
一个环形排列的灯,灯的左侧灯状态为1,改变该灯的状态。否则不改变。n轮过后,所有灯的状态。
递推矩阵为:
1 1 0 0 0 0 0
0 1 1 0 0 0 0
0 0 1 1 0 0 0
0 0 0 1 1 0 0
0 0 0 0 1 1 0
1 0 0 0 0 1 1
乘的结果对2取余
hdu AC的代码:
#include<stdio.h>
#include<string.h>
char num[101];
int initmatrix[1][101];//初始矩阵
int matrix[101][101]={0};//递推矩阵
int temp[101][101];
int len;//矩阵行/列数
void calculate(int a[][101],int b[][101],int m,int p)//m*len...len*p
{
int i,j,k;
int res[101][101];
for(i=0;i<m;i++)
{
for(j=0;j<p;j++)
{
res[i][j]=0;
for(k=0;k<len;k++)
res[i][j]+=a[i][k]*b[k][j];
res[i][j]%=2;
}
}
for(i=0;i<m;i++)
for(j=0;j<p;j++)
a[i][j]=res[i][j];
}
void multiply(int temp[][101],int x)
{
if(x==1) return ;
multiply(temp,x>>1);
calculate(temp,temp,len,len);
if(x&1)
calculate(temp,matrix,len,len);
}
int main()
{
//freopen("Input.txt","r",stdin);
//freopen("1.txt","w",stdout);
int n;int i,j;
//初始化递推矩阵
for(i=0;i<101;i++)
{
for(j=i;j<i+2;j++)
{
matrix[i][j]=1;
}
}
while(~scanf("%d",&n))
{
scanf("%s",num);
len=strlen(num);
//初始化初始矩阵
for(i=0;i<len;i++)
{
initmatrix[0][i]=num[i]-'0';
}
//临时递推矩阵
for(i=0;i<len;i++)
{
for(j=0;j<len;j++)
{
temp[i][j]=matrix[i][j];
}
}
temp[len-1][0]=1;matrix[len-1][0]=1;
multiply(temp,n);//结果修改到matrix
calculate(initmatrix,temp,1,len);//结果修改到matrix
for(i=0;i<len;i++)
printf("%d",initmatrix[0][i]);
printf("\n");
matrix[len-1][0]=0;
}
return 0;
}
nyoj的AC代码:、【可以当模板】
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
#define N 101
#define CLR(data,val) memset(data,val,sizeof(data))
char str[101];
struct Matrix
{
Matrix(){}
void init(int n)
{
row=n;col=n;CLR(data,0);
for(int i=0;i<n;i++)
{
data[i][i]=1;
}
}
void init(int m, int n)
{
row=m;col=n;CLR(data,0);
}
int row,col;
bool data[N][N];
const Matrix &pow(int n);
};
const Matrix &operator *(const Matrix & a,const Matrix &b)
{
Matrix re;
re.init(a.row,b.col);
int i,j,k;
for(i=0;i<a.row;i++)
{
for(j=0;j<a.col;j++)
{
if(a.data[i][j])
{
for(k=0;k<b.col;k++)
{
if(b.data[j][k])
re.data[i][k]=re.data[i][k]^(a.data[i][j]&b.data[j][k]);
}
}
}
}
return re;
}
const Matrix &Matrix::pow(int n)
{
Matrix temp,pre;
temp=*this;pre.init(this->row);
while(n)
{
if(n&1) pre=temp*pre;
temp=temp*temp;
n>>=1;
}
return pre;
}
int main()
{
//freopen("Input.txt","r",stdin);
//freopen("1.txt","w",stdout);
int t,i;
Matrix a,b,res;
while(~scanf("%d",&t))
{
scanf("%s",str);
int len=strlen(str);
a.init(1,len);
for(i=0;i<len;i++)
a.data[0][i]=str[i]-'0';
b.init(len);
for(i=0;i<len;i++)
{
b.data[i][i]=1;
b.data[i][(i+1)%len]=1;
}
res=a*b.pow(t);
for(i=0;i<len;i++)
printf("%d",res.data[0][i]);
printf("\n");
}
return 0;
}
分享到:
相关推荐
ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告 ACM HDU 2000->2099 解题报告
HDU 1010-2500解题报告,ACMer可以借鉴一下
hdu2000-2014ac代码,虽然只有几道,但都是简单的
ACM入门的课件适合于那些想要学习的ACM,提高自己编程能力的。
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
杭州电子科技大学online judge (hdu)第十一卷 2000 - 2099 题目集 doc 格式的,希望大家喜欢!
解题报告|ACM|程序设计参考程序以及题目的分析
ACM程序设计题目分析以及AC的源码
最精准的答案(本人做对的题目拿上来给大家呈现)!不要忘记是C++编的
ACM题库,一些题目和答案,以及解题报告,传上来共享
我去年暑假花了5天,把杭电ACM网站上2000到2099这100道题全AC了,又花了10来天精心写解题报告。 里面包括题目、解题思路、编程技巧以及参考源码。所有代码都是使用C/C++写的。 最近整理资料时无意间发现,打包...
杭电OnlineJudge 200-2099的解题报告
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
HDU 里面的2000~2099道题目的源码。谢谢支持
可拆卸核心板滤波电容电源指示灯排针复位F103--R10不焊F207--R9不焊第19引脚F103--C4焊0欧姆,C3不焊Tuesday, August 31
杭电ACM2000-2099题的解题报告
排母,核心板接口ADC 电位器扩展接口,预留模拟量Tuesday, August 31, 2021Tuesday, August 31, 2021Tuesday