题目
- A、Polycarp and Coins
- B1、Wonderful Coloring - 1
- B2、 Wonderful Coloring - 2
A、Polycarp and Coins
题目链接：Polycarp and Coins
题意：你有两种硬币：一种是面值为一元的、另一种是面值为二元的，现在给出一个数值，要求由尽可能数量相同两种硬币组成这个值，输出一元硬币和二元硬币的数量。
思路：首先清楚两个硬币组合是为3，对于所有数值是3的倍数的话，都可以取到相等的，如果对3取模为1就加一个一元硬币，取模为二就加一个二元硬币，两者的基础值都是数值除3。
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <math.h>
#include <bitset>
#include <cctype>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(a, b, c) for(int a = b; a <= c; a ++)
#define drep(a, b, c) for(int a = b; a >= c; a --)
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl '\n'
#define ccn cout << '\n'
const double PI = acos(-1.0);
const double eps = 1e-6;
ll qpow(ll a, ll b){
ll res = 1; while(b){if(b&1)res*=a; a*=a;b>>=1;} return res;
}
inline int read(){
int s=0,w=1; char ch = getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int main ()
{
int t;
cin >> t;
while(t--)
{
int n;
cin >> n;
int a = n/3;
int b = n - 2*a;
while(b - a >= 2)
{
b -= 2;
a++;
}
cout << b << " " << a << endl;
}
return 0;
}
B1、Wonderful Coloring - 1
题目链接：Wonderful Coloring - 1
题意：涂色题，要么涂红色或者绿色还是不涂三种选择，要求满足字符串中每种字母不会被两种颜色同时涂到，而且涂红色的次数应该和绿色想等，
求红色最多涂了多少。
思路：很简单的题，数据范围也很小，首先是设置一个数组，统计每种字母出现的次数，然后遍历这个数组，如果次数大于等于2：ans直接加一，如果次数小于2：则left加一。最后ans加上left/2的值就是答案了。
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <math.h>
#include <bitset>
#include <cctype>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(a, b, c) for(int a = b; a <= c; a ++)
#define drep(a, b, c) for(int a = b; a >= c; a --)
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl '\n'
#define ccn cout << '\n'
const double PI = acos(-1.0);
const double eps = 1e-6;
ll qpow(ll a, ll b){
ll res = 1; while(b){if(b&1)res*=a; a*=a;b>>=1;} return res;
}
inline int read(){
int s=0,w=1; char ch = getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int ch[28], t;
int main ()
{
cin >> t;
while(t--)
{
for(int i = 1; i <= 26; i++)
{
ch[i] = 0;
}
string s;
cin >> s;
for(int i = 0; i < s.size(); i++)
{
ch[s[i]-'a'+1] ++;
}
int left = 0, ans = 0;
for(int i = 1; i <= 26; i++)
{
if (ch[i] >= 2)
{
ans ++;
}
if (ch[i] == 1)
{
left ++;
}
}
// cout << left << " " << ans << enld;
ans += left/2;
cout << ans << endl;
}
return 0;
}
B2、 Wonderful Coloring - 2
题目链接：Wonderful Coloring - 2
题意：是上一题的增加版本，输入一个n个元素的数组和k种颜色，尽量给数组涂色，满足以下要求：可以涂k种颜色种的任意一种也可以不涂、每种颜色使用的数量必须相等、一个数不允许被同一种颜料涂两次、尽量给数组涂上最多种的颜色。
思路：我们可以简单的想到，如果这个数出现的次数大于等于k的时候，所有这个数就直接涂1到k剩下的都是零。对于剩下的数，我们依次涂1-k就可以了，只不过注意在最后可能会剩下来一些地方情况，即剩下的数不够涂k次，导致最后每种颜色涂的次数不相等，这里我卡住了一个地方，那就是可能会给一个色涂上了一个重复的颜色，所以我们这里可以用一个结构体排序的方式来进行处理。
吐槽：这个题真的是，没注意到直接过去会重复涂，中间实现的时候自闭了，以为自己码不出来已经有思路的题，结果是思路出错了，真的无语。
#include <iostream>
#include <algorithm>
#include <stdlib.h>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <math.h>
#include <bitset>
#include <cctype>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define rep(a, b, c) for(int a = b; a <= c; a ++)
#define drep(a, b, c) for(int a = b; a >= c; a --)
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define endl '\n'
#define ccn cout << '\n'
const double PI = acos(-1.0);
const double eps = 1e-6;
ll qpow(ll a, ll b){
ll res = 1; while(b){if(b&1)res*=a; a*=a;b>>=1;} return res;
}
inline int read(){
int s=0,w=1; char ch = getchar();
while(ch<'0'||ch>'9'){if(ch=='-') w=-1; ch=getchar();}
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int t, a[200005], b[200005], c[200005], ans[200005], n, k;
struct node
{
int val, pos, ans;
};
node x[200005];
bool cmp1(node p, node q)
{
return p.val < q.val;
}
bool cmp2(node p, node q)
{
return p.pos < q.pos;
}
int main ()
{
cin >> t;
while(t--)
{
cin >> n >> k;
for(int i = 1; i <= n; i ++)
{
cin >> x[i].val;
x[i].pos = i;
b[x[i].val]++;
}
int sum = 0;
for(int i = 1;i <= n; i++)
{
if (b[x[i].val] < k) sum ++;
}
sort(x+1, x+1+n, cmp1);
int top = sum/k*k, num = 1, mark = 1;
int flag = 1;
for(int i = 1; i <= n; i ++)
{
if (b[x[i].val] >= k)
{
x[i].ans = ++c[x[i].val];
if (x[i].ans > k) x[i].ans = 0;
}
else
{
if (num <= top)
{
num++;
x[i].ans = mark ++;
if (mark > k) mark = 1;
}
}
}
sort(x+1, x+1+n, cmp2);
// ==== ==== ==== ==== ==== ====
for(int i = 1; i<= n; i++)
{
cout << x[i].ans << " ";
}
cout << endl;
for(int i = 1; i <= n; i++)
{
c[x[i].val] = 0;
b[x[i].val] = 0;
x[i].ans = 0;
}
}
return 0;
}
