题意
给你
n
n
n条直线,现在需要
A
l
i
c
e
Alice
Alice需要从中选出
k
k
k条直线,之后
B
o
b
Bob
Bob生成一条直线
l
l
l,其中贡献为这
k
k
k条直线与
l
l
l相交的数量,而
A
l
i
c
e
Alice
Alice想最大化贡献,
B
o
b
Bob
Bob想最小化贡献,求
k
k
k为
[
1
,
n
]
[1,n]
[1,n]时的贡献。
解题思路
我们知道,两条直线存在公共点当且仅当它们重合或者它们斜率不同。对于
A
l
i
c
e
Alice
Alice自然是尽可能最小化斜率出现次数的最大值,而
B
o
b
Bob
Bob自然是选择其中斜率出现次数最多的最大值。故我们可以将斜率存储起来,然后每种直线依次选择即可。
AC代码
/** *@filename:D_Game_on_Plane *@author: pursuit *@csdn:unique_pursuit *@email: 2825841950@qq.com *@created: 2021-07-31 09:14 **/ #include <bits/stdc++.h> #define x first #define y second using namespace std; typedef pair<int,int> pii; typedef long long ll; const int N = 100000 + 5; const int P = 1e9+7; int t,n; int f[N]; pii v[N]; void solve(){ sort(v + 1,v + 1 + n); memset(f,0,sizeof(f)); int i,j,k; for(i = 1; i <= n; i = j){ for(j = i; j <= n && v[i] == v[j]; ++ j){ //计算从i开始有几条斜率相同的直线。 } for(k = 1; k <= j - i; ++ k){ f[k] ++; } } for(i = j = 1; i <= n; ++ i){ //i为可选择的直线数。 while(!f[j]){ j ++; } f[j] --; printf("%d\n", i - j); } } int main(){ scanf("%d", &t); pii a,b; while(t -- ){ scanf("%d", &n); for(int i = 1; i <= n; ++ i){ scanf("%d%d%d%d", &a.x, &a.y, &b.x, &b.y); int dx = a.x - b.x,dy = a.y - b.y; if(dx == 0){ //说明是垂直的。 dy = 1; } else if(dy == 0){ //说明是水平的。 dx = 1; } else{ //将dx,dy统一化。 if(dx < 0){ dx = -dx, dy = -dy; } int gcd = __gcd(abs(dx),abs(dy)); dx /= gcd, dy /= gcd; } v[i] = pii(dx,dy); } solve(); } return 0; }
题意
给你
n
n
n张图层,每张图层都有
r
,
g
,
b
r,g,b
r,g,b三种颜色属性还有一个特征
m
m
m,即为
1
1
1说明不受前面图层影响,为
2
2
2说明受前面图层影响。问
[
l
,
r
]
[l,r]
[l,r]这区间的图层依次放置后最后的
r
,
g
,
b
r,g,b
r,g,b值。
解题思路
妥妥的前缀和,只不过我们需要注意分割点,记录每个图层最近出现
1
1
1的图层下标。然后利用前缀和计算即可。
AC代码
/** *@filename:G_Photoshop_Layers *@author: pursuit *@csdn:unique_pursuit *@email: 2825841950@qq.com *@created: 2021-07-27 13:43 **/ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100000 + 5; const int P = 1e9+7; int t,n,q,x,f[N]; struct node{ int m,r,g,b; }a[N]; int change(int x){ return x < 255 ? x : 255; } void solve(){ int l,r; while(q -- ){ scanf("%d%d", &l, &r); int x = f[r]; if(x >= l){ //说明中间出现1,中断了。 l = x; } printf("%02X%02X%02X\n", change(a[r].r - a[l - 1].r), change(a[r].g - a[l - 1].g), change(a[r].b - a[l - 1].b)); } } int main(){ scanf("%d", &t); while(t -- ){ scanf("%d%d", &n, &q); for(int i = 1; i <= n; ++ i){ scanf("%d%X", &a[i].m, &x); a[i].b = x & 255; x >>= 8; a[i].g = x & 255; x >>= 8; a[i].r = x & 255; a[i].b += a[i - 1].b, a[i].g += a[i - 1].g, a[i].r += a[i - 1].r; if(a[i].m == 1){ f[i] = i; } else{ f[i] = f[i - 1]; } } solve(); } return 0; }
题意
有
n
×
n
n\times n
n×n的网格地图,起始点在
(
1
,
1
)
(1,1)
(1,1),终止点在
(
n
,
n
)
(n,n)
(n,n),其中只能向东或南方向移动,每个
(
i
,
j
)
(i,j)
(i,j)都有两个个值
a
i
,
b
i
a_i,b_i
ai,bi,分别代表钻石数量和可上升的单价,问最终到达终止点可售卖得到的最大价值。
解题思路
这是最经典的
D
P
DP
DP问题,只不过现在每个点有两个参数影响,所以一个状态可以有好多候选解,我们可以用
v
e
c
t
o
r
vector
vector存储候选解,当然我们也要剔除不可能的解,即一个解两个参数值都小于等于另一个解,那这个是不可能的。按题意进行状态转移即可。
AC代码
/** *@filename:I Rise in Price *@author: pursuit *@csdn:unique_pursuit *@email: 2825841950@qq.com *@created: 2021-07-27 12:08 **/ #include <bits/stdc++.h> #define a first #define b second using namespace std; typedef pair<int,int> pii; typedef long long ll; const int N = 100 + 5; const int P = 1e9+7; int t,n,a[N][N],b[N][N]; int cnt;//(i,j)可选状态的大小。 vector<pii> f[N][N];//f[i][j]表示(i,j)的可选状态。 pii pool[N * 10000];//可选状态池。 void push(pii x){ while(cnt && pool[cnt].b <= x.b){ cnt --; } pool[++ cnt] = x;//加入新的数。 } void judge(int x,int y){ int i = 0, j = 0; cnt = 0; //这里我们默认让a小的先进入pool。然后比较第二维的,若先前进入pool的b也比别的状态小,那就剔除掉。 while(i < f[x - 1][y].size() && j < f[x][y - 1].size()){ push(f[x - 1][y][i].a < f[x][y - 1][j].a ? f[x - 1][y][i ++ ] : f[x][y - 1][j ++ ]); } while(i < f[x - 1][y].size())push(f[x - 1][y][i ++]); while(j < f[x][y - 1].size())push(f[x][y - 1][j ++]); f[x][y].clear(); //cout << "judge : " << endl; for(i = 1; i <= cnt; ++ i){ f[x][y].push_back(pool[i]); //cout << pool[i].a << " " << pool[i].b << endl; } } void solve(){ f[1][1].clear(); f[1][1].push_back({a[1][1],b[1][1]}); for(int i = 1; i <= n; ++ i){ for(int j = 1; j <= n; ++ j){ if(i == j && i == 1)continue; if(i == 1){ //说明只能水平转移。 f[i][j] = f[i][j - 1]; } else if(j == 1){ //说明只能垂直转移。 f[i][j] = f[i - 1][j]; } else{ //计算可选状态。 judge(i,j); } for(int k = 0; k < f[i][j].size(); ++ k){ f[i][j][k].a += a[i][j],f[i][j][k].b += b[i][j]; } } } ll maxx = 0; for(int i = 0; i < f[n][n].size(); ++ i){ maxx = max(maxx,1LL * f[n][n][i].a * f[n][n][i].b); //cout << maxx << endl; } printf("%lld\n", maxx); } int main(){ scanf("%d", &t); while(t -- ){ scanf("%d", &n); for(int i = 1; i <= n; ++ i){ for(int j = 1; j <= n; ++ j){ scanf("%d", &a[i][j]); } } for(int i = 1; i <= n; ++ i){ for(int j = 1; j <= n; ++ j){ scanf("%d", &b[i][j]); } } solve(); } return 0; }
题意
给你
n
n
n个顶点,
m
m
m条边的图,其中边权值有原价和折扣价。问当只能使用
k
k
k条折扣价边的最小生成树权重。
解题思路
假定原边是白边,折扣边是黑边,那么对于每次要输出的,问题就转换成了选
k
k
k条黑边的最小生成树的代价是多少。我们可以先将只用白边和只用黑边的最小生成树所用边给求出来,其他的边都是多余的,然后我们对黑边附上值使得我们能够让黑边和白边组合排序,再跑一下最小生成树求黑边使用数量以及最小权重。最后二分得到满足条件的解即可。
AC代码
/** *@filename:J_Road_DIscount *@author: pursuit *@created: 2021-07-27 13:20 **/ #include <bits/stdc++.h> #define debug(a) cout << (#a)<< ":" << a << endl; using namespace std; typedef pair<int,int> pii; typedef long long ll; const int N = 200000 + 5; const int P = 1e9+7; int t,n,m; int father[1010 * 2 + 10]; struct node{ int u,v,w; int tag;//0表示正常价,1表示折扣价。 bool operator < (const node &A){ return w < A.w; } }edges[N],edges1[N],edges2[N]; pii f[N];//第一维表示适用黑边的次数,第二维表示最小代价。 int find(int x){ int r = x; while(r != father[r])r = father[r]; int i = x,j; while(father[i] != r){ j = father[i]; father[i] = r; i = j; } return r; } void work(node *edges){ for(int i = 1; i <= n; ++ i)father[i] = i; int tot = 0; for(int i = 1; i <= m; ++ i){ int fu = find(edges[i].u),fv = find(edges[i].v); if(fu != fv){ father[fu] = fv; edges[++ tot] = edges[i]; } } } pii cal(int x){ int cnt = 0,ans = 0,tot = 0; for(int i = 1; i <= m; ++ i){ edges2[i].w += x; } edges1[m + 1].w = edges2[m + 1].w = 1e8; for(int i = 1; i <= n; ++ i)father[i] = i; for(int i = 1, j = 1; i <= m || j <= m;){ if(edges1[i].w < edges2[j].w){ edges[++ tot] = edges1[i ++]; } else{ edges[++ tot] = edges2[j ++]; } } for(int i = 1; i <= tot; ++ i){ int fu = find(edges[i].u),fv = find(edges[i].v); if(fu != fv){ father[fu] = fv; cnt += edges[i].tag; ans += edges[i].w; } } for(int i = 1; i <= m; ++ i){ edges2[i].w -= x; } return {cnt,ans}; } void solve(){ sort(edges1 + 1,edges1 + 1 + m); sort(edges2 + 1, edges2 + 1 + m); work(edges1),work(edges2); //处理完之后提取出我们要的n - 1条边。 m = n - 1; //让黑边加上一个值。 for(int i = -1010; i <= 1010; ++ i){ f[1010 + i] = cal(i); } for(int k = 0; k < n; ++ k){ int l = -1010, r = 1010,res,mid; while(l <= r){ mid = l + r >> 1; if(f[mid + 1010].first >= k){ //说明使用黑边数量多 res = f[mid + 1010].second - mid * k; l = mid + 1; } else{ r = mid - 1; } } printf("%d\n", res); } } int main(){ scanf("%d", &t); while(t -- ){ scanf("%d%d", &n, &m); for(int i = 1; i <= m; ++ i){ scanf("%d%d%d%d", &edges1[i].u, &edges1[i].v, &edges1[i].w, &edges2[i].w); edges2[i].u = edges1[i].u,edges2[i].v = edges1[i].v; edges1[i].tag = 0,edges2[i].tag = 1; } solve(); } return 0; }
题意
给你一个建树函数,求生成的结点数。
解题思路
记忆化递推求解。这样只要跑
l
o
g
n
logn
logn即可。
AC代码
/** *@filename:K_Segment_Tree_with_Pruning *@author: pursuit *@csdn:unique_pursuit *@email: 2825841950@qq.com *@created: 2021-07-27 12:27 **/ #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 100000 + 5; const int P = 1e9+7; int t; ll k,n; unordered_map<ll,ll> p; ll build(ll n){ if(p.find(n) != p.end())return p[n]; if(n <= k)return p[n] = 1; return p[n] = build(n / 2) + build(n - n / 2) + 1; } void solve(){ p.clear(); cout << build(n) << endl; } int main(){ cin >> t; while(t -- ){ cin >> n >> k; solve(); } return 0; }