day10
Frost_Delay
2019-08-10 16:10:18
今天和昨天完全不是一个难度好吧
T1考场看数据那么小，暴搜+回溯结果TLE；得分80；
正解先BFS处理水，再遍历人；
T2DP，想不出方程写了个搜索，得分95（数据太水）
正解状压DP
T3不会做，听完正解是单调栈；
T4图论不会做，听完正解是先判断环在不在1到2的路上，然后找DAG统计路径数；
T1[洪水](https://www.luogu.org/problem/P4328)
```cpp
#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[邦德](https://www.luogu.org/problem/P4329)
```cpp
#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[餐桌](https://www.luogu.org/problem/P4417)
50分暴力
```cpp
#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分单调栈
```cpp
#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：
```cpp
原c++栈的方法的基本用法：
1.push(): 向栈内压入一个成员；
2.pop(): 从栈顶弹出一个成员；
3.empty(): 如果栈为空返回true，否则返回false；
4.top(): 返回栈顶，但不删除成员；
5.size(): 返回栈内元素的大小；
```
T4[自行车比赛](https://www.luogu.org/problem/P4645)