Selecting World Finals Teams on Mars I
题解：
dfs模拟
代码：
#include <stdio.h>
#include <string.h>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
const int N = 10005;
struct Node
{
int id;
int s;
friend bool operator < (const Node& _n1,const Node& _n2)
{
if(_n1.s == _n2.s)
return _n1.id < _n2.id;
return _n1.s > _n2.s;
}
};
vector<int> graph[N];//contest info
vector<int> contest[N];//contest(i) contains team
vector<int> result[N];
string name[5005];
int s[5005];
bool visited[N];
int n,m;
void init()
{
for (int i = 1; i <= n; ++i)
{
graph[i].clear();
contest[i].clear();
result[i].clear();
}
memset(visited,0,sizeof(visited));
}
void input()
{
int x,y;
for (int i = 0; i < n+m - 1; ++i)
{
scanf("%d %d",&x,&y);
if(x <= n && y <= n)
{
graph[x].push_back(y);
graph[y].push_back(x);
}
else
{
int kx = min(x,y);
int ky = max(x,y);
contest[kx].push_back(ky - n);
}
}
char buf[300];
int k;
for (int i = 1; i <= m; ++i)
{
scanf("%s %d",buf,&k);
name[i] = string(buf);
s[i] = k;
}
}
void dfs(int _cur)
{
visited[_cur] = true;
if(graph[_cur].size() == 0)//leaf
{
vector<Node> tmp;
Node node;
for (int i = 0 ; i < contest[_cur].size(); ++i)
{
node.id = contest[_cur][i];
node.s = s[node.id];
tmp.push_back(node);
}
sort(tmp.begin(),tmp.end());
int kn;
if(_cur != 1)
kn = min(2,(int)tmp.size());
else
kn = (int)tmp.size();
for (int i = 0; i < kn; ++i)
{
result[_cur].push_back(tmp[i].id);
}
}
else
{
vector<Node> tmp;
Node node;
for (int i = 0; i < graph[_cur].size(); ++i)
{
int next = graph[_cur][i];
if(!visited[next])
{
dfs(next);
for (int j = 0; j < result[next].size(); ++j)
{
node.id = result[next][j];
node.s = s[node.id];
tmp.push_back(node);
}
}
}
for (int i = 0 ; i < contest[_cur].size(); ++i)
{
node.id = contest[_cur][i];
node.s = s[node.id];
tmp.push_back(node);
}
sort(tmp.begin(),tmp.end());
int kn ;
if(_cur != 1)
kn = min(2,(int)tmp.size());
else
kn = (int)tmp.size();
for (int i = 0; i < kn; ++i)
{
result[_cur].push_back(tmp[i].id);
}
}
}
void Test()
{
init();
input();
dfs(1);
vector<Node> tmp;
Node node;
for (int i = 0; i < result[1].size(); ++i)
{
node.id = result[1][i];
node.s = s[node.id];
tmp.push_back(node);
}
sort(tmp.begin(),tmp.end());
for (int i = 0; i < tmp.size(); ++i)
{
printf("%s\n",name[tmp[i].id].c_str());
}
}
int main()
{
//freopen("data.txt","r",stdin);
while (scanf("%d %d",&n,&m) != EOF)
{
Test();
}
return 0;
}Hamilton Circles
题解：
找规律，矩阵快速幂
代码：
#include <stdio.h>
#include<algorithm>
using namespace std;
int tc;
struct Matrix2x2
{
Matrix2x2()
{
for (int i = 0; i < 2; ++i)
{
for (int j = 0; j < 2; ++j)
{
a[i][j] = 1;
}
}
}
long long a[2][2];
void mul(Matrix2x2& _c)
{
long long b[2][2];
b[0][0] = (a[0][0]*_c.a[0][0] + a[0][1]*_c.a[1][0])%1000000007 ;
b[0][1] = (a[0][0]*_c.a[0][1] + a[0][1]*_c.a[1][1])%1000000007 ;
b[1][0] = (a[1][0]*_c.a[0][0] + a[1][1]*_c.a[1][0])%1000000007 ;
b[1][1] = (a[1][0]*_c.a[0][1] + a[1][1]*_c.a[1][1])%1000000007 ;
a[0][0] = b[0][0];
a[0][1] = b[0][1];
a[1][0] = b[1][0];
a[1][1] = b[1][1];
}
};
Matrix2x2 param;
long long pas[2][2] = {3,2,1,1};
Matrix2x2 quickMul(Matrix2x2 _k,int _p)
{
if(_p == 1)
return _k;
if(_p %2 == 1)
{
Matrix2x2 ret = quickMul(_k,_p/2);
Matrix2x2 tmp = ret;
ret.mul(tmp);
ret.mul(_k);
return ret;
}
else
{
Matrix2x2 ret = quickMul(_k,_p/2);
Matrix2x2 tmp = ret;
ret.mul(tmp);
return ret;
}
}
void Test()
{
int n = 0;
scanf("%d",&n);
if(n == 1)
{
printf("%d\n",1);
}
else if(n == 2)
{
printf("%d\n",6);
}
else
{
Matrix2x2 pp = quickMul(param,n - 2);
long long ans1 = 4,ans2 = 2;
long long ans3 = (pp.a[0][0]*ans1 + pp.a[0][1]*ans2)%1000000007;
long long ans4 = (pp.a[1][0]*ans1 + pp.a[1][1]*ans2)%1000000007;
printf("%lld\n",(ans3+ans4)%1000000007);
}
}
int main()
{
//freopen("data.txt","r",stdin);
for (int i = 0; i < 2; ++i)
{
for (int j = 0; j < 2; ++j)
{
param.a[i][j] = pas[i][j];
}
}
scanf("%d",&tc);
for (int i = 0; i < tc; ++i)
{
printf("Case %d: ",i+1);
Test();
}
return 0;
} Word Ladder
题解：暴搜，首先用hash预处理字符串建图
代码：
#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <vector>
using namespace std;
string name[6005];
vector<int> next[6005];
map<string,int> Map;
int visited[6005];
int len;
string start,end;
void input()
{
len = 0;
char buf[128];
scanf("%s",buf);
start = string(buf);
scanf("%s",buf);
end = string(buf);
while (scanf("%s",buf) != EOF)
{
name[len] = string(buf);
Map[name[len]] = len;
++len;
}
}
void pre_process()
{
for (int i = 0; i < len; ++i)
{
int cLen = name[i].length();
string tmp = name[i];
for (int j = 0; j < cLen; ++j)
{
char cl = tmp[j];
for (int k = 'a'; k <= 'z'; ++k)
{
if(k != cl)
{
tmp[j] = k;
map<string,int>::iterator it = Map.find(tmp);
if(it != Map.end())
{
next[i].push_back(it->second);
}
}
}
tmp[j] = cl;
}
}
}
int BFS()
{
memset(visited,0,sizeof(visited));
queue<int> que;
int startId = Map[start];
int endID = Map[end];
que.push(startId);
visited[startId] = 1;
while(!que.empty())
{
int curState = que.front();
que.pop();
if(curState == endID)
return visited[endID] ;
for (int i = 0; i < next[curState].size(); ++i)
{
int extState = next[curState][i];
if (visited[extState] == 0)
{
visited[extState] = visited[curState] + 1;
que.push(extState);
}
}
}
return -1;
}
int main()
{
//freopen("data.txt","r",stdin);
input();
pre_process();
int ret = BFS();
printf("%d\n",ret);
return 0;
} Daka
题解：模拟
代码：
#include <stdio.h>
#include <algorithm>
#include <set>
using namespace std;
long long table[3] = {1L,100L,10000L};
struct Node
{
int hh,mm,ss,yyyy,MM,dd;
friend bool operator < (const Node& _node1,const Node& _node2)
{
if(_node1.yyyy == _node2.yyyy)
{
if(_node1.MM == _node2.MM)
{
if(_node1.dd == _node2.dd)
{
if(_node1.hh == _node2.hh)
{
if(_node1.mm == _node2.mm)
{
return (_node1.ss < _node2.ss);
}
return _node1.mm == _node2.mm;
}
return _node1.hh < _node2.hh;
}
return _node1.dd < _node2.dd;
}
return _node1.MM < _node2.MM;
}
return _node1.yyyy < _node2.yyyy;
}
};
Node nodes[20000];
long long getHash(const Node& _node)
{
return (long long)(_node.dd)*table[0] +
(long long)(_node.MM)*table[1]+
(long long)(_node.yyyy)*table[2];
}
int getTime(const Node& _node)
{
return (_node.ss) + (_node.mm*60) + (_node.hh*3600);
}
Node mEx1,mEx2;
Node mHa1,mHa2;
int main()
{
//freopen("data.txt","r",stdin);
mEx1.mm = 0;mEx1.hh = 7;mEx1.ss = 0;
mEx2.mm = 30;mEx2.hh = 8;mEx2.ss = 0;
mHa1.mm = 0;mHa1.hh = 16;mHa1.ss = 0;
mHa2.mm = 30;mHa2.hh = 21;mHa2.ss = 0;
int mTEx1 = getTime(mEx1);int mTEx2 = getTime(mEx2);
int mTHa1 = getTime(mHa1);int mTHa2 = getTime(mHa2);
int morEx = 0,halfEx = 0;
Node node;
int len = 0;
set<long long> Set;
set<long long> Set2;
while(scanf("%d %d %d %d %d %d",&(node.hh),&(node.mm),&(node.ss),&(node.yyyy),&(node.MM),&(node.dd)) != EOF)
{
nodes[len++] = node;
}
sort(nodes ,nodes + len);
for(int i = 0 ; i < len ; ++i)
{
int time = getTime(nodes[i]);
if((time >= mTEx1) && (time <= mTEx2))
{
if(Set.find(getHash(nodes[i])) == Set.end())
{
Set.insert(getHash(nodes[i]));
++morEx;
}
}
else if((time >= mTHa1) && (time <= mTHa2))
{
int hashCode = getHash(nodes[i]);
int j = i;
while(j < len && (getHash(nodes[j]) == hashCode))
++j;
if(i != j)
{
j = j-1;
if(getTime(nodes[j]) - getTime(nodes[i]) >= 30*60)
{
++halfEx;
}
}
i = j ;
}
}
if(morEx <= 10)
printf("%d ",10 - morEx);
else
printf("0 ");
if(halfEx <= 20)
printf("%d\n",20 - halfEx);
else
printf("0\n");
return 0;
} A Problem about Tree
题解：当更换树的根结点时，只有原根结点到更新的根结点之间经过的路径的所有结点的父子关系发生变化。
代码：
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;
const int N = 10005;
vector<int> graph[N];
int father[N];
void dfs(int _father,int _cur)
{
father[_cur] = _father;
for (int i = 0; i < graph[_cur].size(); ++i)
{
if (father[graph[_cur][i]] == 0)
{
dfs(_cur,graph[_cur][i]);
}
}
}
void init(int _n)
{
for (int i = 1; i <= _n; ++i)
{
graph[i].clear();
}
}
void query(int _x,int _y)
{
int chi = _x;
int par = father[_x];
while (par != -1)
{
if(par == _y)
{
printf("%d\n",chi);
return;
}
chi = par;
par = father[par];
}
printf("%d\n",father[_y]);
}
void Test()
{
int n,q;
scanf("%d %d",&n,&q);
init(n);
int a,b;
for (int i = 1; i < n; ++i)
{
scanf("%d %d",&a,&b);
graph[a].push_back(b);
graph[b].push_back(a);
}
memset(father,0,sizeof(father));
dfs(-1,1);
int x,y;
for (int i = 0; i < q; ++i)
{
scanf("%d %d",&x,&y);
query(x,y);
}
}
int main()
{
int tc;
scanf("%d",&tc);
for (int i = 0; i < tc; ++i)
{
Test();
}
return 0;
}
posted on 2011-05-24 20:39
bennycen 阅读(1398)
评论(0) 编辑 收藏 引用 所属分类:
算法题解