LCX的算法笔记Week-1
详细记录一下一周里做的比较有意思的几道题
一
题目来源：字节跳动网络赛
因为少写了个括号导致WA啦😩😩😩，以为是算法有问题，就让队友写并查集解法啦。导致浪费了太多时间。又间接导致了下面要说的题没时间加特判了，寄。看来还是要多加练习。这道题除了特判比较繁琐，其他的还行。很容易就能想到要想使交换的次数最少，只需要先将给定的无序序列排列成有序序列，然后从第一个数字往后遍历，遍历的过程中，若当前有序序列中数字所在的位置和之前不同，则交换一次，并把记录的交换次数加1。比如样例1的输入 2 4 5 1 3 ，先排成1 2 3 4 5。遍历当前有序序列，发现1原本在下标4的位置，这时候就把下标4位置上的数1和下标1上的数2交换，依次类推，可算出总共交换了3次。样例1的k为0，所以没有预先交换的操作，最大值最小值相等，即3。所以就需要记录下之前无序序列每个数的下标，因为数的值可能会到10的九次方，如果用数组来维护这一信息，肯定会爆掉，且全局变量的数组也最多开到十的六次方的级别，所以用哈希表来存储，通过数据直接访问下标。再多开个数组记下原本的无序序列。所以很容易就能求得最小次数啦。关键在于最大次数的讨论，想要后面换的次数最多，就要使序列越无序越好，最无序的状态就是要n-1次交换才能变有序。假设n个数的无序序列，需要cnt次交换使序列变得有序，那么就需要（n-1）-cnt次使它最无序，这是我在比赛的时候提出的一个假设，当时自己写了几个序列，发现确实是这样的，后面队友写的并查集的解法也从侧面证明了这一点。完整代码如下
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 <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
int a[N],b[N];
unordered_map<int, int> dic;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
cin>>n>>k;
for (int i=1; i<=n; i++) {
cin>>a[i];
dic[a[i]]=i;
b[i]=a[i];
}
sort(a+1,a+1+n);
int cnt=0;
for (int i=1; i<=n; i++) {
if (dic[a[i]]!=i) {
int temp=dic[a[i]];
dic[a[i]]=i;
dic[b[i]]=temp;
int temp2=b[i];
b[i]=b[temp];
b[temp]=temp2;
cnt++;
}
}
int uncnt=n-1-cnt;
int max=0,min=0;
if (k>=cnt) {
if ((k-cnt)%2==0) {
min=0;
}
else min=1;
}
else min=cnt-k;
if (k>=uncnt) {
if ((k-uncnt)%2==0) {
max=n-1;
}
else max=n-2;
}
else max=n-1-(uncnt-k);
cout<<min<<' '<<max;
return 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
| #include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,k;
int a[N],b[N];
int p[N], si[N];
bool st[N];
int cnt,num;
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
void un(int a,int b){
int aa=find(a);
int bb=find(b);
if(aa!=bb){
p[aa]=bb;
si[bb]+=si[aa];
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
si[i] = 1;
}
for(int i=1;i<n;i++){
un(i,a[i]);
}
for(int i=1;i<=n;i++){
if(!st[find(i)]){
cnt+=si[find(i)]-1;
st[find(i)]=1;
num++;
}
}
if(k<=cnt) cout<<cnt-k<<' ';
else{
if((k-cnt)%2) cout<<1<<' ';
else cout<<0<<' ';
}
if(k<num) cout<<cnt+k;
else{
if((k-num)%2) cout<<n-1;
else cout<<n-2;
}
cout<<endl<<num<<' '<<cnt;
return 0;
}
|
二
题目来源：字节跳动网络赛
这道题本来是开局队友在看的，后来他们感觉太繁琐了，就放弃了。我在后期就又去看了看这道题，想到了怎么写，不过也非常繁琐，怒敲一百多行代码，敲那么多也敲出了一些bug，自增写成了自减，又是一个寄。等到bug找出来之后，样例都过了，就直接进行一个代码的提交，然后就WA啦。此时距离结束已经就剩两分钟，想了一会发现是对非法情况的特判不够全面，想出来之后也没时间提交了。希望有生之年能在算法竞赛上完成一次压哨绝杀。题意就是让输出n个数字的序列，数的值1-n里随意排列。且该序列的极大值点和极小值点满足题目的要求，对于极大值数量大于极小值数量的，可以先取出1和2作为两个端点，然后将n作为第一个极大值点，n-1作为第二个极大值点，直到满足数量要求，同样的，3作为第一个极小值，4作为第二个，以此类推，最后把没有用到的数全部放在1-n之间输出。输出的时候注意顺序即可。对于极大值数量小于极小值数量的，思想类似，反着来就行了。极大值极小值数量相等的，只要让第一个数为1然后递增递减依次交错进行就行啦，同样把没有用的数在第一个序列上坡（即1-n这一段）输出来，就一定能满足题目要求啦。代码实现如下
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
| #include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int ma[N],mn[N],state[N];
int main(){
int t;
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>t;
while (t--) {
int n;
cin>>n;
memset(ma, 0, sizeof ma);
memset(mn, 0, sizeof mn);
memset(state, 0, sizeof state);
int a,b;
cin>>a>>b;
if (n%2) {
if((a-b>1)||(a+b>n-2||a>n/2||b>n/2)||(b-a)>1) {cout<<-1<<endl;continue;}
}
else {
if ((a+b>n-2||a>n/2-1||b>n/2-1)||a-b>1||(b-a)>1) {
cout<<-1<<endl;
continue;
}
}
if (a>b) {
int temp=n;
state[1]=1;
state[2]=1;
for (int i=0; i<a; i++) {
ma[i]=temp;
state[temp--]=1;
}
int temp2=3;
for (int i=0; i<b; i++) {
mn[i]=temp2;
state[temp2++]=1;
}
cout<<1<<' ';
for (int i=3; i<=n; i++) {
if (!state[i]) {
cout<<i<<' ';
}
}
for (int i=0; i<a; i++) {
cout<<ma[i]<<' ';
if (i<b) {
cout<<mn[i]<<' ';
}
}
cout<<2<<endl;
}
else if (a<b) {
state[n]=1;
int k=n-1;
state[k]=1;
int temp2=1;
for (int i=0; i<b; i++) {
mn[i]=temp2;
state[temp2++]=1;
}
int temp=n-2;
for (int i=0; i<a; i++) {
ma[i]=temp;
state[temp--]=1;
}
cout<<n<<' ';
for (int i=n-1; i>=1; i--) {
if (!state[i]) {
cout<<i<<' ';
}
}
for (int i=0; i<b; i++) {
cout<<mn[i]<<' ';
if (i<a) {
cout<<ma[i]<<' ';
}
}
cout<<n-1<<endl;
}
else if (a==b) {
state[1]=1;
state[n]=1;
int temp=n-1;
int temp2=2;
for (int i=0; i<a; i++) {
ma[i]=temp;
state[temp--]=1;
mn[i]=temp2;
state[temp2++]=1;
}
cout<<n<<' ';
for (int i=n-1; i>=1; i--) {
if (!state[i]) {
cout<<i<<' ';
}
}
for (int i=0; i<a; i++) {
cout<<mn[i]<<' ';
cout<<ma[i]<<' ';
}
cout<<1<<endl;
}
}
return 0;
}
|
三
这道题选择了一个贪心的策略，即一开始就买下一个适当数量的毛巾，以便以后去洗来用，对于慢洗和快洗的选择是，慢洗越早越好，快洗是在必须得快洗才能满足需求的时候才去选择快洗，并且越晚洗越好，让开销最小化。need数组存储当天用多少毛巾，wash数组存储当天能送洗多少。随着最初买的毛巾数量的变化，最小花销一定是位于极小值点上，所以可以看为一个开口向上的函数，用三分策略降低寻找最优方案的时间复杂度。
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 <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long LL;
const LL inf=0xfffffffffffff;
int need[N],wash[N],n;
LL sum;
int p,t1,p1,t2,p2;
LL llmin(LL x,LL y)
{
return x<y?x:y;
}
LL minprice(LL firbuy)
{
memset(wash, 0, sizeof(wash));
sum=p*firbuy;
LL rest=firbuy;
for (int i=1; i<=n; i++) {
int today=need[i];
if (rest) {
int k=(int)llmin(rest,today);
today-=k;
rest-=k;
wash[i]+=k;
if (!today) {
continue;
}
}
for (int j=1; j<=i-t1; j++) {
if (wash[j]) {
int k=(int)llmin(wash[j],today);
today-=k;
wash[j]-=k;
wash[i]+=k;
sum+=p1*k;
if (!today) {
break;;
}
}
}
for (int j=i-t2; j>=1&&j>i-t1; j--) {
if (wash[j]) {
int k=(int)llmin(wash[j],today);
today-=k;
wash[j]-=k;
wash[i]+=k;
sum+=p2*k;
}
if (!today) {
break;;
}
}
if (today) {
return inf;
}
}
return sum;
}
int main()
{
cin>>n;
LL l,r=0;
for (int i=1; i<=n; i++) {
cin>>need[i];
r+=need[i];
}
l=need[1];
cin>>p>>t2>>p2>>t1>>p1;
while (l+2<r) {
LL k=(r-l)/3,m1=l+k,m2=r-k;
if (minprice(m1)<minprice(m2)) {
r=m2;
}
else l=m1;
}
LL best=minprice(l);
for (LL i=l; i<=r; i++) {
best=llmin(best,minprice(i));
}
cout<<best;
}
|
四
题目来源：BZOJ3969
上道题用到三分的策略，这道题可以直接用二分的策略，因为所有可能的取值是一个线性的函数。所以写一个检查函数，以检查输入的值是否符合条件，不断缩小搜素范围，找到最小值。检查之前先把电池的电量进行排序。检查函数的实现只需要判断可以找到n组电量之差小于所要检查的值，且比所选电池电量大的电池的数量应足够放下其他的位置（芯片中其他电量非最小的位置）
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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,k,sum,a[N];
bool check(int x)
{
int cnt=n;
for (int i=1; i<sum; i++) {
if (a[i+1]-a[i]<=x) {
if (sum-i+1<2*cnt*k) {
return false;
}
cnt--;
i++;
if (cnt==0) {
return true;
}
}
}
return false;
}
int main()
{
cin>>n>>k;
sum=2*n*k;
for (int i=1; i<=sum; i++) {
cin>>a[i];
}
sort(a+1,a+1+sum);
int l=a[2]-a[1],r=a[sum-k+1],mid=0;
while (l<r) {
mid=l+r>>1;
if (check(mid)) {
r=mid;
}
else l=mid+1;
}
cout<<l;
}
|
五
这是一道宽搜的模版题，把当前数字的排列方式转换成字符串，表示当前的一个状态，同时用哈希表，string查找int的方式存储到达每个状态需要走几步，我们可以让空格和上下左右四个位置交换（在有效的前提下），直到出现符合要求的最终状态。这一位置交换操作用坐标来实现，即定义两个数组，存储(0,1)(0,-1)(1,0)(-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
| #include<iostream>
#include <algorithm>
#include <unordered_map>
#include <queue>
#include <string>
using namespace std;
queue<string> q;
unordered_map<string, int> d;
int bfs(string start)
{
string end="12345678x";
d[start]=0;
q.push(start);
int mx[4]={0,0,1,-1},my[4]={1,-1,0,0};
while (q.size()) {
string t=q.front();
q.pop();
if (t==end) {
return d[t];
}
int distance=d[t];
int k=(int)t.find('x');
int tx=k/3,ty=k%3;
for (int i=0; i<4; i++) {
int x=tx+mx[i],y=ty+my[i];
if (x>=0&&x<3&&y>=0&&y<3) {
swap(t[k],t[3*x+y]);
if (!d[t]) {
q.push(t);
d[t]=distance+1;
}
swap(t[k],t[3*x+y]);
}
}
}
return -1;
}
int main()
{
string start;
char c;
for (int i=0; i<9; i++) {
cin>>c;
start+=c;
}
cout<<bfs(start);
}
|
