首页 > 代码库 > Poj 1068

Poj 1068

开始做法错误。想直接计算,发现不太行,回归了朴素的做法,生成所要计算的串,然后在根据串计算结果。
有一点很坑,题目的范围很小,但是测试数据较大,提交的时候一直RE,将数组改大之后通过。
 1 // #includes {{{
 2     #include<stdio.h>
 3     #include<stdlib.h>
 4     #include<string.h>
 5     #include<math.h>
 6     #include<assert.h>
 7     #include<stdarg.h>
 8     #include<time.h>
 9     #include<limits.h>
10     #include<ctype.h>
11     #include<string>
12     #include<map>
13     #include<set>
14     #include<queue>
15     #include<algorithm>
16     #include<vector>
17     #include<iostream>
18     #include<sstream>
19     using namespace std;
20     // }}}
21     // #defines {{{
22     #define FOR(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
23     #define SZ(x) ((int)(x).size())
24     #define ALL(x) (x).begin(),(x).end()
25     #define REP(i,n) for(int i=0;i<(n);i++)
26     #define REP1(i,a,b) for(int i=(a);i<=(b);i++)
27     #define PER(i,n) for(int i=(n)-1;i>=0;i--)
28     #define PER1(i,a,b) for(int i=(a);i>=(b);i--)
29     #define RI(x) scanf("%d",&x)
30     #define DRI(x) int x;RI(x)
31     #define RII(x,y) scanf("%d%d",&x,&y)
32     #define DRII(x,y) int x,y;RII(x,y)
33     #define RIII(x,y,z) scanf("%d%d%d",&x,&y,&z)
34     #define DRIII(x,y,z) int x,y,z;RIII(x,y,z)
35     #define RS(x) scanf("%s",x)
36     #define PI(x) printf("%d\n",x)
37     #define PIS(x) printf("%d ",x)
38     #define CASET int ___T,cas=1;scanf("%d",&___T);while(___T--)
39     #define CASEN0(n) int cas=1;while(scanf("%d",&n)!=EOF&&n)
40     #define CASEN(n) int cas=1;while(scanf("%d",&n)!=EOF)
41     #define MP make_pair
42     #define PB push_back
43 
44     #define MS0(x) memset(x,0,sizeof(x))
45     #define MS1(x) memset(x,-1,sizeof(x))
46 
47     #define F first
48     #define S second
49     typedef pair<int,int> PII;
50     typedef long long LL;
51     typedef unsigned long long ULL;
52     // }}}
53 const int N=900;
54 int n;
55 int a[N],s[N];
56 main(){
57     CASET{
58         cin>>n;
59         int left=0,now=0;
60         int j=0;
61         REP(i,n) {cin>>a[i];
62             if (i==0){
63                 for(j=0;j<a[i];j++) s[j]=1;
64                 s[j]=2;
65             }else{
66             for (int t=0;t<a[i]-a[i-1];t++) 
67             {
68                 j++;
69                 s[j]=1;
70             }
71             j++;
72             s[j]=2;}
73         }
74         //cout<<j<<endl;
75         //REP(i,n*2) cout<<s[i]<<" ";
76         int p=0;
77         REP(i,n){
78             while ((s[p]==1)&&(p<n*2)) p++;
79             int m=1;
80             int q=p-1;
81             int ans=1;
82             while (m>0 && q>=0){
83                 if (s[q]==1) m--;
84                 if (s[q]==2) {ans++;m++;}
85                 q--;
86             }
87             cout<<ans<<" ";
88             p++;
89 
90         }
91         cout<<endl;
92     }
93 }

 

Poj 1068