一家专门做瓷砖特卖的网站,河北建筑工程信息网站,横峰县城乡建设网站,大连市建设网前言 节日快乐#xff01; (逃) day10 50pts 期望#xff1a;10302060 实际#xff1a;0302050 rnk11
彻彻底底的摆烂局了。 但是rnk竟然没有太掉#xff0c;所以我应该并不孤独… 和KH并排坐在机房里#xff0c;各自看着电脑#xff0c;痴痴想着各自的心事#xff0c;…前言 节日快乐 (逃) day10 50pts 期望10302060 实际0302050 rnk11
彻彻底底的摆烂局了。 但是rnk竟然没有太掉所以我应该并不孤独… 和KH并排坐在机房里各自看着电脑痴痴想着各自的心事一坐就是三个小时。 半小时三题了属于是 T1挂分是因为把题目描述的连线理解成了线段但实际上是直线。 我不太确定还和KH统一了一下意见 个人感觉这个题意是真的很模糊为什么不在比赛主页强调而要在钉钉啊谁比赛的时候还会看钉钉啊qwq 事实是我那个靠着毁天灭地的剪枝竟然能过30我也是惊了。
题目解析
圆与连线circle
挺妙的题目。 其实没有想像中那么难。 但完全没有往这边想过。 而且题意都混淆不清
考虑每个点落在圆上的两个切点其对应两个旋转角组成一个区间。两个点可以同时存在的充要条件是其对应的区间相交且不包含。 然后就变成了线段问题先按照左端点排序然后暴力枚举第一条线段把所有与它合法相交的线段提出来拿右端点直接做一个最长上升子序列就行了。 好久没写队列的最长上升子序列了竟然莫名其妙的有些怀念
转移石子rock
都叫它模拟费用流但个人感觉这更像反悔贪心吧… 其实我考场上的大方向是对的但是这个反悔没太整明白。 关键是给每配一对的权值加个-inf这样就自然而然的保证必然会选满。 然后就是尝试在LCA处合并并将反悔元素重新插入。 讨论一下几个深度的大小关系就可以得出配对后两个反悔元素同时选取必然是不优的所以不必担心同时取式子出bug的问题。个人认为题解这个地方的讲解十分草率
藏宝地图treasure
神仙扫描线dp。 完全没有往这方面想过…由于看到连通块一共只有 O(k)O(k)O(k) 个所以一直以为是数据结构题疯狂尝试建 k 棵树套树。 这个题最妙的地方应该就是对于障碍的处理了通过奇技淫巧避免了十分麻烦的上下转移确实十分巧妙。 一个细节问题是要注意障碍要先加后删。
代码
T1
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
void write(ll x){if(x9) write(x/10);putchar(0x%10);
}
const int N2e3100;
const double paiacos(-1.0);
const double eps1e-10;int n,m;
int r;
int x[N],y[N];
struct line{double x,y;bool operator (const line oth)const{return abs(x-oth.x)eps?xoth.x:yoth.y;}
}l[N];
int ans;
double a[N],q[N];
int tot,num;
int f0;
void calc(){num0;for(int i1;itot;i){if(!num||a[i]q[num]-eps) q[num]a[i];else{int st1,ednum;while(sted){int mid(sted)1;if(q[mid]a[i]-eps) edmid;else stmid1;}q[st]a[i];}//printf(i%d num%d\n,i,num);}ansmax(ans,num);if(f){for(int i1;itot;i) printf(%lf ,a[i]);printf(\nnum%d\n\n,num);}
}signed main(){//freopen(a.in,r,stdin);//freopen(a.out,w,stdout);nread();rread();for(int i1;in;i){x[i]read();y[i]read();double gatan2(y[i],x[i]),dacos(1.0*r/sqrt(x[i]*x[i]y[i]*y[i]));l[i].xg-d;l[i].ygd;if(l[i].x-pai) l[i].x2*pai;if(l[i].ypai) l[i].y-2*pai;if(f) printf((%lf %lf)\n,l[i].x/pai,l[i].y/pai);if(l[i].xl[i].y) swap(l[i].x,l[i].y);} if(f) puts();sort(l1,l1n);if(f) for(int i1;in;i) printf((%lf %lf)\n,l[i].x,l[i].y);for(int now1;nown;now){a[tot1]l[now].y;for(int inow1;inl[i].xl[now].yeps;i){if(l[i].yl[now].y-eps) a[tot]l[i].y;}calc();}printf(%d\n,ans);return 0;
}
/*
*/
T2
#includebits/stdc.h
#includeext/pb_ds/priority_queue.hpp
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
void write(ll x){if(x9) write(x/10);putchar(0x%10);
}
const int N3e5100;
const int M2e6100;
const double paiacos(-1.0);
const ll inf1e12;int n,m;
int dis[M],ls[M],rs[M];
ll val[M],tot,rub[M],num;
inline int New(ll v){int nownum?rub[num--]:tot;val[now]v;ls[now]rs[now]0;dis[now]0;//printf( New: now%d v%lld\n,now,v);return now;
}
int merge(int x,int y){if(!x||!y) return x|y;if(val[x]val[y]) swap(x,y);rs[x]merge(rs[x],y);if(dis[rs[x]]dis[ls[x]]) swap(ls[x],rs[x]);dis[x]dis[rs[x]]1;return x;
}
inline ll top(int x,int op0){if(!x) return 1e18;ll resval[x];if(op) rub[num]x,xmerge(ls[x],rs[x]);return res;
}
struct node{int to,nxt,w;
}p[N1];
int fi[N],cnt;
inline void addline(int x,int y,int w){p[cnt](node){y,fi[x],w};fi[x]cnt;
}
ll dep[N];
__gnu_pbds::priority_queuell,greaterlla[N],b[N];
int xx[N],yy[N];
ll ans,S;
void dfs(int x,int f){for(int ifi[x];~i;ip[i].nxt){int top[i].to;if(tof) continue;dep[to]dep[x]p[i].w;dfs(to,x);a[x].join(a[to]);b[x].join(b[to]);}//printf(\ndfs: x %d\n,x);int omin(xx[x],yy[x]);xx[x]-o;yy[x]-o;S-o;if(xx[x]){for(int i1;ixx[x];i){//printf( ins A: %lld\n,dep[x]);a[x].push(dep[x]);}}else if(yy[x]){//printf( ins B: %lld\n,dep[x]-inf);for(int i1;iyy[x];i){b[x].push(dep[x]-inf);}}//printf( a%d topa%lld b%d topb%lld\n,a[x],top(a[x]),b[x],top(b[x]));while(!a[x].empty()!b[x].empty()){ll ua[x].top(),vb[x].top();if(uv-2*dep[x]0) break;ansuv-2*dep[x];a[x].pop();b[x].pop();a[x].push(-v2*dep[x]);b[x].push(-u2*dep[x]);}return;
}signed main(){//freopen(rock.in,r,stdin);//freopen(rock.out,w,stdout);memset(fi,-1,sizeof(fi));cnt-1;dis[0]-1;nread();for(int i1;in;i){int xread(),yread(),wread();//printf((%d %d %d)\n,x,y,w);addline(x,y,w);addline(y,x,w);}for(int i1;in;i) xx[i]read(),yy[i]read(),Syy[i];dfs(1,0);printf(%lld\n,ansS*inf);return 0;
}
/*
*/
T3
#includebits/stdc.h
#includeext/pb_ds/priority_queue.hpp
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)){if(c-)f-1;cgetchar();}while(isdigit(c)){x(x1)(x3)c-0;cgetchar();}return x*f;
}
void write(ll x){if(x9) write(x/10);putchar(0x%10);
}
const int N1e6;
const ll inf1e12;int n,m;
int o1e6;#define mid ((lr)1)
#define ls (k1)
#define rs (k1|1)
int tr[N2],laz[N2];
inline void pushup(int k){tr[k]tr[ls]tr[rs];
}
inline void tag(int k){tr[k]0;laz[k]0;return;
}
inline void pushdown(int k){if(laz[k]!-1){laz[k]-1;tag(ls);tag(rs);}return;
}
int ask(int k,int l,int r,int x,int y){if(xy) return 0;if(xlry) return tr[k];pushdown(k);int res(0);if(xmid) resask(ls,l,mid,x,y);if(ymid) resask(rs,mid1,r,x,y);return res;
}
void add(int k,int l,int r,int p,int w){if(lr){tr[k]w;return;}pushdown(k);if(pmid) add(ls,l,mid,p,w);else add(rs,mid1,r,p,w);pushup(k);return;
}
void clear(int k,int l,int r,int x,int y){if(xlry){tag(k);return;}pushdown(k);if(xmid) clear(ls,l,mid,x,y);if(ymid) clear(rs,mid1,r,x,y);pushup(k);
}//0:block
//1:treasure
//2:query
struct ope{int op,f;int x,y,id;int l,r;bool operator (const ope oth)const{if(y!oth.y) return yoth.y;else if(op!oth.op) return opoth.op;else return foth.f;}
}q[N1];
int tot;
int val[N],ans[N];multisetints;
multisetint::iterator it;signed main(){//freopen(treasure.in,r,stdin);//freopen(treasure.out,w,stdout); o2;memset(laz,-1,sizeof(laz));mread();for(int i1;im;i){int aread(),bread(),cread(),dread();a;b;c;d;q[tot](ope){0,1,0,d,i,a,c};q[tot](ope){0,-1,0,b-1,i,a,c};}mread();for(int i1;im;i){int xread(),yread();x;y;q[tot](ope){1,0,x,y,0,0,0};}nread();for(int i1;in;i){int xread(),yread();x;y;q[tot](ope){2,0,x,y,i,0,0};}sort(q1,q1tot);s.insert(o);for(int i1;itot;i){if(q[i].op0){int lq[i].l,rq[i].r,idq[i].id,ed(*s.lower_bound(q[i].l));if(q[i].f1){s.insert(l-1);s.insert(r);int resask(1,1,o,l,ed);val[id]ask(1,1,o,r1,ed);clear(1,1,o,l,r);add(1,1,o,l-1,res);}else{s.erase(s.find(l-1));s.erase(s.find(r));add(1,1,o,l-1,-val[id]);clear(1,1,o,l,r);}}else if(q[i].op1) add(1,1,o,q[i].x,1);else{int posq[i].x;int ed(*s.lower_bound(pos));ans[q[i].id]ask(1,1,o,pos,ed);}}for(int i1;in;i) printf(%d\n,ans[i]);return 0;
}
/*1 3*/
总结
昨天“现在大部分题目基本上考场上都能想到正确的方向了” 今天就直接两道题完全抓瞎… 《天 高 地 厚》 就这考试也有人AK是我没想到的。 收下我的膝盖
明天加油吧awa
