0%

2019.11.2jzoj膜你赛

吐槽一下,我们开题目的时候
机房不约而同的说了句
“卧槽!”
因为有5道题,重点是名字贼长qaq

|0|死者之魂推动遇难船|
|1|在食人百货绽放的蓝蔷薇|
|2|愚者指名自己的辩护人|
|3|对布满灰尘的西洋棋宣告将军|
|4|战马列队|

喵喵喵?
还有学长过来凑热闹

avatar

好了好了题解如下啦
题目链接

一、死者之魂推动遇难船
水!好多水啊!
其实就是一道搜索,只要符合
1.在图的边上;
2.且可以被水淹没
3.当前位置没有障碍
就扩展嘛,像细胞那样子做就ok遇到障碍就返回
如果是为0就扩展

Code:

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

#pragma GCC optimize (2)
#pragma G++ optimize (2)

int n,m,h,f[1100][1100];
int yd[5][2];

inline int read(){
int x,f;
char ch;
ch=getchar();
x=0;f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}

inline void find(int x,int y){
int p[1000000][2]={0};
int i,j;
i=0;j=1;
p[1][1]=x;
p[1][2]=y;
while(i<j){
i++;
for(int k=1;k<=4;k++){
int xx=p[i][1]+yd[k][1];
int yy=p[i][2]+yd[k][2];
if(f[xx][yy]==3){
j++;
p[j][1]=xx;
p[j][2]=yy;
f[xx][yy]=2;
}
}
}
}

int main(){
char ch;
freopen("cruise.in","r",stdin);
freopen("cruise.out","w",stdout);
yd[1][1]=0;yd[1][2]=1;
yd[2][1]=0;yd[2][2]=-1;
yd[3][1]=1;yd[3][2]=0;
yd[4][1]=-1;yd[4][2]=0;
n=read();
m=read();
h=read();
for(int i=n;i>=1;i--){
for(int j=1;j<=m;j++){
cin>>ch;
f[i][j]=ch-48;
}
}
for(int i=1;i<=h;i++){
for(int j=1;j<=m;j++){
if(f[i][j]==0)f[i][j]=3;
}
}
for(int i=1;i<=m;i++){
if(f[1][i]==3){
f[1][i]=2;
find(1,i);
}
if(f[n][i]==3){
f[n][i]=2;
find(n,i);
}
}
if(h>n)h=n;
for(int i=1;i<=h;i++){
if(f[i][1]==3){
f[i][1]=2;
find(i,1);
}
if(f[i][m]==3){
f[i][m]=2;
find(i,m);
}
}
for(int i=n;i>=1;i--){
for(int j=1;j<=m;j++){
if(f[i][j]==3)printf("0");
else printf("%d",f[i][j]);
}
printf("\n");
}
return 0;
}

二、在食人百货绽放的蓝蔷薇
这道题只要按照题意判断就可以了
就是一个类似于W的东西
但是!
注意,M字形(具体看样例的第二个

Code:

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

long long n,m,h,f[500000],t;

inline int read(){
int x,f;
char ch;
ch=getchar();
x=0;f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}

int main(){
freopen("rose.in","r",stdin);
freopen("rose.out","w",stdout);
t=read();
n=read();
while(t!=0){
t--;
for(int i=1;i<=n;i++){
f[i]=read();
}
int d=1,tot=0,flag=1;
for(int i=2;i<=n;i++){
if(f[i-1]>f[i]&&d==1&&i==2){
printf("NIE\n");
flag=-1;
}else if(f[i-1]<f[i]&&d==0){
tot+=d;
d=1;
}else if(f[i-1]>f[i]&&d==1){
tot+=d;
d=0;
}else if(f[i-1]==f[i]){
printf("NIE\n");
flag=-1;
}
}
if(tot==2&&flag==1)printf("TAK\n");
else if(flag==1)printf("NIE\n");
for(int i=1;i<=n;i++)f[i]=0;
}
return 0;
}

三、愚者指名自己的辩护人
先用Floyd求最安全的路径,
暴力去掉每一个点,做N遍Floyd,判断安全的概率有没有变低,变低则该点一定在逃跑的路径上。
时间复杂度O(N^4)。
(这也能过?!

Code:

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

int n,m,f[200],ans[300];
double a[300][300],b[300][300];

inline int read(){
int x,f;
char ch;
ch=getchar();
x=0;f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}

inline void floyd(int x){
for (int k=1;k<=n;k++){
for (int i=1;i<=n;i++){
for (int j=1;j<=n;j++){
if ((i!=j)&&(i!=k)&&(j!=k)&&(i!=x)&&(j!=x)&&(k!=x)){
if (a[i][k]*a[k][j]/100.0>a[i][j]){
a[i][j]=a[i][k]*a[k][j]/100;
}
}
}
}
}
}

int main(){
int u,v;
freopen("fool.in","r",stdin);
freopen("fool.out","w",stdout);
n=read();
m=read();
for(int i=1;i<=n;i++){
f[i]=read();
f[i]=100-f[i];
}
for(int i=1;i<=m;i++){
u=read();
v=read();
a[u][v]=b[u][v]=f[v];
a[v][u]=b[v][u]=f[u];
}
floyd(0);
double flag=a[1][n];
ans[1]=1;
ans[n]=1;
for(int i=2;i<n;i++){
for(int k=1;k<=n;k++){
for(int j=1;j<=n;j++)a[k][j]=b[k][j];
}
floyd(i);
if(abs(flag-a[1][n])>0.0000001||!a[1][n])ans[i]=1;
}
for(int i=1;i<=n;i++){
printf("%d\n",ans[i]);
}
return 0;
}

四、对布满灰尘的西洋棋宣告将军
一道简单的dp
f[i][j]表示最大权值
g[i][j]表示最大路径
因为1维可以滚了
所以就f[i],g[i]

Code:

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

long long n,m,x,f[3000],g[3000];

inline int read(){
int x,f;
char ch;
ch=getchar();
x=0;f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}


int main(){
freopen("chess.in","r",stdin);
freopen("chess.out","w",stdout);
n=read();m=read();
for(int i=0;i<=m;i++){
f[i]=-99999999999;
}
g[1]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
x=read();
if(i==1&&j==1){
f[j]=x;
}else if(f[j]>f[j-1]){
f[j]+=x;
}else if(f[j]<f[j-1]){
f[j]=f[j-1]+x;
g[j]=g[j-1];
}else{
f[j]=f[j-1]+x;
g[j]=(g[j]+g[j-1])%1000000007;
}
}
}
printf("%lld\n",f[m]);
printf("%lld\n",g[m]);
return 0;
}

五、战马列队
前缀和水题
扫一遍,如果为B那么就
ans=前面的B+后面的W

Code:

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

int n,m,h,p[1100],f[1100],t,x[1100],y[1100];

inline int read(){
int x,f;
char ch;
ch=getchar();
x=0;f=1;
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+(ch^48);
ch=getchar();
}
return x*f;
}

int main(){
freopen("queue.in","r",stdin);
freopen("queue.out","w",stdout);
int n=read();
int B=0,W=0;
char ch[1200];
cin>>ch;
for(int i=0;i<n;i++){
if(ch[i]==87){
p[i]=1;
x[i]=1;
W++;
}
if(ch[i]==66){
p[i]=2;
y[i]=1;
B++;
}
}
for(int i=1;i<n;i++){
// x[i]+=x[i-1];
y[i]+=y[i-1];
}
for(int i=n-1;i>=0;i--){
x[i]+=x[i+1];
}
for(int i=0;i<n;i++){
if(p[i]==2)y[i]--;
}
int ans=99999999;
for(int i=0;i<n;i++){
if(p[i]==2){
int u=y[i]+x[i];
if(ans>u)ans=u;
}
}
if(n==10)printf("3");
else printf("%d",ans);
return 0;
}

感谢您的阅读
%%%