今天我们队去参加的2011北大校赛，想想看，这还是第一次参加北大的校赛。总体感觉还行，就是做比赛的机房太闷热，还有一个队伍只发一套题目，而且发了之后还延迟半小时，又把题目收回去了。。。
题目感觉比去年的简单一些，做了8道，还有两道E和I，E应该是splaytree，I是DP，但是由于没有什么思路而且2点半我们还有事情，1点多点的时候就走了。简单介绍一下题目和代码：
A：模拟
有2种任务，一种时早上7点8点半需要签一次到，需要10次，另一种是下午16点到21点30之间签两次到，两次之间的间隔大于等于1800s才算合法，需要20次。
给你签到的序列，一天每一种最多算一次，问两种各还需签多少次。
简单模拟即可，wa了一次，原因是10或20减到0就不能再减了。。。
B：离线算法
一棵树，n个节点，n-1条边，问q次，每次问以x为根的时候，y的father是谁？
n = 10000，q=10000
统计下问题，以1号节点为根节点，深搜一遍树即可：搜到节点i的时候，如果看看关于以i为根的所有问题，比如问以i为根的时候，j的father是谁，只要看当前遍历路径上j几点的后继节点是谁，如果没有，那么j的father就是当前以1节点为根的时候的father。画画图就很清楚了。
总时间复杂度O(n)
C：简单搜索
D：n^3的DP + Floyd
有3支队伍严格按编号顺序消灭地图上n个城市，城市之间的边和权值告诉你，问总权值最少是多少。
dp[i][j][k]表示第1支队伍在i城市，第2支队伍在j城市，第3支队伍在k城市的最小权值，后面的转移就简单了，注意dp[500][500][500]开不下，需要用滚动数组。详见代码。
H：简单模拟，不知道为什么很多队伍都卡在上面了。
就是模拟竞赛的晋级问题，问最后晋级到总决赛的队伍的信息。
之前忘记添加代码了，这里仅仅给出自己写的几道题目的代码：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
using namespace std;
#define year 0
#define month 1
#define day 2
#define hour 3
#define min 4
#define sec 5
struct pint
{
int
x[6];
}jeo;
bool sameday(pint a, pint b)
{
return
a.x[year] == b.x[year] &&
a.x[month] == b.x[month] &&
a.x[day] == b.x[day];
}
bool type1(pint a)
{
char
from[] = "070000"; char to[] = "083000";
char
tar[10];
sprintf(tar, "ddd", a.x[hour], a.x[min],
a.x[sec]);
return
strcmp(tar, from) >= 0
&& strcmp(tar, to)
<= 0;
}
bool type2(pint a)
{
char
from[] = "160000"; char to[] = "213000";
char
tar[10];
sprintf(tar, "ddd", a.x[hour], a.x[min],
a.x[sec]);
return
strcmp(tar, from) >= 0
&& strcmp(tar, to)
<= 0;
}
bool bet(pint a, pint b)
{
return
b.x[hour] * 3600 + b.x[min] * 60 + b.x[sec] - a.x[hour] * 3600 -
a.x[min] * 60 - a.x[sec] >= 1800;
}
int main()
{
int cnt
= 0;
int aa
= 10, bb = 20;
pint
t1, t2;
t1.x[year] = t2.x[year] = -1;
bool
flag = false;
while(scanf("%d%d%d%d%d%d",
&jeo.x[hour], &jeo.x[min],
&jeo.x[sec], &jeo.x[year],
&jeo.x[month], &jeo.x[day]) !=
EOF)
{
if (type1(jeo))
{
if (!sameday(jeo, t1))
{
t1 =
jeo;
aa--;
}
}
if (type2(jeo))
{
if (sameday(jeo, t2))
{
if
(!flag)
{
if (bet(t2, jeo)) bb--, flag =
true;
else t2 = jeo;
}
}
else
{
t2 =
jeo;
flag =
false;
}
}
}
if (aa
< 0) aa = 0;
if (bb
< 0) bb = 0;
printf("%d %d\n", aa, bb);
return
0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
struct pint
{
pint(int tar, int id):tar(tar), id(id){}
int
tar, id;
};
vector<pint> ask[10001];
vector<int> g[10001];
int now[10001], fa[10001];
int t, n, q, jeo[10001], jeo2[10001];
void dfs(int id, int pre)
{
for(int
i = 0; i < ask[id].size(); i++)
{
jeo[ask[id][i].id] =
now[ask[id][i].tar];
if (jeo[ask[id][i].id] == -1)
jeo2[ask[id][i].id] = ask[id][i].tar;
}
fa[id]
= pre;
for(int
i = 0; i < g[id].size(); i++)
if (g[id][i] != pre)
{
now[id] = g[id][i];
dfs(g[id][i], id);
now[id] = -1;
}
}
int main()
{
scanf("%d", &t);
while(t--)
{
scanf("%d%d",
&n, &q);
for(int i = 1; i
<= n; i++)
{
g[i].clear();
now[i] = -1;
ask[i].clear();
}
for(int i = 1; i
< n; i++)
{
int a, b;scanf("%d%d", &a,
&b);
g[a].push_back(b);
g[b].push_back(a);
}
for(int i = 0; i
< q; i++)
{
int X, Y;
scanf("%d%d", &X,
&Y);
ask[X].push_back(pint(Y, i));
}
dfs(1, -1);
for(int i = 0; i
< q; i++)
if (jeo[i] == -1) printf("%d\n",
fa[jeo2[i]]);
else
printf("%d\n", jeo[i]);
}
return
0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n, m, dp[510][510][510], g[510][510];
int main()
{
while(scanf("%d%d", &n,
&m) != EOF)
{
memset(dp, -1,
sizeof(dp));
for(int i = 0; i
<= n; i++)
for(int j = 0; j <= n; j++)
for(int k =
0; k <= n; k++) dp[i][j][k] = 0x7fffffff;
memset(g, -1,
sizeof(g));
while(m--)
{
int a, b, c;scanf("%d%d%d", &a,
&b, &c);
if (g[a][b] == -1 || c <
g[a][b])
g[a][b] =
g[b][a] = c;
}
for(int k = 0; k
<= n; k++)
for(int i = 0; i <= n; i++)
for(int j =
0; j <= n; j++)
if (g[i][k] != -1
&& g[k][j] != -1
&& (g[i][j] == -1 || g[i][k] +
g[k][j] < g[i][j]))
g[i][j] = g[i][k] + g[k][j];
for(int i = 0; i
<= n; i++) g[i][i] = 0;
dp[0][0][0] = 0;
for(int i = 1; i
<= n; i++)
for(int j = 0; j < i; j++)
for(int k =
0; k < i; k++)
{
if (dp[i - 1][j][k] !=
0x7fffffff)
{
dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][k] +
g[i - 1][i]);
dp[i - 1][i][k] = min(dp[i - 1][i][k], dp[i -
1][j][k] + g[j][i]);
dp[i - 1][j][i] = min(dp[i - 1][j][i], dp[i -
1][j][k] + g[k][i]);
}
if (dp[j][i - 1][k] !=
0x7fffffff)
{
dp[i][i - 1][k] = min(dp[i][i - 1][k], dp[j][i -
1][k] + g[j][i]);
dp[j][i][k] = min(dp[j][i][k], dp[j][i - 1][k] +
g[i - 1][i]);
dp[j][i - 1][i] = min(dp[j][i - 1][i], dp[j][i -
1][k] + g[k][i]);
}
if (dp[j][k][i - 1] !=
0x7fffffff)
{
dp[i][k][i - 1] = min(dp[i][k][i - 1], dp[j][k][i
- 1] + g[j][i]);
dp[j][i][i - 1] = min(dp[j][i][i - 1], dp[j][k][i
- 1] + g[k][i]);
dp[j][k][i] = min(dp[j][k][i], dp[j][k][i - 1] +
g[i - 1][i]);
}
}
int ans = 0x7fffffff;
for(int i = 0; i
<= n; i++)
for(int j = 0; j <= n; j++)
{
int tmp =
g[i][0] + g[j][0] + g[n][0];
if
(dp[i][j][n] != 0x7fffffff) ans = min(dp[i][j][n] + tmp,
ans);
if
(dp[i][n][j] != 0x7fffffff) ans = min(dp[i][n][j] + tmp,
ans);
if
(dp[n][i][j] != 0x7fffffff) ans = min(dp[n][i][j] + tmp,
ans);
}
printf("%d\n", ans);
}
return
0;
}
#include<iostream>
#include<cstring>
#include<vector>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
struct pint
{
int
sc;
char
name[102];
}stu[5001];
vector<int> g[10001],
node[10001];
int n, m;
bool cmp(int a, int b)
{
return
stu[a - n].sc > stu[b - n].sc;
}
void dfs(int id, int pre)
{
for(int
i = 0; i < g[id].size(); i++)
if (g[id][i] != pre)
{
dfs(g[id][i], id);
}
sort(node[id].begin(), node[id].end(),
cmp);
if (pre
!= -1)
{
for(int i = 0; i
< 2 && i
< node[id].size(); i++)
{
//cout << pre
<< ' '
<< node[id][i]
<< ' '
<< stu[node[id][i] - n].sc
<< endl;
node[pre].push_back(node[id][i]);
}
}
}
int main()
{
while(scanf("%d%d", &n,
&m) != EOF)
{
int num = n + m;
for(int i = 1; i
<= n; i++)
{
g[i].clear();
node[i].clear();
}
for(int i = 1; i
< num; i++)
{
int a, b;
scanf("%d%d", &a,
&b);
int mmin = a, mmax = b;
if (b < mmin) mmin = b;
if (mmax < a) mmax = a;
if (a <= n
&& b <= n)
g[a].push_back(b), g[b].push_back(a);
else node[mmin].push_back(mmax);
}
for(int i = 1; i
<= m; i++)
{
scanf("%s%d", stu[i].name,
&stu[i].sc);
}
dfs(1, -1);
for(int i = 0; i
< node[1].size(); i++)
printf("%s\n", stu[node[1][i] - n].name);
}
return
0;
}
加载中…
喜欢