CC BY 4.0 （除特别声明或转载文章外）
如果这篇博客帮助到你，可以请我喝一杯咖啡~
Beautiful Now
以为是贪心但是贪心的策略过不了 2311 ，于是暴搜。
#include<bits/stdc++.h>
using namespace std;
char s[15];
int t,k,mi,ma;
void dfs(int n,int k,int v)
{
if(k<0)return;
if(!s[n])mi=min(mi,v),ma=max(ma,v);
for(int i=n; s[i]; ++i)
{
swap(s[n],s[i]);
if(s[0]!='0')dfs(n+1,k-(s[n]!=s[i]),v*10+s[n]-'0');
swap(s[n],s[i]);
}
}
int main()
{
for(scanf("%d",&t); t--; printf("%d %d\n",mi,ma))
scanf("%s%d",s,&k),mi=1e9,dfs(0,k,ma=0);
}
Everything Has Changed
对于每个小圆 B，在最终答案里加上其在主圆 C 内部的弧长、减去 C 在 B 中的弧长。
#include<bits/stdc++.h>
using namespace std;
const double EPS=1e-9,PI=acos(-1);
typedef complex<double> Coord;
struct Circle
{
Coord c;
double r;
Circle(Coord c=Coord(),double r=0):c(c),r(r) {}
};
int sgn(double d)
{
return (d>EPS)-(d<-EPS);
}
double cal(Circle C,Circle B)
{
double d=abs(B.c-C.c);
return sgn(B.r+C.r-d)<0||sgn(fabs(B.r-C.r)-d)>0?0:
2*C.r*acos((d*d+C.r*C.r-B.r*B.r)/2/d/C.r);
}
int main()
{
int t,m,x,y,r;
for(scanf("%d",&t); t--;)
{
Circle C(Coord(0,0));
double s=0;
for(scanf("%d%lf",&m,&C.r); m--;)
{
scanf("%d%d%d",&x,&y,&r);
Circle B(Coord(x,y),r);
s+=cal(B,C)-cal(C,B);
}
printf("%.9f\n",s+2*PI*C.r);
}
}
Glad You Came
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned ul;
ul rng61(ul &x,ul &y,ul &z)
{
return x^=x<<11,x^=x>>4,x^=x<<5,x^=x>>14,swap(x,y),swap(y,z),z^=x^y;
}
struct SegmentTree
{
struct Node
{
ll set;
};
vector<Node> v;
int LAST,L,R;
SegmentTree(int n):LAST(n),v(2*n+1) {}
Node &lv(int l,int r)
{
return v[l+r|l!=r];
}
void set(int l,int r,ll val,bool out=1)
{
if(out)return L=l,R=r,set(1,LAST,val,0);
if(val<lv(l,r).set)return;
if(L<=l&&r<=R)
{
lv(l,r).set=val;
return;
}
int m=l+(r-l)/2;
if(L<=m)set(l,m,val,0);
if(R>m)set(m+1,r,val,0);
}
ll ask(int l,int r)
{
if(l==r)return l*lv(l,r).set;
int m=l+(r-l)/2;
lv(l,m).set=max(lv(l,m).set,lv(l,r).set);
lv(m+1,r).set=max(lv(m+1,r).set,lv(l,r).set);
return ask(l,m)^ask(m+1,r);
}
};
int main()
{
ul t,n,m,x,y,z;
for(scanf("%u",&t); t--;)
{
scanf("%u%u%u%u%u",&n,&m,&x,&y,&z);
SegmentTree tree(n);
for(int i=0,l,r; i<m; ++i)
{
if(l=rng61(x,y,z)%n+1,r=rng61(x,y,z)%n+1,l>r)swap(l,r);
tree.set(l,r,rng61(x,y,z)%(1<<30));
}
printf("%lld\n",tree.ask(1,n));
}
}