2020.10.9 19级training 补题报告

E - High School: Become Human

 1.题意

　　给定两个正整数x, y，问x的y次方大还是y的x次方大。

2.题解

　　一开始想用快速幂做，但是数据太大了。找规律发现只要两个数至少有一个大于等于3，如果x>y，x的y次方肯定小于y的x次方，反之同理。还有一些特例，2和3，2和4，x为1，y为1。

3.代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e4 + 5;
int main() {
    ll x, y;
    scanf("%lld%lld", &x, &y);
    
    if(x == y) {
        cout << "=" << endl;
        return 0;
    }
    if((x == 2 && y == 4) || (x == 4 && y == 2)) {
        cout << "=" << endl;
        return 0;
    }
    if(x == 2 && y == 3 || x == 1) {
        cout << "<" << endl;
        return 0;
    }
    if(x == 3 && y == 2 || y == 1) {
        cout << ">" << endl;
        return 0;
    }
    
    if(x < y) {
        cout << ">" << endl;
        return 0;
    }
    if(x > y) {
        cout << "<" << endl;
        return 0;
    }

}

F - Three displays

 1.题意

　　有n个位置，每个位置有两个属性s和c，找出三个位置i，j，k，满足si<sj<sk，且三个位置的c之和最小并输出这个和。

 2.题解

　　枚举中间的数，各遍历左右两端的位置，找出符合s条件的位置并更新使得c越来越小，枚举一次记录c的和并维护最小值。

 3.代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e3 + 5;
const int INF = 0x7fffffff;
int n;
int s[3010], c[3010];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
    }
    for(int i = 1; i <= n; i++) {
        scanf("%d", &c[i]);
    }
    
    c[0] = c[n+1] = INF;
    int l, r;
    int ans = INF;
    
    for(int i = 2; i <= n - 1; i++) {
        l = 0;
        r = n + 1;
        for(int j = 1; j < i; j++) {
            if(s[j] < s[i]) {
                if(c[j] < c[l]) {
                    l = j;
                }
            }      
        }
            
        for(int j = i + 1; j <= n; j++) {
            if(s[j] > s[i]) {
                if(c[j] < c[r]) {
                    r = j;
                }
            }       
        }
            
        if(l != 0 && r != n + 1) {
            ans = min(ans, c[l] + c[r] + c[i]);    
        }
    }
    
    if(ans == INF) {
        printf("-1");
    } else {
        printf("%d",ans);
    }
    
    return 0;
}