UCF Local Programming Contest Round 1A_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

A-Briefcases Full of Money_UCF Local Programming Contest Round 1A (nowcoder.com)

题目大意:给定你五种钞票的面额,$1,$5,$10,$20,$50,$100,再给定每种钞票的数目,你只能选择五种钞票中的其中一种,请输出你能获得最大金额的钞票类型.(如果有多种钞票获得金额想通过,那么优先选择金额大的,因为比较轻).

思路:签到题.

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int a[10]={0, 1, 5, 10, 20, 50, 100};
int b[10]={0, 1, 5, 10, 20, 50, 100};
int main(){
    ll temp;
    int ans;
    ll maxnum = 0;
    rep(i,1,6){
        temp = read();
        a[i] *= temp;
    }
    rep(i,1,6){
        if (maxnum <= a[i]){
            maxnum = a[i];
            ans = b[i];
        }
    }
    cout << ans <<endl;

    return 0;
}

B-A Game Called Mind_UCF Local Programming Contest Round 1A (nowcoder.com)

题目大意:现在有至多六名玩家参加一个游戏,每个人手上有若干张卡牌,但他们并不知道卡牌的大小,你知道他们每个人的手牌,请你按照升序的规则,让他们依次放下手牌.

思路:签到题,结构体排序.

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int t, n;
char name[6] = {'A', 'B', 'C', 'D', 'E', 'F' };
struct p{
    int num;
    char s;
}all[105];

bool cmp(p&a, p&b){
    return a.num < b.num;
}

 int main(){
     t =read();
     int index = 0;
     rep(i,0,t-1){
        n =read();
        while(n--){
        all[index].num = read();
        all[index].s = name[i];
        index++;
        }
     }
     sort(all, all+index, cmp);
     rep(i,0,index-1){
        cout << all[i].s;
     }
 }

C-Unique Values_UCF Local Programming Contest Round 1A (nowcoder.com)

题目大意:如果一个连续的数列中没有重复的元素,那么我们称这个序列为一个好序列,现在给定你一个序列,请求出该序列中最多有多少个好序列.

思路:用set来表示元素的关系,然后用双指针来维护区间,进行一个线性扫描.

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
const int MAX = 1e5 + 5;
ll a[MAX];
set<ll>s;
int main() {
    int n;
    n = read();
    ll ans = 0;
    rep(i, 1, n)cin>>a[i];
    int left = 1, right = left+1;
    while(left <= n) {
        if (left != 1)
            s.erase(a[left - 1]);
        if(!s.count(a[left]))s.insert(a[left]);		//如果被右指针添加过则不重复添加
        if (right <= left)++right;		//如果右指针和左指针重合,向右移动一位
        while(right<=n){
            if (!s.count(a[right]))s.insert(a[right++]);
            else break;
        }
        ans += s.size();
        left++;
    }
    cout << ans << endl;
}

D-Gone Fishing_UCF Local Programming Contest Round 1A (nowcoder.com)

题目大意:一个渔夫准备张开一张网捕鱼,已知每条鱼的位置,和渔网的半径,请你合理安排渔夫张开网的的位置,使得能补到的鱼尽可能多.

思路:贪心+几何,为了使捕到的鱼尽可能的多,那么每条鱼就应该尽可能地用边缘来将其捕获,那我们直接枚举渔网圆心的位置,如果能够以两条鱼来构建出一个渔网圆,那么这个圆心一定是较好的选择,只需要求出所有的这些圆心,然后对于每个圆心依次求它和其他鱼的位置关系,然后遍历一次求最大值即可.图例如下

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
   return s*w;
}
struct Point
{
    double x,y;
    Point(double tx=0,double ty=0){x=tx;y=ty;}
}p[200];
double radius;

double cal(Point&a, Point&b){
    double ans = (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
    return  sqrt(ans);
}

int main(){
    syncfalse;
    cin>>radius;
    int n;
    cin>>n;
    rep(i,1,n){
        cin>>p[i].x>>p[i].y;
    }
    int ans  = 1;
    rep(i,1,n){
        rep(j,i+1,n){
            if (cal(p[i], p[j]) > 2.0*radius)continue;
                int temp = 0;
                double dis = cal(p[i], p[j])/2.0;
                Point mid = Point((p[i].x+p[j].x)/2,(p[i].y+p[j].y)/2);
                double angle = atan2(p[i].x-p[j].x, p[j].y-p[i].y);
                double d = sqrt(radius*radius - dis*dis);
                Point now1(mid.x + d*cos(angle), mid.y + d*sin(angle));
                Point now2(mid.x - d*cos(angle), mid.y - d*sin(angle));
                rep(k,1,n){
                    if (cal(p[k], now1) < 1e-8+1.0*radius)temp++;	//保证精度
                }
                ans = max(ans, temp);
                temp = 0;
                rep(k,1,n){
                    if (cal(p[k], now2) < 1e-8+1.0*radius)temp++;
                }
                ans = max(ans, temp);
        }
    }
    cout << ans <<endl;
    return 0;
}

E-Sum of a Function_UCF Local Programming Contest Round 1A (nowcoder.com)

题目大意:现在规定函数f(x) = x的最小质因数,现在给定l,r,和k,请你求出f(l), f(l+1), f(l+2),…f®种最小的k个值的和.

思路:数论题,之前因为输入的l和r到达了1e18,就想着用素数筛晒到1e9,但发现不现实,其实只需要晒到前1000个就可以了,具体原因还不得而知学过相关的数论之后在进行补上.

#include<bits/stdc++.h>
using namespace std;
#define rep(x,y,z) for(int x = y; x<=z;++x)
#define dec(x,y,z) for(int x = y; x>=z;--x)
#define INF 0x3f3f3f3f
#define ll long long
#define LOOP ll _; cin>> _; for(ll LP_ = 1; LP_<=_; ++LP_)
#define syncfalse ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
inline int read() {
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9') { if (ch == '-')w = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9')s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}
const int MAX = 1e3+5;
bool isPrime[1000005];
int Prime[MAX];
int cnt = 1;
int n = 1000000;
void solve(){
    for(int i = 2; i <= n && cnt <= 1000; ++i){
        if (!isPrime[i]){
            Prime[cnt++] = i;
        }
        for (int j = 1; j <= cnt && Prime[j] * i <= n; ++j){
            isPrime[Prime[j]*i] = true;
            if (i % Prime[j] == 0)break;
        }
    }
}
vector<ll>all;
int main() {
    solve();
    ll a, b, c;
    cin >> a >> b >> c;
    ll cur = 1;
    ll tol = a;
    for (ll i = a; i <= b; ++i) {
        bool flag = true;
        for(int j = 1; j <= 1000;++j){
            if (i%Prime[j] == 0){
                all.push_back(Prime[j]);
                flag = false;
                break;
            }
        }
        if (flag)all.push_back(i);
    }
    sort(all.begin(), all.end());
    int i = 0;
    ll ans= 0;
    while(c--){
        ans += all[i++];
    }
    cout << ans << endl;

    return 0;
}