最后一次新生赛 B+C+D
发布日期:2021-09-25 23:57:36 浏览次数:0 分类:技术文章

本文共 5094 字,大约阅读时间需要 16 分钟。

A题:数据很小,直接爆搜就行。

B题:
青铜莲花池
时间限制: 1 Sec 内存限制: 128 MB
题目描述
为了让奶牛们娱乐和锻炼,农夫约翰建造了一个美丽的池塘。这个长方形的池子被分成了M行N列个方格(1 ≤ M, N ≤ 30)。一些格子是坚固得令人惊讶的莲花,还有一些格子是岩石,其余的只是美丽、纯净、湛蓝的水。
贝西正在练习芭蕾舞,她站在一朵莲花上,想跳到另一朵莲花上去,她只能从一朵莲花跳到另一朵莲花上,既不能跳到水里,也不能跳到岩石上。
贝西的舞步很像象棋中的马步:每次总是先横向移动M1 (1 ≤ M1 ≤ 30)格,再纵向移动M2 (1 ≤ M2 ≤ 30, M1 M2)格,或先纵向移动M1格,再横向移动M2格。最多时,贝西会有八个移动方向可供选择。
给定池塘的布局和贝西的跳跃长度,请计算贝西从起点出发,到达目的地的最小步数,我们保证输入数据中的目的地一定是可达的。

输入
第一行:四个用空格分开的整数:M,N,M1和M2
第二行到M + 1行:第i + 1行有N个用空格分开的整数,描述了池塘第i行的状态:0 为水,1 为莲花,2 为岩石,3 为贝西所在的起点,4 为贝西想去的终点。

输出
一个整数,表示从起点到终点的最少步数
样例输入 Copy
4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
0 0 0 1 0
样例输出 Copy
2
提示
贝西从第二行的最左边出发,目标是第二行的最右边。贝西先跳到第一行第三列的莲花上,再跳到终点,需要两步。

一个简单的bfs模板题,方向数组跟马走日一个写法,不过把 1 和 2 换成 m1 m2 就是了,再注意一下check可不可走的时候,有俩位置不能走,一个是0 一个是2 ,此处 wa+2。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=50,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n,m;int m1,m2;int ex,ey;int mp[N][N];bool st[N][N];struct Node{    
                
int x,y;
int step;};queue q;bool check(int x,int y){    
if(st[x][y]||x<1||y<1||x>n||y>m||mp[x][y]==2||mp[x][y]==0)
return true;
return false;}int bfs(){    
int dir[8][2]={    m1,m2,m1,-m2,-m1,-m2,-m1,m2,m2,m1,m2,-m1,-m2,m1,-m2,-m1};
while(q.size())
{    
Node t=q.front();
q.pop();
if(mp[t.x][t.y]==4)
return t.step;
for(int i=0;i<8;i++)
{    
int dx=t.x+dir[i][0];
int dy=t.y+dir[i][1];
if(check(dx,dy))
continue;
q.push({    dx,dy,t.step+1});
st[dx][dy]=true;
}
}
return 0;}int main(){    //
ios::sync_with_stdio(false);//
cin.tie(0);
scanf("%d%d%d%d",&n,&m,&m1,&m2);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{    
scanf("%d",&mp[i][j]);
if(mp[i][j]==3) 
{    
q.push({    i,j,0});
st[i][j]=true;
}
}
int t=bfs();
cout< <
return 0;}

C题:
排队出发
时间限制: 1 Sec 内存限制: 128 MB

题目描述
神牛岛是传说中的一个岛屿,凡是成功到那里游历,完成探险并返回的人,都会成为神牛。但是,现实中却没有人知道如何到达神牛岛。
这天夜里,笃志者睡着之后,不久就进入了梦乡。他突然看到有人在问,“有人想去神牛岛的吗?”神牛岛之旅的牌子前,就开始有不少勇士报名要去冒险探索。
“我们会把勇士安排在前,带领大家一起去神牛岛。下面开始点名!”管理队伍的 LXY 神牛说。其实说实话,给学生排队这种工作是最让神牛头疼的了。因为同学们都有自尊心,都不愿意排后面。共有 n 个同学要排成一列,每个同学有两个属性:影响力和承受能力。给一个同学造成的心理创伤指数等于所有在他前面同学的影响力之和减去他的承受能力。现在请你帮忙安排一下点名顺序,尽量使受到心理创伤最大的同学少受创伤。
输入
输入包含n+1行:
第1行是整数n,表示同学的个数。
第2~n+1行每行两个自然数,分别是该同学的影响力和承受能力。
输出
输出包含1行,为你安排的顺序中受到心理创伤最大的同学受到的创伤。
样例输入 Copy
3
10 3
2 5
3 3
样例输出 Copy
2
提示
对于100%的数据,1<=n<=50000,1<=影响力<=10000,1<=承受能力<=1,000,000,000。

贪心题,可能是二分做多了,上去想了一会二分想不出来,就放弃了。
先说下结论把,按照 a [ i ] + b [ i ] < a [ j ] + b [ j ] 排序,a是影响力,b是承受力。
以下个人观点,欢迎大佬纠错。
下面说一下怎么找出来的吧,具体的证明不是很会用语言描述,应该跟 耍杂技的牛 的证法差不多,用临项交换法即可整出来,但是贪心题不一定要都整出来,ac就行了不是(狗头保命),所以可以观察一下下面的式子:
(1) sum + a [ i ] - b [ j ]
(2) sum + a [ j ] - b [ i ]
其中 i 和 j 为相邻两项,sum为 i 之前的影响力之和,第一个式子是 i 在 j 前面,第二个是 j 在 i 前面,发现好像可按照 a [ i ] - b [ j ] < a [ j ] - b [ i ] 的顺序排,换一下位置就是 a [ i ] + b [ i ] < a [ j ] + b [ j ] 了。
还要注意一下 ans 初始的时候赋值为尽可能小的数 ,因为可能是负的。。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=50010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n;LL sum,ans=-1e18;struct Node{    
                
LL x,y;
bool operator < (const Node & W) const 
{    
return x-W.y
}}a[N];int main(){    //
ios::sync_with_stdio(false);//
cin.tie(0);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld%lld",&a[i].x,&a[i].y);
sort(a+1,a+1+n);
for(int i=1;i<=n;i++)
{    
ans=max(ans,sum-a[i].y);
sum+=a[i].x;
}
printf("%lld\n",ans);
return 0;}

D题:
窗口
时间限制: 1 Sec 内存限制: 128 MB

题目描述
在当今流行的操作系统中,我们要对许许多多的窗口进行操作,屏幕上的每个窗口都是由许多单位为 1 的小方块构成的矩形窗,较晚打开的窗口会将一些早期打开的窗口覆盖。我们可以用鼠标单击一个窗口的右上角的小方块将该窗口关闭,前提是该窗口的右上角的小方块必须是看得见的。
写一个程序计算一下如果我们要关闭最早打开的那个窗口,最少需要按几下鼠标(关闭窗口的方法只能靠点击该窗口右上角的小方块实现)
输入
第一行,一个整数N,表示窗口的总数,其中1≤N≤100;
在接下来的N行中每一行都有4个用空格隔开的整数R1、S1、R2、S2,其中1≤R1≤R2≤10000,1≤S1≤S2≤10000。R1,S1为窗口的左上角坐标,R2、S2为窗口的右下角坐标,窗口打开的次序就是数据给出的次序。
输出
仅一行,包含一个整数表示关闭第一个窗口需要的鼠标最少点击几次。
样例输入 Copy
3
3 1 6 4
1 2 4 6
2 3 5 5
样例输出 Copy
3

一个 递归+分治 的题 ,把大问题化成小问题,要关掉第一个窗口,那么需要检查一下那些窗口覆盖了第一个窗口的右上角,需要将这些窗口关掉,让后递归处理需要关闭的每一个窗口,处理方法跟关掉第一个窗口方法一样。
具体的细节在代码都有体现。

#include
   
    #include
    
     #include
     
      #include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define X first#define Y secondusing namespace std;typedef long long LL;typedef pair
               
                 PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;int n;LL ans;struct Node{    
                
int x1,y1;
int x2,y2;
int f;//f 为1表示还没关,为0表示关掉了 }a[N];void dfs(int x){    
int c=a[x].x1,d=a[x].y2;//找到右上角 
for(int i=x+1;i<=n;i++)
{    
if(a[i].f==0) continue;//如果已经关掉了,就不需要考虑 
int x1=min(a[i].x1,a[i].x2),x2=max(a[i].x1,a[i].x2);//得到该窗口覆盖的x的范围 
int y1=min(a[i].y1,a[i].y2),y2=max(a[i].y1,a[i].y2);//得到该窗口覆盖的y的范围
if(c>=x1&&c<=x2&&d>=y1&&d<=y2)
{    
ans++; 
a[i].f=0;
dfs(i);//递归处理第i个窗口 
}
}}int main(){    //
ios::sync_with_stdio(false);//
cin.tie(0);
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2),a[i].f=1;
dfs(1);
printf("%lld\n",ans+1);//+1是要关掉第一个窗口
return 0;}

转载地址:https://blog.csdn.net/DaNIelLAk/article/details/105755256 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:upc 工作团队 并查集 + 虚父节点
下一篇:upc 马拉松比赛 dp

发表评论

最新留言

网站不错 人气很旺了 加油
[***.238.104.143]2022年07月07日 16时30分47秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章