Znzryb's Blog
0%

Posted on Edited on

思路讲解

拓展欧几里得算法

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

这篇题解非常好

https://www.luogu.com.cn/article/1wawrmip

线性同余方程 $ax=b \ (mod \ n) 的意思是指的意思是指(ax)\ mod \ n=b$ x为未知数

image

那这个线性同余方程方程可以转换为什么方便我们求解那？

image

a∗x=1(mod b)a*x=1(mod\ b)的成立条件是gcd(a,b)∣1 (a，b的最大公约数整除1)gcd(a,b)|1\ (a，b的最大公约数整除1) 当然，这是一定有解的，除非a,b中有一个为0。

这个是对这一问题转化的感性理解

AC代码

x∗y=1(mod p) −>x_∗y+y_∗p=gcd(y,p)x*y=1(mod\ p) \ -> x\_*y+y\_*p=gcd(y,p)

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>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;
// https://ac.nowcoder.com/acm/contest/5891/B
void exgcd(ll a,ll b,ll &x,ll &y){
	if(!b)
		x=1,y=0;
	else
		exgcd(b, a%b, y, x),y-=a/b*x;
}
ll gcd(ll a,ll b){
	if(b==0)
		return a;
	return gcd(b,a%b);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		ll y,p;
		cin>>y>>p;
		// x*y=1(mod p) -> x_*y+y_*p=gcd(y,p)
		if(gcd(y,p)!=1){
			cout<<-1<<endl;
			continue;
		}
		ll x_,y_;
		exgcd(y, p, x_, y_);
		cout<<(x_+p)%p<<endl;
	}
	return 0;
}

心路历程（WA，TLE，MLE……）

需要加一个这个判断是否存在逆元

1
2
3
4
if(gcd(y,p)!=1){
			cout<<-1<<endl;
			continue;
		}

(x∗y) mod p=1 −>(x mod p)∗(y mod p)=1(x*y)\ mod\ p=1\ ->(x\ mod\ p)*(y\ mod\ p)=1

所以说y mod p=1y\ mod\ p=1才有可能求出逆元xx。

Posted on Edited on

思路讲解

因为（a, b）= (b, a mod b) 【（）表示最大公约数】

image

image

AC代码

也可以这么写

1
2
3
4
void Exgcd(ll a, ll b, ll &x, ll &y) {
    if (!b) x = 1, y = 0;
    else Exgcd(b, a % b, y, x), y -= a / b * x;
}

https://www.acwing.com/problem/content/submission/879/

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;

ll exgcd(ll a,ll b,ll &x,ll &y){
	if(b==0){
		// ax+by=(a,b)
		// b=0,
		x=1,y=0;
		return a;
	}
	ll d=exgcd(b, a%b, y, x);
	y-=(a/b)*x;
	return d;
}


int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		ll a,b,x,y;
		cin>>a>>b;
		exgcd(a, b, x, y);
		cout<<x<<" "<<y<<endl;
	}
	return 0;
}
// AC https://www.acwing.com/problem/content/submission/879/

心路历程（WA，TLE，MLE……）

Posted on Edited on

思路讲解

需要综合计量一个分割点的价值。之前迟迟无法AC就是这个原因。

Call.push_back(Cnt1[i]-Cnt0[i]);

一个分割可以产生的相差值就是Cnt1[i]−Cnt0[i]Cnt1[i]-Cnt0[i]，我们把所有分割点产生的相差值push进这个Call里

然后最后sort一下，贪心的减少，统计数量即可。

1
2
3
4
5
6
7
8
9
10
11
12
sort(Call.begin(), Call.end());
ll diff=curBob-curAli;
for(int i=0;i<Call.size();++i){
	diff-=Call[i];
	if(diff==k){
		cout<<cntSplit-i-1<<endl;
		break;
	}else if(diff<k){
		cout<<cntSplit-i<<endl;
		break;
	}
}

AC代码

https://codeforces.com/contest/2042/submission/294590561

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T,k;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n>>k;
		vector<ll> A(n+10,0);
		for(int i=1;i<=n;++i){
			char a;
			cin>>a;
			A[i]=a-'0';
		}
		// 0 表示被Alice捕获，1表示被Bob捕获
		// 怎么分让Bob分比Alice分大至少k？而且分最少的组
		vector<ll> Cnt1(n+10,0);
		vector<ll> Cnt0(n+10,0);
		for(int i=n;i>=1;--i){
			if(A[i]){
				Cnt1[i]=Cnt1[i+1]+1;
				Cnt0[i]=Cnt0[i+1];
			}else{
				Cnt0[i]=Cnt0[i+1]+1;
				Cnt1[i]=Cnt1[i+1];
			}
		}
		ll upS=n+1,curBob=0,curAli=0,cnt1Up=0,cnt0Up=0,cntSplit=1;
		vector<ll> /*C1,C0,*/Call;	// 记录分割点可产生的不同值
		for(int i=n;i>=2;--i){
			if(Cnt1[i]>Cnt0[i]){
				// 之前的所有出现过的1都要再加一遍
				curBob+=Cnt1[i]-Cnt1[upS]+cnt1Up;	
				cnt1Up+=Cnt1[i]-Cnt1[upS];
				curAli+=Cnt0[i]-Cnt0[upS]+cnt0Up;
				cnt0Up+=Cnt0[i]-Cnt0[upS];
				Call.push_back(Cnt1[i]-Cnt0[i]);
				cntSplit+=1;
				upS=i;
			}
		}
		if(curBob-curAli<k){
			cout<<-1<<endl;
			continue;
		}
		// 一个分隔点贡献了多少的不同
		sort(Call.begin(), Call.end());
		ll diff=curBob-curAli;
		for(int i=0;i<Call.size();++i){
			diff-=Call[i];
			if(diff==k){
				cout<<cntSplit-i-1<<endl;
				break;
			}else if(diff<k){
				cout<<cntSplit-i<<endl;
				break;
			}
		}
	}
	return 0;
}
// AC https://codeforces.com/contest/2042/submission/294590561

/*
1
5 6
01011

1
5 2
01011

应该输出2 010｜11

wrong answer 48th numbers differ - expected: '2', found: '3'
*/

心路历程（WA，TLE，MLE……）

之前一直无法AC就是因为没发现一个点产生的不同值

Posted on Edited on

思路讲解

idxrare指出现次数最少的，idxmost指出现次数最多的字母

A[idxrare]=A[idxmost];

然后好了。

AC代码

多用sort啦，宁愿多耗点空间，这样能够确保你的意志能够被准确地执行

唉，前面在遍历的时候瞎搞，唉。

https://codeforces.com/contest/2047/submission/294578039

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
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n;
		vector<char> A(n+10);
		map<char,ll> cntCh;
		if(n==1){
			string s;
			cin>>s;
			cout<<s<<endl;;
			continue;
		}
		for(int i=1;i<=n;++i){
			cin>>A[i];
			if(cntCh.count(A[i]))
				cntCh[A[i]]+=1;
			else
				cntCh[A[i]]=1;
		}
		ll mostOcc=0,rareOcc=17;
		char most='0',rare='0';
		vector<pair<ll,char> > chCnt;
		for(map<char,ll>::iterator it=cntCh.begin();it!=cntCh.end();it++){
			chCnt.emplace_back(it->second,it->first);
//			ll loc=it->second;
//			if(loc>mostOcc){
//				mostOcc=loc,most=it->first;
//			}
//			if(loc<rareOcc && (it==cntCh.begin() || most!=it->first))
//				rareOcc=loc,rare=it->first;
		}
		sort(chCnt.begin(),chCnt.end());
		ll idxmost=0,idxrare=0;
		for(int i=1;i<=n;++i){
			if(A[i]==chCnt.back().second)
				idxmost=i;
			if(A[i]==chCnt.front().second)
				idxrare=i;
		}
		A[idxrare]=A[idxmost];
		for(int i=1;i<=n;++i){
			cout<<A[i];
		}
		cout<<endl;
	}
	return 0;
}
/*
1
9
cbbbbaaaa

hack数据
1
9
abbbbcccc

*/
// https://codeforces.com/contest/2047/submission/294578039

心路历程（WA，TLE，MLE……）

暴力（当然，会超时）

注意next_permutation()如果想遍历全部的话需要sort一下啦。

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(2e5)+10;
ll n,T;

inline ll cntDiffS(string s,ll i,ll j){
	ll res=0;
	s[i]=s[j];
	sort(s.begin(),s.end());
	set<string> judrepeat;
	do{
		if(!judrepeat.count(s)){
			++res;
			judrepeat.insert(s);
		}
	}while (next_permutation(s.begin(), s.end()));
	return res;
}
inline string change(string s,ll i,ll j){
	s[i]=s[j];
	return s;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>T;
	while (T--) {
		cin>>n;
		string s;
		cin>>s;
		vector<pair<ll,string> > ans;
		if(n==1){
			cout<<s<<endl;
			continue;
		}
		for(int i=0;i<n-1;++i){
			for(int j=1;j<n;++j){
				if(i==j)
					continue;
				if(s[i]==s[j])
					continue;
				ans.emplace_back(cntDiffS(s,i,j),change(s,i,j));
			}
		}
		sort(ans.begin(),ans.end());
		cout<<ans.back().second<<endl;
	}
	return 0;
}

Posted on Edited on

思路讲解

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

我们来解释一下为什么可以这样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那？那是因为树状数组中遍历你上面的数组是必然遍历不到你的，这点你不用担心，所以不用担心差分连续加导致出错。

AC代码

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

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
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <bitset>
#include <iterator>
#include <random>
#include <iomanip>
// 树状数组
using namespace std;
typedef long long ll;
const ll N=static_cast<ll>(5e5)+10;
ll n,m,tr[N];
inline ll mod2(ll x){	// 对2取模
	return (x+2)%2;
}
inline ll lowbit(ll x){		
	// 负数补码原理，负数就是把你之前的书全部取反再加1
	// 正数和0的补码就是该数字本身再补上最高比特0
	// 负数的补码则是将其绝对值按位取反再加1。
	return x&(-x);
}
inline void pushup(ll x,ll v){
	while(x<n+1){
		tr[x]+=v;
		x+=lowbit(x);
	}
}
// 
inline void invert(ll s,ll e){
	pushup(s, 1);
	if(e<n){
		pushup(e+1, -1);
	}
}

inline ll search(ll x){
	if(x==0) return 0;
	return search(x-lowbit(x))+tr[x];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin>>n>>m;
	while(m--){
		ll op;
		cin>>op;
		if(op==1){
			ll s,e;
			cin>>s>>e;
			invert(s, e);
		}else{
			ll x;
			cin>>x;
			cout<<mod2(search(x))<<endl;
		}
	}
	return 0;
}
// AC https://www.luogu.com.cn/record/192393560

心路历程（WA，TLE，MLE……）