Im_asleep's blog

By Im_asleep, history, 2 months ago, In English

A. Polycarp and Coins

Submit code:

void solve() {
    int n;
    cin >> n;
    int a, b;
    if(n == 1) {
        a = 1;
        b = 0;
    }
    else if(n % 3 == 0) {
        b = n / 3;
        a = n - (2 * b);
    }
    else if(n % 3 == 1) {
        b = n / 3;
        a = n - (2 * b);
    }
    else {
        b = n / 3 + 1;
        a = n - (2 * b);
    }
    cout << a << ' ' << b << endl;
}

int main() {
    int n;
    cin >> n;
    while (n --) {
        solve();
    }
    return 0;
}

better answer:

void mainA() {
    int n;
    cin >> n;
    int t = n % 3;
    cout << n / 3 + (t == 1) << " " << n / 3 + (t == 2) << "\n";
}

int main() {
    int n;
    cin >> n;
    while(n --) mainA();
    return 0;
}

B1. Wonderful Coloring — 1

void solve() {
    string s;
    cin >> s;
    map<char, int> mp;
    for (int i = 0; i < s.length(); i ++) { //统计每个字符的个数
        mp[s[i]] ++;
    }
    int ans = 0;
    for (char c = 'a'; c <= 'z'; c ++) { //全涂成灰色,因为最终只有两种颜色,最多+=2
        if (mp[c] == 1) ans ++;
        if (mp[c] >= 2) ans += 2;
    }
    cout << ans / 2 << endl; //计算颜色数量
}

B2. Wonderful Coloring — 2

not really understand..

const int MAXN = 2e5;

int a[MAXN + 10];
int b[MAXN + 10];
int c[MAXN + 10];
queue<int> q[MAXN + 10];

void mainB() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) { //a, c保存数组
        cin >> a[i];
        c[i] = a[i];
    }
    sort(a + 1, a + n + 1); // dont forget + 1
    int j = 1;
    int cnt = 1;
    b[1] = a[1];
    for (int i = 2; i <= n; i ++) { // 将已经排好序的 a数组去掉数量大于 k的元素然后放到 b数组中
        if (a[i] == a[i - 1]) { //当前连续cnt个
            cnt ++;
        }
        else {
            cnt = 1;
        }
        if (cnt <= k) { //连续cnt个是否超过k
            j++;
            b[j] = a[i];
        }
        else {
            continue;
        }
    }
    int n2 = j / k * k; // 多余的余数部分就不要了
    int now = 1;
    for (int i = 1; i <= n2; i++) {
        q[b[i]].push(now); // 利用queue保存每一个整数的涂色方案
        now ++;
        if (now > k) now = 1;
    }
    for (int i = 1; i <= n; i++) { // output
        if (q[c[i]].empty()) {
            cout << "0 ";
        }
        else {
            int ft = q[c[i]].front();
            q[c[i]].pop();
            cout << ft << " ";
        }
    }
    cout << endl;
}
 
 
 
 
  • Vote: I like it
  • -18
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Im_asleep (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Dynamic programming, DP for short, can be used when the computations of subproblems overlap.If you're computing for instance fib(3) (the third Fibonacci number), a naive implementation would compute fib(1) twice:With a more clever DP implementation, the tree could be collapsed into a graph:It doesn't look very impressive in this example, but imagine the difference for fib(1000). In fact the naive implementation makes O(2n) calls, while the DP version makes O(n) calls.There are a lot more problems that can be solved with dynamic programming, these are just a few of them: 1. Partition Problem (coming soon) 2. Given a set of integers, find out if it can be divided into two subsets with equal sums 3. Subset Sum Problem (coming soon) 4. Given a set of positive integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum. 5. Coin Change Problem (Total number of ways to get the denomination of coins, coming soon)