哇，貌似14年及以前的HAOI都是专门照顾弱省选手的套题么……
总体来看，HAOI2013的水题占了很大一部分，但也有很好的，区分度不错的题。经我排过版的题面可以在这里下载：Day1.pdf，Day2.pdf
下面是正文。
跑步训练(t1)
出题人你觉得这也叫省选难度？每一段都必须进行往返，我们直接计算出每段往返用的总时间（注意上下坡），然后从前到后依次加入并判断就好了。
时间复杂度，期望得分100分。当然代码是我几年前写的。
AC code
program P1368;
var
m,t,u,f,d,i,sum:longint;
c:char;
a:array[1..100000] of longint;
begin
readln(m,t,u,f,d);
for i:=1 to t do
begin
readln(c);
case c of
'u','d':a[i]:=u+d;
'f':a[i]:=2*f;
end;
end;
i:=0;
sum:=0;
while (sum<=m)and(i<=t) do
begin
inc(i);
inc(sum,a[i]);
end;
if i=t then writeln(t) else writeln(i-1);
end.
花卉节(t2)
因为这题只要求满意的人数最多，所以只要贪心，尽量优先选取较便宜的花卉即可。注意这题的很多数据接近long long的最大值，所以在中间运算过程中可能会越界，造成WA。我的解决办法是尽量少用乘法、加法，尽量用除法、减法代替，把中间值用实数存，这样就可以AC了。
时间复杂度大概是排序的，期望得分100分。
AC code
#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned long long ULL;
struct thing
{
ULL p, c;
};
inline bool operator <(thing x, thing y)
{
return x.p < y.p;
}
int n;
ULL b, cost, ans;
thing x[100010];
int main()
{
scanf("%d%llu", &n, &b);
for (int i = 0; i < n; i++)
scanf("%llu%llu", &x[i].p, &x[i].c);
sort(x, x + n);
for (int i = 0; i < n; i++)
{
ULL ls = (ULL)(1.0 * (b - cost) / x[i].p);
if (ls <= x[i].c)
{
ans +=ls;
break;
}
ans +=x[i].c;
cost += x[i].p * x[i].c;
}
printf("%llu\n", ans);
return 0;
}
开关控制(t3)
啊出题人居然在抄袭USACO的月赛题，太无耻了！
不过这题还是很有意思的。
算法一
根据题意，任何一盏灯连按两次相当于没按，所以这不可能是最优决策。因此每个灯最多按一次，暴力枚举每个开关是否按，然后判断并取最优解就好了。
时间复杂度，期望得分70分（这数据是我从COGS评测记录里发现的）。
算法二
首先，我们用邻接矩阵把图存下来。当然，因为按下一个开关也会改变它自己的状态，所以我们可以把对角线上的元素都设为true。
我们发现对于每个点，灯亮的条件是它本身和与它相连的所有点中，被按过的开关有奇数次。如果我们对每个点都设置一个变量表示第是否按过，那么也就是它及它相连的点的值之和为奇数。
看到这里，直觉告诉我们，这正好对应了一种位运算，因为奇数个1起来仍然是1，而偶数个1之后就变成了0。所以，这样子我们就列出了一个异或方程组：
然后就是解这个方程组。这里要用到高斯消元的方法，把这个方程组消成一个“上三角矩阵”，然后对方程组的所有变元，我们暴力枚举它们的取值，然后推出原方程组的解，计算出有多少个数是1，取最小值即可。
时间复杂度最坏是指数级的，不过可以通过最优性剪枝优化，但我并不会很好的分析。。。就当是好了。期望得分100分。
AC code
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct eq
{
bool c[100], a;
};
eq eqs[100], zero;
int n, m;
bool con[100][100];
int fre[100], cnt;
bool r[100];
int ans, ls;
bool operator <(eq x, eq y)
{
for (int i = 1; i <= n; i++)
if (x.c[i] != y.c[i])
return x.c[i] > y.c[i];
return false;
}
bool operator ==(eq x, eq y)
{
return (!(x < y) && !(y < x));
}
void dfs(int now)
{
if (ls > ans)
return;
if (now < cnt)
{
r[fre[now]] = 0;
dfs(now + 1);
r[fre[now]] = 1;
ls++;
dfs(now + 1);
ls--;
r[fre[now]] = 0;
}
else
{
int now = n, l = 0;
for (int i = n; i >= 1; i--)
{
int j;
for (j = 1; j <= now; j++)
if (eqs[i].c[j])
break;
if (j > now)
continue;
bool ls = 0;
for (int k = j + 1; k <= n; k++)
if (eqs[i].c[k])
ls ^= r[k];
r[j] = eqs[i].a ^ ls;
now = j - 1;
}
for (int i = 1; i <= n; i++)
l += r[i];
ans = min(ans, l);
}
}
int main()
{
freopen("haoi13t3.in", "r", stdin);
freopen("haoi13t3.out", "w", stdout);
scanf("%d%d", &n, &m);
memset(con, 0, sizeof(con));
for (int i = 0; i < m; i++)
{
int x, y;
scanf("%d%d", &x, &y);
con[x][y] = con[y][x] = 1;
}
for (int i = 1; i <= n; i++)
{
eqs[i].a = 1;
for (int j = 1; j <= n; j++)
if (i == j)
eqs[i].c[j] = 1;
else
eqs[i].c[j] = con[i][j];
}
sort(eqs + 1, eqs + n + 1);
int p = 1;
for (int i = 1; i <= n; i++)
{
bool flag = true;
for (int j = p; j <= n; j++)
if (eqs[j].c[i])
{
flag = false;
swap(eqs[p], eqs[j]);
break;
}
if (!flag)
{
for (int j = p + 1; j <= n; j++)
{
if (eqs[j].c[i])
{
for (int k = i; k <= n; k++)
eqs[j].c[k] ^= eqs[p].c[k];
eqs[j].a ^= eqs[p].a;
}
}
p++;
}
else
{
fre[cnt++] = i;
}
}
ans = n;
dfs(0);
printf("%d\n", ans);
return 0;
}
软件安装(t4)
感觉是比赛里唯一一道有区分度的题目了。当时写了好久，最后WA一大片，后来发现少打了个等号……
算法一
直接暴力枚举所有操作，暴力查询。
时间复杂度，期望得分我也不知道，就当是40分吧。
算法二
这题都是区间操作，很自然地会想到用线段树。不过想法还是很新奇的。
线段树上的每个线段除了保存儿子节点的指针之外，还要保存当前区间内最长的连续区间。但只保存这个的话是不能更新状态的对吧，我们还要存储从左边界开始的最长连续区间和到右边界结束的最长连续区间，然后就可以方便的维护了。
其实这维护的思想有些类似于NOI2005的《维修数列》，本身很简单，而这里的难点在于询问。询问的是定长的连续区间最靠左的位置，看似和我们维护的信息无关。但我们进行一些分析的话，问题就好办了。
首先，如果当前区间内的最长连续区间太小，那么直接返回不存在；如果区间长度恰等于询问长度，且区间内均为可行区间，那么返回左边界；如果左儿子区间内的最长连续区间大于等于询问区间，那么递归处理左儿子；如果左儿子区间内的最长连续区间太小，那么从当前区间的中点开始，尽量往左扩展，然后再尽量往右扩展，直到得到长度恰为所要求区间的长度，返回最左边的位置；如果上述操作都不存在可行解，再递归处理右儿子，这时肯定有解，不然最开始就可以返回无解了。
注意以上操作必须严格按照顺序，才能保证返回值最靠前。这样找到可行的区间之后，进行区间覆盖操作，更新线段树即可。
时间复杂度，期望得分100分。
（感觉口胡了好多啊，建议对着代码理解）
AC code
#include <cstdio>
#include <algorithm>
#include <cctype>
using namespace std;
int readint()
{
int x = 0;
char c = getchar();
while (!isdigit(c))
c = getchar();
x = c - '0';
c = getchar();
while (isdigit(c))
{
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
struct node
{
int l, r;
int m, lm, rm, mp;
int tag;
node() : l(0), r(0), m(0), lm(0), rm(0), mp(0), tag(-1) {}
node(int l, int r, int m, int lm, int rm, int mp, int tag) : l(l), r(r), m(m), lm(lm), rm(rm), mp(mp), tag(tag) {}
};
int n, m;
node sgt[300050];
void build(int p, int l, int r)
{
if (l == r)
{
sgt[p] = node(l, r, 1, 1, 1, l, -1);
return;
}
int mid = (l + r) / 2, len = r - l + 1;
build(p << 1, l, mid);
build(p << 1 | 1, mid + 1, r);
sgt[p] = node(l, r, len, len, len, l, -1);
}
void pushdown(int p)
{
if (sgt[p].tag == 1)
{
sgt[p << 1].tag = sgt[p << 1 | 1].tag = 1;
sgt[p].lm = sgt[p].rm = sgt[p].m = -1;
sgt[p].mp = -1;
sgt[p].tag = -1;
}
if (sgt[p].tag == 0)
{
sgt[p << 1].tag = sgt[p << 1 | 1].tag = 0;
sgt[p].lm = sgt[p].rm = sgt[p].m = (sgt[p].r - sgt[p].l + 1);
sgt[p].mp = sgt[p].l;
sgt[p].tag = -1;
}
}
void pushup(int p)
{
pushdown(p);
pushdown(p << 1);
pushdown(p << 1 | 1);
int x1 = sgt[p << 1].m, x2 = sgt[p << 1].rm + sgt[p << 1 | 1].lm, x3 = sgt[p << 1 | 1].m;
if (x1 >= x2 && x1 >= x3)
{
sgt[p].m = x1;
sgt[p].mp = sgt[p << 1].mp;
}
else if (x2 >= x3)
{
sgt[p].m = x2;
sgt[p].mp = sgt[p << 1].r - sgt[p << 1].rm + 1;
}
else
{
sgt[p].m = x3;
sgt[p].mp = sgt[p << 1 | 1].mp;
}
sgt[p].lm = sgt[p << 1].lm;
if (sgt[p << 1].lm == (sgt[p << 1].r - sgt[p << 1].l + 1))
sgt[p].lm = max(sgt[p].lm, sgt[p << 1].lm + sgt[p << 1 | 1].lm);
sgt[p].rm = sgt[p << 1 | 1].rm;
if (sgt[p << 1 | 1].rm == (sgt[p << 1 | 1].r - sgt[p << 1 | 1].l + 1))
sgt[p].rm = max(sgt[p].rm, sgt[p << 1].rm + sgt[p << 1 | 1].rm);
}
inline int query()
{
pushdown(1);
return sgt[1].m;
}
int getsmallest(int p, int len)
{
pushdown(p);
if (sgt[p].m < len)
return 0;
if (sgt[p].lm >= len)
return sgt[p].l;
if (sgt[p << 1].m >= len)
return getsmallest(p << 1, len);
if (sgt[p << 1].rm >= 0 && sgt[p << 1 | 1].lm >= 0 && sgt[p << 1].rm + sgt[p << 1 | 1].lm >= len)
return (sgt[p << 1].r - sgt[p << 1].rm + 1);
return getsmallest(p << 1 | 1, len);
}
void change(int p, int l, int r, int t)
{
pushdown(p);
if (l <= sgt[p].l && r >= sgt[p].r)
{
sgt[p].tag = t;
return;
}
if (l > sgt[p].r || r < sgt[p].l)
return;
change(p << 1, l, r, t);
change(p << 1 | 1, l, r, t);
pushup(p);
}
int main()
{
n = readint();
m = readint();
build(1, 1, n);
for (int i = 0; i < m; i++)
{
int type = readint();
if (type == 1)
{
int l = readint();
if (query() < l)
{
printf("0\n");
}
else
{
int ls = getsmallest(1, l);
printf("%d\n", ls);
change(1, ls, ls + l - 1, 1);
}
}
else
{
int s = readint();
int t = readint();
change(1, s, s + t - 1, 0);
}
}
return 0;
}
遥控器(t5)
小学生都会的最短路。Floyd算法都行。
时间复杂度，期望得分100分。你要想写Dijkstra或SPFA也很好啊~
AC code
#include <cstdio>
#define S1 100
#define S2 101
#define INF 10000000
int graph[110][110];
bool ok[13];
const int tr[13] = {1, 2, 3, 10, 4, 5, 6, 11, 7, 8, 9, 12, 0};
int main()
{
freopen("HAOI2013T5.in", "r", stdin);
freopen("HAOI2013T5.out", "w", stdout);
for (int i = 0; i < 13; i++)
{
int x;
scanf("%d", &x);
ok[tr[i]] = (x == 1);
}
int s, t;
scanf("%d%d", &s, &t);
for (int i = 0; i < 102; i++)
for (int j = 0; j < 102; j++)
graph[i][j] = (i == j) ? 0 : INF;
for (int i = 0; i < 100; i++)
graph[i][S1] = 0;
for (int i = 0; i < 10; i++)
if (ok[i])
graph[S1][i] = 1;
if (ok[10])
{
for (int i = 0; i < 99; i++)
graph[i][i + 1] = 1;
graph[99][0] = 1;
}
if (ok[11])
{
for (int i = 1; i < 100; i++)
graph[i][i - 1] = 1;
graph[0][99] = 1;
}
if (ok[12])
{
for (int i = 0; i < 100; i++)
graph[i][S2] = 1;
for (int i = 10; i < 100; i++)
if (ok[i / 10] && ok[i % 10])
graph[S2][i] = 2;
}
for (int k = 0; k < 102; k++)
for (int i = 0; i < 102; i++)
for (int j = 0; j < 102; j++)
if (graph[i][k] + graph[k][j] < graph[i][j])
graph[i][j] = graph[i][k] + graph[k][j];
if (graph[s][t] == INF)
puts("-1");
else
printf("%d\n", graph[s][t]);
return 0;
}
