注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM556 DIV1  

2012-09-14 19:43:23|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
很明显我的水平不够
由于只做了250分的题目 rank204,rating掉了5
好可怜

250

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
using namespace std;

const int NUM=100;
const int MAX=1500+10;

typedef pair<int,int> F;
int hash[NUM][MAX];

struct XorTravelingSalesman
{
int maxProfit(vector <int> w, vector <string> link)
{
int u,v,ans=w[0];
queue<F> q;
q.push(make_pair(0,w[0]));
hash[0][w[0]]=1;
F now;
while(!q.empty())
{
now=q.front();
q.pop();
u=now.first;
ans=max(now.second,ans);
for(v=0;v<w.size();++v)
if(link[u][v]=='Y')
if(!hash[v][now.second^w[v]])
{
hash[v][now.second^w[v]]=1;
q.push(make_pair(v,now.second^w[v]));
}
}
return ans;
}
};


500分的题目,我的做法是记忆化搜索,中午睡觉的时候想到的,然后晚上调了接近一个小时才写出来,充分说明了我是弱菜

#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<iostream>
using namespace std;

const int MAX=100;

string same[MAX][MAX],big[MAX][MAX],small[MAX][MAX],S,T;
int hash[MAX][MAX];

void work(int now,int k)
{
int i;
if(hash[now][k])
return;
hash[now][k]=1;
string aim=T.substr(now,k+1);

small[now][k]=S.substr(0,k+1);
if(S.substr(0,k+1)>aim)
big[now][k]=S.substr(0,k+1);
else if(S.substr(0,k+1)==aim)
same[now][k]=S.substr(0,k+1);
if(!k)
return;

for(i=k;i>=1;--i)
{
string res;
if(i+1<=k)
res=S.substr(i+1,k-(i+1)+1);
work(now+1,i-1);

string np=S[i]+small[now+1][i-1]+res;
if(np<small[now][k] || !small[now][k].size())
small[now][k]=np;
if(np>aim && (!big[now][k].size() || big[now][k]>np))
big[now][k]=np;
if(np==aim)
same[now][k]=np;

if(same[now+1][i-1].size())
{
np=S[i]+same[now+1][i-1]+res;
if(np<small[now][k] || !small[now][k].size())
small[now][k]=np;
if(np>aim && (!big[now][k].size() || big[now][k]>np))
big[now][k]=np;
if(np==aim)
same[now][k]=np;
}

if(big[now+1][i-1].size())
{
np=S[i]+big[now+1][i-1]+res;
if(np<small[now][k] || !small[now][k].size())
small[now][k]=np;
if(np>aim && (!big[now][k].size() || big[now][k]>np))
big[now][k]=np;
if(np==aim)
same[now][k]=np;
}
}
}

struct LeftRightDigitsGame2
{
string minNumber(string s,string t)
{
S=s;T=t;
work(0,S.size()-1);
if(same[0][S.size()-1].size())
return t;
else return big[0][S.size()-1];
}
};

LeftRightDigitsGame2 b;
//10011011111110110111110010000110000000000000111011
int main()
{
string s="10001011010111000110001000110010001101111001100111";
string t="10011011111110110111110001111000011110011111001101";
string ans=b.minNumber(s,t);
cout<<ans<<endl;
}


对于1000分的题,我只想说wata真神也

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<iostream>
using namespace std;

const int MAX=100*100;
const int INF=10000;

struct Edge
{
int t,flow,C,next;
}e[MAX*100];

int tot,del[MAX],gap[MAX],h[MAX],begin[MAX],n,S,T;

void addedge(int u,int v,int C)
{
e[tot].t=v;
e[tot].next=begin[u];
begin[u]=tot;
e[tot].C=C;e[tot].flow=0;
tot++;
}

void add(int u,int v,int C)
{
addedge(u,v,C);
addedge(v,u,0);
}

int q[MAX];

int sap(int u,int flow)
{
q[++q[0]]=u;
if(u==T )
return flow;
int i,v,remain=flow,temp;
for(i=begin[u];i!=-1;i=e[i].next)
{
if(del[i])continue;
v=e[i].t;
if(h[v]+1==h[u] && e[i].C>e[i].flow)
{
temp=min(e[i].C-e[i].flow,remain);
temp=sap(v,temp);
remain-=temp;
e[i].flow+=temp;
e[i^1].flow-=temp;
if(!remain)
{
--q[0];
return flow;
}
}
}
--gap[h[u]];
if(!gap[h[u]])
h[S]=n+1;
++h[u];
++gap[h[u]];
--q[0];
return flow-remain;
}

int maxflow()
{
int i,ans=0;
for(i=0;i<tot;++i)
e[i].flow=0;
for(i=0;i<n+1;++i)
gap[i]=0;
for(i=1;i<=n;++i)
++gap[h[i]=0];
while(h[S]<n+1)
ans+=sap(S,INF);
return ans;
}

struct OldBridges
{
string isPossible(vector<string> g,int a1,int a2,int an,int b1,int b2,int bn)
{
++a1,++a2,++b1,++b2;
memset(begin,-1,sizeof begin);
n=g.size();
int i,j;
for(i=0;i<(int)g.size();++i)
for(j=i+1;j<(int)g.size();++j)
if(g[i][j]!='X')
{
if(g[i][j]=='N')
{
add(i+1,j+1,INF);
add(j+1,i+1,INF);
}
else
{
add(i+1,j+1,2);
add(j+1,i+1,2);
}
}
S=++n;T=++n;

add(S,a1,2*an);add(a2,T,2*an);
add(S,b2,2*bn);add(b1,T,2*bn);
int FLOW2=maxflow();
for(i=0;i<8;++i)
del[tot-i-1]=1;

add(S,a1,2*an);add(a2,T,2*an);
add(S,b1,2*bn);add(b2,T,2*bn);
int FLOW1=maxflow();

if(FLOW1>=an*2+bn*2 && FLOW2>=an*2+bn*2)
return string("Yes");
else return string("No");
}
};



  评论这张
 
阅读(357)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018