2 条题解
-
0
#include<iostream> #include<vector> #include<string> #include<algorithm> #include<unordered_set> #include<set> #include<unordered_map> #include<queue> using namespace std; bool islastrount(const set<int>& uset, const unordered_set<int>& toerase)//是否是最后一轮删除 { for (const auto& e : uset) { if (toerase.count(e) == 0) { return false; } } return true; } int main() { int N, E, T, P;//N:发动机总数,E:手动启动数(E行),T:手动启动时刻,P:启动发动机的编号 cin >> N >> E; set<int> uset; for (int i = 0; i < N; i++) { uset.insert(i);//在集合中插入所有发动机编号 } unordered_map<int, unordered_set<int>> setup;//<启动时间,该启动时间的发动机编号> for (int i = 0; i < E; i++) { cin >> T >> P; if (setup.find(T) == setup.end())//若该时间点不存在,则创建该时间点的启动编号集合 { setup.insert({ T,unordered_set<int>{P} }); } else//若该时间点存在,则在集合插入编号 { setup[T].insert(P); } } queue<int> toerase; int i; for (i = 0; !islastrount(uset,setup[i]); i++) { for (const auto& e : setup[i]) { toerase.push(e);//将i时间点要启动的发动机编号加入队列 } while (!toerase.empty())//当队列非空 { if (uset.count(toerase.front()) == 1)//如果要删除的队头在未发动的集合中 { uset.erase(toerase.front());//发动该机器 setup[i + 1].insert({ (toerase.front() + N - 1) % N , (toerase.front() + 1) % N }); //并将相邻机器加入i+1时刻的待发动集合中 toerase.pop();//队头删除 } else//若该机器已经发动,则直接删除 { toerase.pop(); } } } cout << uset.size()<<endl; for (const auto& e : uset) { cout << e << ' '; } }
-
0
看似简单,其实坑很多,花了很多时间。
#include <iostream> #include <vector> using namespace std; vector<vector<int>> height(1002); vector<int> hand(1002); //初始化-1,索引为时间,数值为id int N; int E; int mytime = 0; int num = 0; //输出 vector<int> ids; //输出 int test(vector<int> light, int N) { int flag = 1; for (int i = 0; i < N; i++) { if (light[i] == 0) { flag = 0; break; } } return flag; } void Plan() { vector<int> light(N); vector<int> light2(N); fill(light.begin(), light.end(), 0); fill(light2.begin(), light2.end(), 0); int flag = 0; for (mytime = 0; mytime <= N; mytime++) { //检索 if (test(light, N) == 1) { break; } else { num = 0; //清空 ids.clear(); } for (int i = 0; i < N; i++) //扩散 { if (light[i] == 1) { if (i == 0) { if (light[1] == 0 && light2[1] == 0) { light2[1] = 1; num++; ids.push_back(1); } if (light[N - 1] == 0 && light2[N - 1] == 0) { light2[N - 1] = 1; num++; ids.push_back(N - 1); } } else if (i < N - 1) { if (light[i - 1] == 0 && light2[i - 1] == 0) { light2[i - 1] = 1; num++; ids.push_back(i - 1); } if (light[i + 1] == 0 && light2[i + 1] == 0) { light2[i + 1] = 1; num++; ids.push_back(i + 1); } } else { if (light[0] == 0 && light2[0] == 0) { light2[0] = 1; num++; ids.push_back(0); } if (light[N - 2] == 0 && light2[N - 2] == 0) { light2[N - 2] = 1; num++; ids.push_back(N - 2); } } } } //light同步 for (int i = 0; i < N; i++) { if (light2[i] == 1) light[i] = 1; } //手动 if (height[mytime].size() != 0) { int tmpNum = height[mytime].size(); for (int i = 0; i < tmpNum; i++) { int tempInt = height[mytime][i]; if (light[tempInt] == 0) { light[tempInt] = 1; num++; ids.push_back(tempInt); } } } } } int main() { cin >> N; cin >> E; vector<int> temp; int tempInt; int tempInt2; fill(hand.begin(), hand.end(), -1); for (int i = 0; i < E; i++) { cin >> tempInt; cin >> tempInt2; hand[tempInt] = tempInt2; height[tempInt].push_back(tempInt2); //新结构体 } Plan(); cout << num << endl; for (int i = 0; i < num; i++) { cout << ids[i] << " "; } return 0; } /* 输入 8 2 0 2 0 6 输出 2 0 4 */
- 1
信息
- ID
- 105
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- (无)
- 递交数
- 471
- 已通过
- 101
- 上传者