Sephiroth's boring days!!!

数学问题-Black and White

【题目描述】

寻找一个由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

【输入输出示例】

【评分标准】

对于每个测试点，如果你能够在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: 

posted on 2010-09-01 07:00 Sephiroth Lee 阅读(132) 评论(0)  编辑 收藏 引用 所属分类: 信息奥赛