CSU-OJ补完计划（一，10xx）
20170209
虽然好几年来一直是CSU-OJ的super admin，但是退役后就没怎么管OJ了，都是每年的在役队员在加题。不同人对学校OJ的理解不同，有的当对外交流的窗口，有的只是当一个内部的训练工具，导致部分题目残缺、题号不连续等许多问题。多年不做题也怕手生了挺可惜的，打算业余时间偶尔刷几题，把OJ题目重新整理下，调调字体，补补图之类的，顺便做个完整题解。不知道能不能坚持下去，先挖坑吧。
20170222
OJ丑得看不下去了……重做了一个，近期上线吧。
20170307
OJ、主页、报名系统三个网站合并到一起做了个新网站，已上线。 日志留念 CSU-ACM Home Page
1015: 机器人训练
20170316
把每两个点之间的移动，都分解成一横一竖两个移动，两个移动相互独立，只需要关心移动前后面对的方向，这样思路会清晰许多。
每一步从一个箭头末端去下一个箭头始端，无非都是走一个“L”，只有一个决策不同，先横着还是先竖着，受前后两个箭头方向的影响会有不同的转弯次数。但是不必分类讨论，都走一走试试就好了，只需要调一下分解后的横竖移动的顺序，纯粹模拟即可，稍注意下点重合的情况。
1 |
|
1014: 西湖三人行
20170316
先想到的思路是直接DP，dp[cost][status][site]，当前花费、状态（行走、在哪个公交上、在出租上且走了几公里，超过3公里按3公里算）、当前站点，优化的是走的时间。 这个思路的问题是，虽然dp的状态空间是 101*204*100，但是每次更新状态还有100数量级的边遍历，这样就行不通了。然而这个方法却水过去了。
更好的方法状态空间是dp[cost][site]，省去status这一维，需要预处理建图。根据三种交通方式，统一地建成一个点到点的距离+花费的无差别图。
首先是bus，因为公交不会抄近道，如果路线是3->4->5，它不会因为3->6->5更近就绕道，对bus线路上所有能一次性到达的两点都建一条边。
bus之后，就可以Floyd了，因为走路和出租车都是选最短路走的。Floyd之后对任意两点按直达建边。
这样建图在DP时候不需要考虑“当前状态”，比如出租车，都 只考虑起点发车 ，如果不是起点发车， 自然有其他的点建了直达边 。
如此得到了一个有重边的，每条边有距离、花费两个边权的链式图。接下来就可以DP了。最短路做DP也可以，不过多此一举，干净的DP就好。
1 |
|
1013: 狐狸与小狗
20170314
一共32个位置，至多C(32, 5) * 5 * 2 = 2013760种状态，基本思路是状态DP，不难想，却难A。当年出题人或许是为了卡map，设置了1秒，我也不乱改时限了，不过还是用unordered_map先水过了一下。 要做到正常时限还是要自己写Hash，Hash写对了，状态随便压缩一下做记忆化搜索基本就能过了。不过还可以有一些“看起来”挺酷的“优化”。
把所有能放的格子编号，就是0~31，表达棋子位置就有三种模式：坐标(x, y)，编号(0~31)，位标记(0, 2, 4, 8 ... 2147483648)，32个位置用位标记需要unsigned int。 棋子走动，其实就是按位左移或右移3~5个位，棋子能不能落下，就是单个棋子的新位置与所有棋子的旧位置按位与一下来判断。一些细节的分类讨论也可以用位运算减少代码量。
1 |
|
1012: Prestige
20170313
首先理解题意是两个人都要争取自己拿到的多，在这个前提下让对方也拿到的多。优先拿对自己价值高的，等价情况下优先拿走对对方价值低的（把等价情况下对对方价值高的留给对方），这个思路是对的，也即Han也会用这个思路拿，但需要一个全局策略，即求一个全局的尽可能按上面思路拿的策略。
题目数据规模不允许进行全局状态的DP（比如位运算什么的），那么只能用一个调整的策略。
Li的策略比较直白，所以先按Li取的优先级排序，然后游戏开始。
考虑第i个物品，轮到Han，则假设直接取，但做记录，轮到Li，则看物品i对于已假设Han取了的物品集合而言，是否比这个集合中对Han价值最差的（对Han价值尽可能低，对Li价值尽可能高）物品x，要价值更好，如果更好，那么“时光倒流”，当Han面对物品x的时候，取i，因为已经排序，所以“当时”如果取了i，Li肯定会取x。
不断这样进行下去，这个假设的集合最终就是Han的策略会取的物品集合。
需要Log(n)来找到这个x，用一个优先级队列。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
using namespace std;
typedef pair<int, int> pii;
struct cmp { ;
bool operator()(const pii &a, const pii &b) const {
return a.first != b.first ? a.first > b.first : a.second < b.second;
}
};
int main()
{
int t, n, l, h;
char start[10];
for(scanf("%d", &t); t --; )
{
priority_queue<pii, vector<pii>, cmp> H;
int ansl = 0, ansh = 0;
vector<pii> L;
scanf("%d%s", &n, start);
for(int i = 0; i < n; i ++)
{
scanf("%d%d", &l, &h);
L.push_back(pii(l, h));
}
sort(L.begin(), L.end(), cmp());
if(start[0] == 'L')
ansl += L[0].first;
for(int isH = 1, i = start[0] == 'L'; i < L.size(); isH ^= 1, i ++)
{
pii &now = L[i];
if(isH)
{
ansh += now.second;
H.push(pii(now.second, now.first));
}
else
{
if(!cmp()(pii(now.second, now.first), H.top()))
ansl += now.first;
else
{
ansl += H.top().second;
ansh -= H.top().first;
ansh += now.second;
H.pop();
H.push(pii(now.second, now.first));
}
}
}
printf("%d %d\n", ansl, ansh);
}
return 0;
}
1011: Counting Pixels
20170313
只与半径有关，考虑右上的四分之一圆最后乘 4 即可。半径是整数，把这四分之一圆圈住的像素看作一列一列，圆与每列左边界的交点向上取整就是这一列的像素数，加起来。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
long long x, y, r;
while(scanf("%lld%lld%lld", &x, &y, &r) && (x || y || r))
{
long long ans = 0;
for(long long i = 0; i < r; i ++)
{
ans += (long long)(ceil(sqrt(r * r - i * i)) + 1e-8);
}
printf("%lld\n", ans * 4);
}
return 0;
}
1010: Water Drinking
20170222
很稀疏的图，记录父子节点关系最后枚举迭代一下就好。不过其实是个食物链并查集模型，比基本并查集多维护一个与父节点的距离。 已经忘了食物链怎么写了，于是复习一下。。。其实还是瞎写的。
1 |
|
1009: 抛硬币
20170222
对每列排序，大的跟大的乘，小的很小的乘，最后加起来总期望最高。 证明： 设a>c, b>d, (ab+cd) - (ad + bc) = (a - c)*(b - d) > 0，即假设已排好序，这时调换任意两个数的位置，得到的结果会小于先前。
1 |
|
1008: Horcrux
20170222
用栈的结构，每段连续相同颜色的第一个的位置为栈元素，每次变色，相当于最后一段连续颜色的起点变成了当前起点的上一个，也即出栈操作。过程中控制好颜色标记。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int main()
{
int n, horcrux, nowcolor;
std::stack<int> s;
while(scanf("%d", &n) != EOF)
{
nowcolor = -1;
for(int i = 1; i <= n; i ++)
{
scanf("%d", &horcrux);
if(s.empty() || horcrux != nowcolor && (i & 1))
{
s.push(i);
nowcolor = horcrux;
}
else if(horcrux != nowcolor)
{
nowcolor = horcrux;
if(s.size() > 1) s.pop();
}
}
int ans = 0, right = n + 1;
while(!s.empty())
{
ans += (!nowcolor) * (right - s.top());
nowcolor = !nowcolor;
right = s.top();
s.pop();
}
printf("%d\n", ans);
}
return 0;
}
1007: 矩形着色
20170222
把情况想清楚就好。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int main()
{
int t;
int px, py, ax, ay, bx, by;
for(scanf("%d", &t); t --; )
{
scanf("%d%d%d%d%d%d", &px, &py, &ax, &ay, &bx, &by);
if(px < ax || px > bx || py < ay || py > by)
printf("Outside\n");
else if(px == ax || px == bx || py == ay || py == by)
printf("On\n");
else
printf("Inside\n");
}
return 0;
}
1006: SAW
20170222
当年校队的大大们给新人开的一个小玩笑。当时还没看过《电锯惊魂》，都没理解标题的SAW是什么意思。 题目就是随机一个大写的26个英文字母之一，随机也好固定一个字母押宝也好，过的概率是一样的。
但是前些天看到有个代码100% AC，还以为spj坏了，看了一下spj的代码，原来是当年随机字母就用的srand(time(0))做种子，提交的代码也这样，而提交代码与spj代码运行时间很近，两个种子就一样了。
于是我邪恶地把spj的随机过程搞得更乱了 😂。 1
2
3
4
5
6
int main()
{
printf("A");
return 0;
}
1005: Binary Search Tree analog
20170222
二叉搜索树基础 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
struct Node
{
int num;
int left;
int right;
Node(){left = right = num = -1;}
};
Node nd[1111];
int ltp;
void Insert(int x, int now)
{
if(nd[now].num == -1)
nd[now].num = x;
else if(nd[now].num > x)
{
if(nd[now].left == -1)
nd[ltp] = Node(), nd[now].left = ltp ++;
Insert(x, nd[now].left);
}
else
{
if(nd[now].right == -1)
nd[ltp] = Node(), nd[now].right = ltp ++;
Insert(x, nd[now].right);
}
}
bool printed;
void PrintTree(int now, int order)
{
if(order == 1)
printf(printed ? " %d" : "%d", nd[now].num), printed = true;
if(nd[now].left != -1)
PrintTree(nd[now].left, order);
if(order == 2)
printf(printed ? " %d" : "%d", nd[now].num), printed = true;
if(nd[now].right != -1)
PrintTree(nd[now].right, order);
if(order == 3)
printf(printed ? " %d" : "%d", nd[now].num), printed = true;
}
int main()
{
int t, n;
for(scanf("%d", &t); t --; )
{
scanf("%d", &n);
ltp = 0;
nd[ltp ++] = Node();
int x;
while(n --)
{
scanf("%d", &x);
Insert(x, 0);
}
printed = false; PrintTree(0, 1); printf("\n");
printed = false; PrintTree(0, 2); printf("\n");
printed = false; PrintTree(0, 3); printf("\n");
printf("\n");
}
return 0;
}
1004: Xi and Bo
20170222
用并查集合并相连的站点。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
int p[111];
int fa(int x)
{
return x == p[x] ? x : (p[x] = fa(p[x]));
}
int main()
{
int t, n, m, start, end;
for(scanf("%d", &t); t --; )
{
scanf("%d%d", &start, &end);
scanf("%d", &n);
for(int i = 0; i <= 100; i ++)
p[i] = i;
for(int i = 0; i < n; i ++)
{
scanf("%d", &m);
int first = -1, connected;
while(m --)
{
scanf("%d", &connected);
if(first == -1)
first = connected;
else
p[fa(connected)] = fa(first);
}
}
printf("%s\n", fa(start) == fa(end) ? "Yes" : "No");
}
return 0;
}
按题意做。 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int main()
{
int t, n;
char buf[111];
for(scanf("%d", &t); t --; )
{
int score = 0, tmpscore = 0;
scanf("%d%s", &n, buf);
for(int i = 0; i <= n; i ++)
{
buf[i] == '1' ? tmpscore ++ : (tmpscore = 0);
score += 10 * ((tmpscore - 1) % 5 + 1);
}
int level = (score + 50) / 100;
printf("%d\n", level > 8 ? 8 : level);
}
return 0;
}
1002: A+B (III)
20170209
int64基础知识。CSU-OJ是Linux编译器，用long long 1
2
3
4
5
6
7
8
9
10
11
12
int main()
{
long long a, b;
while(scanf("%lld%lld", &a, &b) && a && b)
{
printf("%lld\n", a + b);
}
return 0;
}
1 |
|
1000: A+B (I)
20170209
1 |
|