2021 年百度之星·程序设计大赛 - 初赛三 1004. 环上游走(打表)
2021/8/7 17:35:56
本文主要是介绍2021 年百度之星·程序设计大赛 - 初赛三 1004. 环上游走(打表),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Problem Description
有一个环,环上有 nn 个位置,它们的编号为 1...n1...n。
位置 i(1<i<n)i(1<i<n) 左右两边分别是位置 i−1i−1 和位置 i+1i+1,位置 1 左右两边分别是位置 nn 和位置 2,位置 nn 左右两边分别是位置 n−1n−1 和位置 1。
现在,我们要玩一个游戏。初始我们在位置 1,游戏共 n−1n−1 轮,对于第 i(1≤i<n)i(1≤i<n) 轮,我们可以选择从当前位置往左或往右连续走 ii 个位置。
现在我们想知道,对于给定的 nn,有多少种方案,使得我们停留的 nn 个位置(初始的位置 1 和 n−1n−1 轮中每一轮结束时候的位置)没有重复。
赛时看到数据范围傻逼,直接打了个表交上去就过了...
正解待补
#include <bits/stdc++.h> using namespace std; int cnt = 0; bool v[88]; int n; void dfs(int x, int pos) { if(x == n) { cnt++; return; } int p1 = (pos + x) % n; if(!p1) p1 = n; if(!v[p1]) { v[p1] = 1; dfs(x + 1, p1); v[p1] = 0; } int p2 = (pos + n - x) % n; if(!p2) p2 = n; if(!v[p2]) { v[p2] = 1; dfs(x + 1, p2); v[p2] = 0; } } int main() { for(int i = 1; i <= 80; i++) { n = i; memset(v, 0, sizeof(v)); cnt = 0; v[1] = 1; dfs(1, 1); cout << cnt << ", "; } return 0; }
这篇关于2021 年百度之星·程序设计大赛 - 初赛三 1004. 环上游走(打表)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?