【水题合集】6.9考试 – 徐亦轲的博客

%今天“AK”的陈文卓大爷（蒯就蒯嘛还全蒯了讲题又讲不出多尴尬）

1.开灯

我很生气为什么大家写的暴力都可以跑过

亏我还写的正解

把所有操作的灯都异或起来就可以了因为开的又关异或和为1 暴力搞数组开不了那么大

// <light.cpp> - 06/09/16 08:01:16
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
lol gl(){
    lol res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
int main(){
    freopen("light.in","r",stdin);
    freopen("light.out","w",stdout);
    int n=gi();double a;lol ans=0;
    for(int i=1;i<=n;i++){
        scanf("%lf",&a);
        lol t=gl();
        for(lol i=1;i<=t;i++)ans^=lol(a*i);
    }
    printf("%lld",ans);
    return 0;
}

// <light.cpp> - 06/09/16 08:01:16

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

lol gl(){

lol res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

int main(){

freopen("light.in","r",stdin);

freopen("light.out","w",stdout);

int n=gi();double a;lol ans=0;

for(int i=1;i<=n;i++){

scanf("%lf",&a);

lol t=gl();

for(lol i=1;i<=t;i++)ans^=lol(a*i);

}

printf("%lld",ans);

return 0;

}

2.打砖块

这题好显然的背包啊

然而没有考虑到没子弹的时候送子弹的方块不能打

所以dp就要加一维

首先预处理每一列打i个的得分和花费

然后背包一下，加一维表示是否存在一列最后打的一个不是送子弹方块

然后就是std是个萎的

// <game.cpp> - 06/09/16 08:01:16
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=205;
const int INF=1e9;
int a[MAXN][MAXN],c[MAXN][MAXN],v[MAXN][MAXN];
bool b[MAXN][MAXN];
int dp[MAXN][MAXN][2];
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int n=gi(),m=gi(),k=gi();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            a[i][j]=gi();
            b[i][j]=getchar()!='Y';
        }
    for(int i=n;i;i--)
        for(int j=1;j<=m;j++){
            c[i][j]=c[i+1][j]+b[i][j];
            v[i][j]=v[i+1][j]+a[i][j];
        }
    for(int j=1;j<=m;j++){
        memcpy(dp[j],dp[j-1],sizeof(dp[j]));
        for(int i=1;i<=n;i++)
            for(int o=c[i][j];o<=k;o++){
	    int l=o-c[i][j];
	    dp[j][o][b[i][j]]=max(dp[j][o][b[i][j]],dp[j-1][l][0]+v[i][j]);
	    if(dp[j-1][l][1])dp[j][o][1]=max(dp[j][o][1],dp[j-1][l][1]+v[i][j]);
	}
    }
    int ans=dp[m][k][1];
    for(int o=k-1;o>=0;o--)ans=max(ans,max(dp[m][o][0],dp[m][o][1]));
    printf("%d",ans);
    return 0;
}

// <game.cpp> - 06/09/16 08:01:16

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=205;

const int INF=1e9;

int a[MAXN][MAXN],c[MAXN][MAXN],v[MAXN][MAXN];

bool b[MAXN][MAXN];

int dp[MAXN][MAXN][2];

int main(){

freopen("game.in","r",stdin);

freopen("game.out","w",stdout);

int n=gi(),m=gi(),k=gi();

for(int i=1;i<=n;i++)

for(int j=1;j<=m;j++){

a[i][j]=gi();

b[i][j]=getchar()!='Y';

}

for(int i=n;i;i--)

for(int j=1;j<=m;j++){

c[i][j]=c[i+1][j]+b[i][j];

v[i][j]=v[i+1][j]+a[i][j];

}

for(int j=1;j<=m;j++){

memcpy(dp[j],dp[j-1],sizeof(dp[j]));

for(int i=1;i<=n;i++)

for(int o=c[i][j];o<=k;o++){

int l=o-c[i][j];

dp[j][o][b[i][j]]=max(dp[j][o][b[i][j]],dp[j-1][l][0]+v[i][j]);

if(dp[j-1][l][1])dp[j][o][1]=max(dp[j][o][1],dp[j-1][l][1]+v[i][j]);

}

int ans=dp[m][k][1];

for(int o=k-1;o>=0;o--)ans=max(ans,max(dp[m][o][0],dp[m][o][1]));

printf("%d",ans);

return 0;

}

3.长方形

好像看错了什么东西爆零了。。再改吧

4.收费站

显然二分答案跑最短路

然而这题居然有一个点卡SPFA（虽然早料到了）

不打算改了。。反正在自己机子上能过

// <cost.cpp> - 06/09/16 08:01:16
// This file is created by XuYike's black technology automatically.
// Copyright (C) 2015 ChangJun High School, Inc.
// I don't know what this program is.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long lol;
int gi(){
    int res=0,fh=1;char ch=getchar();
    while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();
    if(ch=='-')fh=-1,ch=getchar();
    while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();
    return fh*res;
}
const int MAXN=5010,MAXM=40010;
const int INF=1e9;
int n,m,u,v,s;
int f[MAXN];
int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM];
inline void add(int x,int y,int c){next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=c;}
queue <int> q;
lol dis[MAXN];
bool in[MAXN];
inline bool check(int k){
    if(f[u]>k)return 0;
    for(int i=1;i<=n;i++)dis[i]=0;
    dis[u]=1;
    q.push(u);in[u]=1;
    while(!q.empty()){
        int now=q.front();q.pop();in[now]=0;
        for(int i=b[now];i;i=next[i]){
            if(f[to[i]]>k)continue;
            if(dis[to[i]]&&dis[now]+val[i]>=dis[to[i]])continue;
            dis[to[i]]=dis[now]+val[i];
            if(in[to[i]])continue;
            in[to[i]]=1;
            q.push(to[i]);
        }
    }
    return dis[v]&&dis[v]-1<=s;
}
int main(){
    freopen("cost.in","r",stdin);
    freopen("cost.out","w",stdout);
    n=gi(),m=gi(),u=gi(),v=gi(),s=gi();
    for(int i=1;i<=n;i++)f[i]=gi();
    for(int i=1;i<=m;i++){
        int a=gi(),b=gi(),c=gi();
        add(a,b,c);add(b,a,c);
    }
    int l=0,r=INF+1;
    while(l<r){
        int m=(l+r)>>1;
        if(check(m))r=m;
        else l=m+1;
    }
    if(l==INF+1)printf("-1");
    else printf("%d",l);
    return 0;
}

// <cost.cpp> - 06/09/16 08:01:16

// This file is created by XuYike's black technology automatically.

// I don't know what this program is.

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring>

#include <cstdio>

#include <cmath>

using namespace std;

typedef long long lol;

int gi(){

int res=0,fh=1;char ch=getchar();

while((ch>'9'||ch<'0')&&ch!='-')ch=getchar();

if(ch=='-')fh=-1,ch=getchar();

while(ch>='0'&&ch<='9')res=res*10+ch-'0',ch=getchar();

return fh*res;

}

const int MAXN=5010,MAXM=40010;

const int INF=1e9;

int n,m,u,v,s;

int f[MAXN];

int bt,b[MAXN],next[MAXM],to[MAXM],val[MAXM];

inline void add(int x,int y,int c){next[++bt]=b[x];b[x]=bt;to[bt]=y;val[bt]=c;}

queue <int> q;

lol dis[MAXN];

bool in[MAXN];

inline bool check(int k){

if(f[u]>k)return 0;

for(int i=1;i<=n;i++)dis[i]=0;

dis[u]=1;

q.push(u);in[u]=1;

while(!q.empty()){

int now=q.front();q.pop();in[now]=0;

for(int i=b[now];i;i=next[i]){

if(f[to[i]]>k)continue;

if(dis[to[i]]&&dis[now]+val[i]>=dis[to[i]])continue;

dis[to[i]]=dis[now]+val[i];

if(in[to[i]])continue;

in[to[i]]=1;

q.push(to[i]);

}

return dis[v]&&dis[v]-1<=s;

}

int main(){

freopen("cost.in","r",stdin);

freopen("cost.out","w",stdout);

n=gi(),m=gi(),u=gi(),v=gi(),s=gi();

for(int i=1;i<=n;i++)f[i]=gi();

for(int i=1;i<=m;i++){

int a=gi(),b=gi(),c=gi();

add(a,b,c);add(b,a,c);

}

int l=0,r=INF+1;

while(l<r){

int m=(l+r)>>1;

if(check(m))r=m;

else l=m+1;

}

if(l==INF+1)printf("-1");

else printf("%d",l);

return 0;

}