闲着无聊做了点hust上 acm的训练题

 

 

A题 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=104738#problem/A

看了20分钟英文才看懂他在瞎比比个啥

基本都是废话。。

大致意思就是

第二行是我们的主人公挂衣服的地方。。 3-n+1行 为 其他人挂衣服的地方。。

找出没有重叠的地方。。（看了半天英文就给我做这个？？）

数据蒟蒻只有100，也就是只要看懂题就能做的模拟题。。

ps:把数据改大才有点意思嘛

15ms

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int n,ll,rr,l,r,ans; 6 bool a[105]; 7 int main() { 8     cin>>n; 9     cin>>l>>r;10     for (int i=l; i
        
         >ll>>rr;14         for (int j=ll; j
        
       
      
     

 

B题 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=104738#problem/B

同样看了20分钟的英文。。然后悲剧的我看错题目了。。

以为  n由 l 和 r 两个数凑出来。。最后发现是l－r之间的数。。

还是怎么做都WA，找不出

最后发现long long 问题。。坑死爹的long long  浪费了好长好长的时间

15ms

 

祭奠我死去的两个小时。。。

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 long long t,n,l,r; 6 int main(){ 7     cin >> t ; 8     for ( int o = 0 ; o < t ; o ++ ) 9     {10         cin >> n >> l >> r ;11         long long k=n/l*r;12         if ( k>=n) cout<<"Yes"<
       
      
     

 

C和D题。。看A的人很少就跳过了。。

先做的E http://acm.hust.edu.cn/vjudge/contest/view.action?cid=104738#problem/E

比较短。。比较好理解。。让我们找出n个数的最大公因数x。。然后输出 n＊x 就可以了 

（找公因数的方法。。。呃。。）31ms

 

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int n,l=500; 6 int a[120]; 7 int main(){ 8     cin>>n; 9     for (int i=1; i<=n; i++)10     {11         cin>>a[i];12         if (a[i]
        
         =1; i--)15     {16         bool y=true;17         for (int j=1; j<=n; j++)18             if (a[j]% i !=0 )19             {20                 y=false; break;21             }22         if (y) { cout<
        
       
      
     

 

F题 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=104738#problem/F

装十字架而已。。找到最上面的＃ 然后模拟判断 整个十字区域是否为＃就可以了。。

又是一题英语阅读理解。

30ms

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int n; 6 char c; 7 bool a[120][120]; 8 int main(){ 9     cin>>n;10     for (int i=1; i<=n; i++)11         for (int j=1; j<=n; j++)12         {13             cin>>c;14             if (c=='#') a[i][j]=true;15         }16     17     for (int i=1; i<=n; i++)18         for (int j=1; j<=n; j++)19         if (a[i][j])20         {21             if (j==1 || !a[i+1][j-1] || !a[i+1][j] || !a[i+1][j+1] || !a[i+2][j] )22             {23                 cout<<"NO"<
       
      
     

 

G题  http://acm.hust.edu.cn/vjudge/contest/view.action?cid=104738#problem/G

这题阅读理解的难度有点高，表示没搞清楚意思就这么WA了。。

意思就是 方块上叠方块。。

方块有个长度 length ，这个方块上面最多放［length］（！！！）个方块 并且只能放置长度不超过length的方块

看懂就很好做了。。。考英语的。。

15ms

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int n,ans,t; 6 bool ok; 7 int a[105]; 8 int main(){ 9     cin>>n;10     for (int i=0; i
        
         >a[i];11     sort(a,a+n);12     while (t
         
          =s)s++,a[i]=-1;17         ans++;18         t+=s;19     }20     cout<
          
           <
          
         
        
       
      
     

 

I题 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=104738#problem/I

这题是我最后时刻做完的。。。。英文题就是神秘get看不懂题目的buff

受到了来自犇犇的嘲讽

做法为贪心。。把 n 组里面的

每组牌 分左边一半和 右边一半 分给不同的两个人

如果这组牌为奇数张，中间多余的一张留下来。

按从大到小顺序给左边给右边给左边给右边…………

（为什么这么贪心呢） 因为题目要求每个人都要尽力而为。。

那么任何一个人都不可能让对手拿到靠近自己这边的牌（如果拿对手那边为最优，那么敌人也会选择最优去阻止自己这边的牌被顺走）。。

所以左边一半和右边一半一开始就可以分给彼此。。

中间剩余的那一张呢。。他们都会尽力拿最大的。。

 

 

1 #include
     
       2 #include
      
        3 #include
       
         4 using namespace std; 5 int n,ansl,ansr,t; 6 bool ok; 7 int a[105]; 8 bool cmp(const int x,const int y) 9 {10     return x>y;11 }12 int main(){13     cin>>n;14     for (int i=1; i<=n; i++)15     {16         int x,y;17         cin>>x;18         for (int j=1; j<=x/2; j++)19         {20             cin>>y;21             ansl+=y;22         }23         if (x%2==1) cin>>a[++t];24         for (int j=1; j<=x/2; j++)25         {26             cin>>y;27             ansr+=y;28         }29     }30     sort(a+1,a+1+t,cmp);31     for (int i=1; i<=t; i++)32         if (i%2==1) ansl+=a[i];33         else ansr+=a[i];34     cout<
        
         <<" "<
         
          <
         
        
       
      
     

 

 

然后做完就没有时间叻。。。！！我做得真太慢了。。。二级英语才60+跪烂

 

闲着研究了一下D题 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=104738#problem/D

寻找质素数。。令q(i)为不超过 i 的最大质素数，p(i) 为超过 i 的 最小质素数。

然后令 i=2-n 累加 1/q(i)p(i)...

这题可以发现一个规律。。就是 1/q(i)p(i)＝( 1/q(i) - 1/p(i) )/ ( p(i)-q(i) );

如果 n+1 为质素数。则 答案就是 1/2 - 1/(n+1)  ..

得到了这个规律就可以做了。。。

然后就是判断质素数的方法。。

呃。。因为我懒得写就没有写了——偷偷调用一下泡犇犇的代码

1 #include 
     
       2 #define LL  long long 3 //------------------------------------------------------------ 4 int  tcase; 5 int  icase; 6  7 LL   n,d; 8 LL   ls,rs; 9 LL   fm,fz;10 //------------------------------------------------------------11 int  su(LL d)12 {13     //--0 init14     LL i; 15     //--116     for (i=2; i*i<=d&&d%i!=0; i++);17     return i*i>d;18 }19 //------------------------------------------------------------20 int  main( )21 {22     for (scanf("%d",&tcase); ++icase<=tcase; )23     {24         scanf("%I64d",&n); 25         ls=n  ; for (; !su(ls); ls--);26         rs=n+1; for (; !su(rs); rs++);27         d=ls+rs-n;28         d=d-1LL;29         d=d*2LL;30         fz=ls*rs;31         fz=fz-d;32         fm=ls*rs;33         fm=fm*2LL;34         if (fz%2 ==0) { fz/=2LL; fm/=2LL; }35         if (fz%ls==0) { fz/=ls; fm/=ls;    }36         if (fz%rs==0) { fz/=rs; fm/=rs;    }37          printf("%I64d/%I64d\n",fz,fm);38     }39 }
     

 

11 int  su(LL d)12 {13     //--0 init14     LL i; 15     //--116     for (i=2; i*i<=d&&d%i!=0; i++);17     return i*i>d;18 }

然后看到这段。。！！卧槽暴力搜不是浪费一大把的时间嘛。。这么可以这么搞。。（跑了702ms）

于是我给稍微改了改去交了一下  然后变成93ms了。。快了好几倍。。

大概就是

int  su(LL d){    //--0 init    LL i;    //--1    for (i=0; a[i]*a[i]<=d && d%a[i]!=0; i++);    return a[i]*a[i]>d;}

 

a[]数组为质素数数组 从 2开始。。 2 3 5 7 11……………………

由于最大的质素数是大于10^9 的。。所以我们只需要 找到 31622 以内附近的质素数就可以了。。到40000也只有4203个质素数。。

可以先筛出那么多个素数后存储下来备用。。节省非常长的时间

 

 

蒟蒻远处％泡犇犇