绍兴文理学院元培学院第十五届大学生程序设计竞赛
- A 阳光明媚的数学题
- B 爱的素数
- C 庄生的笔
- D 上流的聚餐
- E 规划(一)
- F 规划(二)
- G 运动的球球
- H 物资转移
- I 小杨环
- J 前四位
题目很好,可惜不会,最后马马虎虎的过了 4 个签到题
A 阳光明媚的数学题
构造一个无重复只含有正偶数的数列
使得这个数列所有值之和不超过 n
求这个数列长度的最大值
输入格式:
输入一个正整数 n ( 范围 [0,1e9] )
输出格式:
输出一个整数,表示这个数列长度的最大值
输入样例:
样例一
10
样例二
12
输出样例:
2
3
题目解释
签到题,简单的数学题
不断进行正偶数的累加即可
因为题目要求是无重复,所以从 2 开始,每次加 2 ,累加的到的答案就是最优解
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
using namespace std;
typedef long long ll;
const int N=100010;
int main()
{
int n;
cin >> n;
int ans = 0;
int res = 2;
int count = 0;
while(1)
{
if(ans >= n || n < res) break;
res += 2;
ans += res;
count ++ ;
}
cout << count << endl;
return 0;
}
B 爱的素数
给你一个范围,如果素数占百分之50及以上,则这个范围为爱的素数
输入格式:
输入两个正整数L,R(2<=L<R<=1e9)(多组输入)
输出格式:
如果是爱的素数输出yes ,反之输出no
输入样例:
2 3
输出样例:
yes
样例解释
2到3的素数占比百分之百,所以输出yes
题目解释
暴力解法:对于给定的区间,直接进行遍历,判断区间内的素数个数是否大于等于 50%
但是题目给定的范围是 2 – 1e9,直接进行遍历判断,一定会时间超限
暴力打表的结果:
从上面的打表样例我们可以看出,从 2 开始仅到 13 就停止了,从 3 开始仅到 8 就停止了,依次类推我们可以发现直到左端点是 17 右端点是 20 的时候停止,这是第一条规律
当左端点和右端点紧邻的时候,也就是相差 1 的时候,这两个端点中要是有一个是素数,那么就一定符合题意
天真的我本来以为仅有上面两条规律,按照这两条规律进行一个特判就可以过掉,结果愣是交 20 多次都没过,整的我自己都怀疑自己了
最后一条规律,如上图:70 和 71 差 1,70 和 73 差 1,71 和 72 差 1,71 和 73 差 2,71 和 74 差 3,也就是说,当左右端点大于 20 后,进行特判时,不能只是依据两端点是否差 1,且是否有其中一个端点是素数,如果两端差值小于等于3时,也需要 check 一下,看一下素数的数量
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
using namespace std;
typedef long long ll;
const int N=100010;
bool check(ll x)
{
for(ll i = 2; i <= sqrt(x); i ++ )
{
if(x % i == 0) return false;
}
return true;
}
int main()
{
ll l ,r;
while(~scanf("%lld%lld",&l,&r))
{
ll res1 = r - l + 1;
ll res2 = 0;
if(l <= 17 && r <= 20)
{
for(ll i = l; i <= r; i ++ )
if(check(i)) res2 ++ ;
if(res2 * 2 >= res1) printf("yes\n");
else printf("no\n");
}
else
{
if((l + 1 == r) && (check(l) || check(r)))
printf("yes\n");
else if(r - l <= 3)
{
for(int i = l; i <= r; i ++ )
if(check(i)) res2 ++ ;
if(res2 * 2 >= res1) printf("yes\n");
else printf("no\n");
}
else printf("no\n");
}
}
return 0;
}
C 庄生的笔
日后再更ing
D 上流的聚餐
日后再更ing
E 规划(一)
小王生活在美丽的村庄,某天他励志想考上公务员,于是,开始了奋笔疾书。当天却遇到了一个难题,就是每个村庄与每个村庄都有很多条小道路,甚至两个村庄之间有三四条小道路。
现在需要将这些道路整合起来,进行翻新,从泥泞路变成水泥路,每米造价是1w元,要使得每个村庄都联通,问最少需要几个w。
输入格式:
第一行输入两个整数n,m(2<=n<=1e3 && 1<=m<=1e5)分别表示村庄个数和道路个数
接下来的m行,输入三个整数 u,v,w(1<=u,v<=n && 1<=w<=1e6)表示u村到v村需要w米距离
输出格式:
输出一个整数,表示最小需要几个w
如果,所有的村庄连不起,则输出NO
输入样例:
在这里给出一组输入。例如:
4 6
1 2 1
1 2 3
1 2 4
1 3 5
1 3 5
1 3 5
输出样例:
在这里给出相应的输出。例如:
NO
题目解释
最小生成树模板题
直接背 prim() 算法
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int N=1e3+10;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim()
{
int res=0;
memset(dist,0x3f,sizeof dist);
for(int i=0;i<n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
if(i&&dist[t]==0x3f3f3f3f) return 0x3f3f3f3f;
if(i) res+=dist[t];
for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
st[t]=true;
}
return res;
}
int main()
{
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i=0;i<m;i++)
{
int x,y,z;
cin>>x>>y>>z;
g[x][y]=g[y][x]=min(g[x][y],z);
}
int ans=prim();
if(ans==0x3f3f3f3f) puts("NO");
else cout<<ans<<endl;
return 0;
}
F 规划(二)
日后再更ing
G 运动的球球
日后再更ing
H 物资转移
I 小杨环
J 前四位
求n的n次方的前四位
输入格式:
输入一个正整数n(10<=n<=1000)
输出格式:
输出n的n次方的前四位
输入样例:
在这里给出一组输入。例如:
10
输出样例:
在这里给出相应的输出。例如:
1000
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<stack>
#include<queue>
#include<sstream>
using namespace std;
typedef long long ll;
const int N=100010;
int main()
{
int n;
cin >> n;
double res =n * log10(n)- (int)(n * log10(n));
int ans = pow(10, res) * 1000;
cout << ans << endl;
return 0;
}