解题思路

这是一个位运算问题。具体要求:

  1. 使用32个unsigned int记录1024个任务的状态
  2. 每个任务只能完成一次
  3. 需要实现:
    • 设置第一个任务ID为已完成
    • 检查第二个任务ID的完成状态
  4. 任务ID范围为[1,1024]

解决方案:

  1. 使用位图(bitmap)存储任务状态:
    • 每个unsigned int有32位,32个int可以存储1024个状态
    • 任务ID减1后,除以32得到数组索引
    • 对32取模得到具体的位位置
  2. 使用位运算进行状态的设置和检查

代码

#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()

算法及复杂度

  • 算法:位运算
  • 时间复杂度: - 每次操作都是常数时间
  • 空间复杂度: - 使用固定大小的数组