View Code
第三题：CF516/B
题目大意：给一个n × m的矩阵，问在其中空白处放置1 × 2, 2 × 1的骨牌的方案 是否存在且唯一 。1 ≤ n, m ≤ 1000；
我们可以用度来表示这个节点当前周围放置的个数；
那么对应度为1的点是一定确定了放置这个点的方式的（显然），对应这个点的四周四个位子中，此时一定只有一个点，那么对应将此处和那个位子直接放置这个1 × 2的形状即可 。然后处理完这个点之后，对其他点进行操作，如果再发现了度 为1的点，入队 。一直处理下去这样的类似拓扑排序的过程即可 。如果最后还剩下了，说明无法完全覆盖，或者方案不止一个；
所以这个题是拓扑排序的一个拓展；
#include #include #include #include using namespace std;typedef struct Point{int x,y;}Point;Point a[4000000];int in[2002][2002];char p[2002][2002];int dx[] = { 0, 0, 1,-1};int dy[] = { 1,-1, 0, 0};char ch[] = "> 0 && x <= m && y > 0 && y <= n;}void ans(int x,int y){int i,xx,yy,cnt = 0;for(i = 0; i < 4; ++i){xx = x+dx[i];yy = y+dy[i];if(check(xx,yy)&&p[xx][yy]=='.') cnt++;}in[x][y]=cnt;}bool topo(){int i,j,x,y,xx,yy,xxx,yyy,cnt = 0;queue int,int> > q;for(j = 0; j (x,y));in[x][y] = 0;}}pair m;while(!q.empty()){m = q.front();q.pop();x = m.first;y = m.second;in[x][y]--;for(j = 0; j < 4; ++j){xx = x+dx[j];yy = y+dy[j];if(check(xx,yy) && p[xx][yy] == '.'){in[xx][yy] = 0;p[xx][yy] = ch[j];p[x][y] = st[j];for(int f = 0; f < 4; ++f){xxx = xx+dx[f];yyy = yy+dy[f];if(check(xxx,yyy) && p[xxx][yyy] == '.'){ans(xxx,yyy);if(in[xxx][yyy] == 1) q.push(pair(xxx,yyy));}}cnt+=2;}}}return cnt == k;}int main(){int i,j;scanf("%d %d",&m,&n);k = 0;for(i = 1; i <= m; ++i){scanf("%s",p[i]+1);for(j = 1; j <= n; ++j)if(p[i][j] == '.'){a[k].x = i;a[k++].y = j;in[i][j] = 0;if(check(i-1,j) && p[i-1][j] == '.'){in[i-1][j]++;in[i][j]++;}if(check(i,j-1) && p[i][j-1] == '.'){in[i][j-1]++;in[i][j]++;}}}if(topo()){for(i = 1; i <= m; ++i) printf("%s\n",p[i]+1);}else puts("Not unique");return 0;}
View Code

文章插图
第四题：
题目大意：有n头牛，他们按顺序排成了一排，有些牛关系比较好，他们的距 离不能超过某个距离，还有些牛关系不好，他们之间的距离不能小于某 个距离，可能会有多头牛挤在同一位置上，问1号牛和n号牛之间的最大 距离是多少，如果不存在满足条件的排列则输出?1，如果距离无限大则 输出?2 。2 ≤ n ≤ 1000 。
查分约束版子题，由题意列出不等式根据三角不等式，建图，跑最短路即可；
题解：令d[i]表示第i头牛的位置，因为牛按顺序排列，则有d[i] ≤ d[i + 1]，即d[i] ? d[i + 1] ≤ 0 。关系不好的牛有d[a] + d ≤ d[b] 。关系好的牛有d[a] + D ≤ d[b], 即d[a] ? d[n] ≤ ?D。跑最短路即可 。
#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include