寒假测试
2015.02.08
1.肉鸡翅
要做出绝顶美味让人大快朵颐的肉鸡翅，需要放入很多美味的调料。
此时麦当劳来了一位大客户，他要n*m个鸡翅，并且要求用一个带铁丝网格的巨大n行m列铁板装着鸡翅（每个格子里装一个），每个格子里的鸡翅必须用此客户指定的调料（不尽相同），然后此客户将这个铁板整个带回家当艺术品享用。
铁板被分成n*m个方格，每一个格子都只能放上带指定调料的鸡翅，调料是不能覆盖的，即假如P格要放x味的调料，那么不能先放上y味的调料再放上x味的调料。
麦当劳首席大厨TYG很崇尚艺术，他买了一台自动洒调料机，有三种洒调料方法：
A.将同一行某些连续的格子洒上同一种味道的调料，机器损耗的代价为a
B.将同一列某些连续的格子洒上同一种味道的调料，机器损耗的代价为b
C.将某一个格子撒上某种味的调料，机器损耗的代价为c
现在TYG想要一种代价最少的方案将这些鸡翅按客户指定的要求撒上调料。
【输入】：meatchickwing.in
本题有多组数据（有很多那种大客户来订单，引进肉鸡品牌后销量明显增了很多），首先第一行输入数据组数，
每组数据的输入如下：
第一行五个整数n,m,a,b,c
接下来一个n*m的矩阵，表示每一个网格中应洒调料的种类，调料种类用小写字母表示。
（注：不保证字母是连续的出现的。也就是说可能只出现了a和c两种字母）
【输出】：meatchickwing.out
对于每组数据，输出一个整数ans，表示最小代价
样例输入：
2
341183
aaaa
aaaa
aaaa
44352
aabc
aabc
bbbb
ccbc
样例输出：
32
23
数据范围：
数据组数不超过40。
1<=n,m<=30
1<=a,c<=100000
时限1s。
思路：当时写了一个暴力，光爆力就写了1.5h，表示暴力都不打会写，然后等发下题来，哈哈，数据怎么这么水（神），一个点力有多组数据，从第一个就开始T。看了这个题的正解居然是网络流，表示网络流刚学了一天，根本看不出......
仔细地读了题解终于明白了他是怎么做的了：我们可以把撒调料想象成染色，对于同一个格子，同一种正确的颜色可以重复染。我们可以先预处理出所有横着的边，所有竖着的边的个数（表示预处理也是比较呵呵的），这样以后，我们可以建立一个源点S和一个汇点T，然后我们开始连边-->连边我们可以分为三种，对于横着的格子，我们从源点向他连一条容量为a的边，对于竖着的边，我们可以将它和汇点连一条容量为b的边，然后在横着的和竖着的边上都连上容量为c的边，这样我们只需要做一遍最大流，最大流即为答案了。
还需要注意一点：在我们求最小割（最大流）的时候不是横边和竖边每一个都可以割的，必须是这条横边和这条竖边有交集,即有一个交点，要知道为什么，我们必须要比较好的理解这个网络流:我们在求出一个割以后，就是相当于选择了这个割集的其中至少一条边（也就是一种染色方案），所以如歌横边和竖边没有交集，我们就没法去执行单独一个格子染色的这个操作。给予上面的原因，我们在预处理和建图的时候还要多注意一些情况，就是如果横边和竖边没有交集，呢们我们不从这两个之间连边。
#include<iostream>
#include<cstdio>
#include<cstring>
#define MM 2100000000
using namespace std;
struct S{
int st,en,v;
}aa[10000];
int map[40][40]={0},tot,t,n,gap[3000]={0},level[3000]={0},pre[3000]={0},mapp[40][40][2]={0},point[3000]={0},next[10000]={0};
inline int ISAP(int x,int y){
int minn,ans=0,i,j,v,u;
bool f=false;
memset(pre,sizeof(pre));
memset(level,sizeof(level));
memset(gap,sizeof(gap));
u=x;gap[0]=y-x+1;
while(level[x]<y){
f=false;
for(i=point[u];i!=0;i=next[i]){
if(level[u]==level[aa[i].en]+1&&aa[i].v>0){
f=true;break;
}
}
if(f){
pre[aa[i].en]=i;u=aa[i].en;
if(u==y){
minn=MM;
for(i=y;i!=x;i=aa[pre[i]].st){
minn=min(minn,aa[pre[i]].v);
}
ans+=minn;
for(i=y;i!=x;i=aa[pre[i]].st){
aa[pre[i]].v-=minn;
aa[pre[i]^1].v+=minn;
}
u=x;
}
}
else{
minn=y;
for(i=point[u];i!=0;i=next[i]){
if(aa[i].v>0){
minn=min(minn,level[aa[i].en]);
}
}
gap[level[u]]-=1;
if(!gap[level[u]]) break;
minn+=1;
level[u]=minn;
gap[level[u]]+=1;
if(u!=x) u=aa[pre[u]].st;
}
}
return ans;
}
inline void add(int x,int y,int z){
++tot;next[tot]=point[x];point[x]=tot;
aa[tot].st=x;aa[tot].en=y;aa[tot].v=z;
++tot;next[tot]=point[y];point[y]=tot;
aa[tot].st=y;aa[tot].en=x;aa[tot].v=0;
}
int main()
{
freopen("meatchickwing.in","r",stdin);
freopen("meatchickwing.out","w",stdout);
scanf("%d",&t);
while(t--){
memset(point,sizeof(point));
memset(next,sizeof(next));
memset(map,sizeof(map));
memset(mapp,sizeof(mapp));
memset(aa,sizeof(aa));
tot=1;
int i,c,tot1=0,tot2=0;
char ch;
scanf("%d%d%d%d%d",&n,&m,&a,&b,&c);
for(i=1;i<=n;++i){
for(j=1;j<=m;++j){
cin>>ch;
map[i][j]=ch-'a'+1;
}
}
for(i=1;i<=n;++i){
for(j=1;j<=m;++j){
if(map[i][j]!=map[i][j-1]) tot1+=1,tot2+=1;
mapp[i][j][0]=tot2;
}
}
for(j=1;j<=m;++j){
for(i=1;i<=n;++i){
if(map[i][j]!=map[i-1][j]) tot2+=1;
mapp[i][j][1]=tot2;
}
}
for(i=1;i<=tot1;++i) add(0,a);
for(i=tot1+1;i<=tot2;++i) add(i,tot2+1,b);
for(i=1;i<=n;++i){
for(j=1;j<=m;++j){
add(mapp[i][j][0],mapp[i][j][1],c);
}
}
printf("%dn",ISAP(0,tot2+1));
}
}
2.图论入门
给出一个无向连通图,问最小生成树是不是唯一的。
【输入格式】
第一行一个整数t（1<=t<=5),表示测试数据的组数.每组数据描述一个无向连通图,第一行是两个整数n和m(1<=n<=100),图中的点的个数和边数.下面m行给出每条边(xi,yi,wi),表示点xi和yi间有一条长为wi的边。
【输出格式】
对于每组输入,如果最小生成树是唯一的输出最小花费,否则输出'NotUnique!'.
【样例】
unique.in
2
33
121
232
313
44
122
232
342
412
unique.out
3
NotUnique!
时限2s
思路：这个题算是比较简单的一道了，不过当时我很呵呵的在奋力的写第一题的暴力（但是谁知道第一题是网络流......），然后写完第三个就没时间写了。这个题我们可以先用kruskal求出一个最小生成树，然后我们再用其他点当起始点再跑最小生成树，在这次的最小生成树中至少有一条边与第一次不同，如果当前的值与第一次的值相等，那么就说明不止一条，否则就输出第一次答案。
注意：在座的过程中要用并查集维护！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct S{
int s,v;
bool f;
}a[5000];
int n,fa[101],l[101],q,m;
int cmp(const S &a,const S &b){
if(a.v<b.v) return 1;
return 0;
}
int find(int x){
if(fa[x]!=x) fa[x]=find(fa[x]);
return fa[x];
}
int main()
{
freopen("unique.in",stdin);
freopen("unique.out",&q);
while(q--){
int i,minn=0,num=0,ans=0;
bool ff=false;
memset(l,sizeof(l));
scanf("%d%d",&m);
for(i=1;i<=m;++i){
scanf("%d%d%d",&a[i].s,&a[i].t,&a[i].v);
a[i].f=true;
}
sort(a+1,a+m+1,cmp);
for(i=1;i<=n;++i) fa[i]=i;
for(i=1;i<=m;++i){
if(find(a[i].s)==find(a[i].t)) continue;
ans+=a[i].v;
l[0]+=1;
l[l[0]]=i;
fa[find(a[i].s)]=find(a[i].t);
num+=1;
if(num==n-1) break;
}
for(i=1;i<n;++i){
minn=num=0;
for(j=1;j<=n;++j) fa[j]=j;
a[l[i]].f=false;
if(i>1) a[l[i-1]].f=true;
for(j=1;j<=m;++j){
if(find(a[j].s)==find(a[j].t)||!a[j].f) continue;
minn+=a[j].v;
if(minn>ans) break;
fa[find(a[j].s)]=find(a[j].t);
num+=1;
if(num==n-1) break;
}
if(num==n-1&&minn==ans){
ff=true;
break;
}
}
if(ff) printf("Not Unique!n");
else printf("%dn",ans);
}
}
3.千石抚子的三维积木(nadeko.cpp/in/out)3.5s512MB10*10=100分
p.s.本题含有一些(本人)黑历史，请自动过滤题目背景…==
自从蛇切绳被搞掉之后，抚子认识到普通的蛇其实是很和谐的东西。于是她开始养蛇，有天在家无聊就开始用蛇堆积木。由于她是驯蛇高手所以它们都很听话堆上去之后就不会动，并且每条蛇可以被视为一块长方体（这个比喻有点。。好吧，接下来都把蛇叫做积木了）。
堆积木是在一块W*D的平地上进行的，每堆一个积木时会告诉你它的长宽高和放置的左上角x，y坐标。
它的下底面高度等于在它没加进来之前，它所占的平面中最高的积木高度（就像三维俄罗斯方块）。
抚子想知道加入每块积木之后这块积木上底面的高度。
输入格式：
第一行三个数W,D,n，W为场地的长，D为宽，n为积木数
接下来n行，每行5个数a,x,y，分别表示长宽高和放置的左上角x，y坐标(注意左上角指的是平面中x,y都最小的坐标)，即放置在以(x,y)-(x+a,y+b)为对角线的矩形中。(0<=x<=W,0<=y<=D)
输出格式：
n行，每行1个数表示加入这块积木之后这块积木上底面的高度。
SampleInput
754
43200
33130
71203
23322
SampleOutput
2
3
2
6
数据范围：
对于30%数据1<=n<=1000
对于50%数据1<=n<=15000
对于100%数据1<=n<=30000,1<=W,D<=1000，1<=每块积木的长宽高<=1000,保证放置积木的位置不会出场地的边界，输入都是整数
思路:刚开始看这个题的思路还挺简单，就是一道纯数据结构的题，刚开始理解错了题，在每次增加的时候直接给这个节点加上了这个值，其实应该修改成这个值！！然后我开始用了一个n棵线段树的方法，知道一定会T。随后就写了一个四分树，其实就相当于两棵，在修改和查询是需要分四种情况，但是四分树的效率还是比较低，能卡过（我写的代码比较丑陋，还需要加上读入优化QAQ，还有一个小问题，在宏定义的时候用了位运算，结果一直炸，查了半个多小时，最后改成除就好了，表示不知道为什么）
这道题的正解是二维线段树，但是由于代码的复杂度，本人暂时写不出
先放上卡过的程序
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#include<algorithm>
#include<cmath>
#define mid1 (l1+r1)/2
#define mid2 (l2+r2)/2
int w,d,tr[5000][5000]={0},de[5000][5000]={0};
char * ptr=(char *)malloc(2000000);
inline void in(int &x){
while(*ptr<'0'||*ptr>'9')++ptr;
x=0;
while(*ptr>47&&*ptr<58)x=x*10+*ptr++-'0';
}
inline void pushdown(int k1,int k2){
tr[k1<<1][k2<<1]=tr[k1<<1][k2<<1|1]=tr[k1<<1|1][k2<<1]=tr[k1<<1|1][k2<<1|1]=de[k1][k2];
de[k1<<1][k2<<1]=de[k1<<1][k2<<1|1]=de[k1<<1|1][k2<<1]=de[k1<<1|1][k2<<1|1]=de[k1][k2];
de[k1][k2]=0;
}
#define L1 k1<<1,l1,mid1,x1,y1
#define R1 k1<<1|1,mid1+1,r1,y1
#define L2 k2<<1,l2,mid2,x2,y2
#define R2 k2<<1|1,mid2+1,r2,y2
inline int ask(int k1,int l1,int r1,int x1,int y1,int k2,int l2,int r2,int x2,int y2){
/* cout<<"l1,r1: "<<l1<<" "<<r1<<"-->"<<"x1,y1: "<<x1<<" "<<y1<<" <---> "<<"l2,r2: "<<l2<<" "<<r2<<"-->"<<"x2,y2: "<<x2<<" "<<y2<<endl;*/
if(x1<=l1&&y1>=r1&&x2<=l2&&y2>=r2) return tr[k1][k2];
if(de[k1][k2]) pushdown(k1,k2);
int maxn=0;
if(x1<=mid1&&x2<=mid2) maxn=max(maxn,ask(L1,L2));
if(x1<=mid1&&y2>mid2) maxn=max(maxn,R2));
if(y1>mid1&&x2<=mid2) maxn=max(maxn,ask(R1,L2));
if(y1>mid1&&y2>mid2) maxn=max(maxn,R2));
return maxn;
}
inline void insert(int k1,int y2,int z){
if(x1<=l1&&y1>=r1&&x2<=l2&&y2>=r2){
tr[k1][k2]=de[k1][k2]=z;
return ;
}
if(de[k1][k2]) pushdown(k1,k2);
if(x1<=mid1&&x2<=mid2) insert(L1,L2,z);
if(x1<=mid1&&y2>mid2) insert(L1,R2,z);
if(y1>mid1&&x2<=mid2) insert(R1,z);
if(y1>mid1&&y2>mid2) insert(R1,z);
tr[k1][k2]=max(max(tr[k1<<1][k2<<1],tr[k1<<1][k2<<1|1]),max(tr[k1<<1|1][k2<<1],tr[k1<<1|1][k2<<1|1]));
}
int main()
{
freopen("nadeko.in",stdin);
freopen("nadeko.out",stdout);
fread(ptr,1,2000000,stdin);
int i,y,ans;
in(w);in(d);in(n);
for(i=1;i<=n;++i){
in(a);in(b);in(c);in(x);in(y);
ans=ask(1,w,x+1,x+a,y+1,y+b);
insert(1,y+b,ans+c);
printf("%dn",ans+c);
}
}
总结：
①在写数据结构的题的时候一定要细心，否则一点小错误都会很难调，很耽误时间。②堆网络流有了更加深刻的理解，在做网络流的题的时候我们在建模的过程中朝着最小割即为答案的方向靠近，这也是今天在网上听课学到的一些东西，往往我们在建模的过程中都是要把我们的题目向最小割的方向靠近。③当我们再做一些题的过程中，如果我们看到这个题很麻烦，一时想不出思路，搜索的时间复杂度有太高，我们就可以考虑一下网络流！！ （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
