Codeforces Round #313 (Div. 2) 解题报告

时间：2024-06-27 10:34:44

A. Currency System in Geraldion：

  • 题意：有n中不同面额的纸币，问用这些纸币所不能加和到的值的最小值。
  • 思路：显然假设这些纸币的最小钱为1的话，它就能够组成随意面额。

    假设这些纸币的最小值大于1，那么它所不能组成的最小面额就是1.所以自学求最小值就可以。

  • 我的代码：
#include <set>

#include <map>

#include <cmath>

#include <stack>

#include <queue>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long int LL;

const int M = 100009,INF = 0x3fffffff;

int main(void) {

    //problem: , address:

    int n, x, y = INF;

    cin >> n;

    while (n--) {

        cin >> x;

        if (x < y) swap(x, y);

    }

    if(y <= 1) cout << "-1" << endl;

    else cout << "1" << endl;

    return 0;

}

B. Gerald is into Art：

  • 题意：给定三个矩形的 长和款。第一个矩形作为容器。最后两个矩形不可重叠且水平的放置在当中，问能否放下？
  • 思路：这里第一步先把第二个矩形放入容器的左下角显然是最好的策略，能够给第三个矩形最大的可能空间（比赛的时候不够细致，没有注意，第一个大矩形反正左下角必须满足能放下的条件，就没过大数据），注意这里第一个矩形有横放和竖放两种情况。第二步再把第三个矩形放入剩余空间，这时候放置有两种情况：Codeforces Round #313 (Div. 2) 解题报告，每种放置情况第三个矩形又分为横放和竖放两种类型。这样就把放置问题分为了8种情况，满足随意情况就可以。
  • 我的代码：
#include <set>

#include <map>

#include <cmath>

#include <stack>

#include <queue>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long int LL;

const int M = 100009,INF = 0x3fffffff;

int main(void) {

    int a1, a2, a3, b1, b2, b3;

    cin >> a1 >> b1 >> a2 >> b2 >> a3 >> b3;

    int x = a1 - a2, y = b1 - b2;

    bool ans = false;

    if ( (b2 <= b1 && x >= a3 && b3 <= b1) || (x >= 0 && a3 <= a1 && b3 <= y) || (y >= 0 && x >= b3 && a3 <= b1) || (x >= 0 && b3 <= a1 && a3 <= y) ) ans =true;

    x = a1 - b2;

    y = b1 - a2;

    if ( (y >= 0 && x >= a3 && b3 <= b1) || (x >= 0 && a3 <= a1 && b3 <= y) || (y >= 0 && x >= b3 && a3 <= b1) || (x >= 0 && b3 <= a1 && a3 <= y) ) ans =true;

    if (ans) cout << "YES" << endl;

    else cout << "NO" << endl;

    return 0;

}

C. Gerald’s Hexagon：

  • 题意：用等边三角形堆积成一个六边形，六边形每个内角的为120度。告诉你这个六边形的六条边的长度，问该六边形是由多少个等边三角形组成的。
  • 思路：求出这和整个六边形的面积。再除以三角形的面积，就能够了。

    Codeforces Round #313 (Div. 2) 解题报告依据内角都为120度的特点，总是能把六边形切为如图的四个三角形。边上三个三角形面积easy计算。那么依据余弦公式：

    c2=a2+b2−2abcosθ

    能够求出内部三角形的边长。

    再依据海伦公式：

    p=(a+b+c)/2
    s=p(p−a)(p−b)(p−c)−−−−−−−−−−−−−−−−−√

    就可以算出内部三角形面积。

  • 我的代码：
#include <set>

#include <map>

#include <cmath>

#include <stack>

#include <queue>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long int LL;

const int M = 100009,INF = 0x3fffffff;

double pi = sqrt(3), eps = 1e-3;

int main(void) {

    double sum = 0, a, b, c, d, e, f;

    cin >> a >> b >> c >> d >> e >> f;

    double x = sqrt((a * a) + (b * b) + a * b);

    double y = sqrt((c * c) + (d * d) + c * d);

    double z = sqrt((e * e) + (f * f) + e * f);

    double s = (x + y + z) / 2;

    //cout << x << " " << y << " "<< z << endl;

    sum += sqrt(s * (s - x) * (s - y) * (s - z));

    //cout << sum << endl;

    sum += 0.25 * pi * (a * b + c * d + e * f);

    cout << int(sum / ( pi / 4) + eps) << endl;

    return 0;

}

D. Equivalent Strings

  • 题意：给定两个字符串同性的法则。推断其是否同性。
  • 递归就可以。但是比赛的代码在大数据的时候超时了。后来加了一个剪枝过了。

    然后超时的主要原因是用了string后，会出现多次复制字符串的情况，把string换为char*,时间缩短10倍！

  • string实现的代码：
#include <set>

#include <map>

#include <cmath>

#include <stack>

#include <queue>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long int LL;

const int M = 100009,INF = 0x3fffffff;

bool same(string a, string b) {

    int A[26], B[26];

    memset(A, 0, sizeof(A));

    memset(B, 0, sizeof(B));

    for (int i = 0; i < a.size(); i++) {

        A[a[i] - 'a']++;

        B[b[i] - 'a']++;

    }

    for (int i = 0; i < 26; i++) {

        if (A[i] != B[i]) return false;

    }

    if (a == b) return true;

    if (a.size() % 2 != 0) return false;

    string x1, x2, y1, y2;

    for (int i = 0; i < a.size() / 2; i++) {

        x1 += a[i];

        x2 += b[i];

        y1 += a[i + a.size() / 2];

        y2 += b[i + a.size() / 2];

    }

    return (same(x1, x2) && same(y1, y2)) || (same(x1, y2) && same(y1, x2));

}

int main(void) {

    ios::sync_with_stdio(false);

    string a, b;

    while (cin >> a >> b) {

        if (same(a, b)) cout << "YES" << endl;

        else cout << "NO" << endl;

    }

    return 0;

}
  • char* 实现的代码：
#include <set>

#include <map>

#include <cmath>

#include <stack>

#include <queue>

#include <string>

#include <vector>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long int LL;

const int M = 100009,INF = 0x3fffffff;

bool str (char a[], char b[], int n) {

    bool ans = true;

    for (int i = 0; i < n; i++) {

        if (a[i] != b[i]) {

            ans = false;

            break;

        }

    }

    return !ans;

}

bool same(char a[], char b[], int n) {

    int A[26], B[26];

    memset(A, 0, sizeof(A));

    memset(B, 0, sizeof(B));

    for (int i = 0; i < n; i++) {

        A[a[i] - 'a']++;

        B[b[i] - 'a']++;

    }

    for (int i = 0; i < 26; i++) if (A[i] != B[i]) return false;

    if (!str(a, b, n)) return true;

    if (n % 2 != 0) return false;

    return (same(a, b + n / 2, n / 2) && same(a + n / 2, b, n / 2)) || (same(a, b, n / 2) && same(a + n / 2, b + n / 2, n / 2));

}

int main(void) {

    ios::sync_with_stdio(false);

    char a[200009], b[200009];

    while (cin >> a >> b) {

        int n = strlen(a);

        if (same(a, b, n)) cout << "YES" << endl;

        else cout << "NO" << endl;

    }

    return 0;

}

相关文章