赞
踩
A. LCM Challenge
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
Some days ago, I learned the concept of LCM (least common multiple). I’ve played with it for several times and I want to make a big number with it.
But I also don’t want to use many numbers, so I’ll choose three positive integers (they don’t have to be distinct) which are not greater than n. Can you help me to find the maximum possible least common multiple of these three integers?
Input
The first line contains an integer n (1 ≤ n ≤ 106) — the n mentioned in the statement.
Output
Print a single integer — the maximum possible LCM of three not necessarily distinct positive integers that are not greater than n.
Examples
inputCopy
9
outputCopy
504
inputCopy
7
outputCopy
210
Note
The least common multiple of some positive integers is the least positive integer which is multiple for each of them.
The result may become very large, 32-bit integer won’t be enough. So using 64-bit integers is recommended.
For the last example, we can chose numbers 7, 6, 5 and the LCM of them is 7·6·5 = 210. It is the maximum value we can get.
题解:我们从题目中容易得到很容易想到的一个方法---------暴力加上互质的判断即可解决本题,本题的范围较大,我们可以有m=max(1,n-100)这个操作去减少时间的浪费,但是当我们解决了时间复杂度的这个明显的问题时,那么本题的大致解题也就完成了。
第二种思路就是由任意两个连续的奇数一定是互质的,既然要求三个互质数的最大乘积,那么此时我们对于奇偶情况进行不同的讨论,其次我们在进行互质数的选择上来说,3的倍数的选取是一个不容忽略的问题,此时我们只要分情况讨论即可。
一
#include<bits/stdc++.h> using namespace std; #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) long long gcd(long long a,long long b) { return b==0?a:gcd(b,a%b); } int main() { FAST; long long n; cin>>n; long long m=max((long long)1,n-100); long long ans=n; for(int i=m;i<=n;i++) for(int j=i+1;j<=n;j++) { if(gcd(i,j)==1) { for(int k=j+1;k<=n;k++) { if(gcd(i,k)==1&&gcd(j,k)==1) ans=max(ans,(long long)i*j*k); } } } cout<<ans<<endl; }
二
#include<bits/stdc++.h> using namespace std; int main() { long long n; cin>>n; if(n<3) cout<<n<<endl; else { if(n&1) cout<<n*(n-1)*(n-2)<<endl; else { if(n%3==0) cout<<(n-1)*(n-2)*(n-3)<<endl; else cout<<n*(n-1)*(n-3)<<endl; } } return 0; }
B. Let’s Play Osu!
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
You’re playing a game called Osu! Here’s a simplified version of it. There are n clicks in a game. For each click there are two outcomes: correct or bad. Let us denote correct as “O”, bad as “X”, then the whole play can be encoded as a sequence of n characters “O” and “X”.
Using the play sequence you can calculate the score for the play as follows: for every maximal consecutive "O"s block, add the square of its length (the number of characters “O”) to the score. For example, if your play can be encoded as “OOXOOOXXOO”, then there’s three maximal consecutive "O"s block “OO”, “OOO”, “OO”, so your score will be 22 + 32 + 22 = 17. If there are no correct clicks in a play then the score for the play equals to 0.
You know that the probability to click the i-th (1 ≤ i ≤ n) click correctly is pi. In other words, the i-th character in the play sequence has pi probability to be “O”, 1 - pi to be “X”. You task is to calculate the expected score for your play.
Input
The first line contains an integer n (1 ≤ n ≤ 105) — the number of clicks. The second line contains n space-separated real numbers p1, p2, …, pn (0 ≤ pi ≤ 1).
There will be at most six digits after the decimal point in the given pi.
Output
Print a single real number — the expected score for your play. Your answer will be considered correct if its absolute or relative error does not exceed 10 - 6.
Examples
inputCopy
3
0.5 0.5 0.5
outputCopy
2.750000000000000
inputCopy
4
0.7 0.2 0.1 0.9
outputCopy
2.489200000000000
inputCopy
5
1 1 1 1 1
outputCopy
25.000000000000000
Note
For the first example. There are 8 possible outcomes. Each has a probability of 0.125.
“OOO” → 32 = 9;
“OOX” → 22 = 4;
“OXO” → 12 + 12 = 2;
“OXX” → 12 = 1;
“XOO” → 22 = 4;
“XOX” → 12 = 1;
“XXO” → 12 = 1;
“XXX” → 0.
So the expected score is
知识准备:期望dp的相关概念,
将题目给的字符串看作是01序列,成功为1失败为0.
设x当前操作进行连续1的个数.
(x+1) ^2 −x ^2=x ^2+2x+1−x ^2=2x+1
即每新增一个1,那么分数会增加2x+1.
令cnt[i]表示前i个字符,x的期望值,
那么cnt[i]=(cnt[i−1]+1)∗p[i],
令dp[i]表前i个字符,得分的期望值,
我们可以推出本题有关于期望dp的状态转移方程,
那么dp[i]=dp[i−1]+(2∗cnt[i−1]+1)∗p[i].
递推出dp[n]即可.
本题一定需要掌握期望dp的计算过程,而不是死记硬背所谓的模板。
#include<bits/stdc++.h> using namespace std; const int maxn=1e5+5; double dp[maxn],p[maxn],cnt[maxn]; int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lf",&p[i]); } for(int i=1;i<=n;i++) { cnt[i]=(cnt[i-1]+1)*p[i]; dp[i]=dp[i-1]+(2*cnt[i-1]+1)*p[i]; } printf("%.10lf\n",dp[n]); }
E. Number Challenge
time limit per test3 seconds
memory limit per test512 megabytes
inputstandard input
outputstandard output
Let’s denote d(n) as the number of divisors of a positive integer n. You are given three integers a, b and c. Your task is to calculate the following sum:
Find the sum modulo 1073741824 (230).
Input
The first line contains three space-separated integers a, b and c (1 ≤ a, b, c ≤ 2000).
Output
Print a single integer — the required sum modulo 1073741824 (230).
Examples
inputCopy
2 2 2
outputCopy
20
inputCopy
4 4 4
outputCopy
328
inputCopy
10 10 10
outputCopy
11536
Note
For the first example.
d(1·1·1) = d(1) = 1;
d(1·1·2) = d(2) = 2;
d(1·2·1) = d(2) = 2;
d(1·2·2) = d(4) = 3;
d(2·1·1) = d(2) = 2;
d(2·1·2) = d(4) = 3;
d(2·2·1) = d(4) = 3;
d(2·2·2) = d(8) = 4.
So the result is 1 + 2 + 2 + 3 + 2 + 3 + 3 + 4 = 20.
题解:本题根据d的计算公式就可以大胆猜测出与欧拉函数有关,即现对于i,j,k三个有效的数字来说,d函数关于i,j,k三个数的乘积的性质也就是求给定范围内的欧拉函数后再进行相关的求和即可。
但是如果这样进行简单的暴力求和,那么此时只考虑主函数的复杂度---------n^3,这种效率不足以满足我们的需求,那么此时用莫比乌斯反演以及整除分块,那么对于问题求解的规模缩小,并且方便快速求出结果。
#include<bits/stdc++.h> #define pa pair<int,int> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){ x=x*10+ch-'0';ch=getchar();} return x*f; } int a,b,c,cnt; int pri[2005],mu[2005]; bool mark[2005]; ll ans; int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } void pre()//先对于u(x)函数进行相关的预处理 { mu[1]=1; for(int i=2;i<=2000
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。