解题思路
这是一个位运算问题。具体要求:
- 使用32个unsigned int记录1024个任务的状态
- 每个任务只能完成一次
- 需要实现:
- 设置第一个任务ID为已完成
- 检查第二个任务ID的完成状态
- 任务ID范围为[1,1024]
解决方案:
- 使用位图(bitmap)存储任务状态:
- 每个unsigned int有32位,32个int可以存储1024个状态
- 任务ID减1后,除以32得到数组索引
- 对32取模得到具体的位位置
- 使用位运算进行状态的设置和检查
代码
#include <iostream>
using namespace std;
class TaskChecker {
private:
// 检查或设置任务状态
static int checkTask(unsigned int* tasks, int taskId, bool isSet) {
int index = (taskId - 1) / 32; // 数组索引
int bitPos = (taskId - 1) % 32; // 位位置
unsigned int mask = 1u << (31 - bitPos); // 位掩码
if(isSet) {
tasks[index] |= mask; // 设置状态
return 0;
} else {
return (tasks[index] & mask) != 0; // 检查状态
}
}
public:
static void solve() {
int id1, id2;
while(cin >> id1 >> id2) {
// 检查ID范围
if(id1 < 1 || id1 > 1024 || id2 < 1 || id2 > 1024) {
cout << -1 << endl;
continue;
}
// 初始化任务状态数组
unsigned int tasks[32] = {0};
// 设置第一个任务为完成
checkTask(tasks, id1, true);
// 检查第二个任务的状态
cout << checkTask(tasks, id2, false) << endl;
}
}
};
int main() {
TaskChecker::solve();
return 0;
}
import java.util.Scanner;
public class Main {
static class TaskChecker {
// 检查或设置任务状态
private static int checkTask(int[] tasks, int taskId, boolean isSet) {
int index = (taskId - 1) / 32; // 数组索引
int bitPos = (taskId - 1) % 32; // 位位置
int mask = 1 << (31 - bitPos); // 位掩码
if(isSet) {
tasks[index] |= mask; // 设置状态
return 0;
} else {
return (tasks[index] & mask) != 0 ? 1 : 0; // 检查状态
}
}
public static void solve() {
Scanner sc = new Scanner(System.in);
while(sc.hasNext()) {
int id1 = sc.nextInt();
int id2 = sc.nextInt();
// 检查ID范围
if(id1 < 1 || id1 > 1024 || id2 < 1 || id2 > 1024) {
System.out.println(-1);
continue;
}
// 初始化任务状态数组
int[] tasks = new int[32];
// 设置第一个任务为完成
checkTask(tasks, id1, true);
// 检查第二个任务的状态
System.out.println(checkTask(tasks, id2, false));
}
}
}
public static void main(String[] args) {
TaskChecker.solve();
}
}
class TaskChecker:
@staticmethod
def check_task(tasks: list, task_id: int, is_set: bool) -> int:
index = (task_id - 1) // 32 # 数组索引
bit_pos = (task_id - 1) % 32 # 位位置
mask = 1 << (31 - bit_pos) # 位掩码
if is_set:
tasks[index] |= mask # 设置状态
return 0
else:
return 1 if (tasks[index] & mask) != 0 else 0 # 检查状态
@staticmethod
def solve():
while True:
try:
id1, id2 = map(int, input().split())
# 检查ID范围
if id1 < 1 or id1 > 1024 or id2 < 1 or id2 > 1024:
print(-1)
continue
# 初始化任务状态数组
tasks = [0] * 32
# 设置第一个任务为完成
TaskChecker.check_task(tasks, id1, True)
# 检查第二个任务的状态
print(TaskChecker.check_task(tasks, id2, False))
except EOFError:
break
if __name__ == "__main__":
TaskChecker.solve()
算法及复杂度
- 算法:位运算
- 时间复杂度:
- 每次操作都是常数时间
- 空间复杂度:
- 使用固定大小的数组