题目
1002 Dragon slayer
Long, long ago, the dragon captured the princess. In order to save the princess, the hero entered the dragon’s lair.
The dragon’s lair is a rectangle area of length n and width m. The lower left corner is (0,0) and the upper right corner is (n,m).
The position of the hero is (xs+0.5,ys+0.5).
The position of the dragon is (xt+0.5,yt+0.5).
There are some horizontal or vertical walls in the area. The hero can move in any direction within the area, but cannot pass through walls, including the ends of walls.
The hero wants to go where the dragon is, but may be blocked by walls.
Fortunately, heroes have access to special abilities, and each use of a special ability can make a wall disappear forever.
Since using special abilities requires a lot of physical strength, the hero wants to know how many times special abilities need to be used at least on the premise of being able to reach the position of the evil dragon?
Input
The first line contains an integer T(T≤10) —the number of test cases.
The first line of each test case contains 3 integers n,m,K(1≤n,m,K≤15) —length and width of rectangular area, number of walls
The second line of each test case contains 4 integers xs,ys,xt,yt(0≤xs,xt<n,0≤ys,yt<m) — the position of the hero and the dragon.
The next K lines , each line contains 4 integers x1,y1,x2,y2(0≤x1,x2≤n,0≤y1,y2≤m) — indicates the location of the two endpoints of the wall, ensuring that x1=x2 or y1=y2.
Output
For each test case, a line of output contains an integer representing at least the number of times the special ability was required.
Sample Input
3 2 2
0 0 2 1
0 1 3 1
1 0 1 2
3 2 2
0 0 2 1
2 1 2 2
1 0 1 1
Sample Output
2
0
给你一张地图，你从
(
x
s
+
0.5
,
y
s
0
.
5
)
(xs+0.5,ys_0.5)
(
x
s
+
0.5
,
y
s
0
.5
)
出发，到
(
y
t
+
0.5
,
y
t
+
0.5
)
(yt+0.5,yt+0.5)
(
y
t
+
0.5
,
y
t
+
0.5
)
,图中有一些墙，穿过这堵墙的花费是1，问到达终点的最小花费
因为数据很小，所以可以用暴力搜索的方法解决，不妨用二进制的方式遍历每一种可能，从0开始到
1
<
<
k
1<<k
1
<<
k
,读取每一位，若为0则表示不通过该墙，若为1则表示可以通过该墙，并且把不能通过的墙进行标记，然后在后续的dfs中查找是否存在上述条件中可以到达终点的情况，若存在就把当前情况中的1（二进制看）记录一个最小值，最后输出即可，需要注意的是偏移的位置处理
标程
#include<bits/stdc++.h>
using namespace std;
int n,m,K,sx,sy,tx,ty;
struct edge{
int x[2],y[2];
}e[20];
int mp[20][20];
int Lw[20][20],Dw[20][20];
bool dfs(int x,int y){
mp[x][y]=1;
if(x==tx && y==ty){
return 1;
}
bool re=0;
//x-1 y
if(x>=1 && Lw[x][y]==0 && mp[x-1][y]==0){
re|=dfs(x-1,y);
}
//x+1 y
if(x+1<n && Lw[x+1][y]==0 && mp[x+1][y]==0){
re|=dfs(x+1,y);
}
//x y-1
if(y>=1 && Dw[x][y]==0 && mp[x][y-1]==0){
re|=dfs(x,y-1);
}
//x y+1
if(y+1<m && Dw[x][y+1]==0 && mp[x][y+1]==0){
re|=dfs(x,y+1);
}
return re;
}
bool check(int s){
memset(mp,0,sizeof(mp));
memset(Lw,0,sizeof(Lw));
memset(Dw,0,sizeof(Dw));
for(int i=0;i<K;++i){
if((s&(1<<i))==0){
if(e[i].x[0]==e[i].x[1]){
for(int j=e[i].y[0];j<e[i].y[1];++j){
Lw[e[i].x[0]][j]=1;
}
}
else{
for(int j=e[i].x[0];j<e[i].x[1];++j){
Dw[j][e[i].y[0]]=1;
}
}
}
}
return dfs(sx,sy);
}
int popcount(int x){
int re=0;
while(x){
if(x&1) ++re;
x>>=1;
}
return re;
}
int f[(1<<15)+5];
void solve(){
cin>>n>>m>>K>>sx>>sy>>tx>>ty;
for(int i=0;i<K;++i){
cin>>e[i].x[0]>>e[i].y[0]>>e[i].x[1]>>e[i].y[1];
if(e[i].x[0]==e[i].x[1]&&e[i].y[0]>e[i].y[1]){
swap(e[i].y[0],e[i].y[1]);
}
if(e[i].y[0]==e[i].y[1]&&e[i].x[0]>e[i].x[1]){
swap(e[i].x[0],e[i].x[1]);
}
}
int ans=K;
for(int s=0;s<(1<<K);++s){
f[s]=0;
}
for(int s=0;s<(1<<K);++s){
if(f[s]){
continue;
}
f[s]=check(s);
if(f[s]){
ans=min(ans,popcount(s));
for(int j=0;j<K;++j){
f[s|(1<<j)]|=f[s];
}
}
}
cout<<ans<<endl;
return;
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
int t=1;cin>>t;
for(int i=1;i<=t;++i){
solve();
}
return 0;
}
1003 Backpack
Problem Description
Alice has a backpack of capacity m that she now wants to fill with some items!
Alice has n items, each of which has a volume vi and a value wi.
Can a number of items be selected from n items such that the backpack is exactly full (ie the sum of the volumes equals the backpack capacity)? If so, what is the maximum XOR sum of the values of the items in the backpack when the backpack is full?
Input
The first line contains an integer T(T≤10) —the number of test cases.
The first line of each test case contains 2 integers n,m(1≤n,m<2^10) —the number of items, the capacity of the backpack.
The next n lines , each line contains 2 integers vi,wi(1≤vi,wi<2^10) — the volume and value of the item.
Output
For each test case, output a single line, if the backpack cannot be filled, just output a line of “-1”, otherwise output the largest XOR sum.
Sample Input
1
5 4
2 4
1 6
2 2
2 12
1 14
Sample Output
14
Source
[2022“杭电杯”中国大学生算法设计超级联赛（1）](http://acm.hdu.edu.cn/search.php?field=problem&key=2022%A1%B0%BA%BC%B5%E7%B1%AD%A1%B1%D6%D0%B9%FA%B4%F3%D1%A7%C9%FA%CB%E3%B7%A8%C9%E8%BC%C6%B3%AC%BC%B6%C1%AA%C8%FC%A3%A81%A3%A9&source=1&searchmode=source
tags:DP bitset优化
给你体积和价值，问你当背包装满时最大异或和时多少
因为时求最大的异或和，所以我们可以用是否存在作为DP的结果
故可以开成三维DP
f
[
i
]
[
j
]
[
k
]
f[i][j][k]
f
[
i
]
[
j
]
[
k
]
其中i表示前i个物品，j表示异或和，k表示当前的体积
那么当前状态是前一个物品不选择
f
[
i
−
1
]
[
j
]
[
k
]
f[i-1][j][k]
f
[
i
−
1
]
[
j
]
[
k
]
∪ 选择前一个物品
f
[
i
−
1
]
[
j
⊕
w
]
[
k
−
v
]
f[i-1][j \oplus w][k-v]
f
[
i
−
1
]
[
j
⊕
w
]
[
k
−
v
]
按顺序读入可以去掉第一维，然后用bitset优化
f
[
j
]
[
m
]
f[j][m]
f
[
j
]
[
m
]
其中j表示异或和 m表示体积
因为体积和价值均小于
2
10
2^{10}
2
10
，所以异或和也小于
2
10
2^{10}
2
10
所以我们只需要开一个1024X1024的bitset进行优化
同时我们也需要开一个temp临时数组储存上一状态 即i-1
AC代码
// Problem: Backpack
// Contest: HDOJ
// URL: https://acm.hdu.edu.cn/showproblem.php?pid=7140
// Memory Limit: 65 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bitset>
#include <iostream>
using namespace std;
const int N = 1050;
bitset<N> f[N], temp[N];
int main() {
int t;
cin >> t;
while (t--) {
int n, m,x,y;
cin >> n >> m;
for (int i = 0; i < N; i++) f[i].reset();
f[0][0] = 1; //初始状态 前0个物品异或和为0是存在的
long long ans = -1;
for (int i = 1; i <= n; i++) {
cin >> x >> y;
for (int j = 0; j <= 1024; j++) { //此时j为异或和的值
temp[j] = f[j]; //保存上一状态
temp[j] <<= x; //体积加上x;
}
for (int j = 0; j < 1024; j++) f[j] |= temp[j ^ y];
}
for (int i = 1; i <= 1024; i++)
if (f[i][m]) ans = i; //如果存在异或和为i，体积为m，那么记录该答案;
cout << ans << endl;
}
}
1004 Ball
Problem Description
Give a chessboard of M∗M , with N point on it. You should calculate how many solutions there ar to select 3 points to make the median distance between the distance between the 3 points is a prime number?
the distance between (x1,y1) and (x2,y2) is |x1−x2|+|y1−y2|
Input
Each test contains multiple test cases. The first line contains the number of test cases T(1≤T≤10). Description of the test cases follows.
The first line of each test case contains two integers N,M
The next N lines each line contains two integers xi,yi
It’s guaranteed there are no i,j(i≠j) satisfies both xi=xj and yi=yj
1≤N≤2000,1≤M≤105,1≤xi,yi≤M
Output
For each test case, print one integer — the answer to the problem.
Sample Input
2
3 3
1 1
2 2
3 3
3 3
1 1
2 1
3 2
Sample Output
1
1
Source
给你一个MXM的棋盘，上面有N个点，问你选择三个点，其中中位数是素数的情况有多少种
首先处理出1e5中的所有素数（用线性筛），然后考虑一下该如何处理这类问题
如果暴击美剧的话复杂度是8e9，必然超时，所以我们要考虑优化
我们不妨枚举两个点，并且把该边作为我们要求的中位数素数边，那么我们只需要求一条边小于该边，一条边大于该边的情况就可以
那么我们该如何处理呢，这里还是使用bitset，首先按照两个点的距离从小到大进行排序，并进行遍历
并且记录下这条较小边是由哪两个点连接的
如果当前边为素数，那么我们就找这两个点和哪些点相连时会存在较小边，这里涉及到一个几何问题（两边之和大于第三边）那么当你确定好较小边和中位边后剩下的边自然时最大的，这里我们用
p
[
i
]
⊕
p
[
j
]
p[i]\oplus p[j]
p
[
i
]
⊕
p
[
j
]
表示答案，即我在i或j中选都可以，最后用count记录这里面有多少个1，就是有多少个较小边
AC代码
/****************
*@description:for the Escape Project
*@author: Nebula_xuan
* @Date: 2022-07-20 21:43:33
*************************************************************************/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <cmath>
using namespace std;
const int N = 2e3 + 10, M = 2e5 + 10;
struct node
{
int l, r, w;
bool operator<(const node &f) const
{
return w < f.w;
}
} tr[N * N];
int n, m, a[N], b[N];
bitset<N> p[N];
bool st[N * N];
int primes[N * N];
long long cnt, ans;
typedef pair<int, int> PII;
typedef long long ll;
void init()
{
for (int i = 2; i <= M; i++)
{
if (!st[i])
primes[cnt++] = i;
for (int j = 0; primes[j] * i <= M; j++)
{
st[primes[j] * i] = true;
if (i % primes[j] == 0)
break;
}
}
}
int main()
{
init();
st[1] = true;
int t;
scanf("%d", &t);
while (t--)
{
scanf("%d %d", &n, &m);
cnt = 0, ans = 0;
for (int i = 1; i <= n; i++)
p[i].reset();
for (int i = 1; i <= n; i++)
scanf("%d %d", &a[i], &b[i]);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
tr[++cnt] = {i, j, abs(a[i] - a[j]) + abs(b[i] - b[j])};
sort(tr + 1, tr + cnt + 1);
for (int i = 1; i <= cnt; i++)
{
int x = tr[i].l, y = tr[i].r, v = tr[i].w;
if (!st[v])
ans += (p[x] ^ p[y]).count();
p[x][y] = 1, p[y][x] = 1;
}
printf("%d\n", ans);
}
}
1008 Path
Problem Description
Given a graph with n vertices and m edges.Each vertex is numbered from 1 to n.
Each edge i has its cost wi,some edges are common edges and some edges are special edges.
When you pass through a special edge, the next step after passing this edge,you can reach any vertex in the graph. If you goto the vertex which an original edge i can arrive from current vertex, the cost becomes wi−K(0≤wi−K)(if you used edge i), otherwise the cost will become 0(every vertex except the vertex which original edge can arrive from current vertice)
original edge includes all common edges and special edges.
Now you start at S,You need to calculate the minimum cost from the starting vertex to each vertex(If there is a situation where you cannot reach, please output “-1”)
Input
Each test contains multiple test cases. The first line contains the number of test cases T. Description of the test cases follows.
The first line of each test case contains four integers n,m,S,K
The next m lines each line contains four integers x,y,w,t represent an directed edge connect x and y with cost w,t=0 represents it’s a common edge,t=1 represents it’s a special edge.
1≤∑m,∑n≤106,1≤x,y,S≤n,1≤w,K≤109
K≤wi(1≤i≤m)
Output
For each test case, print n integer in a line— the answer to the problem.
There is a space at the end of the line for each line,when you cannot reach, please output “-1”.
Sample Input
2
5 4 1 1
1 2 4 0
1 3 5 0
3 4 3 1
4 5 3 0
5 3 1 1
1 2 4 0
1 3 5 0
3 4 3 1
Sample Output
0 4 5 8 10
0 4 5 8 8
Source
2022“杭电杯”中国大学生算法设计超级联赛（1）
给你一个n个点m条边的无向图，m条边中有两种边，一种是特殊边，一种是普通边，经过这条特殊边后我们可以以0花费到达任意不和它相邻的点，而经过普通边我们需要花费
w
i
−
K
w_i-K
w
i
−
K
,问到达各个点的最小花费是多少
这道题我们用分层图来写，以
d
i
s
t
[
i
]
[
0
]
dist[i][0]
d
i
s
t
[
i
]
[
0
]
表示是从特殊边到达i的最小距离，
d
i
s
t
[
i
]
[
1
]
dist[i][1]
d
i
s
t
[
i
]
[
1
]
表示是从普通边到达i的最小距离,然后我们从源点跑一边dijkstra，需要注意的是如果经过了一条特殊边那么我们就把其他不与该边相邻的点从队列中删除，因为这些点的距离就等于到达特殊边的距离，而因为dijkstra算法我们很容易知道这样的距离是最小的
AC代码
/****************
*@description:for the Escape Project
*@author: Nebula_xuan
* @Date: 2022-07-21 20:49:34
*************************************************************************/
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
using namespace std;
#define rep(h, t) for (int i = h; i <= t; i++)
#define dep(t, h) for (int i = t; i >= h; i--)
typedef pair<int, int> PII;
typedef long long ll;
const int N = 5e5 + 10;
const int M = N * 2;
int n, m, s, k;
ll dist[N][2];
bool st[N][2];
int vis[N];
int h[N], ne[M], e[M], w[M], p[M], idx;
struct node
{
ll a, b, p;
bool operator<(const node &w) const
{
return b > w.b;
}
};
void add(int a, int b, int c, int d)
{
e[idx] = b, ne[idx] = h[a], w[idx] = c, p[idx] = d, h[a] = idx++;
}
void dijkstra()
{
set<int> S;
rep(1, n)
{
if (i != s)
S.insert(i);
st[i][0] = st[i][1] = false;
dist[i][0] = dist[i][1] = 1e18;
}
dist[s][0] = 0;
priority_queue<node> q;
q.push({s, 0, 0});
int cnt = 0;
while (q.size())
{
auto t = q.top();
q.pop();
int ver = t.a, tp = t.p;
cnt++;
if (!tp)
S.erase(ver);
else
{
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
vis[j] = cnt;
}
vector<int> v;
for (auto it : S)
{
if (vis[it] != cnt)
{
dist[it][0] = dist[ver][1];
q.push({it, dist[it][0], 0});
v.push_back(it);
}
}
for (auto it : v)
S.erase(it);
}
int y = 0;
if (tp)
y -= k;
if (st[ver][tp])
continue;
else
st[ver][tp] = 1;
for (int i = h[ver]; i != -1; i = ne[i])
{
int j = e[i];
if (dist[j][p[i]] > dist[ver][tp] + w[i] + y)
{
dist[j][p[i]] = dist[ver][tp] + w[i] + y;
q.push({j, dist[j][p[i]], p[i]});
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
{
idx = 0;
cin >> n >> m >> s >> k;
rep(0, n)
{
h[i] = -1, vis[i] = 0;
}
rep(1, m)
{
int x, y, z, zz;
cin >> x >> y >> z >> zz;
add(x, y, z, zz);
}
dijkstra();
rep(1, n)
{
if (min(dist[i][0], dist[i][1]) != 1e18)
cout << min(dist[i][0], dist[i][1]) << " ";
else
cout << "-1 ";
}
cout << endl;
// puts("");
}
}
1009 Laser
Problem Description
There are n enemies on a two-dimensional plane, and the position of the i-th enemy is (xi,yi)
You now have a laser weapon, which you can place on any grid (x,y)(x, y are real numbers) , and the weapon fires a powerful laser that for any real number k, enemies at coordinates (x+k,y),(x,y+k),(x+k,y+k),(x+k,y−k) will be destroyed.
You are now wondering if it is possible to destroy all enemies with only one laser weapon.
Input
The first line of input is a positive integer T(T≤105) representing the number of data cases.
For each case, first line input a positive integer n to represent the position of the enemy.
Next n line, the i-th line inputs two integers xi,yi(−108≤xi,yi≤108) represents the position of the i-th enemy.
The data guarantees that the sum of n for each test case does not exceed 500,000
Output
For each cases, If all enemies can be destroyed with one laser weapon, output “YES“, otherwise output “NO“(not include quotation marks).
Sample Input
2
6
1 1
1 3
2 2
3 1
3 3
3 4
7
1 1
1 3
2 2
3 1
3 3
1 4
3 4
Sample Output
YES
NO
给你一把激光枪，它可以攻击到以自身为原点八个方向的敌人，问你存不存在一个点，激光枪可以攻击到所有的敌人
如果存在这样的点，那么代表任何敌人他都可以攻击到，那么我们按顺序选一个点，过它做横线，然后遍历其他点，如果其他点画出的线（类似于米字）和该线相交，相交的点与我们选中的两点都会相交，同理作该点的竖线、斜线（这些线可能遍历到，直接旋转坐标即可）那么答案肯定会在这些点之中，我们遍历查找它的可行性，如果存在就输出YES，如果遍历完所有点还是没有答案的话就输出NO
需要注意的是如何处理，比较考验码力
tags:计算几何
AC代码
/****************
*@description:for the Escape Project
*@author: Nebula_xuan
* @Date: 2022-07-20 20:08:27
*************************************************************************/
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5e5 + 10;
typedef pair<int, int> PII;
typedef long long ll;
int x[N], y[N], n, a[N], b[N];
ll read()
{
ll x = 0;
char c = getchar();
bool f = 0;
while (!isdigit(c))
{
if (c == '-')
f = 1;
c = getchar();
}
while (isdigit(c))
{
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f ? -x : x;
}
bool solve(int x, int y)
{
if (x == y || x == 0 || y == 0 || x + y == 0)
return true;
return false;
}
bool check(int xx, int yy)
{
for (int i = 1; i <= n; i++)
if (!solve(xx - x[i], yy - y[i]))
return false;
return true;
}
bool draw()
{
bool flag = true;
for (int i = 2; i <= n; i++)
{
if (x[i] == x[1])
continue;
flag = false; //排除都在一条直线上的情况
if (check(x[1], y[i]))
return true;
if (check(x[1], y[i] + (x[i] - x[1])))
return true;
if (check(x[1], y[i] - (x[i] - x[1])))
return true;
break;
}
return flag;
}
int main()
{
int t;
t = read();
while (t--)
{
bool flag = false;
n = read();
for (int i = 1; i <= n; i++)
{
a[i] = read();
b[i] = read();
}
for (int i = 1; i <= n; i++)
x[i] = a[i], y[i] = b[i];
if (draw())
{
puts("YES");
continue;
}
for (int i = 1; i <= n; i++)
x[i] = b[i], y[i] = a[i];
if (draw())
{
puts("YES");
continue;
}
for (int i = 1; i <= n; i++)
x[i] = a[i] + b[i], y[i] = a[i] - b[i];
if (draw())
{
puts("YES");
continue;
}
for (int i = 1; i <= n; i++)
x[i] = a[i] - b[i], y[i] = a[i] + b[i];
if (draw())
{
puts("YES");
continue;
}
puts("NO");
}
}
1012 Alice and Bob
Problem Description
Alice and Bob like playing games.
There are m numbers written on the blackboard, all of which are integers between 0 and n.The rules of the game are as follows:
If there are still numbers on the blackboard, and there are no numbers with value 0 on the blackboard, Alice can divide the remaining numbers on the blackboard into two sets.
Bob chooses one of the sets and erases all numbers in that set. Then subtract all remaining numbers by one.
At any time, if there is a number with a value of 0 on the blackboard, Alice wins; otherwise, if all the numbers on the blackboard are erased, Bob wins.
Please determine who will win the game if both Alice and Bob play the game optimally.
Input
The first line contains an integer T(T≤2000) —the number of test cases.
The first line of each test case contains a single integers n(1≤∑n≤106) .
The second line of each test case contains n+1 integers a0,a1,a2…an(0≤ai≤106,∑ai=m) — there are ai numbers with value i on the blackboard .
Output
For each test case, print “Alice” if Alice will win the game, otherwise print “Bob”.
Sample Input
2
1
0 1
1
0 2
Sample Output
Bob
Alice
给你一个集合，Alice可以把集合分成两半，Bob会删掉其中一个集合，并将另一个集合的所有数字减一，如果一个集合中出现了0 Alice获胜 如果集合被删完则Bob获胜
因为每个人都会以最优策略进行操作，所以Alice会尽量将小的值分成两半，使Bob操作更多次数，而Bob也会优先删除较小值多的集合
所以我们按平分策略来处理这道题，那么我们从后往前处理
a
i
a_i
a
i
,每次平分会将当前集合数字减一，并且数目减半，所以
a
[
i
−
1
]
=
a
[
i
]
/
2
a[i-1]=a[i]/2
a
[
i
−
1
]
=
a
[
i
]
/2
,如果最后
a
[
0
]
a[0]
a
[
0
]
有值则爱丽丝获胜
tags:思维
标程
#include<bits/stdc++.h>
using namespace std;
int n;
int a[1000005];
void solve(){
cin>>n;
for(int i=0;i<=n;++i){
cin>>a[i];
}
for(int i=n;i>0;--i){
a[i-1]+=a[i]/2;
}
if(a[0]) cout<<"Alice\n";
else cout<<"Bob\n";
}
int main(){
std::ios::sync_with_stdio(false);
cin.tie(0);
int t=1;cin>>t;
for(int i=1;i<=t;++i){
solve();
}
return 0;
}