[考试总结]noip模拟34
2021/8/10 6:35:37
本文主要是介绍[考试总结]noip模拟34,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
实际上简单的题目并不能被题目所吓到,仔细分析实际上难度并不是很高。
如果存在显然的部分分数,其实特盘一下也比较好,有可能你的程序就卡在这个地方。。
这次暴力打的不是很挂,\(T1\) 也还是差一个 \(nth\)_\(element\) ,二分答案的思路显然,但是要有两个 \(log_2\)
\(T2\) 没有进行仔细的分析,实际上手动推导发现可以推导成为一个形式,并且与深度的奇偶性有关。
\(T3\) 这个属实大神题,需要使用常熟优秀的树状数组。
Merchant
我们首先进行二分答案,二分时间,然后进行统计 \(check\),但是发现如果在 \(check\)中使用 \(sort\),就会 \(TLE\) 成 \(78pts\) ,因为这时的复杂度是 \(nlog^2\) 。
然后我们其实可以发现,我们并不需要让他有序,我们只需要将前 \(m\) 大小的提到一边。
这时 \(nth_element\) 的作用就体现出来了,之后我们就可以 \(\mathcal O(n)\) 排除顺序,之后加和比较。
#include<bits/stdc++.h> using std::cout; using std::endl; #define try(i,a,b) for(register signed i=a;i<=b;++i) #define throw(i,a,b) for(register signed i=a;i>=b;--i) #define asm(i,x) for(register signed i=head[x];i;i=edge[i].next) namespace xin_io { #define debug cout<<"debug"<<endl #define enum(x) cout<<#x" = "<<x<<endl; #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++ char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull; class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x) { register type s = 0; register int f = 1; register char ch = gc(); while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();} while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return x = s * f,*this; }}io; } #define int long long using namespace xin_io; static const int maxn = 2e6+10,inf = 1e9+7,mod = 998244353; const ll llinf = 1e18+7; namespace xin { class xin_data { public: int k,b; xin_data(){} xin_data(int k,int b):k(k),b(b){} inline int val(int t) {return k * t + b;} }d[maxn]; int n,m,s,temp; int a[maxn]; inline bool comp(int x,int y) {return x > y;} inline bool check(int x) { try(i,1,n) a[i] = d[i].val(x); std::nth_element(a+1,a+(n-m),a+n+1); s = temp; throw(i,n,n-m+1) { if(a[i] < 0) continue; s -= a[i]; if(s <= 0) return true; } return false; } inline short main() { io >> n >> m >> s; temp = s; try(i,1,n) io >> d[i].k >> d[i].b; register int l = 0,r = inf,mid; if(check(0)) {cout<<0<<endl; return 0;} while(l != r - 1 and l < r) { mid = l + r >> 1; if(check(mid)) r = mid; else l = mid; } if(check(l)) cout<<l<<endl; else if(check(mid)) cout<<mid<<endl; else cout<<r<<endl; // cout<<sizeof(a) / (1 << 20)<<" MB"<<endl; return 0; } } signed main() {return xin::main();}
Equation
我们进行推导,发现每一个式子都可以推成
\[x_1=k+x_u \]或者
\[x_1=k-x_u \]这个符号取决与深度的奇偶性。
然后我们强制使树的边权正负交错,也就是 \(sum_y=w_y-sum_x\)
然后对于 \(2\) 操作,在线段树上维护即可。
#include<bits/stdc++.h> using std::cout; using std::endl; #define try(i,a,b) for(register signed i=a;i<=b;++i) #define throw(i,a,b) for(register signed i=a;i>=b;--i) #define asm(i,x) for(register signed i=head[x];i;i=edge[i].next) namespace xin_io { #define debug cout<<"debug"<<endl #define enum(x) cout<<#x" = "<<x<<endl; #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++ char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull; class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x) { register type s = 0; register int f = 1; register char ch = gc(); while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();} while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return x = s * f,*this; }}io; } using namespace xin_io; static const int maxn = 1e6+10,inf = 1e9+7,mod = 998244353; const ll llinf = 1e18+7; #define int long long namespace xin { class xin_edge{public:int w,next,ver;}edge[maxn]; int head[maxn],zhi = 0; inline void add(int x,int y,int z) {edge[++zhi].ver = y; edge[zhi].w = z; edge[zhi].next = head[x]; head[x] = zhi;} class xin_seg { private: #define ls(fa) (fa << 1) #define rs(fa) (fa << 1 | 1) inline void up(int fa) {t[fa].s = t[ls(fa)].s + t[rs(fa)].s;} inline void down(int fa,int l,int r) { if(!t[fa].debt) return ; register int mid = l + r >> 1; t[ls(fa)].s += t[fa].debt * (mid - l + 1); t[rs(fa)].s += t[fa].debt * (r - mid); t[ls(fa)].debt += t[fa].debt; t[rs(fa)].debt += t[fa].debt; t[fa].debt = 0; } public: class xin_tree{public:int s,debt;}t[maxn * 4]; void update(int fa,int l,int r,int ql,int qr,int val) { if(ql <= l and qr >= r) return t[fa].s += (r - l + 1) * val,t[fa].debt += val,void(); register int mid = l + r >> 1; down(fa,l,r); if(ql <= mid) update(ls(fa),l,mid,ql,qr,val); if(qr > mid) update(rs(fa),mid+1,r,ql,qr,val); up(fa); } int query(int fa,int l,int r,int pos) { if(l == r) return t[fa].s; register int mid = l + r >> 1,ret = 0; down(fa,l,r); if(pos <= mid) ret += query(ls(fa),l,mid,pos); else ret += query(rs(fa),mid+1,r,pos); return ret; } }t; int n,qnum,fa[maxn]; int in[maxn],out[maxn],tot = 0,d[maxn],sum[maxn],w[maxn]; void xt(int x) { in[x] = ++tot; d[x] = d[fa[x]] + 1; asm(i,x) { register int y = edge[i].ver; sum[y] = w[y] - sum[x]; xt(y); } out[x] = tot; } inline short main() { io >> n >> qnum; try(i,2,n) { io >> fa[i] >> w[i]; add(fa[i],i,w[i]); } xt(1); try(i,1,qnum) { register int op; io >> op; if(op & 1) { register int x,y,z; io >> x >> y >> z; register int p1 = t.query(1,1,n,in[x]),p2 = t.query(1,1,n,in[y]); if(!(d[x] & 1)) p1 = -p1; if(!(d[y] & 1)) p2 = -p2; register int ret1 = sum[x] + p1,ret2 = sum[y] + p2; if((d[x] & 1) and (d[y] & 1)) { if((z - ret1 - ret2) & 1) puts("none"); else printf("%lld\n",(z - ret1 - ret2) >> 1); } else if(!(d[x] & 1) and !(d[y] & 1)) { if((ret1 + ret2 - z) & 1) puts("none"); else printf("%lld\n",(ret1 + ret2 - z) >> 1); } else { if(ret1 + ret2 == z) puts("inf"); else puts("none"); } } else { register int x,z; io >> x >> z; register int p = z - w[x]; w[x] = z; if(!(d[x] & 1)) p = -p; t.update(1,1,n,in[x],out[x],p); } } return 0; } } signed main() {return xin::main();}
Rectangle
首先第一思路就是拿四个线卡来卡去。
然后就是 \(n^4\)
可以拿二十多分。。
正解实际上是先拿两条线。
之后发现答案贡献与两条线之间的 \(y\) 有关,所以用树状数组来维护 \(\sum y\)
#include<bits/stdc++.h> using std::cout; using std::endl; #define try(i,a,b) for(register signed i=a;i<=b;++i) #define throw(i,a,b) for(register signed i=a;i>=b;--i) #define asm(i,x) for(register signed i=head[x];i;i=edge[i].next) namespace xin_io { #define debug cout<<"debug"<<endl #define enum(x) cout<<#x" = "<<x<<endl; #define gc() p1 == p2 and (p2 = (p1 = buf) + fread(buf,1,1<<20,stdin),p1 == p2) ? EOF : *p1++ char buf[1<<20],*p1 = buf,*p2 = buf; int ak; typedef long long ll; typedef unsigned long long ull; class xin_stream{public:template<typename type>inline xin_stream &operator >> (type &x) { register type s = 0; register int f = 1; register char ch = gc(); while(!isdigit(ch)) {if(ch == '-') f = -1; ch = gc();} while( isdigit(ch)) s = (s << 1) + (s << 3) + (ch xor 48),ch = gc(); return x = s * f,*this; }}io; } using namespace xin_io; static const int maxn = 2500+10,inf = 1e9+7,mod = 1e9+7; const ll llinf = 1e18+7; namespace xin { #define int long long int n; class xin_bit { private: #define lowbit(x) (x & -x) public: int c[2][maxn][maxn]; inline void plus(int id,int k,int x,int val) { for(int i=x;i<=2500;i+=lowbit(i)) c[id][k][i] += val; } inline int query(int id,int k,int x) { register int ret = 0; for(int i=x;i;i-=lowbit(i)) ret += c[id][k][i]; return ret; } }bit; int a[maxn][maxn],ans; bool vis[maxn][maxn]; inline short main() { io >> n; try(i,1,n) { register int x,y; io >> x >> y; a[x][++a[x][0]] = y; } try(i,1,2500) { std::sort(a[i]+1,a[i]+a[i][0]+1); a[i][a[i][0]+1] = 2501; } try(i,1,2500) { if(!a[i][0]) continue; try(j,1,a[i][0]) if(!vis[i][a[i][j]]) { vis[i][a[i][j]] = 1; bit.plus(1,i,a[i][j],1); bit.plus(0,i,a[i][j],a[i][j]); } throw(j,i-1,1) { if(!a[j][0]) continue; register int l1 = 1,l2 = 1; try(k,1,a[j][0]) if(!vis[i][a[j][k]]) { vis[i][a[j][k]] = 1; bit.plus(1,i,a[j][k],1); bit.plus(0,i,a[j][k],a[j][k]); } register int temp = std::max(a[i][1],a[j][1]); while(a[i][l1+1] <= temp) l1 ++; while(a[j][l2+1]<=temp) l2 ++; while(l1 <= a[i][0] and l2 <= a[j][0]) { register int zhuan = std::min(a[i][l1+1],a[j][l2+1]); int ret1 = (bit.query(0,i,zhuan-1)-bit.query(0,i,temp-1)); int ret2 = (bit.query(1,i,zhuan-1)-bit.query(1,i,temp-1)); //enum(ret1); enum(ret2); ans=(ans+(i-j)*(ret1*bit.query(1,i,std::min(a[i][l1],a[j][l2]))-(ret2*bit.query(0,i,std::min(a[i][l1],a[j][l2])))))%mod; temp = zhuan; if(a[i][l1+1] <= temp) l1 ++; if(a[j][l2+1] <= temp) l2 ++; } } } cout<<ans<<endl; return 0; } } signed main() {return xin::main();}
这篇关于[考试总结]noip模拟34的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)