首页 > 其他分享 >YL 模拟赛总结 3

YL 模拟赛总结 3

时间:2024-03-02 21:45:37浏览次数:22  
标签:总结 YL int top ny ans 1031 模拟 dis

Problem


T1

累加燃烧度,除以 \(m\) 即为答案。

需要开 unsigned __int128,差评。

T2

若有 \(a,b\) 满足 \(a-c=c-b\),化简此式可得 \(a+b=2c\),说明 \(a+b\) 必须为偶数。

于是我们倒序求一遍后缀偶数个数 \(os_i\) 和奇数个数 \(js_i\);

然后枚举每一个 \(i\),若它是奇数,则它可以和它后面的 \(js_i-1\) 个奇数配对,否则可以和它后面的 \(os_i-1\) 个偶数配对。依次累加贡献即可。

T3

用队列维护口味值,令 \(cnt\) 为队列中的不同口味值数量,\(t_i\) 为口味值为 \(i\) 的数量。

先将口味值依次入队,直到其中有 \(m\) 种不同的口味,并且在入队的过程中更新 \(t_i\)。

然后不断弹出队首(即第 \(m\) 种口味),直到第 \(m\) 种口味消失,此时更新 \(ans\) 为 \(\max(ans,top-i+1)\)(\(i\) 是弹出前的队首,\(top\) 是当前队首)。

重复上述操作 \(n\) 次即可得到答案。

#include<bits/stdc++.h>
using namespace std;

int n,m,ans=1e9,a[100031];
int cnt,top,t[100031];

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    while(cnt!=m){
        top++;
        if(top>n) break;
        if(!t[a[top]]) cnt++;
        t[a[top]]++;
    }
    ans=min(ans,top);
    for(int i=1;i<=n&&top<=n;i++){
        t[a[i]]--;
        if(t[a[i]]) continue;
        ans=min(ans,top-i+1);
        cnt--;
        while(cnt!=m){
            top++;
            if(top>n) break;
            if(!t[a[top]]) cnt++;
            t[a[top]]++;
        }
    }
    cout<<ans;
    return 0;
}

T4

简单 bfs。

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

int n,ans=1e9,xa,ya,xb,yb;
char mp[1031][1031];
int dis[2][1031][1031];
int dx[]={0,0,1,-1},dy[]={1,-1,0,0};

void upd(int x,int y,int nx,int ny,queue<pii> &q,int d[1031][1031]){
    if(d[nx][ny]==-1&&mp[nx][ny]=='0'){
        d[nx][ny]=d[x][y]+1;
        q.push(make_pair(nx,ny));
    }
}
void bfs_z(int sx,int sy){
    queue<pii> q;
    memset(dis[0],-1,sizeof(dis[0]));
    for(upd(0,0,sx,sy,q,dis[0]);!q.empty();q.pop()){
        int x=q.front().first,y=q.front().second;
        for(int i=0;i<4;i++){
            upd(x,y,x+dx[i],y+dy[i],q,dis[0]);
            if(mp[x+dx[i]][y+dy[i]]=='0')
                for(int j=0;j<4;j++) upd(x,y,x+dx[i]+dx[j],y+dy[i]+dy[j],q,dis[0]);
        }
    }
}
void bfs_m(int sx,int sy){
    queue<pii> q;
    memset(dis[1],-1,sizeof(dis[1]));
    for(upd(0,0,sx,sy,q,dis[1]);!q.empty();q.pop()){
        int x=q.front().first,y=q.front().second;
        for(int i=0;i<4;i++){
            upd(x,y,x+dx[i],y+dy[i],q,dis[1]);
            if(mp[x+dx[i]][y+dy[i]]=='1') upd(x,y,x+2*dx[i],y+2*dy[i],q,dis[1]);
        }
    }
}

int main(){
    cin>>n>>xa>>ya>>xb>>yb;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>mp[i][j];
    bfs_z(xa,ya),bfs_m(xb,yb);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(mp[i][j]=='0'&&dis[0][i][j]!=-1&&dis[1][i][j]!=-1)
                ans=min(ans,max(dis[0][i][j],dis[1][i][j]));
    cout<<ans;
    return 0;
} 

标签:总结,YL,int,top,ny,ans,1031,模拟,dis
From: https://www.cnblogs.com/XOF-0-0/p/18049280

相关文章

  • 2023-2024第一学期的助教工作总结(教务处老师助教)
    一.帮助老师整理开会后的电子版例会总结,整理各类考试试卷以及完成各类文档二.助教工作的每周时长不定,具体安排是整理电子版例会总结和整理考试试卷三.目前我自己的助教工作还处在初阶阶段,主要是帮助老师处理事情,老师平时很忙,平时帮助老师处理一些小事情,也为老师腾出时间来更......
  • 数学之概率题目总结
    前言如有错误,欢迎各位dalao指出。前置芝士:概率T1题目传送门可以看见,标签是入门,一定非常水。显然,要让小D获胜,我们只需要选出\(max(v,w)\rightarrow6\)这一段的任意一个值即可获胜,注意特判一下\(max(v,w)>6\)的情况就行了。还是比较水。T2题目传送门老师抽我起......
  • 0/1分数规划总结
    前言最近在搞什么树套树,博弈论,啥啥啥的,时间实在紧迫,就先拿0/1规划开刀。0/1分数规划是什么实际上是一类问题。顾名思义,0/1即对于\(n\)个物品,选择或者不选择。分数,即对于每个物体,有两个属性\(a_i,b_i\),选出物品的价值就是\(\dfrac{\suma_i\timesd_i}{\sumb_i\tim......
  • 每日总结
    1.在java中,数组是一个对象,不是一种原生类,对象所以存放在堆中,又因为数组特性,是连续的。2.用户不能调用构造方法,只能通过new关键字自动调用。这句话是错误的。在类内部可以用户可以使用关键字this.构造方法名()调用(参数决定调用的是本类对应的构造方法)在子类中用户可以通过......
  • Linux_Centos_yum报错总结
    ​此篇适用于yum报错【尝试其他镜像】并且【curl外网】不通的情况,此时一般考虑是网络的问题一,出现的报错信息: 此时测试curl/pingwww.baidu.com会发现无法连通 二,解决方法:1,首先查看dns的配置文件/etc/resolv.conf检查这里的nameserver这里有时候会因为第二个网卡......
  • YL 模拟赛总结 15
    ProblemT1感觉是最难的。考虑贪心。首先对牛的按左端点进行排序,然后对于每只鸡去考虑匹配哪头牛。具体地,开一个小根堆,然后对于每只鸡\(t_i\),将\(a_i\let_i\)的牛放入堆中,此时堆中存放的是候选的牛。然后对于堆中的牛,将\(b_i<t_i\)的牛弹出。此时堆中的牛均是合法的......
  • YL 模拟赛总结 14
    Problem省流:三道题写了tjT1见tj。T2见tj。T3见tj。T4二分求出左右端点即可。#include<bits/stdc++.h>usingnamespacestd;intn,q;intp[200031];intmain(){//freopen("haybales.in","r",stdin);//freopen("haybales.out",&quo......
  • YL 模拟赛总结 13
    ProblemT1略。T2略。T3考虑对于每一头向北的牛,计算它能够挡住/被挡住几头向东的牛。一头向北的牛\(i\)能够被向东的牛\(j\)挡住的条件是:\(x_i<x_j\)且\(y_i<y_j\)(\(x_i,y_i\)分别表示牛\(i\)的\(x\)坐标与\(y\)坐标);\(l_j\)没有被更新(\(l_i\)表示第......
  • YL 模拟赛总结 12
    ProblemT1略。T2最理想的情况当然是奇偶交替,每个数单独成为一组。考虑不理想的情况:偶数个数\(>\)奇数个数,此时需要可以先奇偶交替,再将最后剩下的偶数单独分为一组,答案为奇数个数\(\times\2+1\)。奇数个数\(>\)偶数个数,此时再分出两种情况:若奇数个数\(-\)......
  • YL 模拟赛总结 10
    ProblemT1二分板子。对于\(c_i\)降序排序,然后二分\(h\)指数,在check中贪心地使用综述增加引用次数即可。T2通过观察可以发现,在一篇论文的贡献列表中,若某一位置出现了比它前面的名字的字典序更小的情况,则说明从这个位置开始,后面的人的资历一定\(\ge\)前面的人。根据......