记得就更
P1378 油滴扩展
写的挺繁琐的，简单来说就是放长方形里放圆，这个圆的圆心已经确定了，半径慢慢扩展，直到碰到边框或者已放的任何一个圆停止，求总面积减去最大覆盖面积。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define pii pair<int,int>
const int inf = 1e9 + 7;
const ll lnf = 1e18 + 7;
const int maxn = 2e5 + 10;
ll mod = 1e9 + 7;
double eps = 1e-6;
double x, y, xx, yy;
struct point {
double x, y;
}p[10];
double ans = 0;
int cnt = 0;
struct clc {
double x, y, r;
}c[10];
double dis(point a, clc b)
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
int sgn(double x, double y)
{
if (x > y)return 1;
else if (fabs(x - y) < eps)return 0;
else return -1;
}
double getr(int now)
{
double nx = p[now].x, ny = p[now].y;
double res = min(fabs(nx - x), fabs(nx - xx));
res = min(res, min(fabs(ny - y), fabs(ny - yy)));
//cout << cnt << endl;
for (int i = 1; i < cnt; i++)
{
double d = dis(p[now], c[i]);
if (sgn(d, c[i].r) == 1)
res = min(res, d - c[i].r);
else
return 0;
}
return res;
}
bool v[10];
int n;
void dfs(int deep)
{
//cout << deep << endl;
if (deep == n + 1)
{
double res = 0;
for (int i = 1; i <= cnt; i++)
res += c[i].r * c[i].r * acos(-1);
//cout << res << endl;
ans = max(ans, res);
return;
}
for (int i = 1; i <= n; i++)
{
if (v[i])continue;
++cnt;
c[cnt] = { p[i].x,p[i].y,getr(i) };
v[i] = 1;
dfs(deep + 1);
v[i] = 0;
--cnt;
}
}
int main()
{
fastio;
cin >> n;
cin >> x >> y >> xx >> yy;
for (int i = 1; i <= n; i++)
cin >> p[i].x >> p[i].y;
for (int i = 1; i <= n; i++)
{
++cnt;
c[cnt] = { p[i].x,p[i].y,getr(i) };
v[i] = 1;
dfs(2);
v[i] = 0;
--cnt;
}
int res = (fabs((x - xx) * (y - yy)) - ans) + 0.5;
cout << res;
return 0;
}
P1126 机器人搬重物
迷宫求最短步数，其中还有当前面向的方向。左转或右转算一步，前进1、2、3格都算1步。
直接bfs
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
const int inf = 1e9 + 7;
const ll lnf = 1e18 + 7;
const int maxn = 2e5 + 10;
ll mod = 1e9 + 7;
int a[55][55];
int sr, sc, tr, tc;//起点和终点
struct zt {//状态
int mx, my, dir, ste;//0n,1w,2s,3e
};
int checkx[] = { 0,0,1,1 };//check当前点的方向（因为状态存的是四格中的左上角，要check另外3个点）
int checky[] = { 0,1,0,1 };
int tul(int dir)//左转
{
return (dir + 1) % 4;
}
int tur(int dir)//右转
{
return ((dir - 1) + 4) % 4;
}
int dx[] = {-1,0,1,0};
int dy[] = { 0,-1,0,1 };
int n, m;
int check(int x, int y)//check有没有撞墙
{
for (int i = 0; i <= 3; i++)
{
int tx = x + checkx[i], ty = y + checky[i];
if (a[tx][ty] || tx<1 || tx>n || ty<1 || ty>m)
return 0;
}
return 1;
}
int dis[55][55][4];//记忆化，大概不用也可以吧
queue<zt>q;
int main()
{
fastio;
cin >> n >> m;
memset(dis, 0x3f, sizeof(dis));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
cin >> sr >> sc >> tr >> tc;
char tmp;
cin >> tmp;
int dir;
if (tmp == 'N')
dir = 0;
else if (tmp == 'W')
dir = 1;
else if (tmp == 'S')
dir = 2;
else
dir = 3;
q.push({ sr,sc,dir,0 });
while (!q.empty())
{
zt now = q.front(); q.pop();
int x = now.mx, y = now.my;
dir = now.dir;
//cout << x << " " << y << " " << dir << " " << now.ste << endl;
if (x == tr && y == tc)
{
cout << now.ste;
exit(0);
}
if (now.ste >= dis[x][y][dir])continue;
dis[x][y][dir] = now.ste;
q.push({ x,y,tul(dir),now.ste + 1 });
q.push({ x,y,tur(dir),now.ste + 1 });
//只有1步不撞墙再去找走2步、走3步可不可行
if (check(x + dx[dir], y + dy[dir]))
{
q.push({ x + dx[dir],y + dy[dir],dir,now.ste + 1 });
if (check(x + 2 * dx[dir], y + 2 * dy[dir]))
{
q.push({ x + 2 * dx[dir],y + 2 * dy[dir],dir,now.ste + 1 });
if (check(x + 3 * dx[dir], y + 3 * dy[dir]))
q.push({ x + 3 * dx[dir],y + 3 * dy[dir],dir,now.ste + 1 });
}
}
}
cout << -1;
return 0;
}
P1514 [NOIP2010 提高组] 引水入城
从每个起点开始dfs，找出第一排每个点能覆盖最后一排的线段
通过记忆化搜索记录每个点可以覆盖的线段的左端点和右端点
跑完dfs后先check是不是最后一排每个点都能被覆盖（第一行0的情况）
否则区间dp找最小覆盖（第一行1的情况）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define pii pair<int,int>
const int inf = 1e9 + 7;
const ll lnf = 1e18 + 7;
const int maxn = 2e5 + 10;
int n, m;
int a[505][505];
int dpl[505][505], dpr[505][505];
int vis[505][505];
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void dfs(int x, int y)
{
vis[x][y] = 1;
for (int i = 0; i <= 3; i++)
{
int tx = x + dx[i], ty = y + dy[i];
if (a[tx][ty] >= a[x][y] || tx<1 || tx>n || ty<1 || ty>m)continue;
if (!vis[tx][ty])
dfs(tx, ty);
dpl[x][y] = min(dpl[x][y], dpl[tx][ty]);
dpr[x][y] = max(dpr[x][y], dpr[tx][ty]);
}
}
struct line {
int l, r;
friend bool operator<(line x, line y)
{
if (x.l == y.l)
return x.r < y.r;
return x.l < y.l;
}
}l[505];
int dp[505][505];
int main()
{
fastio;
cin >> n >> m;
memset(dpl, 0x3f, sizeof(dpl));
memset(dpr, 0, sizeof(dpr));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= m; i++)
dpl[n][i] = dpr[n][i] = i;
for (int i = 1; i <= m; i++)
if (!vis[1][i])
dfs(1, i);
bool flag = 1;
int cnt = 0;
for (int i = 1; i <= m; i++)
{
if (!vis[n][i])
cnt++, flag = 0;
}
if (!flag)
{
cout << 0 << endl << cnt;
return 0;
}
cout << 1 << endl;
for (int i = 1; i <= m; i++)
l[i] = { dpl[1][i],dpr[1][i] };
sort(l + 1, l + m + 1);
memset(dp, 0x3f, sizeof(dp));
for (int i = 1; i <= m; i++)
{
if (l[i].l == 1)
dp[l[i].l][l[i].r] = 1;
else
{
for (int j = l[i].l - 1; j <= l[i].r; j++)
dp[1][l[i].r] = min(dp[1][l[i].r], dp[1][j] + 1);
}
}
cout << dp[1][m];
return 0;
}
P3953 [NOIP2017 提高组] 逛公园
73pts做法，没有去判-1的情况，假设最短路上不存在0环
先从起点跑一遍spfa，记录每个点到起点的最短路。
然后反向建图，从n点记忆化搜索：对于两点u和v，他们多走的距离cost = dis[u] - (dis[v] + w(u,v))，
如果在最短路上，则cost为0，否则就要记入多走cost的距离
从n点先安排好可以多走多少距离，再去dfs，只有到1的时候正好用完了才return 1。这样从小往大安排可以继承之前的状态
以f[now][hav]记录状态，now为当前位置，hav为还可以多走多少距离 的方案数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
const int inf = 1e9 + 7;
const ll lnf = 1e18 + 7;
const int maxn = 1e5 + 10;
ll mod;
struct edge {
int to, cost, next;
}e[maxn << 1], sb[maxn << 1];
int head[maxn], sbad[maxn], sb_cnt = 0, edge_cnt = 0;
void add(int from, int to, int cost)
{
e[++edge_cnt] = { to,cost,head[from] };
head[from] = edge_cnt;
sb[++sb_cnt] = { from,cost,sbad[to] };
sbad[to] = sb_cnt;
}
ll dp[maxn][55];
int n, m, k;
int dis[maxn];
ll dfs(int from, int hav)
{
ll res = 0;
if (dp[from][hav])return dp[from][hav];
for (int i = sbad[from]; ~i; i = sb[i].next)
{
int to = sb[i].to, cost = sb[i].cost;
cost = dis[from] - dis[to] - cost + hav;
if (cost >= 0)
res = (res + dfs(to, cost)) % mod;
}
if (from == 1 && !hav)res++;
return dp[from][hav] = res;
}
void spfa()
{
for (int i = 1; i <= n; i++)
dis[i] = inf;
dis[1] = 0;
queue<int>q;
q.push(1);
vector<bool>v(n + 1, 0);
while (!q.empty())
{
int from = q.front();
q.pop();
v[from] = 0;
for (int i = head[from]; ~i; i = e[i].next)
{
int to = e[i].to, cost = e[i].cost;
if (dis[to] > dis[from] + cost)
{
dis[to] = dis[from] + cost;
if (!v[to])
q.push(to);
}
}
}
}
int main()
{
fastio;
int t;
cin >> t;
while (t--)
{
cin >> n >> m >> k >> mod;
for (int i = 1; i <= n; i++)
{
head[i] = -1;
sbad[i] = -1;
for (int j = 0; j <= k; j++)
dp[i][j] = 0;
}
edge_cnt = 0;
sb_cnt = 0;
while (m--)
{
int x, y, z;
cin >> x >> y >> z;
add(x, y, z);
}
spfa();
ll ans = 0;
for (int i = 0; i <= k; i++)
ans += dfs(n, i);
cout << ans % mod << endl;
}
return 0;
}
P1312 [NOIP2011 提高组] Mayan 游戏
没A，模拟太难了，60pts
P4799 [CEOI2015 Day2]世界冰球锦标赛
从n个数里任意选，使它们的和不大于m，问有多少种选法。
由于n<=40，枚举所有状态的话，就是2^40种，很显然时间是不够的；
那么把n拆成两半，枚举2次2^20，最后再合并答案即可
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
ll a[22], b[22];
vector<ll>suma, sumb;
int cnt, tot;
void dfs1(ll sum,int now)
{
if (now == cnt + 1)
{
suma.push_back(sum);
return;
}
dfs1(sum, now + 1);
dfs1(sum + a[now], now + 1);
}
void dfs2(ll sum, int now)
{
if (now == tot + 1)
{
sumb.push_back(sum);
return;
}
dfs2(sum, now + 1);
dfs2(sum + b[now], now + 1);
}
int main()
{
fastio;
ll n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
ll x;
cin >> x;
if (i <= n / 2)
a[++cnt] = x;
else b[++tot] = x;
}
dfs1(0, 1);
dfs2(0, 1);
sort(sumb.begin(), sumb.end());
ll ans = 0;
for (auto i : suma)
ans += upper_bound(sumb.begin(), sumb.end(), m - i) - sumb.begin();
cout << ans;
return 0;
}
P3067 [USACO12OPEN]Balanced Cow Subsets G
有点像蓝桥省赛的砝码称重，只不过数的范围很大，不能用背包。把数的大小看做砝码的重量：
思路依旧是去找能称出哪些重量，由于是天平称重，所以没有正负（因为可以将左右盘互换，所以直接取绝对值就可以了）
对于每个数有3种状态，分别是：放在左边、放在右边、不选
由于n<=20，3^20=3486784401
这样又需要把n拆成两部分，分别枚举出每一部分中的所有状态对应的可以称出的重量，最后重量相同的两份状态就可以合并成一个合法状态(这两个状态左右盘的差是一样的，很显然是可以弄出平衡的状态)
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
const int maxn = 2e6 + 10;
ll a[22];
int n,lim;
map<int, int>mp;
int ans[maxn];
vector<int>p[maxn];
int tot = 0;
void dfs1(ll sum, int now, int zt)
{
if (now > lim)
{
if (!mp.count(sum))mp[sum] = ++tot;
p[mp[sum]].push_back(zt);
return;
}
dfs1(sum + a[now], now + 1, zt | (1 << (now - 1)));
dfs1(abs(sum - a[now]), now + 1, zt | (1 << (now - 1)));
dfs1(sum, now + 1, zt);
}
void dfs2(ll sum, int now, int zt)
{
if (now > n)
{
if (mp.count(sum))
{
int id = mp[sum];
for (int i = 0; i < p[id].size(); i++)
ans[zt | p[id][i]] = 1;
}
return;
}
dfs2(sum + a[now], now + 1, zt | (1 << (now - 1)));
dfs2(abs(sum - a[now]), now + 1, zt | (1 << (now - 1)));
dfs2(sum, now + 1, zt);
}
int main()
{
fastio;
cin >> n;
for (int i = 1; i <= n; i++)cin >> a[i];
lim = n / 2;
dfs1(0, 1, 0);
dfs2(0, lim + 1, 0);
ll res = 0;
for (int i = 1; i < 1 << n; i++)
res += ans[i];
cout << res;
return 0;
}