2020牛客暑期多校训练营(第三场)题解A、B、C、E、L

发布于 2020-07-19  0 次阅读


A、Clam and Fish

思路:

当遇到type2和type3时,因为有鱼且只能进行一次操作,所以直接抓鱼即可
type0的情况有饵料就用
type1的情况要考虑是钓鱼还是制作饵料,根据后面剩余的type0和type1来决定,有两种方法
1、从早到晚考虑
能做饵料就做,不能做就钓鱼,最后如果饵料有剩余的x,可以将后面的x/2的做饵料的机会拿来钓鱼
2、从晚到早考虑
遇到type0就记录为抓鱼的地点,往前搜索可以做饵料的机会即可抓鱼,当没有type0的时候并且遇到type1时,可以记录该点为抓鱼的地点,往前搜索可以制作饵料的地方

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
int t, n, ans, ans0;
char s[2000009];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--){
        cin>>n;
        cin>>s;
        ans=0, ans0=0;
        for(int i=n-1; i>=0; i--){
            if(s[i]=='0'){
                ans0++;
            }
            else if(s[i]=='1'){
                if(ans0==0)
                    ans0++;
                else if(ans0>0){
                    ans0--;
                    ans++;
                }
            }
            else if(s[i]=='2'){
                ans++;
            }
            else if(s[i]=='3'){
                ans++;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

B、Classical String Problem

思路:

将字符串s视作首尾相连的圈,每次对s进行‘M’操作时,将初始对应与0的下标k移动

AC Code:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
char s[2000009];
char c;
int n, x, k=0, len;
int main(){
    scanf("%s", &s);
    scanf("%d", &n);
    getchar();
    len=strlen(s);
    while(n--){
        scanf("%c %d", &c, &x);
        getchar();
        if(c=='A')
            printf("%c\n", s[(k+x-1)%len]);
        else{
            k+=x;
			if(k>=len)
				k%=len;
			else if(k<0)
				k+=len;
        }
    }
    return 0;
}

C、Operation Love(计算几何,叉积)

思路:

找出最长的两边,9和8,利用叉积计算两边的连接顺序
求为右手的情况(先8后9)
1、先找到9再找到8,则叉积求得的方向应该为逆时针
2、先找到8再找到9,则叉积求得的方向应该为顺时针

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const double pi = acos(-1.0);
#define INF 0x7f7f7f
// #define TDS_ACM_LOCAL
struct node
{
    double x, y;
}p[21];
double eps=1e-5;
double dis(node p1, node p2){
    return (sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)));
}
double cross(node a, node b, node c){
    return (a.x-b.x)*(a.y-c.y)-(a.y-b.y)*(a.x-c.x);
}

void solve(){
    int flag=0;
    for(int i=0; i<20; i++) cin>>p[i].x>>p[i].y;
    for(int i=0; i<20; i++){
        if((fabs(dis(p[i], p[(i+1)%20])-9)<eps)&&(fabs(dis(p[(i+1)%20], p[(i+2)%20])-8)<eps))
            if(cross(p[i], p[(i+1)%20], p[(i+2)%20])>0)
                flag=1;
        if((fabs(dis(p[i], p[(i+1)%20])-8)<eps)&&(fabs(dis(p[(i+1)%20], p[(i+2)%20])-9)<eps))
            if(cross(p[i], p[(i+1)%20], p[(i+2)%20])<0)
                flag=1;
    }
    if(flag)
        cout<<"right"<<endl;
    else
        cout<<"left"<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

E、Two Matchings

题目大意:

构造p数组和q数组,满足p[p[i]]=i,数组是1到n的排列,p,q数组每位都不同,答案为a数组每位与a[p[i]]的差的绝对值和a[q[i]]的差的绝对值的和。

思路:

总成本最小,即为第一种匹配最小,第二种次小。
最小即为排序后两两匹配即可(1和2,3和4…)
次小稍微列一下会发现规律,其实就是4和6的组合
然后dp求一下每个位置相对应的即可

AC Code:

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f3f3f
// #define TDS_ACM_LOCAL
const int N=2e5 +10;
ll n, ans, a[N], dp[N];
void solve(){   
    cin>>n;
    ans=0;
    for(int i=1; i<=n; i++) cin>>a[i];
    sort(a+1, a+1+n);
    for(int i=2; i<=n; i+=2) ans+=a[i]-a[i-1];
    dp[2]=INF, dp[4]=a[4]+a[3]-a[2]-a[1], dp[6]=a[6]-a[1]+a[5]-a[4]+a[3]-a[2];
    for(int i=8; i<=n; i+=2){
        dp[i]=min(dp[i-4]+a[i]+a[i-1]-a[i-2]-a[i-3], dp[i-6]+a[i]-a[i-5]+a[i-1]-a[i-2]+a[i-3]-a[i-4]);
    }
    cout<<ans+dp[n]<<endl;
    return ;
}   

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    int T;
    cin>>T;
    while(T--)  solve();
    return 0;
}

L、Problem L is the Only Lovely Problem

思路:

签到题

AC Code:

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
// #define TDS_ACM_LOCAL

void solve(){
    string s;
    cin>>s;
    for(int i=0; i<6; i++)  s[i]=tolower(s[i]);
    if(s.substr(0,6)=="lovely") cout<<"lovely"<<endl;
    else cout<<"ugly"<<endl;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef TDS_ACM_LOCAL
    freopen("D:\\VS code\\.vscode\\testall\\in.txt", "r", stdin);
    freopen("D:\\VS code\\.vscode\\testall\\out.txt", "w", stdout);
#endif
    solve();
    return 0;
}

平平无奇的在校大学生