首页 > 代码库 > uva 269 - Counting Patterns(构造)
uva 269 - Counting Patterns(构造)
题目链接:uva 269 - Counting Patterns
题目大意:给出n和k,要求找出满足的序列,要求为n元组,由-k到k组成,并且和为0。求出所有满足的元组个数,并且对于左移,右移,水平翻转,每个元素取相反数相同的视为一种,用字典序最大的表示,输出按照字典序最小的输出。
解题思路:因为表示的时候按照字典序最大的表示,一开始枚举开头的位置,那么在后面的数的绝对值就不会大于该数。最后判断一下,如果该序列不是最优的表示方法,就不是该情况。
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 100005;
const int maxm = 15;
int s[maxn][maxm];
int n, k, key, cnt, a[maxm];
void put (int num[]) {
printf("(%d", num[0]);
for (int i = 1; i < n; i++)
printf(",%d", num[i]);
printf(")\n");
}
bool cmp (int l[], int r[]) {
for (int i = 0; i < n; i++)
if (l[i] != r[i])
return l[i] > r[i];
return false;
}
void check () {
int b[maxm*2];
for (int i = 0; i < n; i++)
b[i] = b[i+n] = a[i];
for (int i = 0; i < n; i++)
if (b[i] == a[0] && cmp(b+i, a))
return;
for (int i = 0; i < 2 * n; i++)
b[i] = -b[i];
for (int i = 0; i < n; i++)
if (b[i] == a[0] && cmp(b+i, a))
return;
for (int i = 0; i < n; i++)
swap(b[i], b[2*n-i-1]);
for (int i = 0; i < n; i++)
if (b[i] == a[0] && cmp(b+i, a))
return;
for (int i = 0; i < 2 * n; i++)
b[i] = -b[i];
for (int i = 0; i < n; i++)
if (b[i] == a[0] && cmp(b+i, a))
return;
memcpy(s[cnt++], a, sizeof(a));
}
void dfs (int d, int sum) {
if (d == n) {
if (sum == 0)
check();
return;
}
if (abs(sum) > ((n - d) * a[0]))
return;
for (a[d] = -key; a[d] < key; a[d]++) {
if (a[d-1] == key && a[d] > a[1])
return;
dfs(d + 1, sum + a[d]);
}
if (a[d] == key && a[d-1] <= a[1])
dfs(d+1, sum+a[d]);
}
int main () {
int cas = 0;
while (scanf("%d%d", &n, &k) == 2 && n) {
cnt = 1;
for (a[0] = 1; a[0] <= k; a[0]++) {
key = a[0];
dfs(1, key);
}
if (cas++)
printf("\n");
printf("%d\n", cnt);
for (int i = 0; i < cnt; i++)
put(s[i]);
}
return 0;
}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。