A1 - Non-alternating Deck (easy version)
题意
给出一个数字n,两个人轮流玩游戏从n中拿数,第一个人首先拿1,第二个人拿2,3,第一个人拿1...循环往复,直到数字全被拿完
思路
模拟即可
void solve() {
int n;
cin >> n;
n --; //减去第一次步骤,将后面拿取分为4次一组,即b拿两次,a拿两次
int i = 2, cnt = 0, a = 1, b = 0;
while (n) {
if (n >= i) {
cnt = cnt % 4;
if (cnt < 2) b += i;
else a += i;
n -= i;
}else {
cnt = cnt % 4;
if (cnt < 2) b += n;
else a += n;
n = 0;
}
i ++;
cnt ++;
}
cout << a << ' ' << b << endl;
}
\[\]A2 - Alternating Deck (hard version)
题意
这题是上题的困难版本,即两个人拿的数字还有颜色,按白黑白黑白黑.....分布,若第二个人拿了2,则他拿了一个黑色,一个白色。问最后第一个人拿了多少个白色,黑色,第二个人拿了多少白色黑色
思路
也是模拟,在上题基础上增加判断当前拿的数字是黑是白就可推断出后面他拿的这部分数字中白色和黑色数量
void solve() {
int n;
cin >> n;
n --;
int i = 2, cnt = 0, a = 1, b = 0, c = 0, d = 0;
int col = 1;
while (n) {
if (n >= i) {
cnt = cnt % 4;
if (cnt < 2) {
c += i / 2; //不管拿的是奇数还是偶数,一定都有一半是黑,一半是白
d += i / 2;
if (col) { //若当前开始颜色是黑色且拿的数为奇数,则后面会多出一个黑色,下一个数变成白色
if (i % 2 == 1) {
d ++;
col = 0;
}
} else {
if (i % 2 == 1) { //若当前开始颜色是白色且拿的数为奇数,则后面会多出一个白色,下一个数变成黑色
c ++;
col = 1;
}
}
}
else {
a += i / 2;
b += i / 2;
if (col) {
if (i % 2 == 1) {
b ++;
col = 0;
}
} else {
if (i % 2 == 1) {
a ++;
col = 1;
}
}
}
n -= i;
}else {
cnt = cnt % 4;
if (cnt < 2) {
c += n / 2;
d += n / 2;
if (col) {
if (n % 2 == 1) {
d ++;
col = 0;
}
} else {
if (n % 2 == 1) {
c ++;
col = 1;
}
}
}
else {
a += n / 2;
b += n / 2;
if (col) {
if (n % 2 == 1) {
b ++;
col = 0;
}
} else {
if (n % 2 == 1) {
a ++;
col = 1;
}
}
}
n = 0;
}
i ++;
cnt ++;
}
cout << a << ' ' << b << ' ' << c << ' ' << d << endl;
}
\[\]B - Cake Assembly Line
题意
有一排n个涂巧克力的机器,还有传送带上n块蛋糕,机器不能动,蛋糕可用传送带左右移动,蛋糕间相对位置不发生变化。
同时机器i可以在bi - h, bi + h这个区间内涂巧克力,蛋糕i的宽度在ai - w, ai + w间。机器涂巧克力只能进行一次。
问是否可以调整传送带,使每个蛋糕都可以涂上巧克力,且巧克力不会洒在其他位置
思路
很明显的区间问题,若要使每个巧克力在蛋糕范围内,那么每一个蛋糕和巧克力的相对位置都要满足传送带调整的位置在许可之内。
如:
3 10 5
65 95 165
40 65 145
若想第一个机器对应第一个蛋糕,那么传送带调节的范围x为:
a[i] - w + x <= b[i] - h
a[i] + w + x >= b[i] + h
调整一下就是
{b[i] + h - a[i] - w, b[i] - h - a[i] + w}
也就是l和r,若有新的l比当前l要大,那要更新,若有新的r要比当前r小,那也要更新
最后判断l是否小于等于r,也就是传送带有移动的空间
否则不行
const int INF = 2e9;
void solve() {
int n, w, h;
cin >> n >> w >> h;
vector<LL> a(n + 1), b(n + 1);
for (int i = 1; i <= n; i ++) cin >> a[i];
for (int i = 1; i <= n; i ++) cin >> b[i];
LL l = -INF, r = INF;
for (int i = 1; i <= n; i ++) {
LL x, y;
y = b[i] - h - a[i] + w;
x = b[i] + h - a[i] - w;
if (l <= x) {
l = x;
}
if (r >= y) {
r = y;
}
}
if (l <= r) {
cout << "YES" << endl;
}else cout << "NO" << endl;
}
\[\]C - Monsters (easy version)
题意
需要击败n只怪兽,有两种操作
1.减少某只怪兽1滴血
2.减少所有存活的怪兽一滴血,若期间有怪兽死了,那继续操作,否则停止
第二种操作只能进行一次,问最少需要多少次操作1可以打败所有怪兽
思路
稍微推断下即可知,我们需要怪兽的血量呈1,2,3,4,5....这样的阶梯型,那么操作2的收益是最大的。那么把怪兽的血量排序,减去多余的就是最少操作
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i ++) cin >> a[i];
sort(a.begin() + 1, a.end());
int x = 1;
LL sum = 0;
for (int i = 1; i <= n; i ++) {
if (a[i] >= x) {
sum += a[i] - x;
x ++;
}
}
cout << sum << endl;
}