@morehigh
2016-12-12T23:08:59.000000Z
字数 6372
阅读 1010
1.第一次作业 CQUPT Training Nov28th - Dec3rd 题解
题解:
A Design Tutorial: Learn from Math
题目大意:
给定一个n(12<=n<=10^6),求出符合以下要求的x和y:
1.x+y=n
2.x和y都是合数
解题思路:
用筛法的思想找出所有的合数并标记,然后判断x与y是不是合数,是的话就输出。
ac代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=1000010;
bool notprime[MAXN];
void getprim()
{
memset(notprime,false,sizeof(notprime));
notprime[0]=notprime[1]=0;
for(int i=2;i<MAXN;i++)
{
if(!notprime[i])
{
if(i>MAXN/i)
continue;
for(int j=i*i;j<MAXN;j+=i)
notprime[j]=true;
}
}
}
int main()
{
int n;
getprim();
while(scanf("%d",&n)!=EOF)
{
int m=4;
while(m<=(n/2))
{
if(notprime[m]&¬prime[n-m])
{
cout<<m<<" "<<n-m<<endl;
break;
}
m++;
}
}
return 0;
}
**Design Tutorial: Learn from Life **
题意:
有一个电梯,每一个人都想乘电梯到达自己想要到达的楼层!
从a层到b层的时间是|a-b|, 乘客上下电梯的时间忽略不计!问最少
需要多少的时间..
解题思路:
把输入的数组从大到小排序,楼层高的人上去之后自然楼层低的人能送到,然后计算时间输出就可以了。
ac代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int f[2010];
bool cmp(int x,int y)
{
return x>y;
}
int main()
{
int n,k;
while(scanf("%d%d",&n,&k)!=EOF)
{
for(int i=1;i<=n;i++)
scanf("%d",&f[i]);
sort(f+1,f+n+1,cmp);
int ans=0;
for(int i=1;i<=n;i++)
{
if(i%k==1||k==1)
ans+=(f[i]-1)*2;
}
cout<<ans<<endl;
}
return 0;
}
**Design Tutorial: Make It Nondeterministic **
题意:
每个人可以选择first name 或者 last name 当自己的账号,现在给出最终的字典序排位,问能不能实现
解题思路:
将first name 与last name 进行比较,如果字典序first name 大与last name的话就交换两个字符串,first name存小的字典序,按照给出的顺序进行比较,如果如果前面的人
first name 大于后面人的last name ,则为NO。
ac代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 101234
using namespace std;
string fir[100860],las[100860];
string tmp;
int main()
{
int n,m;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>fir[i]>>las[i];
}
tmp=" ";
bool flag=true;
for(int i=1;i<=n;i++)
{
cin>>m;
if(fir[m]>las[m])
{
swap(fir[m],las[m]);
/// flag=true;
}
if(tmp<=fir[m])
{
tmp=fir[m];
}else if(tmp<=las[m])
{
tmp=las[m];
}else
{
flag=false;
break;
}
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 0;
}
**MUH and Sticks **
题目大意:
给出6种长度的木棍,问能根据长度拼成哪种动物的形状。其中由脚、头和身体构成。脚为4个一样的长度,如果头和身体长度一样为大象,不一样为熊。否则为异形。
解题思路:
将不同长度的木棍进行计数,然后判断满足存在长度是四根或者四根以上,并且存在两根不相同,就是熊。存在长度大于等于四根,存在两根相同的话,就是大象,否则异形。
ac代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int len[20],num[20];
int main()
{
int l;
memset(num,0,sizeof(num));
for(int i=0;i<6;i++)
{
scanf("%d",&len[i]);
l=len[i];
num[l]++;
}
int numh=0,numb=0,numl=0,ss=1;
for(int i=1;i<=9;i++)
{
if(num[i]==1)
numb++;
if(num[i]==2)
numh++;
if(num[i]>=4)
{
numl=4;
ss=num[i]-4;
}
}
if((numb==2&&numl==4)||(numb==1&&ss==1&&numh==0))
cout<<"Bear"<<endl;
else if((numh==1&&numl==4)||(ss==2&&numb==0&&numh==0))
cout<<"Elephant"<<endl;
else
cout<<"Alien"<<endl;
return 0;
}
```
**MUH and Important Things **
题目大意:
有 n 个 tasks,编号依次为 1 ~ n,每个 task 都有一定的难度值来评估。例如,第 i 个 task 的难度值为 hi。现在的任务是把 n 个 task 全部完成,难度值越小的task越先完成。有3个人,都希望自己完成所有task的输出序列是与众不同的,问是否存在至少3条完成所有task的不同序列,没有的话输出“NO”,否则输出“YES”并输出3条不同的完成序列。
解题思路:
排序后,判断是否有重复的地方,然后就是依次交换
```c++
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int num[2015];
struct Node
{
int h,w;
}h[2015];
bool cmp(Node x,Node y)
{
return x.h<y.h;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
memset(num,0,sizeof(num));
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i].h);
h[i].w=i;
int nn=h[i].h;
num[nn]++;
}
int ans=1;
for(int i=1;i<=n;i++)
{
int nn=h[i].h;
//cout<<num[nn]<<endl;
ans=ans*num[nn];
if(ans>=3)
break;
num[nn]=1;
}
if(ans>=3)
printf("YES\n");
else
printf("NO\n");
sort(h+1,h+n+1,cmp);
if(ans>=3){
for(int i=1;i<=n;i++)
cout<<h[i].w<<" ";
cout<<endl;
int pp=1;
for(int i=1;i<=n;i++)
{
if(h[i].h==h[i+1].h)
{
pp=i+1;
int temp;
temp=h[i].w;
h[i].w=h[i+1].w;
h[i+1].w=temp;
break;
}
}
for(int i=1;i<=n;i++)
cout<<h[i].w<<" ";
cout<<endl;
for(int i=pp;i<=n;i++)
{
if(h[i].h==h[i+1].h)
{
pp=i+1;
int temp;
temp=h[i].w;
h[i].w=h[i+1].w;
h[i+1].w=temp;
break;
}
}
for(int i=1;i<=n;i++)
cout<<h[i].w<<" ";
cout<<endl;
}
}
return 0;
}
**MUH and House of Cards **
题目大意:
求n根火柴搭建房屋的层数有多少种
解题思路:
要使n层火柴全部搭满,推出公式是(3*n+1)*n/2,每次判断一层是否满足条件,剩下的木棒数取余3是否为0,满足条件方案数就加一。
ac代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
long long n;
long long num=0;
cin>>n;
for(long long i=1;(3*i+1)*i/2<=n;i++)
{
if((n-(3*i+1)*i/2)%3==0)
num++;
}
cout<<num<<endl;
return 0;
}
George and Accommodation
题意:
大致意思为求出能同时入住George和Alex的房间有多少间。
解题思路:
直接判断是否还能容下2个人
ac代码:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define N 101234
using namespace std;
int main()
{
int a,b,n;
while(scanf("%d",&n)!=EOF)
{
int ans=0;
for(int i=0;i<n;i++){
cin>>a>>b;
if(b-a>=2)
ans++;
}
cout<<ans<<endl;
}
return 0;
}
**Fedor and New Game **
题意:
给定n,m,k,n种士兵,m个部队,兵种不同数量小于等于k的为友军。然后给出m+1行,前m行表示需要判定的部队,第m+1行Fedor的部队。
解题思路:
直接取异或,找出不同种类的士兵数目,判断是否小于等于k。
ac代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int a[1025];
int main()
{
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=m;i++)
scanf("%d",&a[i]);
int ss,num,fri=0;
for(int j=0;j<m;j++)
{
ss=a[m]^a[j];
num=0;
int mn=1;
for(int i=1;i<=n;i++)
{
if(mn&ss)
num++;
mn*=2;
if(num>k)
{
break;
}
}
if(num<=k)fri++;
}
cout<<fri<<endl;
return 0;
}
**Cheap Travel **
题意:
坐n次地铁,m张票卖b元,单张a元,问最小花费。
解题思路:
开始用贪心算法,比较m张便宜还是单张买便宜,如果买m张便宜的话,又要考虑是否m张和单张的一起买会跟便宜。
ac代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
int n,m,a,b;
cin>>n>>m>>a>>b;
double ave=(b*1.0)/m;
double c=a*1.0;
int x,y;
if(ave<c)
{
x=n/m;
y=n%m;
if(y*a<b)
cout<<x*b+y*a<<endl;
else
cout<<x*b+b;
}else
{
cout<<n*a<<endl;
}
return 0;
}
**Wonder Room **
题意:
a*b大小的房间要容纳n个人,每个人至少需要大小为6的空间,改变房间大小,使n个同学都能住进房间,改变后的房间尽可能小
解题思路:
先求出n个人所需空间的大小,然后枚举房间的长和宽,是得长>a,宽>b,找出最小的长和宽。
ac代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 1e18+1e9
using namespace std;
int main()
{
long long n,a,b;
cin>>n>>a>>b;
long long sun=6*n,ans=N;
long long s;
int flag=0;
if(a>b)
{
s=a;
a=b;
b=s;
flag=1;
}
long long aa,bb;
for(long long i=1;i<=sun;i++)
{
long long x=i,y=(sun-1)/i+1;
if(x>y)break;
x=max(x,a);
y=max(y,b);
// cout<<x<<" "<<y<<endl;
if(x*y<=ans)
{
ans=x*y;
aa=x;
bb=y;
}
}
if(flag)
{
s=aa;
aa=bb;
bb=s;
}
cout<<ans<<endl;
cout<<aa<<" "<<bb<<endl;
return 0;
}
**Number of Ways **
题意:
将一列数分成连续的三份,每一份进行求和,使三份求得的和相等,问有把一组数分成三份有多少种方式。
解题思路:
将这一组数进行求和,除以3,定义一个sum数组保存前i项的和,然后对这组数进行遍历。第一个分割点是总和/3,第二个分割点是(2/3*总和),求出分割点的个数进行组合。
ac代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 500010
using namespace std;
long long sum[N];
int main()
{
int n;
int a;
while(scanf("%d",&n)!=EOF)
{
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
sum[i]=sum[i-1]+a;
}
long long summ=sum[n];
long long ans1=0,ans2=0;
if(summ%3)
cout<<"0"<<endl;
else
{
summ=summ/3;
for(int i=1;i<n;i++)
{
if(summ*2==sum[i])
ans2+=ans1;
if(summ==sum[i])
ans1++;
}
cout<<ans2<<endl;
}
}
return 0;
}