2021“MINIEYE杯”中国大学生算法设计超级联赛（3）题解

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 n n n straight lines on the 2D plane. Alice will select exactly k k k straight lines l 1 , l 2 , … , l k l_1,l_2,\dots,l_k l1​,l2​,…,lk​ among all the n n n straight lines first, then Bob will draw a straight line L L L. The penalty of Bob is defined as the number of lines in { l 1 , l 2 , … , l k } \{l_1,l_2,\dots,l_k\} {l1​,l2​,…,lk​} that shares at least one common point with L L L. 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 n n n lines, please write a program to predict the penalty of Bob for k = 1 , 2 , 3 , … , n k=1,2,3,\dots,n k=1,2,3,…,n​ if both of the players play optimally.

Input

The first line contains a single integer T T T ( 1 ≤ T ≤ 500 1 \leq T \leq 500 1≤T≤500​), the number of test cases. For each test case:

The first line contains a single integer n n n ( 1 ≤ n ≤ 100   000 1 \leq n \leq 100\,000 1≤n≤100000), denoting the number of straight lines.

Each of the next n n n lines contains four integers x a i , y a i , x b i xa_i,ya_i,xb_i xai​,yai​,xbi​ and y b i yb_i ybi​ ( 0 ≤ x a i , y a i , x b i , y b i ≤ 1 0 9 ) 0\leq xa_i,ya_i,xb_i,yb_i\leq 10^9) 0≤xai​,yai​,xbi​,ybi​≤109), denoting a straight line passes both ( x a i , y a i ) (xa_i,ya_i) (xai​,yai​) and ( x b i , y b i ) (xb_i,yb_i) (xbi​,ybi​). ( x a i , y a i ) (xa_i,ya_i) (xai​,yai​) will never be coincided with ( x b i , y b i ) (xb_i,yb_i) (xbi​,ybi​)​.

It is guaranteed that the sum of all n n n is at most 1   000   000 1\,000\,000 1000000​​​​.

Output

For each test case, output n n n lines, the i i i-th ( 1 ≤ i ≤ n 1\leq i\leq n 1≤i≤n) of which containing an integer, denoting the penalty of Bob when k = i k=i k=i.

Solution

😀 算法标签：计算几何

要获得尽可能多的交点数，只需要保证穿过尽可能多的斜率不同的直线即可；

要获取尽可能少的交点数，只需要保证找到尽可能多的斜率相同的直线即可。

Alice 为了让 Bob 与尽量多的直线相交，最优策略就是最小化斜率出现次数的最大值，所以不断从每种斜率的直线中各选一种即可。

#include 
using namespace std;

const int maxn = 1e6 + 10;
map mp;
int f[maxn];
pair 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 > nx >> ny >> mx >> my;
            mx == nx ? (nows++) : (mp[(my - ny) * 1.0 / (mx - nx)]++);
        }
        memset(f, 0, (n + 10) * sizeof(int));
        for(map::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 = 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 n × n n \times n n×n cells on a grid, the top-left cell is at ( 1 , 1 ) (1,1) (1,1) while the bottom-right cell is at ( n , n ) (n,n) (n,n). You start at ( 1 , 1 ) (1,1) (1,1) and move to ( n , n ) (n,n) (n,n). At any cell ( i , j ) (i,j) (i,j), you can move to ( i + 1 , j ) (i+1,j) (i+1,j) or ( i , j + 1 ) (i,j+1) (i,j+1), provided that you don’t move out of the grid. Clearly, you will make exactly 2 n − 2 2n-2 2n−2 steps.

When you are at cell ( i , j ) (i,j) (i,j), including the starting point ( 1 , 1 ) (1,1) (1,1) and the destination ( n , n ) (n,n) (n,n), you can take all the a i , j a_{i,j} ai,j​ diamonds at this cell, and have a chance to raise the price of each diamond by b i , j b_{i,j} bi,j​​ 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 T T T ( 1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10​), the number of test cases. For each test case:

The first line contains a single integer n n n ( 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100), denoting the size of the grid.

Each of the following n n n lines contains n n n integers, the i i i-th line contains a i , 1 , a i , 2 , … , a i , n a_{i,1},a_{i,2},\dots,a_{i,n} ai,1​,ai,2​,…,ai,n​ ( 1 ≤ a i , j ≤ 1 0 6 1\leq a_{i,j}\leq 10^6 1≤ai,j​≤106), denoting the number of diamonds in each cell.

Each of the following n n n lines contains n n n integers, the i i i-th line contains b i , 1 , b i , 2 , … , b i , n b_{i,1},b_{i,2},\dots,b_{i,n} bi,1​,bi,2​,…,bi,n​ ( 1 ≤ b i , j ≤ 1 0 6 1\leq b_{i,j}\leq 10^6 1≤bi,j​≤106​), denoting how much you can raise the price in each cell.

It is guaranteed that all the values of a i , j a_{i,j} ai,j​ and b i , j b_{i,j} bi,j​ are chosen uniformly at random from integers in [ 1 , 1 0 6 ] [1,10^6] [1,106]​​​​​​. 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，搜索只有两个方向，考虑启发式搜索：首先构造估值函数的计算方式

计算每个点对于答案的贡献：对于当前点而言，起点到当前点路径上的点权和(已走路径)记为 c n t a ， c n t b cnt_a，cnt_b cnta​，cntb​​，当前点到终点(未走路径)的路径点权和为 A , B A, B A,B(假设路径已经确定)，那么当前点的贡献可以表示为 ( c n t a + A ) × ( c n t b + B ) (cnt_a + A) \times (cnt_b + B) (cnta​+A)×(cntb​+B)。

但是在实际的路线中，对于已走路径是唯一确定的，而未走路径是不确定的，因此我们可以假设某条可被选的路径所有权值之和为 S U M = A + B SUM = A + B SUM=A+B​​​​，对于 S U M ( i , j ) SUM_{(i, j)} SUM(i,j)​​​​​的最大值(即 A i , j + B i , j A_{i,j} + B_{i, j} Ai,j​+Bi,j​​​最大值​)我们可以由 ( n , n ) (n, n) (n,n)​​​向 ( 1 , 1 ) (1, 1) (1,1)​​​进行状态转移(转移时取 m a x max max​​​​)得到，是一个已经确定的值，状态转移方程如下： m a x v a l [ i ] [ j ] = m a x ( m a x v a l [ i ] [ j ] , a [ i ] [ j ] + b [ i ] [ j ] + m a x v a l [ i + 1 ] [ j ] ) ; ( i ≠ n ) m a x v a l [ i ] [ j ] = m a x ( m a x v a l [ i ] [ j ] , a [ i ] [ j ] + b [ i ] [ j ] + m a x v a l [ i ] [ j + 1 ] ) ; ( j ≠ n ) ( i   f r o m   n   t o   1 ;   j   f r o m   n   t o   1 ) \begin{aligned} maxval[i][j] &= max(maxval[i][j], a[i][j] + b[i][j] + maxval[i + 1][j]);(i \neq n)\\ maxval[i][j] &= max(maxval[i][j], a[i][j] + b[i][j] + maxval[i][j + 1]);(j \neq n)\\ &(i\ from\ n\ to\ 1 ;\ j\ from\ n\ to\ 1) \end{aligned} maxval[i][j]maxval[i][j]​=max(maxval[i][j],a[i][j]+b[i][j]+maxval[i+1][j]);(i​=n)=max(maxval[i][j],a[i][j]+b[i][j]+maxval[i][j+1]);(j​=n)(i from n to 1; j from n to 1)​

我们可以对贡献方程进行变形： ( c n t a + A ) × ( c n t b + S U M − B ) (cnt_a + A) \times (cnt_b + SUM - B) (cnta​+A)×(cntb​+SUM−B)​​，展开可得 c n t a c n t b + A c n t b + S U M c n t a − A c n t a + S U M × A + A 2 cnt_acnt_b + Acnt_b + SUMcnt_a - Acnt_a + SUM \times A + A^2 cnta​cntb​+Acntb​+SUMcnta​−Acnta​+SUM×A+A2​​，其中变量为 A A A​​，对 A A A​​求导或直接由二次方程对称轴可得当贡献取极大值时， A = c n t b − c n t a + S U M 2 A = \frac{cnt_b - cnt_a + SUM}{2} A=2cntb​−cnta​+SUM​​​，则 B = S U M − A = c n t a − c n t b + S U M 2 B = SUM - A = \frac{cnt_a - cnt_b + SUM}{2} B=SUM−A=2cnta​−cntb​+SUM​​​。代入贡献方程： F = ( c n t a + A ) ( c n t b + B ) = ( c n t a + c n t b − c n t a + S U M 2 ) × ( c n t b + c n t a − c n t b + S U M 2 ) = ( c n t a + c n t b + S U M 2 ) 2 F = (cnt_a + A)(cnt_b + B) = (cnt_a + \frac{cnt_b - cnt_a + SUM}{2})\times(cnt_b + \frac{cnt_a - cnt_b + SUM}{2}) = (\frac{cnt_a + cnt_b + SUM}{2})^2 F=(cnta​+A)(cntb​+B)=(cnta​+2cntb​−cnta​+SUM​)×(cntb​+2cnta​−cntb​+SUM​)=(2cnta​+cntb​+SUM​)2 那么对于每个点可以计算其贡献值，如果贡献值小于已知答案，那么终止搜索；如果贡献值大于已知答案，则继续搜索。

#include 
#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  ans) dfs(x + 1, y, cnta + a[x + 1][y], cntb + b[x + 1][y]);
    if(y  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  a[i][j];
        for(int i = 1; i  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  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