陕西网站建设的目的,外贸大型门户网站制作,开发微信公众平台,建网站公司销售A题考虑贪心#xff0c;要使使用的砖头越多#xff0c;每块转的k应尽可能小#xff0c;最小取2#xff0c;最后可能多出来#xff0c;多出来的就是最后一块k3#xff0c;我们一行内用到的砖头就是 m 2 \frac{m}{2} 2m下取整#xff0c;然后乘以行数就是答案。
#inclu…A题考虑贪心要使使用的砖头越多每块转的k应尽可能小最小取2最后可能多出来多出来的就是最后一块k3我们一行内用到的砖头就是 m 2 \frac{m}{2} 2m下取整然后乘以行数就是答案。
#include bits/stdc.h
#define rep(i,a,b) for(int i (a); i (b); i)
#define fep(i,a,b) for(int i (a); i (b); --i)
#define ls p1
#define rs p1|1
#define PII pairint, int
#define ll long long
#define ull unsigned long long
#define db double
#define endl \n
#define debug(a) cout#aaendl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define x first
#define y second
#define int long long
using namespace std;const int N2e510;
vectorints[N];
int u[N],ans[N];void solve()
{int n,m;cinnm;coutm/2*nendl;
}
signed main()
{IOS
// freopen(1.in, r, stdin);int t;cint;while(t--)solve();return 0;
}B题就是猜的一个排序 对于 i , a [ i ] b [ i ] 越大我们就考虑将他往后放 , 有一点贪心的思想吧如果 a [ i ] b [ i ] 越大放在前面产生的逆序对可能就越多所以我们考虑将大的往后放 对于i,a[i]b[i]越大我们就考虑将他往后放,有一点贪心的思想吧如果a[i]b[i]越大放在前面产生的逆序对可能就越多所以我们考虑将大的往后放 对于i,a[i]b[i]越大我们就考虑将他往后放,有一点贪心的思想吧如果a[i]b[i]越大放在前面产生的逆序对可能就越多所以我们考虑将大的往后放 b题wa了两发第一次是排序的时候弄反了。 第二次写排序函数的时候降序就写 不要写 写了 r e 了 不要写写了 re了 不要写写了re了
#include bits/stdc.h
#define rep(i,a,b) for(int i (a); i (b); i)
#define fep(i,a,b) for(int i (a); i (b); --i)
#define ls p1
#define rs p1|1
#define PII pairint, int
#define ll long long
#define ull unsigned long long
#define db double
#define endl \n
#define debug(a) cout#aaendl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define x first
#define y second
//#define int long long
using namespace std;const int N2e510;
struct node
{int a,b,sum;
}kk[N];
bool cmp(node t1,node t2)
{return t1.sumt2.sum;
}
void solve()
{int n;cinn;rep(i,1,n) cinkk[i].a;rep(i,1,n) cinkk[i].b;rep(i,1,n) kk[i].sumkk[i].akk[i].b;sort(kk1,kk1n,cmp);rep(i,1,n) coutkk[i].a ;coutendl;rep(i,1,n) coutkk[i].b ;coutendl;}
signed main()
{IOS
// freopen(1.in, r, stdin);int t;cint;while(t--)solve();return 0;
}c题是位运算贪心 一般1e18很可能就是 l o g log log的算法涉及到异或这些很可能就是要考虑每一位的影响。 这道题就是需要考虑每一位对答案的贡献这种贡献法也是很常用的思考方式。 赛时有框架了但是贪心的细节没考虑好没过。 大佬指导的是位运算很多时候需要考虑贪心因为位与位之间独立。 我们考虑如果ab两个数的二进制下第i位 当 a i b i 时无论 x 取何值这一位对答案的贡献都是 0 , 我们就然 x 的这一位为 0 因为 x 要小于 r x 后面会有用 当a_ib_i时无论x取何值这一位对答案的贡献都是0,我们就然x的这一位为0因为x要小于rx后面会有用 当aibi时无论x取何值这一位对答案的贡献都是0,我们就然x的这一位为0因为x要小于rx后面会有用 当 a i ̸ b i 时这时看 x i 1 是否能然答案变小如果可以就让 x i 1 否则就然 x i 0 当a_i\notb_i时这时看x_i1是否能然答案变小如果可以就让x_i1否则就然x_i0 当aibi时这时看xi1是否能然答案变小如果可以就让xi1否则就然xi0 x i 1 需要建立在 x r 的前提下 x_i1需要建立在xr的前提下 xi1需要建立在xr的前提下
#include bits/stdc.h
#define rep(i,a,b) for(int i (a); i (b); i)
#define fep(i,a,b) for(int i (a); i (b); --i)
#define ls p1
#define rs p1|1
#define PII pairint, int
#define ll long long
#define ull unsigned long long
#define db double
#define endl \n
#define debug(a) cout#aaendl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define x first
#define y second
#define int long long
using namespace std;const int N64;int work(int x,int i)
{return x(1lli);
}void solve()
{int a,b,r;cinabr;if(ab) swap(a,b);int ans0;fep(i,60,0){if(work(a,i)work(b,i)) continue;if(r(1lli)) {int kkabs(ans(work(a,i)^(1lli))-(work(b,i)^(1lli)));if(kkabs(ans)) {anskk;r-(1lli); } else ans(work(a,i)^0)-(work(b,i)^0); }else ans(work(a,i)^0)-(work(b,i)^0); }coutabs(ans)endl;
}
signed main()
{IOS
// freopen(1.in, r, stdin);int t;cint;while(t--)solve();return 0;
}
D 二分大根堆优化dp 首先需要二分答案在b站的一个up看的讲解b站的up讲解 这种题目就是可以通过二分答案然后变成简单的check。 接下来需要考虑如何check由于我们删数的位置不确定同时我们需要求的是在满足一定条件下的最优化问题这时我们可以考虑一下dp f [ i ] 表示处理好的前 i 个前 i 个的区间间隔均 m i d f[i]表示处理好的前i个前i个的区间间隔均mid f[i]表示处理好的前i个前i个的区间间隔均mid 并且删除第 i 个元素所有删除元素的和的最小值 并且删除第i个元素所有删除元素的和的最小值 并且删除第i个元素所有删除元素的和的最小值 考虑转移 : f [ i ] f [ k ] a [ i ] , 其中 k 是满足区间和小于 m i d 的 f 中的最小值 考虑转移:f[i]f[k]a[i],其中k是满足区间和小于mid的f中的最小值 考虑转移:f[i]f[k]a[i],其中k是满足区间和小于mid的f中的最小值 我们可以看到枚举状态 O ( n ) 枚举转移也需要 O ( n ) , 这样复杂度就是 O ( n 2 l o g n ) 我们可以看到枚举状态O(n)枚举转移也需要O(n),这样复杂度就是O(n^2logn) 我们可以看到枚举状态O(n)枚举转移也需要O(n),这样复杂度就是O(n2logn) 考虑优化可以用优先队列维护和双指针维护满足条件的区间以及区间内的 f 的最小值 考虑优化可以用优先队列维护和双指针维护满足条件的区间以及区间内的f的最小值 考虑优化可以用优先队列维护和双指针维护满足条件的区间以及区间内的f的最小值 由于状态的设计所以状态需要计算到 n 1 , 因为 n 有删或不删两种情况这是一个常用的小技巧 由于状态的设计所以状态需要计算到n1,因为n有删或不删两种情况这是一个常用的小技巧 由于状态的设计所以状态需要计算到n1,因为n有删或不删两种情况这是一个常用的小技巧
#include bits/stdc.h
#define int long long
#define rep(i,a,b) for(int i (a); i (b); i)
#define fep(i,a,b) for(int i (a); i (b); --i)
#define ls p1
#define rs p1|1
#define PII pairint, int
#define pll pairlong long, long long
#define ll long long
#define ull unsigned long long
#define db double
#define endl \n
#define debug(a) cout#aaendl;
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 0x3f3f3f3f
#define x first
#define y secondusing namespace std;const int N1e510;
int n,a[N],f[N];bool check(int x)
{priority_queuepll,vectorpll,greaterpllq;int l0,ss0;q.push({0,0});rep(i,1,n1){while(lissx) {ss-a[l];l;}while(q.size()q.top().yl-1) q.pop();f[i]q.top().xa[i];q.push({f[i],i});ssa[i]; }return f[n1]x;
}void solve()
{cinn;rep(i,1,n) cina[i];a[n1]0;int l0,r1e15;while(lr){int mid(lr)1;if(check(mid)) rmid;else lmid1;}coutlendl;rep(i,0,n1) f[i]0;
}
signed main()
{IOS
// freopen(1.in, r, stdin);int t;cint;while(t--)solve();return 0;
}
