题意:n个人围成一圈,另外一个人最开始站在第一个人前面,每次从集合s里面随机选一个数x,这个人顺时针经过x个人后停下来,当前位置的前一个人出队,然后继续进行,求最后剩下的那个人的可能编号。

思路:由于只求最后一个人的编号,可以将一次操作后的人进行重编号,来进行状态转移,转化为子问题用dp来解决。dp方程比较容易写出,注意下细节就好了。

 #pragma comment(linker, "/STACK:102400000,102400000")

 #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <map>
#include <queue>
#include <deque>
#include <cmath>
#include <vector>
#include <ctime>
#include <cctype>
#include <set>
#include <bitset>
#include <functional>
#include <numeric>
#include <stdexcept>
#include <utility> using namespace std; #define mem0(a) memset(a, 0, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define define_m int m = (l + r) >> 1
#define rep_up0(a, b) for (int a = 0; a < (b); a++)
#define rep_up1(a, b) for (int a = 1; a <= (b); a++)
#define rep_down0(a, b) for (int a = b - 1; a >= 0; a--)
#define rep_down1(a, b) for (int a = b; a > 0; a--)
#define all(a) (a).begin(), (a).end()
#define lowbit(x) ((x) & (-(x)))
#define constructInt4(name, a, b, c, d) name(int a = 0, int b = 0, int c = 0, int d = 0): a(a), b(b), c(c), d(d) {}
#define constructInt3(name, a, b, c) name(int a = 0, int b = 0, int c = 0): a(a), b(b), c(c) {}
#define constructInt2(name, a, b) name(int a = 0, int b = 0): a(a), b(b) {}
#define pchr(a) putchar(a)
#define pstr(a) printf("%s", a)
#define sstr(a) scanf("%s", a)
#define sint(a) scanf("%d", &a)
#define sint2(a, b) scanf("%d%d", &a, &b)
#define sint3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define pint(a) printf("%d\n", a)
#define test_print1(a) cout << "var1 = " << a << endl
#define test_print2(a, b) cout << "var1 = " << a << ", var2 = " << b << endl
#define test_print3(a, b, c) cout << "var1 = " << a << ", var2 = " << b << ", var3 = " << c << endl typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> vi; const int dx[] = {, , -, , , , -, -};
const int dy[] = {-, , , , , -, , - };
const int maxn = 2e2 + ;
const int md = ;
const int inf = 1e9 + ;
const LL inf_L = 1e18 + ;
const double pi = acos(-1.0);
const double eps = 1e-; template<class T>T gcd(T a, T b){return b==?a:gcd(b,a%b);}
template<class T>bool max_update(T &a,const T &b){if(b>a){a = b; return true;}return false;}
template<class T>bool min_update(T &a,const T &b){if(b<a){a = b; return true;}return false;}
template<class T>T condition(bool f, T a, T b){return f?a:b;}
template<class T>void copy_arr(T a[], T b[], int n){rep_up0(i,n)a[i]=b[i];}
int make_id(int x, int y, int n) { return x * n + y; } int p[maxn], f[maxn][maxn], ans[maxn];
int main() {
//freopen("in.txt", "r", stdin);
int T, n, m;
cin >> T;
while (T--) {
cin >> n >> m;
rep_up0(i, m) {
sint(p[i]);
}
mem0(f);
f[n][] = true;
for (int i = n - ; i; i --) {
for (int j = ; j < n - i + ; j ++) {
rep_up0(k, m) {
if ((p[k] + n - i) % (n - i + ) == j) continue;
int sta, tmp = p[k] % (n - i + );
if (j >= tmp) sta = j - tmp;
else sta = n - i + - tmp + j;
f[i][j] = f[i][j] || f[i + ][sta];
}
}
}
int cnt = ;
rep_up0(i, n) {
if (f[][i]) ans[cnt ++] = i + ;
}
cout << cnt << endl;
rep_up0(i, cnt) {
printf("%d%c", ans[i], i == cnt - ? '\n' : ' ');
}
}
return ;
}

最新文章

  1. GRU(Gated Recurrent Unit) 更新过程推导及简单代码实现
  2. RabbitMQ headers Exchange
  3. java基础 集合 ArrayList 增删改除
  4. android 文字图片合成
  5. 手机端js模拟长按事件(代码仿照jQuery)
  6. beta阶段事后诸葛亮会议
  7. ajax 无刷新文件上传
  8. [转]undefined reference问题总结
  9. PAT1028—— 人口普查
  10. 道路软件质量:SourceMonitor
  11. 安装MySQL -- SuSE Linux Enterprise Server 11 SP3
  12. 非常不错的MySQL优化的8条经验
  13. Android开发之获取xml文件的输入流对象
  14. CI框架浅析(二)
  15. python利用scrapy框架爬取起点
  16. android自定义xmls文件属性
  17. Java多线程_复习(更新中!!)
  18. 三目算法、if/else,switch/case运用
  19. BOM 浏览器对象模型_渲染引擎_JavaScript 引擎_网页加载流程
  20. PHP 如何获取客户端ip地址

热门文章

  1. 跑Linux内存占用率的shell脚本
  2. BUUOJ [极客大挑战 2019]Secret File
  3. [一道蓝鲸安全打卡Web分析] 文件上传引发的二次注入
  4. Java 排序算法-冒泡排序及其优化
  5. 米特运输——(dfs)
  6. (转)对 Linux 新手非常有用的 20 个命令
  7. 【Linux常见命令】sort命令
  8. element UI排坑记(一):判断tabs组件是否切换
  9. usermod,用户密码管理,mkpasswd命令
  10. CentOS7.x上轻量级TCP转发工具rinetd的安装配置