【训练赛地址】点击打开链接
【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;
}
京公网安备 11010502036488号