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