SRM 612

oh, 好累,今晚又奋战到深夜。。

早上的时候做了一场 srm 612,本来又极有机会把中档题拿下,不过实在手生,这场比赛完全是没有用插件,甚至连机器上都没有装 IDE 的情况下敲下来的,而且这么长时间没搞,还真佩服自己。但最终没把握好时间,最终原来有个下标减一的问题,饮恨只低分过了 250。

第一题 (250):EmoticonsDiv1

简单理解,其实就是一个状态转移,注意两个状态是 message 的数字和 clipboard 的数字,做一下广度优先搜索稍微剪了一下枝,效率不算苛刻。这里就不加赘述了。 #include

include

include

include

include

using namespace std;

class EmoticonsDiv1 { public: int printSmiles(int smiles) { map<pair<int, int>, int> mp; deque a, b, c; a.push_back(1); b.push_back(0); c.push_back(0); mp[make_pair(1, 0)] = 0; while(!a.empty()) { int cur = c.front(); c.pop_front(); int clip = b.front(); b.pop_front(); int msg = a.front(); a.pop_front(); cout << cur << ": " << msg << ", " << clip << endl; if(msg == smiles) return cur; pair<int, int> pos;

  pos = make_pair(msg, msg); 
  if(mp.find(pos) == mp.end()) { 
    mp[pos] = cur + 1; 
    c.push_back(cur+1); 
    b.push_back(msg); 
    a.push_back(msg); 
  } 
  pos = make_pair(msg+clip, clip); 
  if(mp.find(pos) == mp.end()) { 
    if(msg+clip < smiles+smiles) { 
      mp[pos] = cur + 1; 
      c.push_back(cur+1); 
      b.push_back(clip); 
      a.push_back(msg+clip); 
    } 
  } 
  pos = make_pair(msg-1, clip); 
  if(mp.find(pos) == mp.end()) { 
    if(msg-1 >= 0) { 
      mp[pos] = cur + 1; 
      c.push_back(cur+1); 
      b.push_back(clip); 
      a.push_back(msg-1); 
    } 
  } 

} 
return smiles; 

} };

第二题 (450):SpecialCells

这题有意思,A君给出一个矩阵里面的一系列坐标 x[0..n-1] 和 y[0..n-1],然后将y的次序打乱。 然后B君(居然还是 Gustavo)拿着打乱的xy去猜A君原本的那些坐标点是哪些,问最差的情况可以猜到多少个。 题目自己慢慢分析,下面直接上结论:用的算法是最小费用最大流。

构造一个图,0 是源,1 是汇,然后 distinct x 坐标构成左顶点集,distinct y 坐标构成右顶点集。

  1. 所有 distinct x 到 distinct y 有一条容量为 1 的边(有1个流量代表猜了这一个点,由于不可重复所以流量为 1);
  2. 在 1 里面定义的边,如果 x-y 对应的是原本的正确的坐标,这条边的费用为 1(猜中了这一条就计算费用,费用最小的时候就是我们的最优解);
  3. 然后是要限制总流量,从源到左侧集的每个 distinct x 添加一条边,容量就是该 distinct x 在 x[] 中出现的次数;同样,在右侧集每个 distinct y 到汇点也同样增加一条边。

这样就可以看出,当流量最大的时候正好匹配到一个合法的猜测方案,那么费用最小的就是我们的输出了,很好。

下面贴代码: #include

include

include

include

include

using namespace std;

//求网络最小费用最大流,邻接阵形式 //返回最大流量,flow返回每条边的流量,netcost返回总费用 //传入网络节点数n,容量mat,单位费用cost,源点source,汇点sink

define MAXN 110

define inf 1000000000

int min_cost_max_flow(int n,int mat[][MAXN],int cost[][MAXN],int source,int sink,int flow[][MAXN],int& netcost){ int pre[MAXN],min[MAXN],d[MAXN],i,j,t,tag; if (source==sink) return inf; for (i=0;i<n;i++) for (j=0;j<n;flow[i][j++]=0); for (netcost=0;;){ for (i=0;i<n;i++) pre[i]=0,min[i]=inf; //通过bellman_ford寻找最短路,即最小费用可改进路 for (pre[source]=source+1,min[source]=0,d[source]=inf,tag=1;tag;) for (tag=t=0;t<n;t++) if (d[t]) for (i=0;i<n;i++) if (j=mat[t][i]-flow[t][i]&&min[t]+cost[t][i]<min[i]) tag=1,min[i]=min[t]+cost[t][i],pre[i]=t+1,d[i]=d[t]<j?d[t]:j; else if (j=flow[i][t]&&min[t]<inf&&min[t]-cost[i][t]<min[i]) tag=1,min[i]=min[t]-cost[i][t],pre[i]=-t-1,d[i]=d[t]<j?d[t]:j; if (!pre[sink]) break; for (netcost+=min[sink]*d[i=sink];i!=source;) if (pre[i]>0) flow[pre[i]-1][i]+=d[sink],i=pre[i]-1; else flow[i][-pre[i]-1]-=d[sink],i=-pre[i]-1; } for (j=i=0;i<n;j+=flow[source][i++]); return j; }

class SpecialCells { map<int, int> m1, m2, s1, s2; int mat[MAXN][MAXN]; int cost[MAXN][MAXN]; int flow[MAXN][MAXN]; public: int getx(int i) { return 2 + i; } int gety(int i) { return 2+m1.size()+i; } int guess(vector x, vector y) { m1.clear(); m2.clear(); for(int i = 0; i < x.size(); ++i) { // 就是下面这两句害了我:后面 m1.size() 是不行的,就差个 -1。 if(m1.find(x[i]) == m1.end()) m1[x[i]] = m1.size()-1; if(m2.find(y[i]) == m2.end()) m2[y[i]] = m2.size()-1; } int netcost = 0; memset(mat, 0, sizeof(mat)); memset(cost, 0, sizeof(cost)); for(int i = 0; i < m1.size(); ++i) { for(int j = 0; j < m2.size(); ++j) { mat[getx(i)][gety(j)] = 1; } } for(int i = 0; i < x.size(); ++i) { mat[0][getx(m1[x[i]])] += 1; mat[gety(m2[y[i]])][1] += 1; cost[getx(m1[x[i]])][gety(m2[y[i]])] = 1; } int sz = 2+m1.size()+m2.size(); return netcost; } };

int main() { int xx[] = {1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9}; int yy[] = {1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3}; vector x(xx,xx+sizeof(xx)/sizeof(int)), y(yy,yy+sizeof(yy)/sizeof(int)); SpecialCells obj; cout << obj.guess(x, y) << endl; system("pause"); }


【转载请附】愿以此功德,回向 >>

原文链接:https://www.huangwenchao.com.cn/2014/03/srm612.html【SRM 612】

发表评论

电子邮件地址不会被公开。 必填项已用*标注