数学知识(二)
数学知识(二)
高斯消元
初等行列变换
1、把某一行乘一个非零的数
2、交换某两行
3、某行若干倍加到另一行上去
目的:通过初等行列变换将增广矩阵变为阶梯型矩阵
操作
1、找到当前列绝对值最大的一行
2、把这一行换到最上面(未确定行的最上面)交换某两行
3、将该行的第一个数变成1 **乘上一个非零数 **
4、将下面所有行的当前列的值变成0 某行若干倍加到另外一行
模板
1234567891011121314151617181920212223242526272829303132333435363738394041424344const int N = 110;const double eps = 1e-6;int n;double a[N][N];int gauss(){ int c,r; //行,列 for (c = 0, r = 0; c < n; c ++){ int t = r;//找这一列绝对值最大的行 for ...
SDUT 2021 Spring Individual Contest(for 20) - 19
SDUT 2021 Spring Individual Contest(for 20) - 19
题目链接:A - Rooms and Passages
题意:
一条路上有nnn个房间,每个相邻房间之间有加密设备,初始时有所有密码,如果a[i]>0a[i]>0a[i]>0,只有拥有房间密码才能通过;如果a[i]<0a[i]<0a[i]<0,可以通过,但密码∣a[i]∣|a[i]|∣a[i]∣失效。从0−−n−10--n-10−−n−1个房间出发,计算出能通过的最多房间数。
思路:
通过符号为负的房间后,遇到的第一个对应权值的正号房间会停止,因为密码已经失效。
当满足此条件时,之前所有的起始位置都会在这个点停下,这样就可以算出之前所有点对应的可走的最大房间数。
结束位置nnn可能不满足这个条件,但相应的,此时已经没有条件限制,可以直接求出上个满足条件的位置到结束位置之间各点的最大房间数。
代码:
123456789101112131415161718192021222324#include<iostream>#include <cst ...
Codeforces Round 725 (Div. 3)
Codeforces Round 725 (Div. 3)
A.Stone Game
题目链接Stone Game
题意
给出一个长度为nnn的序列,每次可进行一次操作,求达成目标的最小操作数。
操作:每次可以删除序列的头元素或尾元素。
目标:最小值以及最大值被删除。
思路
枚举三种可行的操作,取最小值。
1、从序列头开始删,删到需要删除的数停止。然后从序列尾开始删,删到需要删除的数停止。
2、从序列头开始删,直至删除两个需要删除的数。
3、从序列尾开始删,直至删除两个需要删除的数。
代码
123456789101112131415161718192021222324252627282930313233#include <iostream>#include <algorithm>#include <map>#include <set>#include <cstring>#include <cmath>using namespace std;int n;const int N = 10010;int a[N];int ...
SDUT 2021 Spring Team Contest(for 20) - 10
SDUT 2021 Spring Team Contest(for 20) - 10
A - ABB
题意
给一个初始串,在初始串后加上一个字符为一次合法操作,求使初始串变成回文串的最小操作次数。
思路
枚举iii从左到右的位置,如果i ni~ni n能构成回文串,那么只需要在所给串的后面加上iii,就是所求的字符串,答案为iii;若不存在回文,需要在所给串的后面加上前面n−1n-1n−1个字符,答案为n−1n-1n−1
代码
123456789101112131415161718192021#include <iostream>#include <cstring>using namespace std;int n;int main(){ string a,b; cin>>n>>a; int res = 1e9; for (int i = 0 ; a[i] ;i ++){ int cnt = 0; for (int j = 0; j <= n -1 - i &g ...
数学知识(一)
约数
设aaa为一个非零整数,bbb是一个整数,如果存在一个整数qqq ,使得 b=a∗qb=a*qb=a∗q,那么bbb可被aaa整除,记作 a∣ba|ba∣b ,bbb是aaa的倍数,aaa是bbb的约数
性质
1、如果a∣ba|ba∣b且b∣cb|cb∣c,那么a∣ca|ca∣c
2、a∣ba|ba∣b且a∣ca|ca∣c,对任意的整数xxx和yyy,有a∣(b∗x+c∗y)a|(b*x+c*y)a∣(b∗x+c∗y)
3、a∣ba|ba∣b等价于(a∗m)∣(b∗m)(a*m)|(b*m)(a∗m)∣(b∗m),m不为零
4、设整数xxx 和 yyy满足下式a∗x+b∗y=1a*x + b * y =1a∗x+b∗y=1,且a∣na|na∣n,b∣nb|nb∣n,那么(a∗b)∣n(a*b)|n(a∗b)∣n
算术基本定理
任何一个大于1的自然数 N,如果
N不为质数,那么N可以唯一分解成有限个质数的乘积
N=p1c1p2c2...pmcmN = p_1^c1p_2^c2...p_m^cm
N=p1c1p2c2...pmcm
其中cicici都是正整数
试除法求整数x的 ...
博客搭建完成啦(大雾
输入密码,查看文章。
Incorrect Password!
No content to display!
U2FsdGVkX1+4GeAzrh/wcdJAVPleIOLWZKkqFlKJxT64hgZf/e0j83XC71PBGZbbqmFMy48JcRQWyy3RI3e8uJTL9BPFP1YvGiSTuxRdc98jx3SAmEI8hBs0t9DcGX7PvirAFnFyfP+YO2Ry+vnSy5ljqxBnmCJ7Jr+N7+ij5xo0/NL2fxsWMxIK8d8gt9tve7PTvpNtVAIUg6wPA9HFgAm2m+VP3DW6VvHTtp878ITITk+yUdhDolBSQydIdmfmyOz3myJkcHTFqp4zbJNmtb8KnZVD0SosfIDqytzQMAUAvtIEeyBrJ4OuK0QI7ZWGATKgEx0plJDuCLu3MUdCx/KpzOzjQP37egldP8zz1896/st/+NeUMVDhoYS7AFwX1jiqxEBV4tNmuFE1NPn1aXncnsogWmvPfjrk80Nu ...