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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SRM 563  

2013-03-03 16:11:16|  分类: topcoder |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
题目算是比较优质的了(至少不像后面的几次比赛1000pt的题目一点可想性都没有)

300分的题目是挺好的:串A和串B合并就是将A,B不改变每个串内部的字符的相对顺序然后将两者的字符合并起来的一个排列。现在有个串S,求字典序最小的C,使得C和C中字符的一个排列合并起来是S。
求字典序最小的最经典方法:依次暴力枚举每一位,判定该位的值为某个字符时剩下的是否有解。这道题也不例外。判定依据就是是否能够对于所有剩下的字符使得能够划分成两个集合。算法实现比较纠结,我错了蛮多次。具体看代码吧。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int NUM=100+10;

int hash[NUM],before[NUM],after[NUM];

struct FoxAndHandle
{
string lexSmallestName(string S)
{
int n=S.size();
int i,j,k,last=0;
string ans;
REP2(i,0,n/2)
{
int minplace=-1;
REP2(j,last,n)
{
if(hash[j])continue;
int flag=1;
hash[j]=1;
memset(before,0,sizeof before);
memset(after,0,sizeof after);
REP2(k,0,n)
if(!hash[k])
{
if(k<j)++before[S[k]-'a'];
else ++after[S[k]-'a'];
}
else --before[S[k]-'a'];
REP2(k,0,26)
if(before[k]>after[k] ||after[k]+before[k]<0)
{
flag=0;
break;
}
hash[j]=0;
if(flag && (minplace==-1 || S[minplace]>S[j]))
minplace=j;
}
hash[minplace]=1;
ans+=S[minplace];
last=minplace+1;
}
return ans;
}
};




500pt的题目反倒比较水:
一个数列,每个数由Li,和Di刻画。你可以做如下操作:
将最左端的L0个数删除,sum+=D0.(0即当前最左端的数的标号)
将最右端的数移动到最左端。
最大化sum。

本题考验的其实就是看到题目之后要分析题目而不要盲目地照着题目来。
注意由于旋转操作具有极大地任意性:
如果我们决定了有哪些数是会被加进sum里面,那么只要必须被删除的数不超过n就行了。
你想,每个数与其后面的L个没有被选择的数一起删除,如果有某个被选择的,那么先把那个数解决就行了。
所以其实质是个很裸的dp

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

struct SpellCards
{
const static int NUM=50+10;
const static int INF=1000000000;
int f[NUM][NUM];

int maxDamage(vector <int> L, vector <int> D)
{
int i,j,k;
int n=L.size();
REP2(i,0,NUM)
REP2(j,0,NUM)
f[i][j]=-INF;
f[0][0]=0;
REP2(i,0,n)
REP(j,0,n)
if(f[i][j]>=0)
{
if(L[i]+j<=n)
f[i+1][L[i]+j]=max(f[i+1][L[i]+j],f[i][j]+D[i]);
f[i+1][j]=max(f[i+1][j],f[i][j]);
}
k=0;
REP(i,0,n)
k=max(f[n][i],k);
return k;
}
};



950分的题目:
n*m的网格,里面有些格子是障碍,现在要求在一些格子里面扔一些点,使得存在一种移动方案(该移动方案会应用于所有点),使得一部分点移动出了边界而一部分没有。移动规则:
只能往四周移动,若移动出了边界就消失,否则若是障碍则不移动否则移动到相邻的格子。
其实是很简单的题目。
反过来考虑,只要选择的点对于任意一种移动方案,都会同时移出边界,那么这样的两个点就不能同时选择。也就是说,如果选择的点都是同时移动出边界的,有且仅有这种方案不可行。
然后注意到这种关系与相等是相同的。
所以连边只有团。暴力处理每个团即可。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<fstream>
#include<map>
#include<ctime>
#include<set>
#include<queue>
#include<cmath>
#include<vector>
#include<bitset>
#include<functional>
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define REP(i,l,r) for((i)=(l);(i)<=(r);++(i))
#define REP2(i,l,r) for((i)=(l);(i)!=(r);++(i))
using namespace std;

typedef long long LL;
typedef double ld;

const int NUM=40+10;
const int Mod=1000000009;

int walk[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int can[NUM][NUM][NUM][NUM];
int n,m,hash[NUM][NUM];

struct CoinsGame
{
vector<string> g;

friend int operator == (const pair<int,int>& a,const pair<int,int>& b)
{
return a.x==b.x && a.y==b.y;
}

pair<int,int> next(pair<int,int> a,int d)
{
if(a.x<0 || a.x>=n || a.y<0 || a.y>=m)
return mp(-1,-1);
if(g[a.x][a.y]=='#')
return mp(-1,-1);
pair<int,int> b(a.x+walk[d][0],a.y+walk[d][1]);
if(b.x<0 || b.x>=n || b.y<0 || b.y>=m )
return mp(-1,-1);
if(g[b.x][b.y]=='#')
return a;
return b;
}

int dfs(int x,int y)
{
int nx,ny,ans=2;
hash[x][y]=1;
REP2(nx,0,n)
REP2(ny,0,m)
if(g[nx][ny]=='.' && !hash[nx][ny] && !can[x][y][nx][ny])
ans=(LL)ans*dfs(nx,ny)%Mod;
return ans;
}

int ways(vector<string> board)
{
/*
如果a移动出去,b也移动出去
这个关系是等价关系,这是解题的关键
*/
int i,j,k,l,d;
g=board;
n=g.size();
m=g[0].size();
queue< pair< pair<int,int>,pair<int,int> > > q;
REP2(i,0,n)REP2(j,0,m)
REP2(k,0,n)REP2(l,0,m)
{
if(g[i][j]=='#')continue;
if(g[k][l]=='#')continue;
REP2(d,0,4)
{
pair<int,int> a=next(mp(i,j),d);
pair<int,int> b=next(mp(k,l),d);
if((a.x==-1)!=(b.x==-1) && !can[i][j][k][l])
{
can[i][j][k][l]=1;
q.push(mp(mp(i,j),mp(k,l)));
}
}
}
while(!q.empty())
{
pair<int,int> a=q.front().x;
pair<int,int> b=q.front().y;
q.pop();
REP2(d,0,4)
{
pair<int,int> na,nb;
REP(i,0,1)
if(next(na=(i?a:next(a,d^1)),d)==a)
REP(k,0,1)
if(next(nb=(k?b:next(b,d^1)),d)==b)
if(!can[na.x][na.y][nb.x][nb.y])
{
can[na.x][na.y][nb.x][nb.y]=1;
cout<<na.x<<" "<<na.y<<" "<<nb.x<<" "<<nb.y<<endl;
q.push(mp(na,nb));
}
}
}
int all=1,tot=0;
REP2(i,0,n)
REP2(j,0,m)
if(!hash[i][j] && g[i][j]=='.')
{
int temp=dfs(i,j);
all=(LL)all*temp%Mod;
tot=(tot+temp-1)%Mod;
}
return (all-tot+Mod-1)%Mod;
}
};



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

历史上的今天

评论

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

页脚

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