【題目描述】
尋找一個由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: