【題目描述】
尋找一個(gè)由n個(gè)整數(shù)組成的數(shù)列，其中任意連續(xù)p個(gè)整數(shù)之和為正，任意連續(xù)q個(gè)整數(shù)之和為負(fù)。若不存在這樣的整數(shù)數(shù)列，則輸出NO，否則輸出其中一個(gè)數(shù)列。
【輸入】
對(duì)于每個(gè)測(cè)試點(diǎn)將給你M組數(shù)據(jù)，要求你對(duì)于每組數(shù)據(jù)，判斷是否存在這樣的整數(shù)數(shù)列。
輸入的第一行是一個(gè)正整數(shù)M，（1<=N<=10000）,接下來(lái)的M行對(duì)應(yīng)M組數(shù)據(jù)，每行有三個(gè)正整數(shù)N、P、Q（1<=n,p,q<=10^8）。
【輸出】
輸出數(shù)據(jù)共N行，每行為yes或者no，如果第I組數(shù)據(jù)有解，則在第I行輸出yes，否則輸出no
【輸入輸出示例】
| 輸入(sequence.in) | 輸出(sequence.out) |
2
1 1 9
10 2 4 | yes
no |
【評(píng)分標(biāo)準(zhǔn)】
對(duì)于每個(gè)測(cè)試點(diǎn)，如果你能夠在1S內(nèi)通過(guò)每組數(shù)據(jù)，你將得到這個(gè)測(cè)試點(diǎn)的分?jǐn)?shù)，否則，這個(gè)測(cè)試點(diǎn)你只能得0分。
【分析】
原題目是要求輸出一種可能的解，如果沒(méi)有解就輸出-1。這樣的話(huà)就要用到差分約束。
現(xiàn)在的話(huà)，只需要一個(gè)公式。如果有解，應(yīng)滿(mǎn)足：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:
下面是我寫(xiě)的查分約束。
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: