第一道题就不说了,刚学会编程的就会~
所以直接从后往前说~
要说第六题:方程,需要了解矩阵快速幂,这个知识在算法基础课里是没有讲解的,所以我自学了一下
写的很小白,很适合我~笔记如下,另外找了一道考矩阵快速幂的考研机试题目:
当然,如果觉得我写的字不堪入目的请自行搜索学习~
然后我在acwing上找了一道相关的题,链接如下:https://www.acwing.com/problem/content/description/3537/
这道考研机试题的代码如下,稍后会比较这道题和算法赛第六题的代码,会发现他们有不少相同的地方.
/*
两个矩阵a,b相乘得到的新矩阵c,新矩阵的第i行第j列元素是a的第i行和b的第j列的对应元素相乘的求和.
核心代码:
for(int i = 0 ; i < n ; i ++)
for(int j = 0 ; j < n ; j++)
for(int k = 0 ; k < n ; k++)
tmp[i][j] += a[i][k] * b[k][j];
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 15;
int n, k;
int w[N][N];
void mul(int c[][N], int a[][N], int b[][N])
{
static int tmp[N][N];
memset(tmp,0,sizeof tmp);
for(int i = 0 ; i < n ; i++)
for(int j = 0 ; j < n ; j++)
for(int k = 0 ; k < n ; k++)
tmp[i][j] += a[i][k] * b[k][j];
memcpy(c,tmp,sizeof tmp);//复制到res数组里面
}
int main()
{
cin >> n >> k;
for(int i = 0 ; i < n ; i++)//存数据
for(int j = 0 ; j < n ; j++)
cin >> w[i][j];
//接下来两部将res初始化为单位矩阵
int res[N][N] = {0};
for(int i = 0 ; i < n ; i++) res[i][i] = 1;
//k次幂,快速幂,矩阵快速幂;
while(k--) mul(res,res,w);
for(int i = 0 ; i < n ; i++)//存数据
{
for(int j = 0 ; j < n ; j++)
cout << res[i][j] << " ";
cout << endl;
}
return 0;
}
接下来就开始放蓝桥第六道题目的代码:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int mod = 1e9 + 7;
#define int long long
int t,n,k;
void mul(int c[][2], int a[][2], int b[][2])//第一步:重新定义乘法,mul就是multiple
{
int tmp[2][2] = {0};
for(int i = 0 ; i < 2 ; i++)
for(int j = 0 ; j < 2 ; j++)
for(int k = 0 ; k < 2 ; k++)
tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % mod;
memcpy(c,tmp,sizeof tmp);//重新赋值到res数组里面
}
void qmi(int a[2][2],int b)//第二步就是快速幂的操作
{
//下面两步定义单位矩阵,为下面铺垫
int res[2][2] = {0};
for(int i = 0 ; i < 2 ; i++) res[i][i] = 1;
while(b)
{
if(b & 1) mul(res,res,a);
mul(a,a,a);
b >>= 1;
}
memcpy(a,res,sizeof res);//填到a数组里面
}
signed main()
{
cin >> t;
//这里第一次写法不对哦!!!
while(t--)
{
cin >> n >> k;int f1 = k, f2 = ((k * k - 2) % mod + mod) % mod;
if(n == 1) {cout << f1 << endl;continue;}
if(n == 2) {cout << f2 << endl;continue;}
int a[2][2] = {{k,-1},{1,0}};//现代知识!!!
qmi(a,n - 2);
int re = (a[0][0] * f2 + a[0][1] * f1) % mod;// 定义了2个内容是因为数学式子:f(i + 2) = //f(1)*f(i + 1) - f(i);要表示等式右边的两个量
cout << (re + mod) % mod << endl;//这里写的格式也不对哦!!!
}
return 0;
}
其实我们不难发现这两道题目的相同部分的代码.
第五题
题目问的是一个棋子的邻居数目,而一个棋子最多可以有4个邻居,而剩下的不是邻居的位置的数目,就应该被减去,即:4 * n(总数) - 空余的周长数目.而在数学上我们知道圆的周长是最小的,所以当图形越接近圆,那么他的周长就应该越小.所以我们核心思路应该是去构成正方形.
之后模拟一下可以发现有两种情况:
1,尚且还没有构成一个正方形的棋子摆放,这里我们先得到正方形的最大边长,也就是填补之后得到的正方形的边长,因为组成的单位面积是1*1,所以得到的面积的意义就是组成的棋子的数目,因为构不成完整的正方形,所以差应该小于i,就是一个边长的数目对应代码:
i * i - n < i ,
2,已经构成一个正方形了,但是却又多出来摆放了几个棋子,这种情况下直接else就可以了
开始讨论第一种思路:因为它没有构成一个完整的正方形,而且棋子的总邻居数是定的:4 * 总棋子数,开始讨论空余的周长数目~ 我们考虑填补法,去填补出一个完整的正方形然后再去计算,可以推理知道这种状态下填补前和填补后的空余周长数目相同,所以直接计算完整的正方形的边长:4 * i * 1 1,i是i个,每个的长度是1,因为是单位正方形(一个棋子的周围四条边).
所以方案一的代码:4 * n - 4 * i * 1;
接下来考虑方案二:不难发现,它和第一种情况的填补完之后的正方形相比多垒了一条行棋子,它和没垒的棋子数目相比多了两列单位边,所以应该减去 ,代码: 4 * n - (4 * i - 2);
完成代码如下:
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
signed main()
{
int n;cin >> n;
int i = 0;
for(i = 0 ; i * i < n ; i++);//得到特殊情况下的i的值
//接下来开始讨论
if(i * i - n < i )cout << 4 * n - 4 * i << endl;
else cout << 4 * n - 4 * i + 2 << endl;
}
第四题
这道题没什么好说的,简单的一匹
但我想提醒的是:这道题可以不开数组去解决的,也就是你输入一个判断一个就行了,如果你要开数组,那么一定一定要注意数组的范围!!!不然你一个也过不了~当然,二者思路完全相同
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int a;
int main()
{
int n; cin >> n ;
int retcnt = 0 , versecnt = 0;
for(int i = 1 ; i <= n * 2 ; i ++)
{
cin >> a;
if(i & 1)
{
if(a == 1) retcnt ++;
else versecnt ++; //一定要注意一点,题目输入在你数组中的编号问题!!!
}
}
int cnt = min(retcnt , versecnt);
cout << cnt << endl;
}
第三题
这道题你要注意一点,这道题考的是思维,没有考任何算法.
看题目的两个关系你会不会转化.简单的转化完之后,就是O(n)的1e5的时间复杂度.这里直接放代码
#include <iostream>
#include <algorithm>
using namespace std;
#define int long long
const int N = 100010;
int a[N];
signed main()
{
int n ; cin >> n;
for(int i = 1 ; i <= n ; i++)
{
cin >> a[i];
a[i] = i * a[i];
}
sort(a+1,a + n + 1);
int cnt = 0;
for(int i = 1 ; i < n ; i++)
{
if(a[i] == a[i + 1]) cnt ++;
}
cout << cnt << endl;
return 0;
}
第二题:
我写这道题仅仅是因为我没用STL而已~,因为写这道题应该都会用STL(不会用)
#include <iostream>
using namespace std;
const int A = 15,N = 100010;
int st[A][N];
int a,b,cnt = 0;
int main()
{
// 请在此输入您的代码
int n; cin >> n;
int m = n;
while(m--)
{
cin >> a >> b;
st[a][b]++;
}
for(int i = 0 ; i < A ; i ++)
for(int j = 0 ; j < N ; j++)
if(st[i][j] > 0) cnt ++;
cout << cnt << endl;
return 0;
}
很期待我学完线代之后实力的微弱的提升~