UCF Local Programming Contest Round 1A中的CDEF题解

本文主要是介绍UCF Local Programming Contest Round 1A中的CDEF题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

牛客题目链接

C-Unique Values

大概题意：给定一个数字序列，找出其中有多少对连续子序列中不含重复元素。（一个元素也算连续子序列）
示例一：
input：
5
1 1 2 1 5
output：
9
示例二：
input：
8
2 12 3 12 3 2 6 9
output：
22

思路：
用一个左指针（记为i）和一个右指针（记为j）从序列中取子序列，因为输入的数字范围在1-1e18，所以不能用数组来记录某个数字是否出现，而应该用map。
开始时i指向第一个数字，j指向第二个数字。然后进行判断：
如果j指向的元素在i到j-1这段序列中已经出现过，那么i++，否则j++。
每次j++后，当前子序列在末尾加入了一个元素，那么可以形成的新子序列等于原来子序列的长度。
复杂度为O(n)

#include<bits/stdc++.h>
using namespace std;int main()
{ios::sync_with_stdio(false);cin.tie(0);map<int,bool> vis;//记录某数字在子序列中是否出现过int len,num[100005],i=1,j=2;long long ans=0;//统计子序列数量cin>>len;ans+=len;//把每个单独的数字加入统计中for(int i=1;i<=len;i++) cin>>num[i];vis[num[1]]=1;while(i<len){while(!vis[num[j]]&&j<=len){vis[num[j]]=1;ans+=j-i;++j;}vis[num[i]]=0;i++;}cout<<ans;return 0;
}

D-Gone Fishing

题意：给定一个圆的半径和一些点的坐标，计算这个圆最多能包含多少个点
思路：只要圆内点数不少于两点，一定能将圆平移至有两点在圆上，再以新圆的圆心遍历剩余点，看其是否在圆内，因为根据两点和半径能确定的圆有两个，因此两个半径都要计算。本题另一个容易错的点就是精度问题，但凡涉及浮点数运算都要考虑精度问题。
只要将点两两组合，进行遍历即可。

#include <bits/stdc++.h>
#define eps 1e-6
using namespace std;double r;
struct point
{double x;double y;
};double distance(point a, point b)
{return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}
//计算圆心，将圆心坐标赋值给o1和o2
void get_Center(point x, point y,point &o1,point &o2)
{point p;point mid = {(x.x + y.x) / 2, (x.y + y.y) / 2};double len = distance(x, y);double angle = atan2(x.x - y.x, y.y - x.y);double d = sqrt(r * r - pow(distance(x, mid), 2));o1.x = mid.x + d * cos(angle);o1.y = mid.y + d * sin(angle);o2.x = mid.x - d * cos(angle);o2.y = mid.y - d * sin(angle);
}
int main()
{int n,ans = 1;point o1,o2,p[101];cin >> r >> n;for (int i = 0; i < n; i++){cin >> p[i].x >> p[i].y;}for (int i = 0; i < n; i++){for (int j = i + 1; j < n; j++){//若两点距离大于半径，构不成圆if (distance(p[i], p[j]) > 2.0 * r)continue;get_Center(p[i], p[j],o1,o2);int cnt1=0,cnt2=0;for (int k = 0; k < n; k++){//考虑精度问题if (distance(o1, p[k]) < 1.0 * r + eps)cnt1++;if (distance(o2, p[k]) < 1.0 * r + eps)cnt1++;}ans = max(ans,max(cnt1,cnt2));}}cout << ans;return 0;
}

E-Sum of a Function

题目大意：f(n)表示n的最小质因数,输入s，e，k，求从f(s),f(s+1),…,f(e)这个序列中前k小的元素的和。数据说明：2<s<1e18，100<e-s<1e6，1<=k<(e-s)*0.9
示例一：
in：
100 200 70
out：
165
示例二：
in：
213 419 169
out：
546

思路：
因为s的范围过大，用欧拉筛筛选出2-1e9之间的素数显然不合理，但是e-s最多只有1e6，且k<(e-s)*0.9，也就是说s到e之间的数的最小质因数无需统计全部，只要统计出2，3，5，…，这些比较小的质数，就能占到90%左右。

#include <bits/stdc++.h>
using namespace std;int prime[1000];
bool isprime[1005];
//vis数组统计某数是否已被统计，因为有些数有多个质因数，但是只能取最小的质因数
int vis[1000005];
//欧拉筛，筛选出小于n的素数
void get_prime(int prime[], bool isprime[], int n)
{int cnt = 0;memset(isprime, 1, sizeof(bool) * n);isprime[1] = 0;for (int i = 2; i <= n; i++){if (isprime[i])prime[++cnt] = i;for (int j = 1; j <= cnt && i * prime[j] <= n; j++){isprime[i * prime[j]] = 0;if (i % prime[j] == 0)break;}prime[0] = cnt;}
}int main()
{get_prime(prime, isprime, 10000);memset(vis, 0, sizeof(vis));long long s, e, k, sum = 0;cin >> s >> e >> k;for (int i = 1; i < 1000 && k>0; i++){//be表示不小于s的最小的能被prime[i]整除的数long long be=(s/prime[i])*prime[i];if(be<s) be+=prime[i];for (long long j = be; j <= e && k>0 ; j += prime[i]){if (!vis[j - s] && j % prime[i] == 0){//因为s的范围过大，用j-s表示下标vis[j - s]=1;k--;sum+=prime[i];}}}cout << sum << endl;return 0;
}

F-Hang Gliding

题目大意：给定每个任务的分值和开始结束时间，并给出每个飞行员完成这个任务的概率，求出每个飞行员的期望分值，并输出前三名。
第一行t,p表示任务数量和飞行员数量
接下来三行表示每个任务的开始结束时间和分值
接下来t*p行，每t行表示一个飞行员完成任务的概率。
示例一：
in：

3 3
0 1 5
1 2 10
2 3 15
0.0
0.0
0.2
1.0
0.0
0.0
0.0
0.75
0.0

out：

3 7.50
2 5.00
1 3.00
示例二：
in：

3 4
0 3 50
3 6 50
0 6 75
0.2
0.3
0.6
0.6
0.6
0.5
0.6
0.5
0.4
0.9
0.9
0.9

out：

4 90.00
2 60.00
3 55.00

思路：dp，动态规划。
dp[i]表示在0-i的时间得飞行员最多获得的分数，s，e，point表示任务的开始和结束时间及分值，p表示飞行员的概率，则dp[e]=max(dp[s]+p*point,dp[e])，遍历方式选择对任务进行遍历，先将任务按结束时间进行排序，从结束时间早的往后遍历。复杂度为O(n)
如果是对时间进行遍历，每次需要查找某个时间点结束的任务，如果用二分查找，复杂度为O(nlogn)
与普通动态规划部不同的是，任务时间上具有不连续性，因此dp中间段可能会存在为0的情况，那么就要找前面的值进行填充。

#include <bits/stdc++.h>
#define mem(a, n) memset(a, n, sizeof(a))
#define rd1(x) scanf("%f", &x)
typedef unsigned long long ull;
using namespace std;
struct result //存储玩家的成绩
{float score;int id;//保存玩家编号，以便在排序后能找到编号
};
struct Task//表示任务
{int s;int e;int point;int id;//保存任务编号，以便在排序后能找到编号
};
Task task[10005];
result ret[105];
float pilot[105][10005];//pilot[i][j]表示飞行员i完成任务j的概率
float dp[10005]; //dp[e]表示在e分钟之前最多获得的分数
void init()//dp初始化
{for (int i = 0; i < 10005; i++)dp[i] = 0.00;
}
bool cmpt(Task &a, Task &b)
{return a.e < b.e;
}
bool cmpr(result &a, result &b)
{return a.score > b.score;
}void trans(int s)//因为任务的时间不具有连续性，可能中间某段会为0，需要向前找到第一个不为0的dp，然后填充后面的
{if (s && dp[s] < 0.000001){int l = s;while (dp[l] < 0.000001 && l > 0)l--;if (l > 0){for (int i = l; i < s; i++){dp[i + 1] = dp[i];}}}
}
int main()
{int t, p, ss, ee, pp, id, last;cin >> t >> p;for (int i = 1; i <= t; i++){scanf("%d %d %d", &task[i].s, &task[i].e, &task[i].point);getchar();task[i].id = i;}//对任务按结束时间进行排序sort(task + 1, task + t + 1, cmpt);for (int i = 1; i <= p; i++){ret[i].id = i;for (int j = 1; j <= t; j++)rd1(pilot[i][j]);getchar();}//开始dpfor (int i = 1; i <= p; i++){//每个飞行员都是独立的，所以每次都要初始化dpinit();for (int j = 1; j <= t; j++){ss = task[j].s;ee = task[j].e;pp = task[j].point;id = task[j].id;/*这两句代码是关键，缺一不可*/trans(ss);//如果dp[ss]==0，就找到前面的值进行填充trans(ee);//dp[ee]如果为0，也找前面的进行填充//如果dp[ee]为0进行比较，那么会被置为dp[ss] + pp * pilot[i][id]，就会出错//一开始WA了很多次就是因为忘了加trans(ee)if (dp[ss] + pp * pilot[i][id] > dp[ee]){dp[ee] = dp[ss] + pp * pilot[i][id];}}ret[i].score = dp[ee];}sort(ret + 1, ret + p + 1, cmpr);printf("%d %.2f\n", ret[1].id, ret[1].score);printf("%d %.2f\n", ret[2].id, ret[2].score);printf("%d %.2f\n", ret[3].id, ret[3].score);return 0;
}