### Im_asleep's blog

By Im_asleep, history, 2 months ago, #### 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;
}


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 = a;
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;
} Comments (3)
 » Auto comment: topic has been updated by Im_asleep (previous revision, new revision, compare).
 » 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)
•  » » But B2 is not DP.