2021“MINIEYE杯”中国大学生算法设计超级联赛（3）题解
| 😊 | Powered By HeartFireY | MINIEYE Contest 1 Solution |
D.Game on Plane
Problem Description
Alice and Bob are playing a game. In this game, there are straight lines on the 2D plane. Alice will select exactly straight lines among all the straight lines first, then Bob will draw a straight line . The penalty of Bob is defined as the number of lines in that shares at least one common point with . Note that two overlapping lines also share common points.
Alice wants to maximize the penalty of Bob while Bob wants to minimize it. You will be given these lines, please write a program to predict the penalty of Bob for if both of the players play optimally.
Input
The first line contains a single integer (), the number of test cases. For each test case:
The first line contains a single integer (), denoting the number of straight lines.
Each of the next lines contains four integers and (, denoting a straight line passes both and . will never be coincided with .
It is guaranteed that the sum of all is at most .
Output
For each test case, output lines, the -th () of which containing an integer, denoting the penalty of Bob when .
Solution
| 😀 算法标签：计算几何 |
要获得尽可能多的交点数，只需要保证穿过尽可能多的斜率不同的直线即可；
要获取尽可能少的交点数，只需要保证找到尽可能多的斜率相同的直线即可。
Alice 为了让 Bob 与尽量多的直线相交，最优策略就是最小化斜率出现次数的最大值，所以不断从每种斜率的直线中各选一种即可。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
map<double, int> mp;
int f[maxn];
pair<double, int> pus;
signed main(){
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 0; cin >> t;
while(t--){
int n = 0, nows = 0, maxx = INT_MIN, cnt = 0; cin >> n;
mp.clear();
for(int i = 0; i < n; i++){
int nx, ny, mx, my; cin >> nx >> ny >> mx >> my;
mx == nx ? (nows++) : (mp[(my - ny) * 1.0 / (mx - nx)]++);
}
memset(f, 0, (n + 10) * sizeof(int));
for(map<double,int>::iterator i = mp.begin(); i != mp.end(); i++)
pus=*i, f[pus.second]++, maxx=max(maxx, pus.second);
f[nows]++, maxx = max(maxx, nows);
for(int i = maxx; i; i--) f[i] += f[i + 1];
for(int i = 1;i <= maxx; i++){
while(f[i]--) cnt++,printf("%d\n",cnt - i);
}
}
return 0;
} G.Photoshop Layers
Solution
| 😀 算法标签：前缀和 |
队友写的，简述一下思路：
首先每个图层有两种情况
- 图层置为当前颜色(“覆盖”)
- 图层置为上一层颜色+当前层颜色(“重叠”)
首先按输入顺序进行扫描，处理出对于每个图层而言左侧第一个"覆盖"的图层，用表示。然后预处理出前缀和。
则对于每个询问，根据值找到，剩余的中间部分直接利用前缀和相减求出答案即可。
放个标程。。。
#include <cstdio>
const int N = 100005;
int Case, n, m, i, x, y, t[N], r[N], g[N], b[N], f[N];
inline int ask(int *s, int l, int r)
{
int x = f[r], ret;
if (x < l) ret = s[r] - s[l - 1];
else ret = s[r] - s[x - 1];
return ret < 255 ? ret : 255;
}
int main()
{
scanf("%d", &Case);
while (Case--)
{
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
{
scanf("%d%X", &t[i], &x);
b[i] = x & 255;
x >>= 8;
g[i] = x & 255;
x >>= 8;
r[i] = x;
r[i] += r[i - 1];
g[i] += g[i - 1];
b[i] += b[i - 1];
if (t[i] == 1) f[i] = i;
else f[i] = f[i - 1];
}
while (m--)
{
scanf("%d%d", &x, &y);
printf("%02X%02X%02X\n", ask(r, x, y), ask(g, x, y), ask(b, x, y));
}
}
} I.Rise in Price
Problem Description
There are cells on a grid, the top-left cell is at while the bottom-right cell is at . You start at and move to . At any cell , you can move to or , provided that you don’t move out of the grid. Clearly, you will make exactly
When you are at cell , including the starting point and the destination , you can take all the diamonds at this cell, and have a chance to raise the price of each diamond by dollars. You will sell all the diamonds you have with the final price in the end, and your goal is to choose the optimal path that will maximize your profits. Note that initially the price of each diamond is zero, and you have nothing to sell.
Input
The first line contains a single integer (), the number of test cases. For each test case:
The first line contains a single integer (), denoting the size of the grid.
Each of the following lines contains integers, the -th line contains (), denoting the number of diamonds in each cell.
Each of the following lines contains integers, the -th line contains (), denoting how much you can raise the price in each cell.
It is guaranteed that all the values of and are chosen uniformly at random from integers in . The randomness condition does not apply to the sample test case, but your solution must pass the sample as well.
Output
For each test case, output a single line containing an integer: the maximum number of dollars you can earn by selling diamonds.
Solution
| 😀 算法标签：启发式搜索 |
带点权双约图束寻路，单图范围100*100，搜索只有两个方向，考虑启发式搜索：首先构造估值函数的计算方式
计算每个点对于答案的贡献：对于当前点而言，起点到当前点路径上的点权和(已走路径)记为，当前点到终点(未走路径)的路径点权和为(假设路径已经确定)，那么当前点的贡献可以表示为。
但是在实际的路线中，对于已走路径是唯一确定的，而未走路径是不确定的，因此我们可以假设某条可被选的路径所有权值之和为，对于的最大值(即最大值)我们可以由向进行状态转移(转移时取)得到，是一个已经确定的值，状态转移方程如下：
我们可以对贡献方程进行变形：，展开可得，其中变量为，对求导或直接由二次方程对称轴可得当贡献取极大值时，，则。代入贡献方程：
那么对于每个点可以计算其贡献值，如果贡献值小于已知答案，那么终止搜索；如果贡献值大于已知答案，则继续搜索。
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 110;
int n = 0, ans = 0, maxval[maxn][maxn], a[maxn][maxn], b[maxn][maxn];
inline int h(int x, int y, int sum1, int sum2){ return ((sum1 + sum2 + maxval[x][y]) >> 1); }
void dfs(int x, int y, int cnta, int cntb){
if(x == n && y == n){
ans = max(ans, cnta * cntb);
return;
}
int h0 = h(x + 1, y, cnta, cntb), h1 = h(x, y + 1, cnta, cntb);
if(x < n && h0 * h0 > ans) dfs(x + 1, y, cnta + a[x + 1][y], cntb + b[x + 1][y]);
if(y < n && h1 * h1 > ans) dfs(x, y + 1, cnta + a[x][y + 1], cntb + b[x][y + 1]);
}
signed main(){
ios_base::sync_with_stdio(false);
int t = 0; cin >> t;
while(t--){
cin >> n;
ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) cin >> a[i][j];
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) cin >> b[i][j];
for(int i = n; i > 0; i--)
for(int j = n; j > 0; j--){
maxval[i][j] = a[i][j] + b[i][j];
if(i != n)
maxval[i][j] = max(maxval[i][j], a[i][j] + b[i][j] + maxval[i + 1][j]);
if(j != n)
maxval[i][j] = max(maxval[i][j], a[i][j] + b[i][j] + maxval[i][j + 1]);
}
dfs(1, 1, a[1][1], b[1][1]);
cout << ans << endl;
}
return 0;
} K.Segment Tree with Pruning
Problem Description
Chenjb is struggling with data stucture now. He is trying to solve a problem using segment tree. Chenjb is a freshman in programming contest, and he wrote down the following C/C++ code and ran ‘’’’ to build a standard segment tree on range :
Node* build(long long l, long long r) {
Node* x = new(Node);
if (l == r) return x;
long long mid = (l + r) / 2;
x -> lchild = build(l, mid);
x -> rchild = build(mid + 1, r);
return x;
} Chenjb submitted his code, but unfortunately, got MLE (Memory Limit Exceeded). Soon Chenjb realized that his program will new a large quantity of nodes, and he decided to reduce the number of nodes by pruning:
Node* build(long long l, long long r) {
Node* x = new(Node);
if (r - l + 1 <= k) return x;
long long mid = (l + r) / 2;
x -> lchild = build(l, mid);
x -> rchild = build(mid + 1, r);
return x;
} You know, Chenjb is a freshman, so he will try different values of to find the optimal one. You will be given the values of and , please tell him the number of nodes that will be generated by his new program.
Input
The first line contains a single integer (), the number of test cases. For each test case:
The only line contains two integers and (), denoting a query.
Output
For each query, print a single line containing an integer, denoting the number of segment tree nodes.
Solution
| 😀 算法标签：记忆化搜索 |
#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int, int> mp;
int n = 0, k = 0;
inline void init(){ mp.clear(); }
int dfs(int l, int r){
if(r - l + 1 <= k) return 1;
if(mp.find(r - l + 1) != mp.end()) return mp[r - l + 1];
int mid = l + r >> 1, now = 1;
now += dfs(l, mid), now += dfs(mid + 1, r);
mp[r - l + 1] = now;
return now;
}
signed main(){
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 0; cin >> t;
while(t--){
cin >> n >> k;
init();
cout << dfs(1, n) << endl;
}
return 0;
} ![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)