高斯消元-解异或线性方程

核心
1. 理解异或线性方程为什么可以用高斯线性方程解法

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
int a[N][N];

int gauss()  // 高斯消元，答案存于a[i][n]中，0 <= i < n
{
    int c, r;
    for (c = 0, r = 0; c < n; c ++ )
    {
        int t = r;
        for (int i = r; i < n; i ++ )  // 找非零行
            if (a[i][c])
                t = i;

        if (!a[t][c]) continue;

        for (int i = c; i <= n; i ++ ) swap(a[r][i], a[t][i]);  // 将非零行换到最顶端
        for (int i = r + 1; i < n; i ++ )  // 用当前行将下面所有的列消成0
            if (a[i][c])
                for (int j = n; j >= c; j -- )
                    a[i][j] ^= a[r][j];

        r ++ ;
    }

    if (r < n)
    {
        for (int i = r; i < n; i ++ )
            if (a[i][n])
                return 2;  // 无解
        return 1;  // 有多组解
    }

    for (int i = n - 1; i >= 0; i -- )
        for (int j = i + 1; j < n; j ++ )
            a[i][n] ^= a[i][j] * a[j][n];  // a[i][j] 是0，&之后就是0，是1则&之后为1，再^就为0

    return 0;  // 有唯一解
}


int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n + 1; j++) {
            cin >> a[i][j];
        }
    }

    int t = gauss();

    if (t == 0) {
        for (int i = 0; i < n; i++) cout << a[i][n] << endl;
    } else if (t == 1) {
        cout << "Multiple sets of solutions" << endl;
    } else {
        cout << "No solution" << endl;
    }
    return 0;
}

代码

#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
vector<int> vec[101010];
vector<int> ans;
int n,d,k;
int main(int argc, char const *argv[])
{
    cin>>n>>d>>k;
    for(int i=1;i<=n;i++)
    {
        int t,id;
        cin>>t>>id;
        vec[id].push_back(t);
    }
    for(int i=1;i<=100000;i++)
    {
        sort(vec[i].begin(), vec[i].end());
    }
    for(int A=1;A<=100000;A++)
    {
        if(vec[A].size()<k)continue;
        queue<int> que;
        for(int i=0;i<vec[A].size();i++)
        {
            if(que.size()<k){que.push(vec[A][i]);}
            if(que.size()>=k)
            {
                int fir = que.front();
                int last = que.back();
                if(last-fir<=d-1){ans.push_back(A);break;}
                while(que.back()-que.front()>d-1)que.pop();
            }
        }

    }
    for(auto x : ans)
    {
        cout<<x<<endl;
    }
    system("pause");
    return 0;
}

算法1

思路：二分
具体分析就是，在0-n-1中递增序列，最小值是nums[0],完全翻转后，所有值都是小于nums[0]的，于是我们在二分判断的时候，取得右半段，所以if(nums[mid]>mid)l=mid+1,最后答案就是二分的nums[l]

C++ 代码

class Solution {
public:
    int findMin(vector<int>& nums) {

        if(nums.back()>=nums[0])return nums[0];
        int l=0,r=nums.size()-1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(nums[mid]<nums[0]) r=mid;//注意最小值选的是二分的右半段
            else l=mid+1;
        }
        return nums[l];
    }
};

求1~n中每个数的欧拉函数:

基于线性筛法

1.当数值为i且i为质数时， 其欧拉函数的值temp[i] 为 i - 1; (为1 ~ i - 1)

2.当 i % prim[j] == 0时， 

temp[i * prim[j]]  == temp[i] * prim[j];  //因为temp[i]中存在 i * (1 - 1 / p1) * (1 - 1 / p2) * ... * (1 - 1 / pj) (存在pj)
所以temp[i * prim[j]] == temp[i] * prim[j];

3.当 i % prim[j] != 0 时

temp[i * prim[j]] == temp[i] * prim[j] * (1 - 1 / prim[j]) == temp[i] * (prim[j] - 1);

代码实现：

    long long res = 0;

    temp[1] = 1;

    int cnt = 0;
    for(int i = 2 ; i <= n ; i++)
    {
        if(!choose[i])
        {
            choose[i] = 1;
            prim[cnt++] = i;
            temp[i] = i - 1;
        }
        for(int j = 0 ; prim[j] <= n / i ; j++)
        {
            choose[prim[j] * i] = 1;
            if(i % prim[j] == 0)
            {
                temp[i * prim[j]] = prim[j] * temp[i];
                break;
            }
            else
            {
                temp[i * prim[j]] = temp[i] * (prim[j] - 1);
            }
        }
    }

    for(int i = 1 ; i <= n ; i++)
    {
        res += temp[i];
    }

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

要求时间复杂度为 O(n)。

样例

输入：[1, -2, 3, 10, -4, 7, 2, -5]

输出：18

算法1

DP

分为3个状态即可DP

ans[j]为以位置j结束的连续子数组的最大和

由上图分析出在位置j的连续子数组的最大和可能有3种状态得出

1：由j-1位置的数加上j位置的数。
2：由以j-1位置结尾的连续子数组的和加上j位置的数。
3：j位置数本身最大。因此可得

ans[ j ]=max(nums[ j ],nums[ j-1 ]+nums[ j ],ans[ j-1 ]+nums[ j ]);

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans[100010];
        ans[0]=nums[0];
        for (int j = 1; j <nums.size(); j ++ )
        {
            ans[j]=max(nums[j],nums[j-1]+nums[j]);
            ans[j]=max(ans[j],ans[j-1]+nums[j]);
        }
        int k=-0x3f3f3f3f;
        for (int j = 0; j <nums.size(); j ++ )k=max(k,ans[j]);
        return k;

    }
};

高斯消元解线性方程

核心
1. 线性代数的解题逻辑，理清思路即可
2. 需要弄清r和c两个变量的含义

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 110;
const double eps = 1e-6;
double a[N][N];  // double 类型
int n;

int guass() {
    int r, c;  //c用来循环列，r记录有多少行进行了调整
    for (r = 0, c = 0; c < n; c++) {
        int t = r;  //记录当前的行数
        for (int i = r; i < n; i++) if (fabs(a[i][c]) > fabs(a[t][c])) t = i;  //在当前列找最大值
        if (fabs(a[t][c]) < eps) continue;  //表示当前列全部为0

        for (int i = c; i < n + 1; i++) swap(a[r][i], a[t][i]);  //交换r行和t行的数
        for (int i = n; i >= c; i--) a[r][i] /= a[r][c];  //首位变成1
        for (int i = r + 1; i < n; i++) {  
            if (fabs(a[i][c]) > eps) {  // 如果当前c列的这一行开始为0，则不需要减
                for (int j = n; j >= c; j--) {
                    a[i][j] -= a[r][j] * a[i][c];
                }
            }
        }
        r++;
    }  // 循环结束的时候，判断r是不是为n，如果不是，说明有行左边全为0
    if (r < n) {
        for (int i = r; i < n; i++) {  //右侧有部位0，则无解
            if (fabs(a[i][n]) > eps) return 2;
        }
        return 1;
    }
    for (int i = n - 1; i >= 0; i--) {  // 对每一行的a[i][i]求解，也就是a[i][n]，
        for (int j = i + 1; j < n; j++) { 
            a[i][n] -= a[i][j] * a[j][n];  
        }
    }
    return 0;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n + 1; j++) {
            cin >> a[i][j];
        }
    }
    int t = guass();
    if (t == 0) {
        for (int i = 0; i < n; i++) printf("%.2lf\n", a[i][n]);
    } else if (t == 1) {
        cout << "Infinite group solutions" << endl;
    } else {
        cout << "No solution" << endl;
    }

    return 0;
}

dp ：

（剪枝：若当前点离中心点的偏移量减剩下的行数大于1，则跳过）

C++ 代码

#include<iostream>
using namespace std;
int a[101][101];
int dp[101][101];
int n;

int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++)cin>>a[i][j];
    }
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++){
            if( abs( j - i/2 )- n + i > 1)continue;
            dp[i][j] = max(dp[i-1][j-1],dp[i-1][j]) + a[i][j];
        }
    }
    if(n%2==1)cout << dp[n][n/2+1]; //n为奇数必走回中心点
    else cout << max( dp[n][n/2], dp[n][n/2+1] );  //n为偶数有两种情况
    return 0;
}

dfs ：

用一样的思路n=30就超时了555

C++ 代码

#include<iostream>
using namespace std;
int a[101][101];
int n,ans=0;

void dfs(int i,int j,int sum,int dir){
    if( abs(dir) - n + i > 1)return;
    if(i == n) {
        if(dir==1 ||dir==-1 ||dir==0 )ans = max(ans,sum);
        return;
    }
    dfs(i+1, j+1, sum+a[i+1][j+1], dir+1 );
    dfs(i+1, j, sum+a[i+1][j], dir-1);
}

int main(){
    cin>>n;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=i; j++)cin>>a[i][j];
    }
    dfs(1,1,a[1][1],0);
    cout << ans;
    return 0;
}

return ' '.join(s.split()[::-1])

求欧拉函数（求1~n 中与 数值n互质的值的个数）

数学公式：

N = (p1 ^ n1) * (p2 ^ n2) * (p3 ^ n3) * ... * (pj ^ nj);

则欧拉函数的值:
g(N) = N * (1 - 1 / p1) * （1 - 1 / p2） * (1 - 1 / p3) * ... * (1 - 1 / pj);

代码实现：

int temp ;
scanf("%d",&temp);

long long res = temp;

for(int i = 2 ; i <= temp / i ; i++)
{
    if(temp % i == 0)
    {
        res = res / i * (i - 1); //不能使用res = res * (1 - 1 / i); 因为res 这个时候包含了temp , 而temp % i == 0, 所以res / i 不会有小数存在。
        while(temp % i == 0)
        {
            temp /= i;
        }
    }
}

#include<bits/stdc++.h>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=100000+10;
int b[N];  //差分数组

void f(int l,int r,int c){ //l=r时表示赋值
    b[l]+=c;
    b[r+1]-=c;
}

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int c;
        cin>>c;
        f(i,i,c);
    }
    while(m--){
        int l,r,c;
        cin>>l>>r>>c;
        f(l,r,c);
    }
    for(int i=1;i<=n;i++){
        b[i]=b[i]+b[i-1];
        cout<<b[i]<<' ';
    }
    return 0;
}