Frost_Delay 的博客

Frost_Delay 的博客

day10

posted on 2019-08-10 16:10:18 | under 未分类 |

今天和昨天完全不是一个难度好吧

T1考场看数据那么小,暴搜+回溯结果TLE;得分80;

正解先BFS处理水,再遍历人;

T2DP,想不出方程写了个搜索,得分95(数据太水)

正解状压DP

T3不会做,听完正解是单调栈;

T4图论不会做,听完正解是先判断环在不在1到2的路上,然后找DAG统计路径数;

T1洪水

#include<iostream>
#include<cstdio>
using namespace std;
int mp[60][60],n,m,water[60][60],xx,yy,xw[2510],yw[2510],l=1,r=1,dx[5]={0,1,-1,0,0},dy[5]={0,0,0,1,-1},ans=0x7fffff,v[60][60],f[60][60];
char c;
void home(int x,int y,int tim)
{
    if(f[x][y]<=tim)return;
    f[x][y]=tim;
    if(mp[x][y]==2){
        ans=ans<tim?ans:tim;
        return;
    }
    for(int i=1;i<=4;i++)
    {
        if(mp[x+dx[i]][y+dy[i]]&&water[x+dx[i]][y+dy[i]]>tim+1&&!v[x+dx[i]][y+dy[i]])
        {
            v[x+dx[i]][y+dy[i]]=1;
            home(x+dx[i],y+dy[i],tim+1);
            v[x+dx[i]][y+dy[i]]=0;
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        cin>>c;
        f[i][j]=water[i][j]=0x7fffff;
        if(c=='.')mp[i][j]=1;
        if(c=='*'){
            xw[r]=i;
            yw[r]=j;
            r++;
            mp[i][j]=1;
            water[i][j]=1;
        }
        if(c=='X')mp[i][j]=0;
        if(c=='D')mp[i][j]=2;
        if(c=='S'){
            xx=i;yy=j;mp[i][j]=1;
        }
    }
    while(l<r)
    {
        v[xw[l]][yw[l]]=1;
        for(int i=1;i<=4;i++)
        {
            if(mp[xw[l]+dx[i]][yw[l]+dy[i]]==1&&!v[xw[l]+dx[i]][yw[l]+dy[i]])
            {
                water[xw[l]+dx[i]][yw[l]+dy[i]]=water[xw[l]][yw[l]]+1;
                xw[r]=xw[l]+dx[i];yw[r]=yw[l]+dy[i];
                r++;
            } 
        }
        l++;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    v[i][j]=0;
    home(xx,yy,1);
    if(ans!=0x7fffff)
    cout<<ans-1<<endl;
    else cout<<"KAKTUS"<<endl;
    return 0;
}

T2邦德

#include<iostream>
#include<cstdio>
using namespace std;
double max(double x,double y){return x>y?x:y;}
int n;
double a[21][21],f[(1<<20)+1];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    cin>>a[i][j],a[i][j]/=100;
    int tot=1<<n;
    f[0]=100;
    for(int i=0;i<tot;i++)
    {
        int gs=0;
        for(int j=i;j;j>>=1)
        if(j&1)gs++;
        for(int j=1;j<=n;j++)
        if(i&(1<<(j-1)))
        f[i]=max(f[i],f[i^(1<<j-1)]*a[gs][j]);
    }
    printf("%.6lf\n",f[tot-1]); 
    return 0;
}

T3餐桌 50分暴力

#include<iostream>
#include<cstdio>
using namespace std;
int s[2100][2100],n,c,ans=-1;
char a[2100][2100];
int main()
{
    cin>>n>>c;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=c;j++)
    cin>>a[i][j];
    for(int i=1;i<=n;i++)
    for(int j=1;j<=c;j++)
    if(a[i][j]=='X')s[i][j]=s[i][j-1]+1;
    else s[i][j]=s[i][j-1];
    for(int l=1;l<=c;l++)
    for(int r=l;r<=c;r++)
    {
        int maxx=0,len=0;
        for(int i=1;i<=n;i++){
            if(s[i][r]-s[i][l-1]==0){len++;
            maxx=maxx>len?maxx:len;} 
            else len=0;
        }
        if(!maxx)continue;
        ans=max(ans,2*(maxx+r-l+1)-1);
    }
    cout<<ans<<endl;
    return 0;
}

100分单调栈

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
using namespace std;
int r,c,sum[2001][2001],ans=-1;
char cc;
struct node{
    int x,y;
}k;
stack <node> s;
node nod(int x,int y)
{
    k.x=x;k.y=y;
    return k;
}
int main()
{
    cin>>r>>c;
    for(int i=1;i<=r;i++) 
    for(int j=1;j<=c;j++)
    {
        cin>>cc;
        if(cc=='.')
        sum[i][j]=sum[i-1][j]+1;
    } 
    for(int i=1;i<=r;i++)
    {
        while(!s.empty())
        s.pop();
        s.push(nod(sum[i][1],1));
        for(int j=2;j<=c+1;j++)
        {
            int yi=0,xi;
            while(!s.empty() &&s.top().x>sum[i][j])
            {
                xi=s.top().x;
                yi+=s.top().y;
                s.pop() ;
                ans=max(ans,(xi+yi)*2);
            } 
            s.push(nod(sum[i][j],yi+1)); 
        }
    }
    cout<<ans-1<<endl;
    return 0;
}

tips:

原c++栈的方法的基本用法:
1.push(): 向栈内压入一个成员;
2.pop(): 从栈顶弹出一个成员;
3.empty(): 如果栈为空返回true,否则返回false;
4.top(): 返回栈顶,但不删除成员;
5.size(): 返回栈内元素的大小;

T4自行车比赛