1005Everything Has Changed
题意：初始有原点在（0,0）半径为R的圆盘，现在有m个圆的圆心为(xi，yi)半径为ri对圆盘进行切割，小圆之间不相交，没有一个小圆将整个圆盘切出，问企切割后圆盘的外周长。
解析：考虑只有内切，相交两种情况对外周长有贡献。
内切直接加上小圆周长即可；
相交时设dis=sqrt(xi*xi+yi*yi)为圆心之间距离，那么考虑对，dis和R和ri之间的三角形使用余弦定理，可以求出两个圆圆心与两圆交点之间圆心角，再由圆心角求出两圆互相被包含的圆周长度即可。
代码：
#include<bits/stdc++.h> using namespace std; const double PI=acos(-1.0); int main() { int T,m; double R,r,x,y; scanf("%d",&T); while(T--) { scanf("%d%lf",&m,&R); double ans=2.0*PI*R; while(m--) { scanf("%lf%lf%lf",&x,&y,&r); double dis=sqrt(x*x+y*y); if(dis>=R+r) { continue; } else if(dis==fabs(R-r))//内切 { ans+=2.0*PI*r; } else if(dis<r+R&&dis>fabs(R-r))//两个交点 { double j1=acos((dis*dis+R*R-r*r)/(2.0*dis*R)); double j2=acos((dis*dis+r*r-R*R)/(2.0*dis*r)); j1=j1*2.0;j2=j2*2.0; double l1=j1*R; double l2=j2*r; ans=ans-l1+l2; } } cout<<fixed<<setprecision(20)<<ans<<endl; } return 0; }1007Glad You Came
题意：有长为n的数组a[]初始值全为0，现在有长度为3*m的随机数组f[]，f[]是用来更新a[]数组用的辅助数组。有m次操作目，第i次操作将a数组中区间[li,ri]中值小于vi的元素更新为vi，这里li,ri,vi是用f[]数组求出。
解析：用线段树维护区间中最小值，更新时当区间中最小值都大于v，就不用往下更新，否则暴力往叶子节点更新即可。
代码来自https://blog.csdn.net/a1046765624：
//不带lazy的- #include <bits/stdc++.h> #define ll long long #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int maxn=1e5+10; const int INF=0x3f3f3f3f; const int mod=(1<<30); unsigned x,y,z; unsigned f[15000010]; ll min_1[maxn<<2]; void pushup(int rt) { min_1[rt]=min(min_1[rt<<1],min_1[rt<<1|1]); } void update(int L,int R,ll v,int l,int r,int rt) { if(min_1[rt]>=v)return;//小于v的才更新，区间内值都大于v则返回 if(l==r)//一定小于v { min_1[rt]=v; return; } int m=(l+r)/2; if(m>=L)update(L,R,v,lson); if(m<R)update(L,R,v,rson); pushup(rt); } long long getsum(int L,int R,int l,int r,int rt) { if(l==r) { return min_1[rt]; } int m=(l+r)/2; long long ans=0; if(L<=m)ans=getsum(L,R,lson); if(m<R)ans=getsum(L,R,rson); return ans; } unsigned get() { x=x^(x<<11); x=x^(x>>4); x=x^(x<<5); x=x^(x>>14); unsigned w=x^(y^z); x=y; y=z; z=w; return z; } int main() { int t; scanf("%d",&t); while(t--) { int n,m; memset(min_1,0,sizeof(min_1)); scanf("%d%d%d%d%d",&n,&m,&x,&y,&z); for(int i=1;i<=3*m;i++) { f[i]=get(); } for(int i=1;i<=m;i++) { int l=min(f[3*i-2]%n+1,f[3*i-1]%n+1); int r=max(f[3*i-2]%n+1,f[3*i-1]%n+1); int w=f[3*i]%mod; update(l,r,w,1,n,1); } ll sum=0; for(int i=1;i<=n;i++) { ll w=getsum(i,i,1,n,1); //cout<<w<<endl; sum^=(w*i); } printf("%lld\n",sum); } return 0; }
