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 閱讀(1421)
評論(0) 編輯 收藏 引用 所屬分類:
算法題解