【题目描述】
寻找一个由n个整数组成的数列，其中任意连续p个整数之和为正，任意连续q个整数之和为负。若不存在这样的整数数列，则输出NO，否则输出其中一个数列。
【输入】
对于每个测试点将给你M组数据，要求你对于每组数据，判断是否存在这样的整数数列。
输入的第一行是一个正整数M，（1<=N<=10000）,接下来的M行对应M组数据，每行有三个正整数N、P、Q（1<=n,p,q<=10^8）。
【输出】
输出数据共N行，每行为yes或者no，如果第I组数据有解，则在第I行输出yes，否则输出no
【输入输出示例】
| 输入(sequence.in) | 输出(sequence.out) |
2
1 1 9
10 2 4 | yes
no |
【评分标准】
对于每个测试点，如果你能够在1S内通过每组数据，你将得到这个测试点的分数，否则，这个测试点你只能得0分。
【分析】
原题目是要求输出一种可能的解，如果没有解就输出-1。这样的话就要用到差分约束。
现在的话，只需要一个公式。如果有解，应满足：n<=q+p-gcd(p,q)-1。
1: #include <stdio.h>
2: #include <iostream>
3: using namespace std;
4:
5: int n,m,p,q;
6:
7: int gcd(int a,int b)
8: {
9: if (a<b) swap(a,b);
10: int t;
11: while (b!=0)
12: {
13: t=a;
14: a=b;
15: b=t%a;
16: }
17: return a;
18: }
19:
20: int main()
21: {
22: freopen("sequence.in","r",stdin);
23: freopen("sequence.out","w",stdout);
24:
25: scanf("%d",&m);
26: for (int i=0;i<m;++i)
27: {
28: scanf("%d%d%d",&n,&p,&q);
29: if (n<=p+q+gcd(p,q)-1) printf("YES\n");
30: else printf("NO\n");
31: }
32: return 0;
33: }
34:
下面是我写的查分约束。
1: #include <stdio.h>
2: #define MAXINT 1000000
3: #define maxn 1010
4:
5: struct ss
6: {
7: int x,y,dis;
8: } l[10000];
9:
10: int s[maxn];
11: int a[maxn];
12: int d[maxn];
13: int n,q,p,tot;
14:
15: int main()
16: {
17: scanf("%d%d%d",&n,&p,&q);
18: for (int i=0;i<=n;++i)
19: if (i+p>n) break;
20: else
21: {
22: l[++tot].x=i+p;
23: l[tot].y=i;
24: l[tot].dis=-1;
25: }
26: for (int i=0;i<=n;++i)
27: if (i+q>n) break;
28: else
29: {
30: l[++tot].x=i;
31: l[tot].y=i+q;
32: l[tot].dis=-1;
33: }
34: for (int i=1;i<=n;++i)
35: {
36: for (int j=1;j<=tot;++j)
37: if (d[l[j].y]>d[l[j].x]+l[j].dis)
38: d[l[j].y]=d[l[j].x]+l[j].dis;
39: for (int j=1;j<=tot;++j)
40: if (d[l[j].y]>d[l[j].x]+l[j].dis)
41: {
42: printf("-1\n");
43: return 0;
44: }
45: }
46: for (int i=0;i<=n;++i)
47: s[i]=d[i];
48: for (int i=1;i<=n;++i) printf("%d\n",s[i]-s[i-1]);
49: return 0;
50: }
51: