目录
A - Range Product
分情况讨论：
- \(a \le 0 \le b\) 时，乘积一定为 \(0\)；
- 否则：
- \(0 < a \le b\) 时，乘积一定为正；
- 否则，负数的个数有 \(b - a + 1\) 个，判断这个数是否为奇数，若是，乘积为负，否则为正。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
int main() {
int a = Read(), b = Read();
if(a <= 0 && b >= 0) {
printf("Zero\n");
}
else {
bool p = false;
if(a > 0 && b > 0) {
p = true;
}
else {
p = (b - a) & 1;
}
if(p) {
printf("Positive\n");
}
else {
printf("Negative\n");
}
}
return 0;
}
B - Box and Ball
考虑对于每个操作，动态记录里面是否有红球。
如果将盒子 \(x\) 中的一个球放到盒子 \(y\) 中：
- 若盒子 \(x\) 中可能有红球，那么盒子 \(y\) 中也可能有红球；
- 假设盒子 \(x\) 中已经没有球了，那么盒子 \(x\) 也不可能有红球。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
const int N = 100005;
int n, cnt[N];
bool a[N];
int main() {
int i, m;
n = Read(), m = Read();
for(i = 1; i <= n; i++) {
cnt[i] = 1;
}
a[1] = true;
while(m--) {
int u = Read(), v = Read();
cnt[v]++, cnt[u]--, a[v] |= a[u];
if(!cnt[u]) {
a[u] = false;
}
}
int ans = 0;
for(i = 1; i <= n; i++) {
ans += a[i];
}
Write(ans);
return 0;
}
C - Knot Puzzle
对于一段完整的绳子，剪去最左边或最右边的小绳子比不这么做是不优的。证明可以考虑，存在至少一种剪法，使得前者留下的较长的绳子比后者留下的较短的且需要被再次剪开的绳子长。
倒着考虑，假设最后一步的绳长不小于 \(L\)，则前面所有步的绳长均不小于 \(L\)，留下总长最长的两段连续的小绳子最后剪即可。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll Read() {
int sig = 1;
ll num = 0;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') {
sig = -1;
}
c = getchar();
}
while(isdigit(c)) {
num = (num << 3) + (num << 1) + (c ^ 48);
c = getchar();
}
return num * sig;
}
void Write(ll x) {
if(x < 0) {
putchar('-');
x = -x;
}
if(x >= 10) {
Write(x / 10);
}
putchar((x % 10) ^ 48);
}
const int N = 100005;
int n;
ll a[N], k;
int main() {
int i, j = 0;
n = Read(), k = Read();
for(i = 1; i <= n; i++) {
a[i] = Read();
if(a[i] + a[i - 1] > a[j] + a[j - 1]) {
j = i;
}
}
if(a[j] + a[j - 1] < k) {
printf("Impossible\n");
return 0;
}
printf("Possible\n");
for(i = 1; i < j - 1; i++) {
Write(i), putchar('\n');
}
for(i = n - 1; i >= j; i--) {
Write(i), putchar('\n');
}
Write(j - 1), putchar('\n');
return 0;
}