T1：
比较水的模拟，注意点：多想特殊情况即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UL unsigned long long
10 #define P pair<I,I>
11 #define MP make_pair
12 #define fir first
13 #define sec second
14 #define lowbit(x) (x & -x)
15 I len;
16 UL a[10];
17 C s[50];
18 B typ;
19 inline I read() {
20 I x(0),y(1); C z(getchar ());
21 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
22 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
23 return x * y;
24 }
25 inline V Max (I &a,I b) { a = a > b ? a : b; }
26 inline V Min (I &a,I b) { a = a < b ? a : b; }
27 inline I max (I a,I b) { return a > b ? a : b; }
28 inline I min (I a,I b) { return a < b ? a : b; }
29 inline V swap (I &a,I &b) { a ^= b, b ^= a,a ^= b; }
30 signed main () {
31 scanf ("%s",s + 1);
32 len = strlen (s + 1);
33 I cnt(1);
34 for (I i(1);i <= len; ++ i) {
35 B jud1(0),jud2(0);
36 while (!isdigit(s[i]) && i <= len) {
37 typ = 1; i ++ ;
38 }
39 while ( isdigit(s[i]) && i <= len) {
40 if ( jud2) typ = 1;
41 if (!jud1 && (s[i] ^ 48) == 0) jud2 = 1;
42 jud1 = 1;
43 a[cnt] = a[cnt] * 10 + (s[i] ^ 48);
44 i ++ ;
45 if (i > len) break;
46 if ( isdigit(s[i])) continue;
47 else {
48 if (cnt != 4 && s[i] == '.') break;
49 else {
50 typ = 1; break;
51 }
52 }
53 }
54 cnt ++ ;
55 }
56 for (I i(1);i <= 4; ++ i)
57 if (a[i] > 255)
58 a[i] = 255, typ = 1;
59 if (!typ) puts ("YES");
60 else {
61 puts ("NO");
62 for (I i(1);i <= 4; ++ i) {
63 printf ("%llu",a[i]);
64 if (i != 4) printf (".");
65 }
66 }
67 }
View Code
注意化简问题
T2：
考场Dfs+记忆化+Hash
问题在于读题太慢，未想正解，直接打暴力，关键在于游戏的机制即只能删除AP || PP
发现关键点在于A只能由AP删除，而A又会阻碍P的删除
于是贪心的先把所有AP删除，再将所有P删除即可，具体实现采用栈模拟即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UL unsigned long long
10 #define P pair<I,I>
11 #define MP make_pair
12 #define fir first
13 #define sec second
14 #define lowbit(x) (x & -x)
15 const I N = 1e4 + 5;
16 C s[N];
17 B q[N];
18 inline I read() {
19 I x(0),y(1); C z(getchar ());
20 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
21 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
22 return x * y;
23 }
24 inline V Max (I &a,I b) { a = a > b ? a : b; }
25 inline V Min (I &a,I b) { a = a < b ? a : b; }
26 inline I max (I a,I b) { return a > b ? a : b; }
27 inline I min (I a,I b) { return a < b ? a : b; }
28 inline V swap (I &a,I &b) { a ^= b, b ^= a,a ^= b; }
29 signed main () {
30 scanf ("%s",s + 1);
31 I len (strlen (s + 1)),h(1),t(0);
32 for (I i(1); s[i] ; ++ i) {
33 if (s[i] == 'A')
34 q[++t] = 1;
35 else {
36 if (h <= t && q[t])
37 t -- ;
38 else q[++t] = 0;
39 }
40 }
41 I ans(t - h + 1);
42 for (I i(h);i <= t; ++ i) {
43 if (!q[i] && !q[i + 1])
44 ans -= 2, i ++ ;
45 }
46 printf ("%d\n",ans);
47 }
View Code
T3：
O(n^4)能过，然而时间不够了，调+优化T2用的时间太长
正解是考虑问题关键在于判断菱形，根据O(n^4)暴力的思路很容易想到记录所有点的祖先
正确性在于由于问题的机制，每个点作为K只会出现一次，无后消性
考虑如何判断菱形，比较显然的思路为在记录当前结点祖先时枚举所有子节点，合并祖先信息
若a & b != 0，则说明出现菱形，判掉即可
然而具体实现仍然有些细节：首先需要将点按出现时间从大到小排序，因为在处理当前点父节点时，
可能父节点也是另一父节点的父节点，而从大到小排序可以解决问题，而从小到大排序却极难实现
因为菱形与父节点的判断都是由时间早向时间晚进行，同序（记录时间从小到大，并从小到大排序）难以判断
无法理解则根据时间顺序与节点关系造Hack数据即可
代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3 #define I int
4 #define C char
5 #define B bool
6 #define V void
7 #define D double
8 #define LL long long
9 #define UL unsigned long long
10 #define P pair<I,I>
11 #define MP make_pair
12 #define fir first
13 #define sec second
14 #define lowbit(x) (x & -x)
15 const I N = 1005;
16 I n,num;
17 unordered_map <string,I> h;
18 string s,t;
19 bitset <N> jud[N];
20 inline I read() {
21 I x(0),y(1); C z(getchar ());
22 while (!isdigit(z)) { if (z == '-') y = -1; z = getchar(); }
23 while ( isdigit(z)) x = x * 10 + (z ^ 48), z = getchar();
24 return x * y;
25 }
26 inline V Max (I &a,I b) { a = a > b ? a : b; }
27 inline V Min (I &a,I b) { a = a < b ? a : b; }
28 inline I max (I a,I b) { return a > b ? a : b; }
29 inline I min (I a,I b) { return a < b ? a : b; }
30 inline V swap (I &a,I &b) { a ^= b, b ^= a,a ^= b; }
31 inline B com (const I &a,const I &b) { return a > b; }
32 signed main () {
33 n = read();
34 for (I i(1);i <= n; ++ i) {
35 I idx; B typ(0);
36 vector <I> anc;
37 bitset <N> a;
38 cin >> s;
39 h.find (s) != h.end () ?
40 typ = 1 : idx = ++num;
41 getchar (); getchar (); getchar ();
42 while (1) {
43 cin >> t; getchar();
44 if (t[0] == ';') break;
45 if (h.find (t) != h.end ())
46 anc.push_back (h[t]);
47 else
48 typ = 1;
49 }
50 if (typ) goto flag;
51 sort (anc.begin (),anc.end (),com);
52 for (auto y : anc) if (!a[y]) {
53 if ((a & jud[y]).any ()) typ = 1;
54 a |= jud[y]; a[y] = 1;
55 }
56 if (!typ) jud[idx] = a, h[s] = idx;
57 flag : typ ? puts ("greska") : puts ("ok");
58 }
59
60 }
View Code