B. Dragon slayer(二进制枚举 + bfs)
题意：给定一个n * m的网格，视格子中间为点，格线为墙，指定x堵墙（x <= 15），穿过一堵墙耗费一体力，问从起点到终点的最小体力为多少
分析: 注意到墙的数量很小，所以可以考虑二进制枚举哪些墙被拆，然后bfs 判断可达性，这题难点在于他给的图很特殊，所以将原图扩大二倍，比较好写
ac 代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3)
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 50,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0);
int n,m,k,t;
struct Wall
{
int x1,y1,x2,y2;
}wall[N];
PII s,e;
bool st[N][N],g[N][N];
int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1};
void add(Wall & w)
{
int x1 = w.x1,y1 = w.y1,x2 = w.x2,y2 = w.y2;
if(x1 == x2) for(int i = min(y1,y2);i <= max(y1,y2);i ++) g[x1][i] = true;
else for(int i = min(x1,x2);i <= max(x1,x2);i ++) g[i][y1] = true;
}
void del(Wall & w)
{
int x1 = w.x1,y1 = w.y1,x2 = w.x2,y2 = w.y2;
if(x1 == x2) for(int i = min(y1,y2);i <= max(y1,y2);i ++) g[x1][i] = false;
else for(int i = min(x1,x2);i <= max(x1,x2);i ++) g[i][y1] = false;
}
bool bfs()
{
queue<PII> q;
memset(st,0,sizeof st);
q.push({s.x,s.y});
st[s.x][s.y] = true;
while(q.size())
{
PII t = q.front();
q.pop();
if(t.x == e.x && t.y == e.y) return true;
for(int i = 0;i < 4;i ++)
{
int x = t.x + dx[i],y = t.y + dy[i];
if(x <= 0 || x >= 2 * n || y <= 0 || y >= 2 * m) continue;
if(st[x][y] || g[x][y]) continue;
st[x][y] = true;
q.push({x,y});
}
}
return false;
}
int main()
{
ios;
cin >> t;
while(t --)
{
memset(g,0,sizeof g);
cin >> n >> m >> k;
cin >> s.x >> s.y >> e.x >> e.y;
s.x = s.x * 2 + 1,s.y = s.y * 2 + 1;
e.x = e.x * 2 + 1,e.y = e.y * 2 + 1;
for(int i = 0;i < k;i ++)
{
int x1,y1,x2,y2;
cin >> x1 >> y1 >> x2 >> y2;
wall[i] = {x1 + x1,y1 + y1,x2 + x2,y2 + y2};
}
int ans = 0;
for(int i = 0;i < (1 << k);i ++)
{
int cnt = 0;
for(int k = 15;k >= 0;k --) if(i >> k & 1) cnt ++;
if(cnt <= ans) continue;
for(int k = 15;k >= 0;k --) if(i >> k & 1) add(wall[k]);
if(bfs()) ans = cnt;
for(int k = 15;k >= 0;k --) if(i >> k & 1) del(wall[k]);
}
cout << k - ans << endl;
}
return 0;
}
C. Backpack（dp + bitset优化）
题意 ：背包问题变种，求如何在恰好塞满背包的前提下让所有背包里的物品价值总异或和最大。
分析 ：设 \(f[i,j,k]\) 表示前i个物品中当前容量为j的情况下能否凑出异或和为 k 的
对于某个物品
选：\(f[i,j,k] |= f[i - 1,j - v,k \bigoplus w]\)
不选 ：\(f[i,j,k] |= f[i - 1,j,k]\)
第一维可以用滚动数组优化掉,然后用bitset优化。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3)
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 1100,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0);
int n,m,k,t;
bitset<N> f[N],g[N];
void init()
{
for(int i = 0;i <= 1024;i ++) f[i].reset(),g[i].reset();
}
int main()
{
ios;
cin >> t;
while(t --)
{
cin >> n >> m;
init();
f[0][0] = 1;
for(int i = 1;i <= n;i ++)
{
int w,v;
cin >> v >> w;
for(int j = 0;j < 1024;j ++) g[j] = f[j] << v;
for(int j = 0;j < 1024;j ++) f[j] |= g[j ^ w];
}
bool success = false;
for(int i = 1024;i >= 0;i --)
if(f[i][m])
{
cout << i << endl;
success = true;
break;
}
if(!success) cout << -1 << endl;
}
return 0;
}
D. Ball(枚举 + bitset)
题意 ：给定棋盘上的n个点，找到三元组\((i,j,k)\) 使得i,j,k三者之间的曼哈顿距离的中位数为素数，问这样的三元组的个数
分析 ：线性筛处理素数，将每两个点之间的距离预处理出来，按距离排序，从小到大枚举这些边。因为我们是从小到大枚举的这些边，那么在枚举当前边之前的边都是比较小的，我们在枚举完前面的边都做一个标记，最后找枚举过的边和没有枚举过的边即可。
ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3)
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 2010,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0);
int n,m,k,t;
int primes[N * N],cnt;
bool st[N * N];
bitset<N> p[N];
struct Edge
{
int a,b,w;
bool operator < (const Edge & t)const
{
return w < t.w;
}
}edges[N * N];
void get_primes(int n)
{
st[1] = true;
for(int i = 2;i<=n;i++)
{
if(!st[i]) primes[cnt++] = i;
for(int j = 0 ; primes[j]<=n/i;j++)
{
st[primes[j]*i] = true;
if(i % primes[j] == 0) break;//此时primes[j] 为 i 的最小质因子
}
}
}
int main()
{
ios;
get_primes(200010);
cin >> t;
while(t --)
{
LL idx = 0,ans = 0;
cin >> n >> m;
vector<int> x(n + 1),y(n + 1);
for(int i = 1;i <= n;i ++) cin >> x[i] >> y[i],p[i].reset();
p[0].reset();
for(int i = 1;i <= n;i ++)
for(int j = i + 1;j <= n;j ++)
edges[idx ++] = {i,j,abs(x[i] - x[j]) + abs(y[i] - y[j])};
sort(edges,edges + idx);
for(int i = 0;i < idx;i ++)
{
int a = edges[i].a,b = edges[i].b,w = edges[i].w;
if(!st[w]) ans += (p[a] ^ p[b]).count();
p[a][b] = 1,p[b][a] = 1;
}
cout << ans << endl;
}
return 0;
}
H. Path(分层图最短路)
题意 ：给你一个n个点m条边的无向图，m条边中有两种边，一种是特殊边，一种是普通边，经过这条特殊边后我们可以以0花费到达任意不和它相邻的点，而经过普通边我们需要花费\(w_i − K\),问从源点到各个点的最小花费是多少
分析 ：这道题我们用分层图来写，以dist[i][0]表示是从特殊边到达i的最小距离，dist[i][1]表示是从普通边到达i的最小距离,然后我们从源点跑一边dijkstra，需要注意的是如果经过了一条特殊边那么我们就把其他不与该边相邻的点从队列中删除，因为这些点的距离就等于到达特殊边的距离，而因为dijkstra算法我们很容易知道这样的距离是最小的
ac代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <stack>
#include <set>
#include <sstream>
#include <fstream>
#include <cmath>
#include <iomanip>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <random>
//#pragma GCC optimize(3)
#define x first
#define y second
#define ios ios::sync_with_stdio(false),cin.tie(0);
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()
#define all1(x) x.begin()+1,x.end()
using namespace std;
typedef unsigned long long uLL;
typedef long long LL;
typedef pair<int,int> PII;
const int N = 1000010,M = 10010,INF = 0x3f3f3f3f,mod = 1e9 + 7;
const double INFF = 0x7f7f7f7f7f7f7f7f,pi = acos(-1.0);
int n,m,k,t;
int h[N],e[N],ne[N],w[N],is[N],idx;
struct node
{
int a;
LL w;
int is;
bool operator < (const node & t)const
{
return w > t.w;
}
};
LL dist[N][2];
bool st[N][2];
void add(int a,int b,int c,int d)
{
e[idx] = b,w[idx] = c,is[idx] = d,ne[idx] = h[a],h[a] = idx ++;
}
void dijkstra(int s)
{
set<int> S;
for(int i = 1;i <= n;i ++)
{
if(i != s) S.insert(i);
dist[i][0] = dist[i][1] = 1e18;
st[i][0] = st[i][1] = 0;
}
priority_queue<node> heap;
dist[s][0] = 0;
heap.push({s,0,0});
vector<int> vis(n + 1);
int cnt = 0;
while(heap.size())
{
node t = heap.top();
heap.pop();
cnt ++;
int ver = t.a,Is = t.is;
if(!Is) S.erase(ver);
else
{
for(int i = h[ver];~ i;i = ne[i])
{
int j = e[i];
vis[j] = cnt;
}
vector<int> x;
for(auto i : S)
if(vis[i] != cnt)
{
x.pb(i);
dist[i][0] = dist[ver][1 ];
heap.push({i,dist[i][0],0});
}
for(auto i : x) S.erase(i);
}
int y = 0;
if(Is) y -= k;
if(st[ver][Is]) continue;
st[ver][Is] = true;
for(int i = h[ver];~ i;i = ne[i])
{
int j = e[i];
if(dist[j][is[i]] > dist[ver][Is] + w[i] + y)
{
dist[j][is[i]] = dist[ver][Is] + w[i] + y;
heap.push({j,dist[j][is[i]],is[i]});
}
}
}
}
int main()
{
ios;
cin >> t;
while(t --)
{
int s;
cin >> n >> m >> s >> k;
for(int i = 1;i <= n;i ++) h[i] = -1;
idx = 0;
while(m --)
{
int a,b,c,d;
cin >> a >> b >> c >> d;
add(a,b,c,d);
}
dijkstra(s);
for(int i = 1;i <= n;i ++)
if(min(dist[i][0],dist[i][1]) == 1e18) cout << -1 << ' ';
else cout << min(dist[i][0],dist[i][1]) << ' ';
cout << endl;
}
return 0;
}