Codeforces Round #308 (Div. 2)

這次cf真是發揮的有點醉，下次有div1我都不敢做了。

A. Vanya and Table

給你n個矩形，問你面積之和。

是面積之和不是面積并，直接算。然而我這個傻逼交錯檔案了WA了一發233333。

#include <bits/stdc++.h>

using namespace std;

int n;
int main() {
    int a, b, c, d;
    cin >> n;
    int ans = ;
    for (int i = ; i < n; i++) {
        cin >> a >> b >> c >> d;
        ans += abs(c - a + ) * abs(d - b + );
    }
    cout << ans << endl;
    return ;
}
           

B. Vanya and Books

給你一個整數n，問你從1到n一共有多少位。比如n = 13，1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13一共17位。

f[i]表示從1到 10i 一共有多少位，以753為例，從100到753都是3位數，是以答案就是f[2]+653*3。

#include <bits/stdc++.h>

using namespace std;

int n;
long long f[];
long long t[];
int main() {
    cin >> n;
    t[] = ;
    for (int i = ; i <= ; i++)
        t[i] = t[i - ] * ;
    f[] = ;
    for (int i = ; i <= ; i++)
        f[i] = f[i - ] + (t[i] - t[i - ]) * i + ;
    long long ans;
    long long base;
    for (int i = ; i <= n; i++) {
        if (t[i] > n) {
            base = i - ;
            break;
        }
    }
    ans = f[base] + (n - t[base]) * (base + );
    cout << ans << endl;
    return ;
}
           

C. Vanya and Scales

要用品質為 w0,w1,...,w100 的砝碼各1個稱出重量m，砝碼可以放在天平左邊也可以放在右邊。問是否可以稱出，輸出YES或NO。

如樣例3，7：左邊放3和物品，右邊放1和9即可。

假設可以稱出，則用w進制表示m，每一位上一定是0，1或w - 1，否則一定不行。

而如果某一位是w - 1則說明目前砝碼跟物品放在一起，相當于給物品加上了這個砝碼的重量。

我們隻需要模拟這個過程，提取m的每一位然後計算即可。

#include <bits/stdc++.h>

using namespace std;

int n, m;
int main() {
    cin >> n >> m;
    if (n == ) {
        cout << "YES" << endl;
        return ;
    }
    while (m) {
        int z = m % n;
        if (z <= ) {
            m /= n;
        } else if (z == n - ) {
            m = m / n + ;
        } else {
            cout << "NO" << endl;
            return ;
        }
    }
    cout << "YES" << endl;

    return ;
}
           

D. Vanya and Triangles

給你二維坐标下的n個點，問一共能構成多少個面積不為0的三角形。

如果不考慮面積則總方案數為 c3n 。

如果有三點共線則這三點不能構成三角形。

我們枚舉每一個點i，計算其他所有點與i連線的斜率，如果有重複的斜率則說明有三點共線，即，如果有m個點與i的連線斜率相同，則非法的方案數為 c2m 。

#include <bits/stdc++.h>

using namespace std;

const double INF = ;
const double eps = ;

struct Point{
    int x, y;
    Point() {}
    Point(int a, int b) : x(a), y(b) {}
};

int n;
Point p[];

int main() {
    cin >> n;
    for (int i = ; i < n; i++)
        cin >> p[i].x >> p[i].y;
    if (n < ) {
        cout <<  << endl;
        return ;
    }
    long long tot = (long long)n * (n - ) * (n - ) / ;;
    long long sum = ;
    vector<double> ans;
    for (int i = ; i < n; i++) {
        ans.clear();
        for (int j = i + ; j < n; j++) {
            int dx = p[j].x - p[i].x;
            int dy = p[j].y - p[i].y;
            double k;
            if (dx == ) k = INF;
            else if (dy == ) k = ;
            else k = (double)dy / (double)dx;
            ans.push_back(k);
        }
        sort(ans.begin(), ans.end());
        double num = ans[];
        int cnt = ;
        for (int j = ; j < ans.size(); j++) {
            if (fabs(ans[j] - num) < eps) {
                cnt++;
            } else {
                sum += (long long)cnt * ((long long)cnt - l) / ;;
                cnt = ;
                num = ans[j];
            }
        }
        sum += (long long)cnt * ((long long)cnt - l) / ;
    }
    cout << tot - sum << endl;
    return ;
}
           

E. Vanya and Brackets

給你一個表達式，隻有乘号和加号，數字都是1到9，要求加一個括号，使得表達式的值最大，問最大是多少。乘号個數<=15。

左括号一定在乘号右邊，右括号一定在乘号左邊，因為如果不是這樣的話，一定可以調整括号的位置使表達式的值增大。這個應該不難想。

于是隻要枚舉括号的位置然後計算表達式即可。

#include <bits/stdc++.h>

using namespace std;

int n;
string str;
vector<int> pos;
stack<char> sc;
stack<long long> sn;

long long twoResult(long long a, long long b, char c) {
    return (c == '*') ? a * b : a + b;
}

void cal() {
    char t = sc.top();
    sc.pop();
    long long a = sn.top();
    sn.pop();
    long long b = sn.top();
    sn.pop();
    sn.push(twoResult(a, b, t));
}

long long expression(string s) {
    for (int i = ; i < s.length(); i++) {
        char c = s[i];
        if (isdigit(c)) {
            sn.push(c - '0');
        } else if (c == '(') {
            sc.push(c);
        } else if (c == ')') {
            while (sc.top() != '(')
                cal();
            sc.pop();
        } else {
            if (c == '+') {
                while (!sc.empty() && sc.top() == '*')
                    cal();
                sc.push(c);
            } else sc.push(c);
        }
    }
    while (!sc.empty()) cal();
    return sn.top();
}

int main() {
    cin >> str;
    n = str.size();
    pos.push_back(-);
    for (int i = ; i < n; i += )
        if (str[i] == '*') pos.push_back(i);
    pos.push_back(n);
    int len = pos.size();
    long long ans = ;
    for (int i = ; i < len - ; i++) { // left
        for (int j = i + ; j < len; j++) { // right
            string s = str;
            s.insert(pos[i] + , , '(');
            s.insert(pos[j] + , , ')');
            ans = max(ans, expression(s));
        }
    }
    cout << ans << endl;
    return ;
}