HDU 5203 Rikka with wood sticks 分类讨论

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdio>
 4 using namespace std;
 5 
 6 const int maxn=1000+10;
 7 const int INF=0x3f3f3f3f;
 8 typedef long long LL; 
 9 
10 int n,m;
11 
12 int main(){
13     while(scanf("%d%d",&n,&m)==2&&n){
14         //找出bad stick的左右界限 
15         int beg=INF,end=-1;
16         for(int i=0;i<m;i++){
17             int x;
18             scanf("%d",&x);
19             beg=min(beg,x);
20             end=max(end,x);
21         }
22         int l1=beg-1,l2=n-end;
23         if(l1>l2) swap(l1,l2);
24         LL ans=0;
25          
26         if(l1>0){
27             //截取的bad stick段在中间 
28             for(int i=1;i<l2;i++){
29                 int a=l1,b=i,c=l2-i;
30                 if(a+b>c&&a+c>b&&b+c>a) ans++;
31             }
32         }else{
33             //截取的bad stick段在两边 
34             for(LL x=(l2+2)/3;x<(l2+1)/2;x++){
35                 //枚举最长边为x的情况 
36                 LL tmp=3*x+1-l2,cnt=0;//tmp代表第一条边为x时的所有合法的情况（后两条边有考虑顺序，第一条边不考虑顺序） 
37                 if(l2-2*x>0){
38                     //最长边有可能存在两条的情况 
39                     if(l2-2*x==x){
40                         //三条边相等（x,x,x） 
41                         cnt=(tmp-1)*3+1;
42                     }else{
43                         if(((l2-x)&1)==0){
44                             //有两条边相等的情况（1、x,x,a(a<x)；2、x,a,a(a<x)) 
45                             cnt=(tmp-3)*3+3*1+3*1;
46                         }else{
47                             //（x,x,a） 
48                             cnt=(tmp-2)*3+3*1;
49                         }
50                     }
51                 }else{
52                     //最长边不可能存在两条的情况 
53                     if(((l2-x)&1)==0){
54                         //（ x,a,a） 
55                         cnt=(tmp-1)*3+3*1;
56                     }else{
57                         //（x,b,a(b!=a)）
58                         cnt=tmp*3;
59                     }
60                 }
61                 ans+=cnt;
62             }
63         }
64         printf("%lld\n",ans);
65     }
66     return 0;
67 }