-
CF750D
tag: DP, 二维数组映射二维平面的方法
-
CF750E
tag: 矩阵,状态转移，结合律，线段树
-
CF754D
tag: 贪心，排序，优先队列
CF750D
题目链接: http://codeforces.com/contest/750/problem/D
题解：如果每条线段以一个带起点的向量表示的话，每个阶段有2^n个向量
但是平面的最大范围为300*300，所以有很多向量起点相同，而且一个起点
最多只有8个方向把它们合并起来就行了。复杂度 (30*300*300*8*5)
平面到二维数组的映射方法
bool va[MAXV][MAXV];
bool (*vis)[MAXV] = (bool (*)[MAXV])(va[150]+150);
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define sf scanf
#define pf printf
const int MAXV = 301;
const int MAXN = 32;
int dir[8][2] = {0,1,-1,1,-1,0,-1,-1,0,-1,1,-1,1,0,1,1};
int db[MAXV][MAXV][MAXN];
bool va[MAXV][MAXV];
int (*dirst)[MAXV][MAXN] = (int (*)[MAXV][MAXN])(db[150]+150);
bool (*vis)[MAXV] = (bool (*)[MAXV])(va[150]+150);
int n, t;
void color(int x, int y, int t, int d) {
for(int i=1; i<=t; ++i) {
int tx = x+i*dir[d][0];
int ty = y+i*dir[d][1];
vis[tx][ty] = true;
}
}
int main() {
sf("%d", &n);
dirst[0][0][0] = (1<<0);
for(int step=1; step<=n; ++step) {
sf("%d", &t);
for(int x=-150; x<=150; ++x)
for(int y=-150; y<=150; ++y) {
for(int i=0; i<8; ++i) {
int ox = x-dir[i][0]*t;
int oy = y-dir[i][1]*t;
if(ox>=-150&&ox<=150&&oy>=-150&&oy<=150) {
if(dirst[ox][oy][step-1]&(1<<i)) {
color(ox,oy,t, i);
dirst[x][y][step] |= (1<<((i+7)%8));
dirst[x][y][step] |= (1<<((i+1)%8));
}
}
}
}
}
int cnt = 0;
for(int i=-150; i<=150; ++i)
for(int j=-150; j<=150; ++j)
if(vis[i][j]) ++cnt;
printf("%d\n", cnt);
return 0;
}
CF750E
题目链接: http://codeforces.com/contest/750/problem/E
题解：
假定
- 状态0 为只能匹配到空串，
- 状态1为只能匹配到"2"** 不能匹配到更多**
- 状态2为只能匹配到"20"** 不能匹配到更多**
- 状态3为只能匹配到"201"** 不能匹配"2016" 和 "2017"**
- 状态4为只能匹配到"2017"** 不能匹配到"2016"**
定义一个字符串区间对应的矩阵a[i][j]为
当前面的区间为状态i时，附加上这段区间变为状态j所需要的代价
矩阵合并时可用矩阵乘法，且满足结合律
然后就可以用线段树划分区间做了
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define sf scanf
#define pf printf
#define inf 0x3f3f3f3f
const int MAXN = 2e5+1e3;
struct Node{
int a[5][5];
int *operator [] (int x) {
return a[x];
}
Node operator + (Node b) {
Node c;
memset(c.a, 0x3f, sizeof(c.a));
for(int i=0; i<5; ++i)
for(int j=0; j<5; ++j)
for(int k=0; k<5; ++k)
c[i][j] = min(c[i][j], a[i][k]+b[k][j]);
return c;
}
}tr[MAXN<<2];
char str[MAXN];
int sl, sr;
Node build(int id, int l, int r) {
if(l==r) {
Node& e = tr[id];
for(int i=0; i<5; ++i)
for(int j=0; j<5; ++j)
e[i][j] = (i==j)?0:inf;
switch(str[l]) {
case '2':
e[0][0] = 1;
e[0][1] = 0;
break;
case '0':
e[1][1] = 1;
e[1][2] = 0;
break;
case '1':
e[2][2] = 1;
e[2][3] = 0;
break;
case '7':
e[3][3] = 1;
e[3][4] = 0;
break;
case '6':
e[3][3] = 1;
e[4][4] = 1;
break;
}
}
else {
int m = l+r>>1;
tr[id] = build(id<<1, l, m)+build(id<<1|1, m+1, r);
}
return tr[id];
}
Node query(int id, int l, int r) {
if(sl<=l&&r<=sr) return tr[id];
int m = l+r>>1;
if(m>=sr) return query(id<<1, l, m);
if(m<sl) return query(id<<1|1, m+1, r);
return query(id<<1, l, m)+query(id<<1|1, m+1, r);
}
int main() {
int n, q;
sf("%d%d", &n, &q);
sf("%s", str+1);
build(1,1,n);
while(q--) {
sf("%d%d", &sl, &sr);
int ans = query(1, 1, n)[0][4];
if(ans==inf) puts("-1");
else pf("%d\n", ans);
}
return 0;
}
CF754D
题目链接: http://codeforces.com/contest/754/problem/D
题解
<p>When we choose k coupons, (x1, y1), (x2, y2) ... (xk, yk), number of products we can use is minimum y — maximum x + 1. So we need maximize this value.</p>
<p>Sort initial points by y coordinate increasing. Let's say we are at position i. We can fix this point as the one with the minimum y, and we need to take k — 1 points from range [i + 1 ... n].</p>
<p>The k — 1 points must have maximum x coordinate as small as possible, in order to maximize the value (minimum y — maximum x + 1).
Let's iterate over all points in this order : n, n — 1.... 1, and maintain a heap / set with smallest K x coordinates we have met until now.</p>
<p>The answer for a position i would be : y coordinate of i-th point — largest value in the heap + 1.</p>
代码
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define sf scanf
#define pf printf
#define l first
#define r second
#define pb push_back
typedef pair<int,int> pr;
const int MAXN = 3e5+1e3;
int n, k, ans, cur;
pr seg[MAXN];
int id[MAXN];
struct cmpl{
bool operator() (int a, int b) {
return seg[a].l<seg[b].l;
}
};
bool cmpr(int a, int b) {
return seg[a].r<seg[b].r;
}
priority_queue<int, vector<int>, cmpl> pq;
void work(int st, int ed) {
while(!pq.empty()) pq.pop();
for(int i=st; i>=ed; --i) {
pq.push(id[i]);
if(pq.size()>k) {
int x =pq.top();
pq.pop();
if(x==id[i]) continue;
}
if(pq.size()==k) {
int x=pq.top();
int len = seg[id[i]].r-seg[x].l+1;
if(len>ans) {
ans = len;
cur = i;
}
}
}
}
int main() {
sf("%d%d", &n, &k);
for(int i=0; i<n; ++i) {
sf("%d%d", &seg[i].l, &seg[i].r);
id[i] = i;
}
sort(id, id+n, cmpr);
work(n-1,0);
pf("%d\n", ans);
work(n-1, cur);
while(!pq.empty()) {
pf("%d ", 1+pq.top());
pq.pop();
}
puts("");
return 0;
}
