UCF Local Programming Contest Round 解题/补题报告

A Briefcases Full of Money

题目大意：

输入各个面值钞票的数量，根据题目中的面值，求出和最大的钞票面值

如果有相同的输出钞票数最少的

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
long long cnt=0;

int main(){

    int a[10],b[6]={1,5,10,20,50,100};
    int maxx=-1,maxi;
    for(int i=0;i<6;i++){
        cin>>a[i];
        if(a[i]*b[i]>=maxx){
            maxx=a[i]*b[i];
            maxi=b[i];
        }
    }
    cout<<maxi<<endl;
    return 0;
}

View Code

B A Game Called Mind

2-6名玩家，每名玩家有1-9张牌，每张牌的值在10-99之间无重复

按照从小到大的顺序出牌，输出出售顺序

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
long long cnt=0;

int main(){

    queue<int> q[10];
    int s[500];
    int n,a,b,c=0;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a;
        while(a--){
            cin>>b;
            q[i].push(b);
            s[c++]=b;
        }
    }
    sort(s,s+c);
    for(int i=0;i<c;i++){
        for(int j=0;j<n;j++){
            if(q[j].front()==s[i]){
                char ch='A'+j;
                cout<<ch;
                q[j].pop();
                break;
            }
        }
    }
    return 0;
}

View Code

C Unique Values

求又多少个子串不包含重复的数字

从头开始找最长没有重复的子序列，加上，再判断下一个

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
long long a[maxn];
int main(){

    long long n,cnt=0,x=1,j=0,i;
    cin>>n;
    for(long long i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    cnt=n;
    map<long long,long long> mp;
    for(i=0;i<n;i++){
        for(;j<n;j++){
             mp[a[j]]++;
             //cout<<j<<" "<< mp[a[j]]<<endl;
             if(mp[a[j]]>=2){
                mp[a[j]]--;
               // cout<<"从"<<i<<"开始到"<<x<<endl;
                break;
             }
        }
        cnt+=j-i-1;
       // cout<<"第i个是"<<cnt<<endl;
        mp[a[i]]--;
    }
    cout<<cnt<<endl;
    return 0;
}

View Code

从s到e，找出其中的k个数，使f(x)最小，f(x)为x的最小素因子

思路：先数素因子可能为二的，并求和标记，在数3，，，

#include<bits/stdc++.h>
using namespace std;
const int maxn=100005;
long long a[1000010];
int main(){
    long long s,e,k,sum=0,cnt=0,flag=1;
    cin>>s>>e>>k;
    while(cnt<k){
        flag++;
        long long x=(s/flag)*flag;
        if(x<s){
            x+=flag;
        }
        //x 第一个含这个因子的
        while(x<=e && cnt<k){
            if(a[x-s]==0){
                a[x-s]=flag;
                sum+=flag;
                cnt++;
            }
            x+=flag;
        }
    }
    cout<<sum<<endl;
    return 0;

}

View Code

D Gone Fishing

题目大意：给一个半径，n个点，求该圆最多能圈几个点

通过在圆上的任意两点和半径确定圆心，再枚举其他点有多少在圆内（。

//参考大佬代码

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

using namespace std;

typedef long long ll;
typedef pair<double, double> PII;

const int N = 110;
const int INF = 2e9;
const double eps = 1e-6;
const int mod = 1e9 + 7;
    double r;
PII a[N];

double getLen(PII a, PII b)
{
    double x1 = a.first, y1 = a.second, x2 = b.first, y2 = b.second;
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

PII getCenter(PII p1, PII p2) //坐标用PII存，p1和p2为已知的两个圆上坐标，r为圆半径
{
    PII mid = PII((p1.first + p2.first) / 2, (p1.second + p2.second) / 2); //求得中点坐标
    double angle = atan2(p1.first - p2.first, p2.second - p1.second); //求出极坐标角度
    double d = sqrt(r * r - pow(getLen(p1, mid), 2)); //求出侧边也就是圆心到其中点的距离
    return PII(mid.first + d * cos(angle), mid.second + d * sin(angle)); //求出圆心坐标
}

int main()
{
    fastio;
    cin >> r;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].first >> a[i].second;
    ll ans = 1;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (getLen(a[i], a[j]) > 2 * r)
                continue;
            PII center = getCenter(a[i], a[j]);
            ll t = 0;
            for (int k = 1; k <= n; k++)
            {
                double len = getLen(center, a[k]);
                if (len <= r + eps) //直接写成r+eps把大于和小于的情况都包括了
                    t++;
            }
            ans = max(ans, t);
        }
    }
    cout << ans << endl;
    return 0;
}

View Code