找装修公司去哪个网站,外贸网站建设公司平台,免费空间访问,网络培训学校排名2020/8/21 晚上打完球就22:10了#xff0c;愣是没报上名#xff08;cf打不开#xff0c;然后就做了一下赛后交的过了3个题
A - Distance and Axis
数学题分类讨论一下即可
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#inclu…2020/8/21 晚上打完球就22:10了愣是没报上名cf打不开然后就做了一下赛后交的过了3个题
A - Distance and Axis
数学题分类讨论一下即可
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
int n,k;
int main()
{IO;int T;cinT;while(T--){cinnk;int res0;if(kn){resk-n;}else{if(k%2!n%2) res;}coutresendl;}return 0;
}B - Ternary Sequence
贪心先让第一个序列的2找第二个序列的1配对加分 然后看看第一个序列的1先找第二个序列的0和1配对分数不变最后找第二个序列2配对减分
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef pairint,int pii;
ll x,y,z;
ll a,b,c;
int main()
{IO;int T;cinT;while(T--){cinxyz;cinabc;ll res0;res2*min(z,b);y-a;y-b-min(z,b);if(y0) res-2*y;coutresendl;}return 0;
}C - Mere Array
这题是个脑筋急转弯。首先先找到数组中最小的数mina如果想要交换两个数那么两个数的最大公因数必须是mina然后可以先把原数组排序不妨记作数组b[]如果a[i]!b[i]说明原数组中该位置的值需要交换位置那么这个数必须是mina的倍数并且只要是这个数的倍数就一定能交换我们可以考虑让它和mina所在位置交换。因此只要位置不正确的数全都是mina的倍数就可以满足题意。
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N200010;
int a[N],b[N];
int n;
int main()
{IO;int T;cinT;while(T--){cinn;int mina1e91;for(int i1;in;i) {cina[i];b[i]a[i];minamin(mina,a[i]);}sort(b1,b1n);bool ok1;for(int i1;in;i)if(a[i]!b[i]a[i]%mina!0) {ok0;break;}if(ok) coutYESendl;else coutNOendl;}return 0;
}D - Maximum Distributed Tree
贪心可以考虑统计每条边通过的次数然后通过次数多的分配边权最大。 如何统计每条边通过次数 考虑树中的一条边如果将该边去掉将会分成两部分可以统计该两部分的点的数量该边的通过次数即两部分相乘一部分点数为sz那么另一部分即为n-sz那么该边通过次数即sz*(n-sz)。跑一个dfs即可统计出来。 目前有n-1条边待分配边权有m个边权值如果mn-1把前几个大数乘起来保证所有边权乘起来等于k分配给经过边数最多的那条边。如果mn-1那么就一个边一个数贪心经过次数多的边权重大。如果mn-1最后几条边权重是1。 之前没考虑mn-1这种情况wwwsTO
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includevector
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int mod1e97;
const int N100010,M2*N;
int n,m;
int h[N],e[M],ne[M],idx;
vectorllw;
ll sz[N],p[N];
void add(int a,int b)
{e[idx]b;ne[idx]h[a];h[a]idx;
}
void dfs(int u,int fa)
{sz[u]1;for(int ih[u];i!-1;ine[i]){int je[i];if(jfa) continue;dfs(j,u);sz[u]sz[j];w.push_back(1ll*sz[j]*(n-sz[j]));}
}
void init(int n)
{for(int i0;in;i) h[i]-1;w.clear();idx0;
}
int main()
{IO;int T;cinT;while(T--){cinn;init(n);for(int i1;in;i){int a,b;cinab;add(a,b);add(b,a);}cinm;for(int i0;im;i) cinp[i];sort(p,pm);reverse(p,pm);dfs(1,-1);sort(w.begin(),w.end());reverse(w.begin(),w.end());ll res0;if(mw.size()){for(int i0;im;i) res(res1ll*(w[i]%mod*p[i]%mod))%mod;for(int im;iw.size();i) res(resw[i])%mod;}else{int km-w.size();resw[0]%mod;for(int i0;ik;i) resres*p[i]%mod;for(int ik1;im;i) res(resw[i-k]%mod*p[i]%mod)%mod;}coutresendl;}return 0;
}F-Reverse and Swap
F题Reverse and Swap 留个坑回来补这题数据结构 2020/8/23补 方法一 首先这题单点修改区间查询无疑线段树可以做。 考虑如何进行区间交换 由于数组线段树固定做儿子和右儿子的下标父节点 u 左孩子u1 右孩子u1|1传统方式不宜进行区间交换因此采用指针方式记录左右孩子主席树方式那么区间交换直接交换左右孩子即可而区间反转则是递归交换左右子树直到叶子节点。 尝试用懒标极维护区间操作lazy看成一个二进制数状态压缩对于一个节点如果lazy^id!0说明id中的1所在的位置lazy中也是1那么表示需要该节点的左右子树。 于是区间反转则是在根节点直接打上标记tree[root].lazy^(1(k1))-1; 区间交换则tree[root].lazy^1(k1); 参考大佬题解
// [1 2 3 4 5 6 7 8] 1000 id:3
// [1 2 3 4] [5 6 7 8] 0100 id:2
// [1 2] [3 4] [5 6] [7 8] 0010 id:1
// [1][2][3][4][5][6][7][8] 0001 id:0
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includevector
#includeset
#includemap
#includestring
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N(118)10;
int n,q;
ll a[N];
struct node
{int l,r;ll s;int id,lazy;
}tree[40*N];
int cnt,root;
void pushup(int u)
{tree[u].stree[tree[u].l].stree[tree[u].r].s;
}
void pushdown(int u)
{if(tree[u].idtree[u].lazy){swap(tree[u].l,tree[u].r);tree[u].lazy^tree[u].id;}tree[tree[u].l].lazy^tree[u].lazy;tree[tree[u].r].lazy^tree[u].lazy;tree[u].lazy0;}
void build(int u,int l,int r)
{ucnt;tree[u].idr-l1;tree[u].lazy0;if(lr){tree[u].sa[l];return;}int midlr1;build(tree[u].l,l,mid);build(tree[u].r,mid1,r);pushup(u);
}
void modify(int u,int l,int r,int pos,int x)
{if(lr){tree[u].sx;return;}pushdown(u);int midlr1;if(posmid) modify(tree[u].l,l,mid,pos,x);else modify(tree[u].r,mid1,r,pos,x);pushup(u);
}
ll query(int u,int l,int r,int vl,int vr)
{if(vllrvr) return tree[u].s;pushdown(u);int midlr1;ll v0;if(vlmid) vquery(tree[u].l,l,mid,vl,vr);if(vrmid) vquery(tree[u].r,mid1,r,vl,vr);pushup(u);return v;
}
void rev(int k)
{tree[root].lazy^(1(k1))-1;if(tree[root].idtree[root].lazy){swap(tree[root].l,tree[root].r);tree[root].lazy^tree[root].id;}
}
void swp(int k)
{tree[root].lazy^1(k1);if(tree[root].idtree[root].lazy){swap(tree[root].l,tree[root].r);tree[root].lazy^tree[root].id;}
}
int main()
{IO;cinnq;for(int i1;i1n;i) cina[i];build(root,1,1n);while(q--){int op,x,y;cinop;if(op1){cinxy;modify(root,1,1n,x,y);}else if(op2){cinx;rev(x);}else if(op3){cinx;swp(x);}else {cinxy;coutquery(root,1,1n,x,y)endl;}}return 0;
}看standing发现了一个神奇的做法自己写一下 方法二 把线段树看成一层一层的可以发现反转和交换操作都是在同层进行因此可以以层数记录lazy方法一是用swap操作实现reverse操作同样其实也可以用reverse操作实现swap可以先把上一层每个区间进行reverse然后把该层的每个区间再reverse实际上实现的就是swap操作。 之前说过传统线段树不宜进行区间反转等操作这个方法秒在不进行区间反转操作只记录每层的区间是否需要进行反转仅仅在查询和更改时候进行相应的坐标变化即可。
// [1 2 3 4 5 6 7 8] level:3
// [1 2 3 4] [5 6 7 8] level:2
// [1 2] [3 4] [5 6] [7 8] level:1
// [1][2][3][4][5][6][7][8] level:0
// 区间交换 level2 只需要先反转level3 然后再反转level2即可
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#pragma GCC optimize(2)
#includevector
#includeset
#includemap
#includestring
#includecstring
#includeiostream
#includealgorithm
using namespace std;
typedef long long ll;
typedef pairint,int pii;
const int N(118)10;
int n,q;
int b[20];
ll a[N];
struct node
{int l,r,level;ll val;
}tree[4*N];
void pushup(int u)
{tree[u].valtree[u1].valtree[u1|1].val;
}
void build(int u,int l,int r,int level)
{tree[u]{l,r,level};if(lr){tree[u].vala[l];return;}int midlr1;build(u1,l,mid,level-1);build(u1|1,mid1,r,level-1);pushup(u);
}
void modify(int u,int pos,int x)
{if(tree[u].ltree[u].r){tree[u].valx;return;}if(b[tree[u].level]) postree[u].r-(pos-tree[u].l);int midtree[u].ltree[u].r1;if(posmid) modify(u1,pos,x);else modify(u1|1,pos,x);pushup(u);
}
ll query(int u,int l,int r)
{if(tree[u].llrtree[u].r) return tree[u].val;int lnowl,rnowr;if(b[tree[u].level]){lnowtree[u].r-(r-tree[u].l);rnowtree[u].r-(l-tree[u].l);}ll v0;int midtree[u].ltree[u].r1;if(rnowmid) vquery(u1,lnow,rnow);else if(lnowmid) vquery(u1|1,lnow,rnow);else{vquery(u1,lnow,mid);vquery(u1|1,mid1,rnow);}return v;
}
int main()
{cinnq;for(int i1;i1n;i) cina[i];build(1,1,1n,n);while(q--){int op,x,y;cinop;if(op1){cinxy;modify(1,x,y);}else if(op2){cinx;b[x]^1;}else if(op3){cinx;b[x]^1;b[x1]^1;}else {cinxy;coutquery(1,x,y)endl;}}return 0;
}
要加油哦~
