2021年暑训热身专题

暑训比自己在家学效率真的高了不少，但也确实累了不少

21年暑假集训热身专题

problem A：Codeforce-127B

Canvas Frames
题目大意：给你n个木棍，一对长度相同的木棍为一组，两组构成一个四边形，问最多组成多少个。
题解：用map判断是否存在“一对”（有一根就加一，凑成一对就归零），sum记录一共出现了多少对，除2即可。
AC代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,a[101],sum=0;
    map<int,int>mp;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!mp[a[i]])mp[a[i]]=1;
        else{
            sum+=1;
            mp[a[i]]=0;
        }
    }
    cout<<sum/2;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

problem B：Codeforce-127C

Hot Bath
题目大意：已知冷水与热水的温度和最大流速，求最佳的冷水热水流速使得温度最接近t0，相同条件下速度越快越好。
题解：（暴力解法）直接利用已知最大流速求出当前t的值，当t<t0时意味着冷水流速过快，x1- -，当t>=t0时意味着热水流速过快，此时用一个minn记录最小值，以得到最佳答案。
AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
long long t1,t2,x1,x2,t0;
double t,minn=maxn;
long long  a,b;
int main(){
    cin>>t1>>t2>>x1>>x2>>t0;
    while(x1>=0&&x2>=0){
        t=(double)(t1*x1+t2*x2)/(x1+x2);
        if(t<t0){
            x1--;
        }else{
            if(t<minn){
                minn=t;
                a=x1;
                b=x2;
            }
            x2--;
        }
    }
    cout<<a<<" "<<b;
    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

problem C：Codeforce-126B

Password
题目大意：已知一个字符串，我们需要求出最长的子串使其等于母串的前缀和后缀，并且出现于母串内部。
题解：利用KMP算法中的Next数组（可以得到当前字符前面串中最长相等前后缀的长度），判断在母串内部是否存在一个值在Next数组右端点出现过，存在则直接输出，不存在则判断更短长度的子串。
AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
string str;
int Next[maxn];
int cnt[maxn];
void get_next(string str){
    int j=0,k=-1;
    Next[0]=-1;
    while(j<str.size()){
        if(k==-1||str[j]==str[k]){
            Next[++j]=++k;
        }
        else k=Next[k];
    }
    for(int i=0;i<str.size();i++){
        cnt[Next[i]]=1;//记录出现过的值
    }
}
int main(){
    cin>>str;
    get_next(str);
    int l;
    int len=str.size();
    int temp=Next[len];
    int flag=0;
    while(temp>0){
        if(cnt[temp]){//出现过直接跳出循环输出
            flag=1;
            l=temp;
            break;
        }
        temp=Next[temp];//往前找
    }
    if(flag){
        for(int i=len-l;i<len;i++){
            cout<<str[i];
        }
        cout<<endl;
    }
    else{
        cout<<"Just a legend"<<endl;
    }
    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

problem D：Codeforce-152A

Cupboards
题目大意：已知n对门（分左右）的开关状态（0关1开），求使左边门与右边门分别达到相同状态的最小操作次数是多少。
题解：记录左边和右边门的开关情况，4种状态一一枚举，找到最小值即可。
AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+7;
int n,l[maxn],r[maxn];
int l0=0,l1=0,r0=0,r1=0;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>l[i]>>r[i];
        if(l[i]==0)l0++;
        else if(l[i]==1)l1++;
        if(r[i]==0)r0++;
        else if(r[i]==1)r1++;
    }
    int minn1=min(l0+r1,l1+r0);
    int minn2=min(l0+r0,l1+r1);
    cout<<min(minn1,minn2);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

problem E ：Codeforce-248B

Chilly Willy
题目大意：某人喜欢能整除2、3、5、7的数，给出一个数的位数，求最小的满足条件的数是多少。
题解：找规律。
AC代码：

#include<bits/stdc++.h>
using namespace std;
long long  n;
int main(){
    cin>>n;
    if(n<=2){
        printf("-1\n");
        return 0;
    }
    else if(n==3){
        printf("210\n");
        return 0;
    }
    long long k=n%6;
    printf("1");
    if(k==0){
        for(int i=0;i<n-4;i++){
            printf("0");
        }
        printf("170\n");
    }else if(k==1){
        for(int i=0;i<n-3;i++){
            printf("0");
        }
        printf("20\n");
    } else if(k==2){
        for(int i=0;i<n-4;i++)
            printf("0");
        printf("200\n");
    }else if(k==3){
        for(int i=0;i<n-4;i++)
            printf("0");
        printf("110\n");
    }else if(k==4){
        for(int i=0;i<n-3;i++)
            printf("0");
        printf("50\n");
    }else if(k==5){
        for(int i=0;i<n-3;i++)
            printf("0");
        printf("80\n");
    }
    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

problem F ：Codeforce-155A

题目大意：有长度为n*2的数列，如果该数列里的数能两两配对，输出配对数的下标，否则输出-1.
题解：pair存数据+下标，，sort排序，先遍历一遍看是否有不配对的数，全部配对则输出下标。（会卡cin）（注意要用文件输入输出）
AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+7;
pair<int,int>a[maxn*2];
int n;
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d",&n);
    for(int i=1;i<=n*2;i++){
        scanf("%d",&a[i].first);
        a[i].second=i;
    }
    sort(a+1,a+1+n*2);
    for(int i=1;i<=n*2;i+=2){
        if(a[i].first!=a[i+1].first){
            printf("-1");
            return 0;
        }
    }
    for(int i=1;i<=n*2;i+=2){
        printf("%d %d\n",a[i].second,a[i+1].second);
    }
    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

problem G ：Codeforce-254B

Jury Size
题目大意：

题解：

AC代码：

problem H：Codeforce-254C

Anagram
题目大意：

题解：

AC代码：

problem I：Codeforce-254C

Rats
题目大意：

题解：唯一一篇题解啊

AC代码：

problem J：Codeforce-498A

Adjacent Replacements
题目大意：给你n个数，按照以下步骤操作：把1变为2，把2变为1，把3变为4，把4变为3…，求改变完后的数

题解：奇数不变，偶数减一。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int n,a[1001];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(!(a[i]&1))a[i]-=1;
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

problem K：Codeforce-498B

Polycarp’s Practice
题目大意：n本作业，k天写完，不可跳本，每天获得当天写完的最高难度的经验，问如何分配能让经验最多。

题解：贪心，只用把最高经验的作业计算进来，其他作业随便包含。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+7;
int n,k;
pair<int,int>a[2020];
int b[2020];
int cnt=1;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+1+n);
    long long sum=0;
    for(int i=n-k+1;i<=n;i++){
        sum+=a[i].first;
        b[cnt++]=a[i].second;
    }
    cout<<sum<<endl;
    sort(b+1,b+cnt);
    b[cnt-1]=n;
    for(int i=1;i<cnt;i++){
        //cout<<b[i]<<" ";
        if(i==1)cout<<b[i]<<" ";
        else cout<<b[i]-b[i-1]<<" ";
    }
    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

problem L：Codeforce-498C

Three Parts of the Array
题目大意：将一个数列分为3部分，可以为空，要求第一部分和等于第三部分，且第一部分和越大越好。

题解：首尾指针向内部推进，左边大了加右边，右边大了加左边。

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
long long arr[MAXN] = {0};
int main(){	
	int N;
	cin>>N;
	for(int i = 0; i < N; i++){
		cin>>arr[i];
	}
	long long a = arr[0], b = 0, ans = 0;
	int i = 1, j = N - 1;
	while(i <= j){
		if(a > b){
			b += arr[j];
			j--;
		}else if(a < b){
			a +=  arr[i];
			i++; 
		}
		if(a == b){
			ans = max(ans, a);
			a += arr[i];
			i++; 
		}	
	}
	cout<<ans<<endl;
	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

problem M：Codeforce-1006D

Two Strings Swaps
题目大意：

题解：

AC代码：

problem N：Codeforce-1006E

Military Problem
题目大意：

题解：

AC代码：

problem O：Codeforce-499D

Rocket
题目大意：

题解：

AC代码：

problem P：Codeforce-499E

Border
题目大意：

题解：（欧几里得加裴蜀定理）

AC代码：