【训练赛地址】点击打开链接
【PS】由于几乎是中文题目和题目比较短，就不说题意了。
【A】中文题目，状压+BFS，没有什么坑点，上代码。
【AC代码】
// //Created by just_sort 2016/12/1 //Copyright (c) 2016 just_sort.All Rights Reserved // #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/hash_policy.hpp> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; using namespace __gnu_pbds; typedef long long LL; typedef pair<int, LL> pp; #define MP(x,y) make_pair(x,y) const int maxn = 200005; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set; //head int n, m, tt, sx, sy; int dir[4][2] = {{0,1},{0,-1},{-1,0},{1,0}}; char maze[22][22]; bool vis[22][22][1<<10]; struct node{ int x, y, t, state; node(){} node(int x, int y, int t, int state):x(x), y(y), t(t), state(state){} }; int getid(char c) { if(islower(c)){ return c - 'a'; } else{ return c - 'A'; } } int bfs() { queue<node>q; node now, nex; now = node(sx, sy, 0, 0); q.push(now); vis[sx][sy][0] = 1; while(!q.empty()){ now = q.front(); q.pop(); if(now.t >= tt) break; for(int i = 0; i < 4; i++){ int dx = now.x + dir[i][0]; int dy = now.y + dir[i][1]; int t = now.t + 1; int state = now.state; if(vis[dx][dy][state] || dx < 0 || dx >= n || dy < 0 || dy >= m || maze[dx][dy] == '*'){ continue; } if(isupper(maze[dx][dy]) && !(state & (1<<getid(maze[dx][dy])))) continue; if(islower(maze[dx][dy])) state |= (1<<getid(maze[dx][dy])); if(maze[dx][dy] == '^') return t; if(!vis[dx][dy][state]){ vis[dx][dy][state] = 1; q.push(node(dx, dy, t, state)); } } } return -1; } int main() { while(scanf("%d%d%d",&n,&m,&tt)!=EOF) { tt -= 1; memset(vis, false, sizeof(vis)); for(int i = 0; i < n; i++) scanf("%s", maze[i]); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ if(maze[i][j] == '@'){ sx = i, sy = j, maze[i][j] = '.'; break; } } } int ans = bfs(); printf("%d\n",ans); } return 0; } 【B】先考虑每一行，再考虑一下每一行里面的元素，发现解决的这个问题有大量的重叠子问题，一个简单的dp想法就由然而生了。【代码君】
// //Created by just_sort 2016/12/1 //Copyright (c) 2016 just_sort.All Rights Reserved // #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/hash_policy.hpp> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; using namespace __gnu_pbds; typedef long long LL; typedef pair<int, LL> pp; #define MP(x,y) make_pair(x,y) const int maxn = 200005; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set; //head int dp1[maxn], dp2[maxn]; int n, m; int main() { while(scanf("%d%d",&n,&m)!=EOF) { memset(dp1, 0, sizeof(dp1)); memset(dp2, 0, sizeof(dp2)); for(int i = 2; i <= n + 1; i++){ for(int j = 2; j <= m + 1; j++){ int x; scanf("%d", &x); dp1[j] = max(dp1[j-1], dp1[j-2]+x); } dp2[i] = max(dp2[i-1], dp2[i-2] + dp1[m + 1]); } printf("%d\n", dp2[n+1]); } return 0; } 【C】就是线段树的区间合并问题，不过这个题要维护的东西有点多，看代码吧。 // //Created by just_sort 2016/12/1 //Copyright (c) 2016 just_sort.All Rights Reserved // //#include <ext/pb_ds/assoc_container.hpp> //#include <ext/pb_ds/tree_policy.hpp> //#include <ext/pb_ds/hash_policy.hpp> //#include <set> //#include <map> //#include <queue> //#include <stack> //#include <cmath> //#include <cstdio> //#include <cstdlib> //#include <cstring> //#include <iostream> //#include <algorithm> //using namespace std; //using namespace __gnu_pbds; //typedef long long LL; //typedef pair<int, LL> pp; //#define MP(x,y) make_pair(x,y) const int maxn = 200005; //typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set; //head #include <cstdio> #include <iostream> #include <algorithm> using namespace std; struct node{ int l, r, len; int l0, l1;//左端点开始的0,1的个数 int r0, r1;//右端点开始的0,1的个数 int max0, max1, cnt0, cnt1, flag;//区间连续0,1的个数，区间0,1的个数 }Tree[maxn<<2]; int n, m, A[maxn]; void pushup(int rt) { Tree[rt].l0 = Tree[rt*2].l0; if(Tree[rt*2].l0 == Tree[rt*2].len) Tree[rt].l0 += Tree[rt*2+1].l0; Tree[rt].r0 = Tree[rt*2+1].r0; if(Tree[rt*2+1].r0 == Tree[rt*2+1].len) Tree[rt].r0 += Tree[rt*2].r0; Tree[rt].max0 = max(Tree[rt*2].max0, Tree[rt*2+1].max0); Tree[rt].max0 = max(Tree[rt].max0, Tree[rt*2].r0 + Tree[rt*2+1].l0); Tree[rt].cnt0 = Tree[rt*2].cnt0 + Tree[rt*2+1].cnt0; Tree[rt].l1 = Tree[rt*2].l1; if(Tree[rt*2].l1 == Tree[rt*2].len) Tree[rt].l1 += Tree[rt*2+1].l1; Tree[rt].r1 = Tree[rt*2+1].r1; if(Tree[rt*2+1].r1 == Tree[rt*2+1].len) Tree[rt].r1 += Tree[rt*2].r1; Tree[rt].max1 = max(Tree[rt*2].max1, Tree[rt*2+1].max1); Tree[rt].max1 = max(Tree[rt].max1, Tree[rt*2].r1 + Tree[rt*2+1].l1); Tree[rt].cnt1 = Tree[rt*2].cnt1 + Tree[rt*2+1].cnt1; //Tree[rt].len = Tree[rt*2].len + Tree[rt*2+1].len; } void Build(int l, int r, int rt) { Tree[rt].l = l, Tree[rt].r = r, Tree[rt].len = r - l + 1, Tree[rt].flag = -1; if(l == r){ Tree[rt].l0 = Tree[rt].r0 = Tree[rt].max0 = Tree[rt].cnt0 = !A[l]; Tree[rt].l1 = Tree[rt].r1 = Tree[rt].max1 = Tree[rt].cnt1 = A[l]; return ; } int mid = (l + r) / 2; Build(l, mid, rt*2); Build(mid+1, r, rt*2+1); pushup(rt); } void update(int L, int R, int rt, int cmd) { if(Tree[rt].l == L && Tree[rt].r == R){ if(cmd == 0) { Tree[rt].l0 = Tree[rt].r0 = Tree[rt].max0 = Tree[rt].cnt0 = Tree[rt].len; Tree[rt].l1 = Tree[rt].r1 = Tree[rt].max1 = Tree[rt].cnt1 = 0; Tree[rt].flag = 0; } else if(cmd == 1){ Tree[rt].l0 = Tree[rt].r0 = Tree[rt].max0 = Tree[rt].cnt0 = 0; Tree[rt].l1 = Tree[rt].r1 = Tree[rt].max1 = Tree[rt].cnt1 = Tree[rt].len; Tree[rt].flag = 1; } else if(cmd == 2){ swap(Tree[rt].l0, Tree[rt].l1); swap(Tree[rt].r0, Tree[rt].r1); swap(Tree[rt].max0, Tree[rt].max1); swap(Tree[rt].cnt0, Tree[rt].cnt1); Tree[rt].flag = 1 - Tree[rt].flag; } return ; } //lazy 操作 if(Tree[rt].flag >= 0){ update(Tree[rt*2].l, Tree[rt*2].r, rt*2, Tree[rt].flag); update(Tree[rt*2+1].l, Tree[rt*2+1].r, rt*2+1, Tree[rt].flag); Tree[rt].flag = -1; } int mid = (Tree[rt].l + Tree[rt].r) / 2; if(R <= mid) update(L, R, rt*2, cmd); else if(L > mid) update(L, R, rt*2+1, cmd); else { update(L, mid, rt*2, cmd); update(mid+1, R, rt*2+1, cmd); } pushup(rt); } node query(int L, int R, int rt) { if(L == Tree[rt].l && Tree[rt].r == R) return Tree[rt]; //lazy 操作 if(Tree[rt].flag >= 0){ update(Tree[rt*2].l, Tree[rt*2].r, rt*2, Tree[rt].flag); update(Tree[rt*2+1].l, Tree[rt*2+1].r, rt*2+1, Tree[rt].flag); Tree[rt].flag = -1; } int mid = (Tree[rt].l + Tree[rt].r) / 2; if(R <= mid) return query(L, R, rt*2); else if(L > mid) return query(L, R, rt*2+1); else{ node t1, t2, t3; t1 = query(L, mid, rt*2); t2 = query(mid+1, R, rt*2+1); t3.cnt1 = t1.cnt1 + t2.cnt1; t3.l1 = t1.l1; if(t1.l1 == t1.len) t3.l1 += t2.l1; t3.r1 = t2.r1; if(t2.r1 == t2.len) t3.r1 += t1.r1; t3.max1 = max(t1.max1, t2.max1); t3.max1 = max(t3.max1, t1.r1 + t2.l1); t3.len = t1.len + t2.len; return t3; } } int main() { int n, m; while(scanf("%d%d",&n,&m) != EOF) { for(int i = 1; i <= n; i++) scanf("%d", &A[i]); Build(1, n, 1); int op, a, b; for(int i = 1; i <= m; i++){ scanf("%d%d%d",&op,&a,&b); a++; b++; if(op <= 2){ update(a, b, 1, op); } else{ node ans = query(a, b, 1); if(op == 3){ printf("%d\n",ans.cnt1); } else{ printf("%d\n",ans.max1); } } } } return 0; } 【D】贪心+排序， 按比率排，避免小数，所以讲式子进行转换【代码君】
// //Created by just_sort 2016/12/1 //Copyright (c) 2016 just_sort.All Rights Reserved // #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/hash_policy.hpp> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; using namespace __gnu_pbds; typedef long long LL; typedef pair<int, LL> pp; #define MP(x,y) make_pair(x,y) const int maxn = 200005; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set; //head struct node{ int dps, hp; node(){} node(int dps, int hp):dps(dps), hp(hp){} bool operator <(const node &rhs) const{ return (hp*rhs.dps) < (dps*rhs.hp); } void read(){ scanf("%d%d",&dps,&hp); } }a[22]; int main() { int n; while(scanf("%d",&n)!=EOF) { for(int i = 0; i < n; i++) a[i].read(); sort(a, a + n); int sum = 0; int ans = 0; for(int i = 0; i < n; i++){ sum = sum + a[i].dps; } for(int i = 0; i < n; i++){ ans = ans + sum * a[i].hp; sum = sum - a[i].dps; } printf("%d\n", ans); } return 0; } 【E】 将不小于m的数看成1，剩下的看成0，只要区间1的个数不小于k就可以，枚举区间左端点，右端点可以通过two-pointers求出，时间复杂度O(n)【代码君】
// //Created by just_sort 2016/12/1 //Copyright (c) 2016 just_sort.All Rights Reserved // #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> #include <ext/pb_ds/hash_policy.hpp> #include <set> #include <map> #include <queue> #include <stack> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> using namespace std; using namespace __gnu_pbds; typedef long long LL; typedef pair<int, LL> pp; #define MP(x,y) make_pair(x,y) const int maxn = 200005; typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>order_set; //head int a[maxn]; int n, m, K; LL ans; int main() { int T, n; scanf("%d",&T); while(T--){ scanf("%d%d%d", &n,&m,&K); for(int i = 1; i <= n; i++) scanf("%d",&a[i]); ans = 0; int r = 0, num = 0; for(int i = 1; i <= n; i++){ while(num < K && r <= n){r++; num += (a[r] >= m);} if(num < K) break; ans += n - r + 1; num -= (a[i] >= m); } printf("%lld\n",ans); } return 0; }