首页 > > 程序设计 > C/C++ >

2020年04月10日UCF Local Programming Contest 2…

2020-04-10 16:00:35来源：博客园阅读 ()

2020年04月10日UCF Local Programming Contest 2017

A. Electric Bill

题意:这一题比较简单，相当于小学的分组函数的计算电力费用的的题型。

题解：签到题。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    int F,E;
    int n;
    cin>>F>>E;
    cin>>n;
    int temp;
    while(n--){
        cin>>temp;
        int ans=0;
        cout<<temp<<" ";
        if(temp<=1000){
            cout<<temp*F<<endl;
        }else{
            cout<<1000*F+(temp-1000)*E<<endl;;
        }
    }
    return 0;
}

B. Simplified Keyboard

题意：这一题的大概意思就是新组合的字母的排列，给出了字母间相邻的定义。题目给出两个字符串，要你在题目要求的情况下判断这两个字符串属于哪一种类型。

题解：简单签到题，根据题意对那个字符串进行分情况判断，在判断两个字符是否是“邻居”时候，可利用：

net[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1}};

进行每个方向的判断。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
char arr[3][9]= {{'a','b','c','d','e','f','g','h','i'},
    {'j','k','l','m','n','o','p','q','r'},
    {'s','t','u','v','w','x','y','z','#'}
};
int net[8][2]={{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,-1},{-1,1}};
int check(int r,int c){
    if(r>=0&&r<3){
        if(r==2){
            if(c>=0&&c<=7){
                return 1;
            }
        }else{
            if(c>=0&&c<=8){
                return 1;
            }
        }
    }
    return 0;
}
int app(char a/*主体*/,char b/*客体*/){//是否是相邻的 
    int x,y;
    for(int i=0;i<3;i++){//找到 本尊的位置 
        for(int j=0;j<9;j++){
            if(arr[i][j]==a){
                x=i;
                y=j;
                break;
            }
        } 
    }
    int d=0;
    for(int i=0;i<8;i++){
        int dx=x+net[i][0];
        int dy=y+net[i][1];//这是下一个坐标
        if(check(dx,dy)/*判断坐标是否合法*/){
            if(arr[dx][dy]==b){//相等
            d=1;
            break;
            }else{//不相等 
            }
        } 
    }    
    return d;
}
int main() {
    int n;
    string str1,str2;
    cin>>n;
    while(n--) {
        cin>>str1>>str2;
        int len1=str1.length();
        int len2=str2.length();
        if(len1!=len2) {
            cout<<3<<endl;
        } else { //两者的长度相同  在这里，可能输出 1 ，可能输出 2 ，可能输出 3
            int f=1;
            for(int i=0; i<len1; i++) {
                if(str1[i]!=str2[i]) { //出现了不相等的
                    f=0;
                }
            }
            if(f==1) {
                cout<<1<<endl;
            } else { //可能输出 2 ，可能输出 3
                //以 str1 为基础，寻找它的邻居，或和它本身相邻
                int g=1;//记录是否找到 邻居
                for(int i=0; i<len1; i++) {
                    if(str1[i]==str2[i]) { //若两者相等
                    } else { //两者不相等，找两者相邻
                        g=app(str1[i],str2[i]);
                        if(!g) {
                            break;
                        }
                    }
                }
                if(g) {
                    cout<<2<<endl;
                } else {
                    cout<<3<<endl;
                }
            }
        }
    }
    return 0;
}

C. Singin' in the Rain

题意：题目的大概意思就是：给出一张CD的歌曲数目，一串喜欢歌曲的序列，通过按下“下一曲”、“上一曲”的按键来改变曲目的播放顺序，要你求，最少要你按多少次才能达到要求。

题解：注意播放顺序的改变规则即可，模拟。

#include<iostream>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int main(){
    ll n;//样例的数量 
    cin>>n;
    ll t,s;
    while(n--){
        cin>>t/*一张CD上的歌曲的总数*/>>s/*喜欢歌曲的数量*/;
        ll num[10000]={0};
        for(ll i=0;i<s;i++){
            cin>>num[i];//输入喜欢歌曲的序号 
        }//序号输入完毕，下面开始处理啊数据
        ll ans=0;//存储的是答案
        ll tt=num[0];//当前播放歌曲的位置
        //当第一首歌曲播放完之后。
        ll net;//下一首要播放的歌曲
        for(ll i=1;i<s;i++){
            net=num[i];//这是下一首 
            if(net<num[i-1]){//在它之前 
                ans=ans+min(num[i-1]-net+1,t-num[i-1]-1+net);
            }else if(net>num[i-1]){//在之后 
                if(net-num[i-1]==1){//不需要按 
                }else{//需要按 
                    ans=ans+min(net-num[i-1]-1,num[i-1]+(t-net+1));
                }
            }else if(net==num[i-1]){//下一首播放的歌曲和上一首播放的歌曲一样 
                ans++;//往后在按一次 “后退键 ”
                tt=net;//在一次到达原位置 
            }
            //当前歌曲播放完
        }
        cout<<ans<<endl;
    }
    return 0;
}

D. Editor Navigation

题意：这题是一个最短路的问题，给你两个点的坐标，要你求移动最少的次数到达目的地，创新的是它给出的不是一个“规矩”的矩阵，移动的规则也和正常的题目有点不同，

题解：BFS求最短路，但要注意在确定它的下一个坐标的时候和正常的题型不同。最短路的步数和点的坐标一起整合在一个结构体中。

代码：

#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int T,n;
int str,stc,enr,enc;
int num[900]={0};
int vis[900][900]={0};
struct node{
    int r,c,cnt;
};
int net[4][2]= {-1,0,1,0,0,-1,0,1};
void bfs(){
    queue<node> q;
    q.push({str,stc,0});
    vis[str][stc]=1;
    memset(vis,0,sizeof(vis));
    while(!q.empty()){
        node p=q.front();
        q.pop();
        int r=p.r;
        int c=p.c;
        int cnt=p.cnt;
        if(r==enr&&c==enc){//找到目标点 
            printf("%d\n",cnt);
            return ;
        }
        for(int i=0;i<4;i++){//遍历四个方向 
            int dr=r+net[i][0];
            int dc=c+net[i][1];
            if(dr>=1&&dr<=n){
                if(i==0||i==1){//上下移动
                    if(dc<=num[dr]&&!vis[dr][dc]){//直来支直去
                        vis[dr][dc]=1;
                        q.push({dr,dc,cnt+1});
                    }
                    if(dc>num[dr]&&!vis[dr][num[dr]]){
                        vis[dr][num[dr]]=1;
                        q.push({dr,num[dr],cnt+1});
                    }
                }else{//左右移动
                    if(dc==-1&&i==2&&r-1>=1){
                        int tr=r-1;
                        int tc=num[tr];
                        if(!vis[tr][tc]){
                            q.push({tr,tc,cnt+1});
                            vis[tr][tc]=1;
                        }
                    }
                    if(dc==num[r]+1&&i==3&&r+1<=n){//这是坐标向右移动，处在最后的一个点移动到下一行的的第一个字符
                        int tr=r+1;
                        int tc=0;
                        if(!vis[tr][tc]){
                            vis[tr][tc]=1;
                            q.push({tr,tc,cnt+1});
                        }
                    }
                    if(dc>=0&&dc<=num[dr]&&!vis[dr][dc]){
                        vis[dr][dc]=1;
                        q.push({dr,dc,cnt+1});
                    }
                }
            }
        }
    }
}
int main(){
    cin>>T;
    while(T--){
       cin>>n;/*总共有几行*/
       for(int i=1;i<=n;i++){
            cin>>num[i];
       }
       cin>>str>>stc>>enr>>enc;
       bfs();
    }
    return 0;
}

E. Simple Darts

题意：这是一道反三角函数利用的题目，给你一个圆盘，将其划分为W个区域，每个区域的得分各不相同，向其投向n个镖，求出最终得分。

题解：通过计算点到原点的距离，可以判断它属于那个环内，通过计算点与原点的连线和X轴的夹角可以判断它属于内阁楔形--这个的计算方法是：

double gf=atan((y*1.0)/x)*(180.0*1.0/pi);//算出应有的角度

gf是指点（x,y）与x轴所夹的锐角，但要注意当返回的是一个负值时，可以通过增加180度or360度来进行调整，具体增加多少，要根据点所处的象限来判断。

代码：

#include<iostream>
#include<cstring>
#include<algorithm>
#include<math.h>
#define ll long long
double pi= 3.1415926535898 ;
using namespace std;
double app(double x,double y){
    return sqrt(x*x+y*y);
}
int main(){
    int n,t;
    int w,b,d,s;
    double x,y;
    cin>>n;//样例的数量 
    while(n--){
        cin>>w>>b>>d>>s;
        //圆形平均分成了 w 份
        double cc=360*1.0/w;//每一份的度数
        double tch[25]={0};
        tch[1]=cc;
        for(int i=2;i<=w;i++){
            tch[i]=tch[i-1]+cc;
        }
        cin>>t;
        int ans=0;//存储最终得分 
        //边输入，边处理 
        for(int i=0;i<t;i++){
            scanf("%lf %lf",&x,&y);//输入两个点的坐标
            double len1=app(x,y);
            if(len1<=b){//位于  第一个小圆环中  
                ans=ans+50;
            }else{
                int f=0;//这是放大的倍数
                if(len1>b&&len1<d){
                    f=2;
                }else if(len1>d&&len1<s){
                    f=1;
                }
                //下面关键是判断位于哪一个楔形内 
                double gf=atan((y*1.0)/x)*(180.0*1.0/pi);//算出应有的角度
                //判断是否要选装
                if(x<0&&y>0){//二象限 
                    gf=180+gf;
                }
                if(x<0&&y<0){//三象限 
                    gf=gf+180;
                }
                if(x>0&&y<0){
                    gf=gf+360;
                }
                int gg=0; 
                for(int i=1;i<=w;i++){
                    if(gf<tch[i]){//在这之中 
                        gg=i;
                        break;
                    }
                }
                ans=ans+gg*f;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}