題目

• 1002 Dragon slayer
• • 標(biāo)程
• 1003 Backpack
• • AC代碼
• 1004 Ball
• • AC代碼
• 1008 Path
• • AC代碼
• 1009 Laser
• • AC代碼
• 1012 Alice and Bob
• • 標(biāo)程

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

給你一張地圖，你從$(xs+0.5,y{s}_0.5)$出發(fā)，到$(yt+0.5,yt+0.5)$,圖中有一些墻，穿過這堵墻的花費(fèi)是1，問到達(dá)終點(diǎn)的最小花費(fèi)
因?yàn)閿?shù)據(jù)很小，所以可以用暴力搜索的方法解決，不妨用二進(jìn)制的方式遍歷每一種可能，從0開始到$1<<k$,讀取每一位，若為0則表示不通過該墻，若為1則表示可以通過該墻，并且把不能通過的墻進(jìn)行標(biāo)記，然后在后續(xù)的dfs中查找是否存在上述條件中可以到達(dá)終點(diǎn)的情況，若存在就把當(dāng)前情況中的1（二進(jìn)制看）記錄一個(gè)最小值，最后輸出即可，需要注意的是偏移的位置處理

標(biāo)程

#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 yif(x>=1 && Lw[x][y]==0 && mp[x-1][y]==0){re|=dfs(x-1,y);}//x+1 yif(x+1<n && Lw[x+1][y]==0 && mp[x+1][y]==0){re|=dfs(x+1,y);}//x y-1if(y>=1 && Dw[x][y]==0 && mp[x][y-1]==0){re|=dfs(x,y-1);}//x y+1if(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“杭電杯”中國(guó)大學(xué)生算法設(shè)計(jì)超級(jí)聯(lián)賽（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優(yōu)化
給你體積和價(jià)值，問你當(dāng)背包裝滿時(shí)最大異或和時(shí)多少
因?yàn)闀r(shí)求最大的異或和，所以我們可以用是否存在作為DP的結(jié)果
故可以開成三維DP$f[i][j][k]$
其中i表示前i個(gè)物品，j表示異或和，k表示當(dāng)前的體積
那么當(dāng)前狀態(tài)是前一個(gè)物品不選擇 $f[i?1][j][k]$ ∪ 選擇前一個(gè)物品$f[i?1][j\oplus w][k?v]$
按順序讀入可以去掉第一維，然后用bitset優(yōu)化 $f[j][m]$ 其中j表示異或和 m表示體積
因?yàn)轶w積和價(jià)值均小于$2^{10}$，所以異或和也小于$2^{10}$ 所以我們只需要開一個(gè)1024X1024的bitset進(jìn)行優(yōu)化
同時(shí)我們也需要開一個(gè)temp臨時(shí)數(shù)組儲(chǔ)存上一狀態(tài) 即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; //初始狀態(tài) 前0個(gè)物品異或和為0是存在的long long ans = -1;for (int i = 1; i <= n; i++) {cin >> x >> y;for (int j = 0; j <= 1024; j++) { //此時(shí)j為異或和的值temp[j] = f[j]; //保存上一狀態(tài)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

2022“杭電杯”中國(guó)大學(xué)生算法設(shè)計(jì)超級(jí)聯(lián)賽（1）

給你一個(gè)MXM的棋盤，上面有N個(gè)點(diǎn)，問你選擇三個(gè)點(diǎn)，其中中位數(shù)是素?cái)?shù)的情況有多少種
首先處理出1e5中的所有素?cái)?shù)（用線性篩），然后考慮一下該如何處理這類問題
如果暴擊美劇的話復(fù)雜度是8e9，必然超時(shí)，所以我們要考慮優(yōu)化
我們不妨枚舉兩個(gè)點(diǎn)，并且把該邊作為我們要求的中位數(shù)素?cái)?shù)邊，那么我們只需要求一條邊小于該邊，一條邊大于該邊的情況就可以
那么我們?cè)撊绾翁幚砟?#xff0c;這里還是使用bitset，首先按照兩個(gè)點(diǎn)的距離從小到大進(jìn)行排序，并進(jìn)行遍歷
并且記錄下這條較小邊是由哪兩個(gè)點(diǎn)連接的
如果當(dāng)前邊為素?cái)?shù)，那么我們就找這兩個(gè)點(diǎn)和哪些點(diǎn)相連時(shí)會(huì)存在較小邊，這里涉及到一個(gè)幾何問題（兩邊之和大于第三邊）那么當(dāng)你確定好較小邊和中位邊后剩下的邊自然時(shí)最大的，這里我們用$p[i]\oplus p[j]$表示答案，即我在i或j中選都可以，最后用count記錄這里面有多少個(gè)1，就是有多少個(gè)較小邊

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“杭電杯”中國(guó)大學(xué)生算法設(shè)計(jì)超級(jí)聯(lián)賽（1）

給你一個(gè)n個(gè)點(diǎn)m條邊的無向圖，m條邊中有兩種邊，一種是特殊邊，一種是普通邊，經(jīng)過這條特殊邊后我們可以以0花費(fèi)到達(dá)任意不和它相鄰的點(diǎn)，而經(jīng)過普通邊我們需要花費(fèi)$w_i?K$,問到達(dá)各個(gè)點(diǎn)的最小花費(fèi)是多少
這道題我們用分層圖來寫，以$dist[i][0]$表示是從特殊邊到達(dá)i的最小距離，$dist[i][1]$表示是從普通邊到達(dá)i的最小距離,然后我們從源點(diǎn)跑一邊dijkstra，需要注意的是如果經(jīng)過了一條特殊邊那么我們就把其他不與該邊相鄰的點(diǎn)從隊(duì)列中刪除，因?yàn)檫@些點(diǎn)的距離就等于到達(dá)特殊邊的距離，而因?yàn)閐ijkstra算法我們很容易知道這樣的距離是最小的

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;elsest[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]) << " ";elsecout << "-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

給你一把激光槍，它可以攻擊到以自身為原點(diǎn)八個(gè)方向的敵人，問你存不存在一個(gè)點(diǎn)，激光槍可以攻擊到所有的敵人
如果存在這樣的點(diǎn)，那么代表任何敵人他都可以攻擊到，那么我們按順序選一個(gè)點(diǎn)，過它做橫線，然后遍歷其他點(diǎn)，如果其他點(diǎn)畫出的線（類似于米字）和該線相交，相交的點(diǎn)與我們選中的兩點(diǎn)都會(huì)相交，同理作該點(diǎn)的豎線、斜線（這些線可能遍歷到，直接旋轉(zhuǎn)坐標(biāo)即可）那么答案肯定會(huì)在這些點(diǎn)之中，我們遍歷查找它的可行性，如果存在就輸出YES，如果遍歷完所有點(diǎn)還是沒有答案的話就輸出NO
需要注意的是如何處理，比較考驗(yàn)碼力

tags:計(jì)算幾何

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

給你一個(gè)集合，Alice可以把集合分成兩半，Bob會(huì)刪掉其中一個(gè)集合，并將另一個(gè)集合的所有數(shù)字減一，如果一個(gè)集合中出現(xiàn)了0 Alice獲勝 如果集合被刪完則Bob獲勝
因?yàn)槊總€(gè)人都會(huì)以最優(yōu)策略進(jìn)行操作，所以Alice會(huì)盡量將小的值分成兩半，使Bob操作更多次數(shù)，而Bob也會(huì)優(yōu)先刪除較小值多的集合
所以我們按平分策略來處理這道題，那么我們從后往前處理$a_i$,每次平分會(huì)將當(dāng)前集合數(shù)字減一，并且數(shù)目減半，所以$a[i?1]=a[i]/2$,如果最后$a[0]$有值則愛麗絲獲勝

tags:思維

標(biāo)程

#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; }

總結(jié)

以上是生活随笔為你收集整理的2022“杭电杯”中国大学生算法设计超级联赛 （1) 杭电多校第一场 2 3 4 5 8 12的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。