首页 > 其他分享 >[挑战记录]模拟/搜索题单

[挑战记录]模拟/搜索题单

时间：2022-10-04 19:47:40浏览次数：52  
标签：ch int make dir 搜索 WR include 模拟 题单

20221003 20:18 [省选联考2022]预处理器

\(\operatorname{string}\) 科技题

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<map>
#define WR WinterRain
#define int long long
using namespace std;
const int WR=1001000;
string modu="1234567890_abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
int n,len;
string str;
map<string,string>mp;
map<string,bool>vis;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
void def(string s){
    if(s[1]=='d'){
        int pos=s.find(" ",8);
        string name=s.substr(8,pos-8),content=s.substr(pos+1);
        mp[name]=content;
    }else{
        string name=s.substr(7);
        mp.erase(name);
    }
    printf("\n");
}
string work(string s){
    string res;
    s=" "+s+" ";
    int pos=s.find_first_of(modu,0),nxt=0;
    while(pos!=-1){
        res+=s.substr(nxt,pos-nxt);
        nxt=s.find_first_not_of(modu,pos);
        string tmp=s.substr(pos,nxt-pos);
        if(mp.count(tmp)!=0&&(!vis[tmp])){
            vis[tmp]=true;
            res+=work(mp[tmp]);
            vis[tmp]=false;
        }else res+=tmp;
        pos=s.find_first_of(modu,nxt);
    }
    res+=s.substr(nxt);
    return res.substr(1,res.length()-2);
}
signed main(){
    freopen("preprocessor.in","r",stdin);
    freopen("preprocessor.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        getline(cin,str);
        if(str[0]=='#') def(str);
        else cout<<work(str)<<endl;
    }
    return 0;
}

20221004 08:39 NOI1999生日蛋糕

这里有一个比较玄学的剪枝证明一下：
设已经做了 \(i\) 层蛋糕，则还需做 \(m-i\) 层
不妨设 \(S_i\) 为第 \(i\) 层蛋糕的侧面积，\(res_i\) 为余下 \(m-i\) 层的侧面积，\(V_i\) 为目前的体积
根据定义 \(V=\pi r^2h\)，\(S=2\pi rh\)（在这里统一删掉 \(\pi\) ）
则有：

\[\begin{aligned} 2V_i & =2\sum\limits_{j=i+1}^{m}r_{j}^2h_j \\ & = \sum\limits_{j=i+1}^{m}r_{j}S_j \\ & \leqslant r_{i+1}\sum\limits_{j=i+1}^{m}S_j\\ & = r_{i+1}\times res_i \end{aligned}\]

\(\therefore\) \(\large res_i\geqslant \frac{2V_i}{r_i}+1\)

也就是 \(\large \frac{2(n-V_i)}{r_i}+posS\geqslant ans\) 时可以剪枝（ \(posS\) 是目前的总面积）

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#define WR WinterRain
#define int long long
using namespace std;
const int WR=10010,INF=1099511627776;
int minV[WR],minS[WR];
int n,m;
int ans=INF;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
void dfs(int dpt,int posV,int posS,int lstH,int lstR){
    if(dpt==0){
        if(posV==n) ans=min(ans,posS);
        return;
    }
    if(posV+minV[dpt]>n) return;
    if(posS+minS[dpt]>ans) return;
    if(posS+2*(n-posV)/lstR>ans) return;
    for(int i=lstR-1;i>=dpt;i--){
        if(dpt==m) posS=i*i;
        int maxH=min(lstH-1,(n-posV-minV[dpt-1])/(i*i));
        for(int j=maxH;j>=dpt;j--){
            dfs(dpt-1,posV+i*i*j,posS+2*i*j,j,i);
        }
    }
}
signed main(){
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        minV[i]=minV[i-1]+i*i*i;
        minS[i]=minS[i-1]+2*i*i;
    }
    dfs(m,0,0,n,(int)sqrt(n));
    printf("%lld\n",ans);
    return 0;
}

20221004 15:38 [POJ1915]Knight moves

双向广搜模板

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<queue>
#define WR WinterRain
#define int long long
using namespace std;
const int WR=510,INF=2147483647;
pair<int,int>dir[9];
struct Node{
    int x,y,step;
};
int n;
int visst[WR][WR],vised[WR][WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
Node make_node(int _x,int _y,int _step){
    Node res;
    res.x=_x,res.y=_y,res.step=_step;
    return res;
}
int bfs(int stx,int sty,int edx,int edy){
    queue<Node>st,ed;
    visst[stx][sty]=0,vised[edx][edy]=0;
    st.push(make_node(stx,sty,0));
    ed.push(make_node(edx,edy,0));
    while((!st.empty())||(!ed.empty())){
        if(!st.empty()){
            int posx=st.front().x,posy=st.front().y,poscnt=st.front().step;
            // cerr<<"Begin : "<<posx<<" "<<posy<<" "<<poscnt<<endl;
            st.pop();
            if(vised[posx][posy]!=-1) return poscnt+vised[posx][posy];
            for(int i=1;i<=8;i++){
                int nxtx=posx+dir[i].first,nxty=posy+dir[i].second;
                // cerr<<"nxtx = "<<nxtx<<",nxty = "<<nxty<<endl;
                if(nxtx<0||nxty<0||nxtx>=n||nxty>=n||visst[nxtx][nxty]!=-1) continue;
                visst[nxtx][nxty]=poscnt+1;
                st.push(make_node(nxtx,nxty,poscnt+1));
            }
        }
        if(!ed.empty()){
            int posx=ed.front().x,posy=ed.front().y,poscnt=ed.front().step;
            ed.pop();
            if(visst[posx][posy]!=-1) return poscnt+visst[posx][posy];
            for(int i=1;i<=8;i++){
                int nxtx=posx+dir[i].first,nxty=posy+dir[i].second;
                if(nxtx<0||nxty<0||nxtx>=n||nxty>=n||vised[nxtx][nxty]!=-1) continue;
                vised[nxtx][nxty]=poscnt+1;
                ed.push(make_node(nxtx,nxty,poscnt+1));
            }
        }
    }
    return 0;
}
signed main(){
    int T=read();
    dir[1]=make_pair(-2,-1),dir[2]=make_pair(2,1),dir[3]=make_pair(-2,1),dir[4]=make_pair(2,-1);
    dir[5]=make_pair(-1,-2),dir[6]=make_pair(1,2),dir[7]=make_pair(-1,2),dir[8]=make_pair(1,-2);
    while(T--){
        n=read();
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                visst[i][j]=vised[i][j]=-1;
            }
        }
        int stx=read(),sty=read(),edx=read(),edy=read();
        printf("%lld\n",bfs(stx,sty,edx,edy));
    }
    return 0;
}

20221004 19:23 [BalticOI2011]Switch The Lamp On

双端队列优化 \(\operatorname{bfs}\) 裸题
对于不需要转向的可以从队首入队，这样就可以先搜到
需要转向就在队尾入队，搜完了不转向的才会搜这些
只要搜索的东西存在一个优先级（比如这个题里的要转向和不用转向）就可以用一个双端队列

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#define WR WinterRain
#define int long long
using namespace std;
const int WR=1001000,INF=1099511627776;
pair<int,int>pntdir[5],tbldir[5];
pair<int,int>deq[WR];
char dir[5];
int l=5e5,r=5e5;
int n,m;
char mp[1010][1010];
int dis[1010][1010];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<3)+(s<<1)+ch-'0';
        ch=getchar();
    }
    return s*w;
}
int bfs(){
    memset(dis,0x3f,sizeof(dis));
    dis[1][1]=0;
    deq[l]=make_pair(1,1);
    while(l<=r){
        // cerr<<r-l+1<<endl;
        int posx=deq[l].first,posy=deq[l].second;l++;
        for(int i=1;i<=4;i++){
            int pntx=posx+pntdir[i].first,pnty=posy+pntdir[i].second;
            int tblx=posx+tbldir[i].first,tbly=posy+tbldir[i].second;
            if(pntx<0||pntx>n+1||pnty<0||pnty>m+1) continue;
            if(mp[tblx][tbly]==dir[i]){
                if(dis[posx][posy]<dis[pntx][pnty]){
                    // cerr<<"1 - "<<posx<<" "<<posy<<" : "<<pntx<<" "<<pnty<<endl;
                    l--,deq[l]=make_pair(pntx,pnty);
                    dis[pntx][pnty]=dis[posx][posy];
                }
            }else{
                if(dis[posx][posy]+1<dis[pntx][pnty]){
                    // cerr<<"2 - "<<posx<<" "<<posy<<" : "<<pntx<<" "<<pnty<<endl;
                    r++,deq[r]=make_pair(pntx,pnty);
                    dis[pntx][pnty]=dis[posx][posy]+1;
                }
            }
        }
    }
    return dis[n+1][m+1];
}
signed main(){
    pntdir[1]=make_pair(1,1),pntdir[2]=make_pair(1,-1);
    pntdir[3]=make_pair(-1,1),pntdir[4]=make_pair(-1,-1);
    tbldir[1]=make_pair(0,0),tbldir[2]=make_pair(0,-1);
    tbldir[3]=make_pair(-1,0),tbldir[4]=make_pair(-1,-1);
    dir[1]=dir[4]='\\',dir[2]=dir[3]='/';
    n=read(),m=read();
    if((n+m)%2==1){
        printf("NO SOLUTION");
        return 0;
    }
    for(int i=1;i<=n;i++) scanf("%s",mp[i]+1);
    printf("%lld",bfs());
    return 0;
}

标签：ch,int,make,dir,搜索,WR,include,模拟,题单
From： https://www.cnblogs.com/WintersRain/p/16753157.html

相关文章

  • Cisco模拟器使用教程
    一、使用三层交换机实现跨VLAN间的通信1.vlan配置如图所示局域网，要将不同的PC机配置到不同的vlan下。在二层交换机的配置模式（即Switch(config)#）下：这里配置的端口是与P......
  • 43rd 2022/10/4 模拟赛总结30
    这次还行？rank5，其实也不是多高不可攀，就是认真打，暑假时就上过前五好多次其实比赛历程也很简单第一题很忽悠，思路乱的一批，但是这次冷静下来把思路理清就切了很简单的概率D......
  • leetcode 235. Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最近公
    一、题目大意给定一个二叉搜索树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树T的两个结点p、q，最近公共祖先表示为一个结点......
  • 一个简单的模拟实例说明Task及其调度问题
    编者荐语：蒋老师只用短短的几百行样例代码就为大家解释清楚了在C#中至关重要的Task和其调度的原理，这是不可多得的高质量文章。Task对于.NET的重要性毋庸置疑。通过最近的一些......
  • Elasticsearch搜索引擎的使用
    Elasticsearch搜索引擎的使用1.需求分析当用户在搜索框输入关键字后，我们要为用户提供相关的搜索结果。这种需求依赖数据库的模糊查询like关键字可以实现，但是like关键字......
  • 10.2模拟赛
    10.2模拟赛目录10.2模拟赛\(\to\rmlink\leftarrow\)二分图排列最短路问题V3捡石子游戏凹函数\(\to\rmlink\leftarrow\)二分图排列#include<bits/stdc++.h>using......
  • 给女朋友写的一个利用搜索引擎爬取会议论文的脚本
    importbs4,requests,osfrommultiprocessingimportManager,Pool#红色：报错defR(message):return"\033[1;91m{}\033[0;m".format(message)#绿色：成功defG......
  • this 的指向与 call, apply, bind 的模拟实现
    1.this的指向问题关于函数的this的指向并不是一个很复杂的问题我们首先要明确一个定义:fn=function(){...}指的是fn这个属性存储着一个函数的地址fn_addr,......
  • 如何不用 TeX 制作优美的 NOIP 模拟赛题面（详细揭秘）
    不用TeX制作优美的NOIP模拟赛题面是怎么回事呢？那么优美的NOIP模拟赛题面为什么会不用TeX制作，相信大家都很好奇。大家可能会感到很惊讶，那么优美的NOIP模拟赛题面......
  • CSP模拟练习赛1 https://www.luogu.com.cn/contest/82861#problems
    P1321单词覆盖还原简单思路字符串#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#include<map>#definelllonglon......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99