一只橘橘猫

2020-03-05 13:20 已编辑不鸣科技_游戏开发工程师

关注

UCF Local Programming Contest 2012 补题记录 - 闫志强 - 2020.3.5

点击进入题解即可

https://ac.nowcoder.com/acm/contest/4685/A

比赛主页：https://www.jisuanke.com/contest/7332

A. Wall Street Monopoly:

solution:

涉及知识点：区间dp

划重点：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的最优解进而得出整个大区间上最优解的dp算法。

下面我们通过一个例子来了解一下这道题是如何用区间dp求解,：

图片说明

如图所示，我们设dp[i][j]代表第 i 个物体到第 j 个物体相连的最小代价

设a[i] , b[i] 代表第 i 个物体的长和宽

初始化dp[1][1] = dp[2][2] = ... = dp[n][n] = 0,因为自身相连的代价是0

我们需要依次枚举相连的长度，长度等于2 ：

dp[1][2] = dp[1][1] + dp[2][2] + min(a[1] , b[1])*min(a[2],b[2] )

dp[2][3] = dp[2][2] + dp[3][3] + min(a[2] , b[2])*min(a[3],b[3] )

dp[3][4] = dp[3][3] + dp[4][4] + min(a[3] , b[3])*min(a[4],b[4] )

那么长度为3的dp[1][3] 和 dp[2][4] 大家是否能自己写出来呢？

划重点：通项公式

为了便于理解，我们手写一下通向公式

dp[i][j] = min（dp[i][j] , dp[i][k] + dp[k+1][j] + 合并的代价）

那么区间dp的核心代码：

for(int len = 1; len <= n; len++){
    for(int j =1; j + len <= n+1; j++){
        int ends = j + len - 1;
        for(int i = j; i < ends; i++){
            dp[j][lens] = min(dp[j][lens] , dp[j][i] + dp[i+1][ends] + something);
        }
    }
}

显然这道题的问题就变成了求something是什么？

题目中明确指示，合并两个物体的代价是较小的边相乘，我们只需要模拟一下多个物体合在一起的长和宽，记录下最小值，相乘即可

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 25;
ll a[maxn],b[maxn];
ll dp[maxn][maxn];
int main()
{
    int t;
    cin>>t;
    for(int cas = 1;cas <= t; cas++)
    {
        int n;
        scanf("%d",&n);
        memset(dp,0x3f3f3f,sizeof(dp));
        for(int i=1;i<=n;i++){
            scanf("%lld %lld",&a[i],&b[i]);
            dp[i][i] = 0;
        }
        ll k1 = 0,k2 = 0,k3 = 0,k4 = 0;
        for(int len=1;len<n;len++){

            for(int i=1;i<=n;i++){
                int j = i+len;
                if(j > n)
                    continue ;
                for(int k=1;k<=len;k++){
                    k1 = k2 = k3 = k4 = 0;
                    for(int z = i;z<=i+k-1;z++){
                        k1 += a[z];
                        k2 = max(k2 , b[z]);
                    }
                    for(int z=i+k;z<=j;z++){
                        k3 += a[z];
                        k4 = max(k4 , b[z]);
                    }
                    dp[i][j] = min(dp[i][j] , dp[i][i+k-1] + dp[i+k][j] + min(k1,k2)*min(k3,k4));
                }
            }
        }
        printf("The minimum cost for lot #%d is $%lld.\n",cas,1ll*100*dp[1][n]);
        if(cas != t){
            printf("\n");
        }
    }
    return 0;
}

B. Wall Street Monopoly:

solution:

涉及知识点：字符串的字典序

从‘z’-‘a’比较两个字符串拥有的个数即可，注意输出

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
map<char ,int> mp1 , mp2;
int main()
{
    int n;
    cin>>n;
    for(int cas = 1;cas <= n;cas++)
    {
        int flag = 0;
        mp1.clear(),mp2.clear();
        string s1,s2;
        cin>>s1>>s2;
        for(int i=0;i<s1.length();i++){
            mp1[s1[i]]++;
        }
        for(int i=0;i<s2.length();i++){
            mp2[s2[i]]++;
        }
        for(int i=25;i>=0;i--){
            char c = i+'a';
            if(mp1[c] == mp2[c]){
                continue ;
            }
            if(mp1[c] > mp2[c]){
                flag = 1;
                break ;
            }
            if(mp1[c] < mp2[c]){
                flag = 2;
                break ;
            }
        }
        if(flag == 0){
            printf("Data set #%d: The two strings are the same age\n",cas);
        }
        else if(flag == 1){
            printf("Data set #%d: First string is older\n",cas);
        }
        else{
            printf("Data set #%d: First string is younger\n",cas);
        }
        if(cas != n){
            printf("\n");
        }
    }
    return 0;
}

C. Clean Up the Powers that Be:

solution:

涉及知识点：结构体，排序，模拟

这道题有一个坑人的地方，就是指数和幂数如果等于0，要记一下长度为1，而不是0

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1005;
int pre1[maxn],pre2[maxn];
struct node{
    int x,y;
};
node a[maxn];
bool cmp(node p1,node p2)
{
    if(p1.x == p2.x)
        return p1.y < p2.y;
    return p1.x < p2.x;
}
map<int , int> mp;
int main()
{
    int t;
    cin>>t;
    for(int cas = 1;cas <= t; cas++)
    {
        mp.clear();
        int n;
        cin>>n;
        int cnt = 0,x,y;
        for(int i=1;i<=n;i++){
            cin>>x>>y;
            if(mp[x]){
                a[mp[x]].y += y;
            }else{
                a[++cnt].x = x;
                a[cnt].y = y;
                mp[x] = cnt;
            }
        }
        sort(a+1,a+1+cnt,cmp);
        for(int i=1;i<=cnt;i++){
            int x = a[i].x;
            int y = a[i].y;
            int cnt1 = 0,cnt2 = 0;
            if(x == 0)
                cnt1 = 1;
            if(y == 0)
                cnt2 = 1;
            while(x){
                x /= 10,cnt1++;
            }
            while(y){
                y/=10,cnt2++;
            }
            pre1[i] = cnt1;
            pre2[i] = cnt2;
        }
        printf("Prime Factorization #%d:\n",cas);
        for(int i=1;i<=cnt;i++){
            for(int j=1;j<=pre1[i];j++){
                printf(" ");
            }
            printf("%d",a[i].y);
        }
        printf("\n");
        for(int i=1;i<=cnt;i++){
            for(int j=1;j<=pre2[i-1];j++){
                printf(" ");
            }
            printf("%d",a[i].x);
        }
        for(int j=1;j<=pre2[cnt];j++){
            printf(" ");
        }
        printf("\n");
        if(cas != t){
            printf("\n");
        }
    }
    return 0;
}

D. The Clock Algorithm:

solution:

涉及知识点：读题！

这道题我在浩洋哥哥的帮助下，一个小时才读明白，整理成了能看懂的样子
这是样例2的解释，希望能帮到大家：
图片说明

std:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1e5 + 5;
struct node{
    ll x;
    ll flag;///1为新，0为旧
}N[maxn];
ll a[maxn];

int main(){
    ll n, m, Case = 1;
    while(~scanf("%lld%lld",&n,&m)){
        if(!n && !m) break;
        memset(a, 0, sizeof(a));
        ll Count = 1, sum = 0;    ///指针,计数
        for(ll i = 1; i <= m; i++)
            scanf("%lld", &a[i]);
        for(ll i = 1; i <= n; i++){
            N[i].x = 0;
            N[i].flag = 0;
        }
        printf("Program %lld\n", Case++);
        for(ll i = 1; i <= m; i++){
            ll flag1 = 0;
            for(ll j = 1; j <= n; j++){
                if(N[j].x == a[i]){
                    N[j].flag = 1;
                    flag1 = 1;
                    printf("Access page %lld in cell %lld.\n", a[i], j);
                    sum++;
                }
            }
            if(flag1 == 1)
                continue;
            while(N[Count].flag == 1){
                N[Count].flag = 0;
                Count++;
                if(Count == n + 1){
                    Count = 1;
                }
            }
            if(N[Count].flag == 0){
                N[Count].x = a[i];
                N[Count].flag = 1;
                printf("Page %lld loaded into cell %lld.\n", a[i], Count);
                Count++;
                if(Count == n + 1)
                    Count = 1;
            }
        }
        printf("There are a total of %lld page faults.\n\n", m - sum);
    }

    return 0;
}

F. Metallic Equipment Rigid:

solution:

涉及知识点：计算几何，线段和圆的相交判断

比较简单的一道计算几何板子题吧，~~起码我这个计算几何没做几道的还会做~~

先枚举每个点是否在某个圆内，然后将n个点按照先后顺序组成n-1条线，判断是否和m个圆相交

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 55;

struct point
{
    double x;
    double y;
};
point A[maxn],O[maxn];
int pan_duan(point p1,point p2,double r,int k)
{
    double a,b,c,dist1,dist2,angle1,angle2;//ax+by+c=0;
    if(p1.x==p2.x)
        a=1,b=0,c=-p1.x;//特殊情况判断，分母不能为零
    else if(p1.y==p2.y)
        a=0,b=1,c=-p1.y;//特殊情况判断，分母不能为零
    else
    {
        a=p1.y - p2.y;
        b=p2.x - p1.x;
        c=p1.x*p2.y - p1.y*p2.x;
    }
    dist1=a*O[k].x+b*O[k].y+c;
    dist1*=dist1;
    dist2=(a*a+b*b)*r*r;
    if(dist1 > dist2)
        return 0;//点到直线距离大于半径
    angle1=(O[k].x-p1.x)*(p2.x-p1.x)+(O[k].y-p1.y)*(p2.y-p1.y);
    angle2=(O[k].x-p2.x)*(p1.x-p2.x)+(O[k].y-p2.y)*(p1.y-p2.y);
    if(angle1>0&&angle2>0)return 1;
    return 0;
}
double r[maxn];
int ans[maxn];

int main()
{
    int t;
    cin>>t;
    for(int cas = 1;cas <= t;cas++)
    {

        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            ans[i] = 0;
            scanf("%lf%lf%lf",&O[i].x,&O[i].y,&r[i]);
        }
        for(int i=1;i<=m;i++){
            scanf("%lf%lf",&A[i].x,&A[i].y);
        }
        int flag = 0;
        for(int j=1;j<=m;j++){
            double x0 = A[j].x,y0 = A[j].y;
            for(int i=1;i<=n;i++){
                double cnt1 = fabs((O[i].x - x0)*(O[i].x - x0));
                double cnt2 = fabs((O[i].y - y0)*(O[i].y - y0));
                if(cnt1 + cnt2 <= r[i]*r[i]){
                    ans[i] = 1;
                    flag = 1;
                }
            }
        }
        for(int i=2;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(pan_duan( A[i] , A[i-1] , r[j] , j) == 1){
                    ans[j] = 1;
                    flag = 1;
                    //cout<<i<<endl;
                }
            }
        }
        printf("Compound #%d: ",cas);
        if(flag == 0){
            printf("Rigid Reptile was undetected\n");
        }
        else{
            printf("Reptile triggered these cameras:");
            for(int i=1;i<=n;i++){
                if(ans[i] == 1)
                    printf(" %d",i);
            }printf("\n");
        }
        if(cas != t)
            printf("\n");



    }
    return 0;
}

G:

solution:

涉及知识点：题解给的是括号匹配模拟，我写了个简单搜索，反正都对

我这里讲一下搜索吧，因为要求字符串要么是s，要么是t，搜索过程中判断，如果是s，那么可以有3种情况，如果是t，那么可以有两种情况，否则无解，按照要求写应该没什么问题吧，模拟呗

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 55;
int dfs(string s,int k)
{
    if(k == 1){
        if(s.length() == 0){
            return 1;
        }
        if(s[0] == 'c'){
            string ss = s.substr(1,s.length()-1);
            return dfs(ss , 1);
        }
        else if(s[0] == 'a'){
            int len = s.length();
            for(int i=2;i<len;i++){
                if(s[i] == 'b'){
                    string ss = s.substr(1 , i-1);
                    string sss = s.substr(i+1,len - i - 1);
                    //cout<<ss<<" "<<sss<<endl;
                    if(dfs(ss , 0)&&dfs(sss,1) == 1){
                        return 1;
                    }
                }
            }
            return 0;
        }
        else{
            return 0;
        }
    }else{
        if(s.length() == 0){
            return 0;
        }
        if(s[0] == 'c'){
            string ss = s.substr(1,s.length()-1);
            return dfs(ss , 1);
        }
        else if(s[0] == 'a'){
            int len = s.length();
            for(int i=2;i<len;i++){
                if(s[i] == 'b'){
                    string ss = s.substr(1 , i-1);
                    string sss = s.substr(i+1,len - i - 1);
                    if(dfs(ss , 0)&&dfs(sss,1) == 1){
                        return 1;
                    }
                }
            }
            return 0;
        }
        else{
            return 0;
        }
    }
}
string s;
int main()
{
    int t;
    cin>>t;
    for(int cas = 1;cas <= t;cas++)
    {
        cin>>s;
        printf("Pattern %d: ",cas);
        int x = dfs(s , 1);
        int y = dfs(s , 0);
        if(x || y){
            printf("More aliens!\n");
        }else{
            printf("Still Looking.\n");
        }
        if(cas != t){
            printf("\n");
        }
    }
    return 0;
}

H:

solution:

涉及知识点：排序

签到题，排序输出

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int a[3],b[3];
int main()
{
    int n;
    cin>>n;
    for(int cas = 1;cas <= n;cas++)
    {
        for(int i=0;i<3;i++){
            cin>>a[i];
            b[i] = a[i];
        }
        sort(a,a+3);
        printf("Data set #%d:\n",cas);
        printf("   Original order:");
        for(int i=0;i<3;i++)
            printf(" %d",b[i]);
        printf("\n");
        printf("   Smallest to largest:");
        for(int i=0;i<3;i++)
            printf(" %d",a[i]);
        printf("\n");
        if(cas != n)
            printf("\n");
    }
    return 0;
}