Znzryb's Blog
0%

Posted on Edited on

题目大意

给定一个包含 n 个未知数、n 个方程的线性方程组（实数域），判断方程组：

  • 无解输出 -1

  • 有无穷多组解输出 0

  • 有唯一解则输出每个未知数的解（按题目要求格式）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn=105;
const double eps=1e-6;
int n;
double a[maxn][maxn];
void out(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n+1;j++){
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	cout<<endl;
}
void gauss() {
    int r=1;
    for(int c=1;c<=n;c++) {  // 化为阶梯形矩阵
        int maxR=r;double absMax=0;
        for(int i=r;i<=n;i++)    // 找到该列绝对值最大的一行
            if(absMax<fabs(a[i][c]))
                absMax=fabs(a[i][c]),maxR=i;
        if(absMax<eps) continue;    // 如果为0 说明这一列已经全部消为0
        for(int j=n+1;j>=1;j--)   // 将该最大一行该列变为0
            a[maxR][j]/=a[maxR][c];
        if(maxR!=r)
            for(int i=1;i<=n+1;i++)      // 将该行换到上面
                swap(a[r][i],a[maxR][i]);
        for(int i=r+1;i<=n;i++)      // 将其他行的这一列全部归零
            for(int j=n+1;j>=c;j--)
                a[i][j]-=a[r][j]*a[i][c];
        r++;
        
        // out();
    }
    // cout<<r<<endl;
    if(r<=n) {
    	for(int i=r;i<=n;i++){
    		if(fabs(a[i][n+1])>eps){	// 0=非0的情况 
    			cout<<-1<<endl;return;
			}
			// cout<<"fabs(a[i][n+1]) "<<fabs(a[i][n+1])<<endl;
		} 
		cout<<0<<endl;return;
	}
	
	for(int i=n-1;i>=0;i--)		// 化为简化阶梯形 
		for(int j=i+1;j<=n;j++)
			a[i][n+1]-=a[i][j]*a[j][n+1]; //  将自己的非主元列消去
			// 当然不是真消去，只是=右边列减一下常数 
	for(int i=1;i<=n;i++){
		cout<<'x'<<i<<'='<<setprecision(2)<<fixed<<a[i][n+1]<<endl;
	}
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n+1;j++) cin>>a[i][j];
    }
    // out();
    gauss();
    return 0;
}
// https://www.acwing.com/problem/content/885/
// AC https://www.acwing.com/problem/content/submission/code_detail/37263760/
// AC https://www.luogu.com.cn/record/180256788

Posted on Edited on

题目大意

维护一个长度为 n 的数组，支持两类操作：

1）对区间 [l,r] 所有元素加上一个值。

2）查询单点 a[x] 的当前值。

P3368 BIT2 区别在于区间加减和单点查询

P3374 【模板】树状数组 1

视频教程

https://www.bilibili.com/video/BV1pE41197Qj?spm_id_from=333.788.recommend_more_video.-1&vd_source=4350e5f2584d2f27c848b347ea11b675

tr实际上是一个差分数组，只不过用了树状数组维护，a[ ]即原始数组就是diff的前缀和，所以甚至不需要再建一个前缀和数组

https://www.luogu.com.cn/record/180209186

和这题代码基本一样，还是比较适合我复训的。

我们来解释一下为什么可以这样pushup

1
2
3
4
5
6
inline void invert(ll s,ll e){
	pushup(s, 1);
	if(e<n){
		pushup(e+1, -1);
	}
}

众所周知，我们知道差分数组是给diff[s]+1，给diff[e+1]-1，那为什么可以直接pushup那？那是因为树状数组中遍历你上面的数组是必然遍历不到你的，这点你不用担心，所以不用担心差分连续加导致出错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
typedef long long ll;
using namespace std;
const int maxn=5e5+10;
ll n,m,tr[maxn],a[maxn],x,y,k,op; // tr[] is difference array
inline int lowbit(ll x){
	return (x&(-x));	// two's complementary (6)x=110  (two's..)x=001+1=010 
} 
inline void add(ll p,ll v){ 
	while(p<n+1){
		tr[p]+=v;
		p+=lowbit(p);
	}
}
ll search(ll p){
	if(p==0) return 0;
	return search(p-lowbit(p))+tr[p];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	// 这是在建树
	for(int i=1;i<=n;i++){			// tr[] is the diff array's BIT 
		tr[i]=a[i]-a[i-lowbit(i)];  // lowbit(i)=1 is the value of diff array
	}
	for(int _=1;_<=m;_++){
		cin>>op;
		if(op==1){
			cin>>x>>y>>k;   
			// 执行了两遍add操作，模拟差分
			add(x,k);		// walk around. convert range plus v to diff[L]+v && diff[R+1]-v
			if(y+1<=n)
				add(y+1,-k);
			
		}else{
			cin>>x;
			int ans=search(x);
			cout<<ans<<endl;
		}
	}
	// cin>>n;
}
// 30pts https://www.luogu.com.cn/record/180207859  add(y+1,k)->add(y+1,-k)
// AC https://www.luogu.com.cn/record/180209186

Posted on Edited on

题目大意

维护一个长度为 n 的数组，支持两类操作：

1）单点加上一个值。

2）查询区间 [l,r] 的元素和。

P3369 【模板】普通平衡树

似乎这题也可以用树状数组解决

https://zh.wikipedia.org/wiki/二補數

lowbit()原理详见这里

视频教程

https://www.bilibili.com/video/BV1ce411u7qP/?spm_id_from=333.337.search-card.all.click&vd_source=4350e5f2584d2f27c848b347ea11b675

区间和我们实际上是用两前缀和相减得到的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
using namespace std;
const int maxn=5e5+10;
int n,m,tr[maxn],sumTr[maxn],x,y,k,op;
inline int lowbit(int x){
	return (x&(-x));	// two's complementary (6)x=110  (two's..)x=001+1=010 
} 
inline void add(int p,int v){ 
	while(p<n+1){  // 这里要注意，别写成p<n了，会全WA
		tr[p]+=v;
		p+=lowbit(p);  
	}
}
int search(int p){
	if(p==0) return 0;
	return search(p-lowbit(p))+tr[p];
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>tr[i];
	}
	for(int i=1;i<=n;i++){
		sumTr[i]=tr[i]+sumTr[i-1];
	}
	for(int i=1;i<=n;i++){
		tr[i]=sumTr[i]-sumTr[i-lowbit(i)];
	}
	for(int _=1;_<=m;_++){
		cin>>op;
		if(op==1){
			cin>>x>>k;
			add(x,k);
		}else{
			cin>>x>>y;
			int ans=search(y)-search(x-1);  // 区间和我们实际上是用两前缀和相减得到的
			cout<<ans<<endl;
		}
	}
}
// AC https://www.luogu.com.cn/record/180138960

Posted on Edited on

题目大意

给定两个长度为 n 的 01 字符串 a、b，以及 m 次区间操作。每次操作可以选择是否交换区间 [l,r] 内 a 与 b 对应位置的字符。目标是经过若干选择后，使最终得到的 a 的字典序尽可能小，输出最小的结果字符串。

https://class.luogu.com.cn/classroom/LGR197

比赛的时候暴力法打了20分，record：

https://www.luogu.com.cn/record/179510631

前面暴力没搞对是发现是有个双重循环写错了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <bitset>
using namespace std;
const int maxn=2e5+10;
int n,m,l[maxn],r[maxn];
char a[maxn],b[maxn],c[maxn];
// bool vis[maxn];
void out() {
    for(int i=1;i<=n;i++) {
        cout<<c[i];
    }
    cout<<endl;
}
inline void compare(){
    for(int i=1;i<=n;i++) {
        if(c[i]>a[i])
            break;
        if(a[i]>c[i]) {
            for(int j=1;j<=n;j++) {
                c[j]=a[j];       // 双重循环一定要小心，前面WA是因为c[i]=a[i]
            }
            break;
        }
    }
}
void dfs(int x) {
    // out();
    // compare();
    if(x>m)
        return;
    for(int i=l[x];i<=r[x];i++) {
        swap(a[i],b[i]);
    }
    compare();
    dfs(x+1);
    for(int i=l[x];i<=r[x];i++) {
        swap(a[i],b[i]);
    }
    // compare();
    dfs(x+1);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++) {
        cin>>b[i];
    }
    for(int _=1;_<=m;_++) {
        cin>>l[_]>>r[_]; 
    }
    for(int i=1;i<=n;i++)
        c[i]=a[i];
    dfs(1);
    for(int i=1;i<=n;i++) {
        cout<<c[i];
    }
    cout<<endl;
    return 0;
}

Posted on Edited on 
1
2
3
4
5
6
#include <iostream>
#include <cstdlib>
using namespace std;
int main(){
	cout<<rand()<<endl;
}
1
41