2020.01.11【NOIP提高组】模拟B组
今天的题是不是和 \(C\) 组放错了?
呵呵
然，却只有 \(300\) 分
首先，\(T4\) 看错题了
后，一时想不到正解
讨论区，一看，三个字——网络流
恍然大悟
脑推了一下，遂得正解
进入正题：
\(T1\)
题目大意：设一矩阵，分东西南北四个方向（上北下南左西又动），从西南角出发，然后到北边的任一位置，再到南边的任一位置，最后到东北角，求最短距离。
果真水！
将军饮马问题
直接以北线为对称轴把西南角映射过去，再以南线为对称轴把东北角映射过去，求这映射后的两点距离，原理：两点之间线段最短
代码
#include<cstdio>
#include<cmath>
using namespace std;
double w , h , ans;
int main()
{
scanf("%lf%lf" , &w , &h);
ans = sqrt(9 * h * h + w * w);
printf("%.0lf" , ans);
} \(T2\)
题目大意：有2n个人在售票处排队买票，门票5元一张，恰有n个人每人有5元一张的人民币，另n个人每人只有10元一张的人民币。
最开始售票处没有零钱，问最后2n个人都能顺利买到票（即能够成功找零）的排列有多少种？
解析：瞟一眼，特性：任何时刻 \(5\) 元的不少于 \(10\) 元的
啊啊啊啊啊
卡特兰数！秒切！！
通项公式：
\[ h_n = \frac{1}{n + 1}\binom{n}{2n} \]
代码
#include<cstdio>
using namespace std;
typedef long long LL;
LL fm[50] , fz[50] , ans = 1;
int mt , zt , n;
int main()
{
scanf("%d" , &n);
for(register int i = (n << 1); i >= (n + 1); i--) fm[++mt] = (LL)i;
for(register int i = (n + 1); i >= 2; i--) fz[++zt] = (LL)i;
for(register int i = 1; i <= mt; i++)
for(register int j = 1; j <= zt; j++)
if (fm[i] % fz[j] == 0 && fz[j] != 1) fm[i] = fm[i] / fz[j] , fz[j] = 1;
for(register int i = 1; i <= mt; i++) ans *= fm[i];
for(register int i = 1; i <= zt; i++) ans /= fz[i];
printf("%lld" , ans);
}\(T3\)
题目大意：给定一个N*M的迷宫和一个机器人，迷宫里有一些障碍物，机器人无法通过。现在机器人要从起点走到终点，每个时刻可以执行三种操作：前进，左转，右转。
前进无需费用，但左转和右转则需要不同的费用。
现在问你，机器人从起点走到终点的最小费用是多少？
机器人的起始方向可以由你指定。注意这是一个四连通的迷宫，即每个格子只与其上下左右的格子相邻，与对角不相邻。起始方向可以选这四种方向的其中一种。
解析：正好前天做过一道和这题差不多但更难一点的题
今天：\(SPFA\) 大水题
前提：\(BFS/SPFA\) + \(DP\)
相信学过最短路的必然秒切
代码
#include<cstdio>
#include<iostream>
using namespace std;
int lcost , rcost , r , c , sx , sy , ex , ey , ans = 1e9;
int dis[105][105][5] , map[105][105] , vis[105][105][105] , head , tail;
int fx[4][2] = { -1 , 0 , 0 , 1 , 1 , 0 , 0 , -1 };
char ch;
struct node{
int x , y , d;
}d[1000005];
inline bool check(int xx , int yy)
{
return (xx > 0 && yy > 0 && xx <= r && yy <= c);
}
inline int spfa(int sd)
{
head = 0 , tail = 0;
d[++tail] = node{sx , sy , sd};
for(register int i = 1; i <= r; i++)
for(register int j = 1; j <= c; j++)
for(register int d = 0; d < 4; d++)
dis[i][j][d] = 1e9 , vis[i][j][d] = 0;
dis[sx][sy][sd] = 0 , vis[sx][sy][sd] = 1;
node now;
int xx , yy , dd;
while (head < tail)
{
now = d[++head] , vis[now.x][now.y][now.d] = 1;
//straight
xx = now.x + fx[now.d][0] , yy = now.y + fx[now.d][1] , dd = now.d;
if (check(xx , yy) && (map[xx][yy] == 0) && (dis[xx][yy][dd] > dis[now.x][now.y][now.d]))
{
dis[xx][yy][dd] = dis[now.x][now.y][now.d];
if (vis[xx][yy][dd] == 0) vis[xx][yy][dd] = 1 , d[++tail] = node{xx , yy , dd};
}
//left
xx = now.x , yy = now.y , dd = (now.d + 3) % 4;
if (map[xx][yy] == 0 && dis[xx][yy][dd] > dis[now.x][now.y][now.d] + lcost)
{
dis[xx][yy][dd] = dis[now.x][now.y][now.d] + lcost;
if (vis[xx][yy][dd] == 0) vis[xx][yy][dd] = 1 , d[++tail] = node{xx , yy , dd};
}
//right
xx = now.x , yy = now.y , dd = (now.d + 1) % 4;
if (map[xx][yy] == 0 && dis[xx][yy][dd] > dis[now.x][now.y][now.d] + rcost)
{
dis[xx][yy][dd] = dis[now.x][now.y][now.d] + rcost;
if (vis[xx][yy][dd] == 0) vis[xx][yy][dd] = 1 , d[++tail] = node{xx , yy , dd};
}
}
int res = 1e9;
for(register int i = 0; i < 4; i++) res = min(res , dis[ex][ey][i]);
return res;
}
int main()
{
scanf("%d%d%d%d%d%d%d%d" , &lcost , &rcost , &r , &c , &sx , &sy , &ex , &ey);
for(register int i = 1; i <= r; i++)
for(register int j = 1; j <= c; j++)
{
ch = getchar();
while (ch != '*' && ch != '.') ch = getchar();
if (ch == '*') map[i][j] = 1;
}
for(register int i = 0; i < 4; i++) ans = min(ans , spfa(i));
printf("%d" , ans == 1e9 ? -1 : ans);
}\(T4\)
题目大意：\(T\)组数据，给定 \(n\) 个文件，他有文件大小和每秒最大下载量，且只能从 \(s\) 秒开始到 \(t\)秒可以下载
你的电脑有每秒最大下载量，且只能从 \(1\) 秒开始到 \(s\)秒可以下载这些文件
问能否下载完所有文件
解析：改题时，因看到网络流三个字
恍然大悟，脑推了一下，遂得正解
然后码了一波，\(WA\) 了
瞎想一会，才明白题面是错的
所有时间都可以从 \(0\) 秒开始，也就是说你的电脑可以从 \(0\) 就开始下载
好了，纠正完题面，来正解
很容易想到 \(n\) 个文件是节点，时间也是节点，最大下载量就是流量
考虑建边
超级源点 \(S\) 连向每个时间点，流量为电脑每秒最大下载量，实际上就表示你的电脑可以在任意合法时刻内下载文件
每个时间点连向可以再改时间点下载的文件，流量为文件每秒最大下载量，实际上就表示这个时间可以下载文件，且不超过每秒最大下载量
因为前面超级源点 \(S\) 连向每个时间点，所以用在文件的每秒下载量之和不会超过电脑每秒最大下载量
在考虑让所有文件连向超级汇点 \(T\) ，流量为文件大小，表示从此文件下载的大小不会超过文件大小，也就是说不会帮其他文件下载，保证正确性
最后跑最大流，看最大流量是不是能下载完所有文件
套路而巧妙
代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n , w , s , S = 119 , T = 120 , INF = 1e9 , h[200] , cur[200] , dep[200] , d[200] , tot;
struct node{
int m , w , c , d;
}a[200];
struct edge{
int to , nxt , v;
}e[100005];
inline void add(int x , int y , int z)
{
e[++tot].to = y , e[tot].nxt = h[x] , e[tot].v = z , h[x] = tot;
}
inline void build()
{
tot = 1;
memset(h , 0 , sizeof(h));
for(register int i = 1; i <= s; i++) add(S , i , w) , add(i , S , 0);
for(register int i = 1; i <= n; i++)
{
add(s + i , T , a[i].m) , add(T , s + i , 0);
for(register int j = a[i].c; j <= a[i].d; j++)
add(j , s + i , a[i].w) , add(s + i , j , 0);
}
}
inline bool bfs()
{
register int head = 0 , tail = 0 , now;
for(register int i = 1; i <= T; i++) cur[i] = h[i] , dep[i] = INF;
d[++tail] = S , dep[S] = 0;
while (head < tail)
{
now = d[++head];
for(register int i = h[now]; i; i = e[i].nxt)
{
register int v = e[i].to;
if (dep[v] == INF && e[i].v > 0) dep[v] = dep[now] + 1 , d[++tail] = v;
}
}
return dep[T] != INF;
}
inline int dfs(int x , int mi , int fa)
{
if (mi <= 0 || x == T) return mi;
register int flow = 0 , f;
for(register int i = cur[x]; i; i = e[i].nxt)
{
cur[x] = i;
register int v = e[i].to;
if (e[i].v > 0 && v != fa && dep[v] == dep[x] + 1)
{
f = dfs(v , min(mi , e[i].v) , x);
if (f > 0) mi -= f , e[i].v -= f , e[i ^ 1].v += f , flow += f;
if (mi <= 0) break;
}
}
return flow;
}
inline int dinic()
{
int Maxflow = 0;
while (bfs()) Maxflow += dfs(S , INF , 0);
return Maxflow;
}
inline bool check(int sum)
{
build();
return dinic() >= sum;
}
int main()
{
// freopen("d.in" , "r" , stdin);
scanf("%d" , &n);
while (n)
{
scanf("%d%d" , &w , &s) , s++;
register int sum = 0;
for(register int i = 1; i <= n; i++)
{
register int m , w , c , d;
scanf("%d%d%d%d" , &m , &w , &c , &d) , sum += m;
a[i] = (node){m , w , c + 1 , d + 1};
}
if (check(sum)) printf("yes\n");
else printf("no\n");
scanf("%d" , &n);
}
}愉快！！！