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

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

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

基本都是废话。。

大致意思就是

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

找出没有重叠的地方。。(看了半天英文就给我做这个??)

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

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

15ms

 #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,ll,rr,l,r,ans;
bool a[];
int main() {
cin>>n;
cin>>l>>r;
for (int i=l; i<r; i++) a[i]=true;
for (int i=; i<n; i++)
{
cin>>ll>>rr;
for (int j=ll; j<rr; j++) a[j]=false;
}
for (int i=l; i<r; i++) if (a[i]) ans++;
cout<<ans;
return ;
}

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

Acm hust 1.25-LMLPHP

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

 #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long t,n,l,r;
int main(){
cin >> t ;
for ( int o = ; o < t ; o ++ )
{
cin >> n >> l >> r ;
long long k=n/l*r;
if ( k>=n) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
return ;
}

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

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

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

(找公因数的方法。。。呃。。)31ms

 #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,l=;
int a[];
int main(){
cin>>n;
for (int i=; i<=n; i++)
{
cin>>a[i];
if (a[i]<l) l=a[i];
}
for (int i=l; i>=; i--)
{
bool y=true;
for (int j=; j<=n; j++)
if (a[j]% i != )
{
y=false; break;
}
if (y) { cout<<n*i; break;}
}
return ;
}

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

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

又是一题英语阅读理解。

30ms

 #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n;
char c;
bool a[][];
int main(){
cin>>n;
for (int i=; i<=n; i++)
for (int j=; j<=n; j++)
{
cin>>c;
if (c=='#') a[i][j]=true;
} for (int i=; i<=n; i++)
for (int j=; j<=n; j++)
if (a[i][j])
{
if (j== || !a[i+][j-] || !a[i+][j] || !a[i+][j+] || !a[i+][j] )
{
cout<<"NO"<<endl;
return ;
}
a[i+][j-]=false;
a[i+][j]=false;
a[i+][j+]=false;
a[i+][j]=false;
}
cout<<"YES"<<endl;
return ;
}

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

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

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

方块有个长度 length ,这个方块上面最多放[length](!!!)个方块 并且只能放置长度不超过length的方块

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

15ms

 #include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,ans,t;
bool ok;
int a[];
int main(){
cin>>n;
for (int i=; i<n; i++) cin>>a[i];
sort(a,a+n);
while (t<n)
{
int s=;
for (int i=; i<n; i++)
if (a[i]>=s)s++,a[i]=-;
ans++;
t+=s;
}
cout<<ans<<endl;
return ;
}

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

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

受到了来自犇犇的嘲讽

Acm hust 1.25-LMLPHP

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

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

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

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

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

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

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

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

 #include<acstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int n,ansl,ansr,t;
bool ok;
int a[];
bool cmp(const int x,const int y)
{
return x>y;
}
int main(){
cin>>n;
for (int i=; i<=n; i++)
{
int x,y;
cin>>x;
for (int j=; j<=x/; j++)
{
cin>>y;
ansl+=y;
}
if (x%==) cin>>a[++t];
for (int j=; j<=x/; j++)
{
cin>>y;
ansr+=y;
}
}
sort(a+,a++t,cmp);
for (int i=; i<=t; i++)
if (i%==) ansl+=a[i];
else ansr+=a[i];
cout<<ansl<<" "<<ansr<<endl;
return ;
}

然后做完就没有时间叻。。。!!我做得真太慢了。。。二级英语才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)  ..

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

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

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

 #include <cstdio>
#define LL long long
//------------------------------------------------------------
int tcase;
int icase; LL n,d;
LL ls,rs;
LL fm,fz;
//------------------------------------------------------------
int su(LL d)
{
//--0 init
LL i;
//--1
for (i=; i*i<=d&&d%i!=; i++);
return i*i>d;
}
//------------------------------------------------------------
int main( )
{
for (scanf("%d",&tcase); ++icase<=tcase; )
{
scanf("%I64d",&n);
ls=n ; for (; !su(ls); ls--);
rs=n+; for (; !su(rs); rs++);
d=ls+rs-n;
d=d-1LL;
d=d*2LL;
fz=ls*rs;
fz=fz-d;
fm=ls*rs;
fm=fm*2LL;
if (fz% ==) { fz/=2LL; fm/=2LL; }
if (fz%ls==) { fz/=ls; fm/=ls; }
if (fz%rs==) { fz/=rs; fm/=rs; }
printf("%I64d/%I64d\n",fz,fm);
}
}
 int  su(LL d)
{
//--0 init
LL i;
//--1
for (i=; i*i<=d&&d%i!=; i++);
return i*i>d;
}

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

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

大概就是

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

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

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

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

蒟蒻远处%泡犇犇

05-28 10:02