国庆5天乐在今天终于结束了，怀着明天又得上学的心情，我开始写这篇题解。
T1 wzoi
期望得分：100
实际得分：100
首先题面非常的迷，我看了十分钟都没懂，看完T2，T3后再回来看T1，总共看题看了20分钟才懂……
我发现最优的答案一定是回文串，那么ans = 10 * (len / 2)，于是为了维护这个，我就开了个栈，如果栈是空的或者栈顶元素和当前数字不同，就放入栈，否则就把栈顶元素弹出，加10分。最后栈中要么不剩，要么一定是偶数个，加上5 * num / 2即可。
总的来说就是贪心，正确性其实我也不太确定，但是手出的数据都过了……
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e6 + 5; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 void MYFILE() 37 { 38 #ifndef mrclr 39 freopen("wzoi.in", "r", stdin); 40 freopen("wzoi.out", "w", stdout); 41 #endif 42 } 43 44 int n; 45 char c[maxn]; 46 int a[maxn]; 47 int st[maxn], sc = 0; 48 int ans = 0; 49 50 int main() 51 { 52 MYFILE(); 53 scanf("%s", c + 1); 54 n = strlen(c + 1); 55 for(int i = 1; i <= n; ++i) a[i] = c[i] - '0'; 56 for(int i = 1; i <= n; ++i) 57 { 58 if(!sc || st[sc] != a[i]) st[++sc] = a[i]; 59 else ans += 10, sc--; 60 } 61 if(sc) ans += 5 * (sc >> 1); 62 write(ans); enter; 63 return 0; 64 }
T2 course
期望得分：10
实际得分：40
这题实在不会，开始搞10%的暴力：枚举全排列，然后判断是否合法，如果合法，在O(nm)判断单词是否是一个子串，记录个数。复杂度O(n! * n2 * m)。
对于大的数，固输0.000000.
然后成绩下来后也是惊了：0的点竟然有三个，净赚30.
标程说出来可能不信：随机 +暴力判断。按题中描述可知，这些点构成一个森林，然后对于每一层的拓扑序，直接随机选哪个根节点，这样就得到了一个序列，剩下的就和暴力一样了。
Ssy大佬直接随机序列，连判断都没有，竟然期望得分80~100……果然tql。
放一个考场40分的代码吧
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 20; 21 inline ll read() 22 { 23 ll ans = 0; 24 char ch = getchar(), last = ' '; 25 while(!isdigit(ch)) {last = ch; ch = getchar();} 26 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 27 if(last == '-') ans = -ans; 28 return ans; 29 } 30 inline void write(ll x) 31 { 32 if(x < 0) x = -x, putchar('-'); 33 if(x >= 10) write(x / 10); 34 putchar(x % 10 + '0'); 35 } 36 void MYFILE() 37 { 38 #ifndef mrclr 39 freopen("course.in", "r", stdin); 40 freopen("course.out", "w", stdout); 41 #endif 42 } 43 44 int n, m, pre[maxn], t[maxn]; 45 char c[maxn], no[6][21], New[maxn]; 46 bool vis[maxn]; 47 48 bool judge() 49 { 50 for(int i = 1; i <= n; ++i) vis[i] = 0; 51 vis[0] = 1; 52 for(int i = 1; i <= n; ++i) 53 { 54 if(!vis[pre[t[i]]]) return 0; 55 vis[t[i]] = 1; 56 New[i] = c[t[i]]; 57 } 58 return 1; 59 } 60 void work0() 61 { 62 int tot = 0, totno = 0; 63 do 64 { 65 if(judge()) 66 { 67 tot++; 68 for(int i = 1; i <= m; ++i) 69 { 70 bool flg = 0; 71 int l = strlen(no[i] + 1); 72 for(int j = 1; j <= n - l + 1; ++j) 73 { 74 bool flg2 = 1; 75 for(int k = 1; k <= l; ++k) 76 if(New[j + k - 1] != no[i][k]) {flg2 = 0; break;} 77 if(flg2) {flg = 1; break;} 78 } 79 if(flg) {totno++; break;} 80 } 81 } 82 }while(next_permutation(t + 1, t + n + 1)); 83 printf("%.6lf ", (db)(tot - totno) / (db)tot); 84 } 85 86 int main() 87 { 88 MYFILE(); 89 n = read(); 90 if(n > 18) {printf("0.000000 "); return 0;} 91 for(int i = 1; i <= n; ++i) pre[i] = read(), t[i] = i; 92 scanf("%s", c + 1); 93 m = read(); 94 for(int i = 1; i <= m; ++i) scanf("%s", no[i] + 1); 95 work0(); 96 return 0; 97 }
T3 painting
期望得分：40
实际得分：30
这噶的更不会了！
不过40分暴力想想还是能写出来的：把bfs的队列改成优先队列，每一次都从当前已经算出的最小的数向四个方向延伸，而且延伸出来的一定是w + d（w == wmin），因为对于任意一个w，一定有w + d >= wmin + d，说明这个点一定不是限制上限的点，为了最大化ans，就取w + d。
丢了10分是因为没开long, long。（太zz了……）
正解：没看懂。
40分代码
1 #include<cstdio> 2 #include<iostream> 3 #include<cmath> 4 #include<algorithm> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cctype> 8 #include<vector> 9 #include<stack> 10 #include<queue> 11 using namespace std; 12 #define enter puts("") 13 #define space putchar(' ') 14 #define Mem(a, x) memset(a, x, sizeof(a)) 15 #define rg register 16 typedef long long ll; 17 typedef double db; 18 const int INF = 0x3f3f3f3f; 19 const db eps = 1e-8; 20 const int maxn = 1e3 + 5; 21 const ll mod = 1e9 + 7; 22 inline ll read() 23 { 24 ll ans = 0; 25 char ch = getchar(), last = ' '; 26 while(!isdigit(ch)) {last = ch; ch = getchar();} 27 while(isdigit(ch)) {ans = ans * 10 + ch - '0'; ch = getchar();} 28 if(last == '-') ans = -ans; 29 return ans; 30 } 31 inline void write(ll x) 32 { 33 if(x < 0) x = -x, putchar('-'); 34 if(x >= 10) write(x / 10); 35 putchar(x % 10 + '0'); 36 } 37 void MYFILE() 38 { 39 #ifndef mrclr 40 freopen("painting.in", "r", stdin); 41 freopen("painting.out", "w", stdout); 42 #endif 43 } 44 45 int n, m, k, d; 46 ll mp[maxn][maxn], ans = 0; 47 48 const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}; 49 struct Node 50 { 51 int x, y; 52 ll w; 53 bool operator < (const Node &oth)const 54 { 55 return w > oth.w; 56 } 57 }; 58 priority_queue<Node> q; 59 void bfs() 60 { 61 while(!q.empty()) 62 { 63 Node now = q.top(); q.pop(); 64 ans += now.w; ans %= mod; 65 for(int i = 0; i < 4; ++i) 66 { 67 int newx = now.x + dx[i], newy = now.y + dy[i]; 68 if(newx > 0 && newx <= n && newy > 0 && newy <= m) 69 { 70 if(mp[newx][newy]) 71 { 72 if(mp[newx][newy] > now.w + d) 73 {printf("IMPOSSIBLE "); return;} 74 } 75 else 76 { 77 mp[newx][newy] = now.w + d; 78 q.push((Node){newx, newy, now.w + d}); 79 } 80 } 81 } 82 } 83 write(ans); enter; 84 } 85 86 int main() 87 { 88 MYFILE(); 89 n = read(); m = read(); k = read(); d = read(); 90 if(n > 1000 || m > 1000) {printf("IMPOSSIBLE "); return 0;} 91 for(int i = 1; i <= k; ++i) 92 { 93 int x = read(), y = read(), w = read(); 94 mp[x][y] = w; 95 q.push((Node){x, y, w}); 96 } 97 bfs(); 98 return 0; 99 }
总结一下：第一题送的，剩下两题暴力+固输 = 40 + 40，所以今天应该180起……