传送门
听说比赛的时候T4T4T4标程锅了？？？
WTF换我时间我要写T3啊
于是在T4T4T4调半天无果的情况下260pts260pts260pts收场真的是tcltcltcl。
T1 快速多项式变换(FPT)
题意：给两个整数表示m,f(m)m,f(m)m,f(m)，要求你构造一个nnn次多项式f(x)f(x)f(x),nnn自己定大小，要求所有系数非负，最高项系数不为000。
思路：
直接mmm进制分解就完了。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int RLEN=1<<18|1;
inline char gc(){
static char buf[RLEN],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,RLEN,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=gc();
return ans;
}
typedef long long ll;
ll m,fm,mult;
int main(){
cin>>m>>fm;
vector<ll>ans;
ll tim=0;
mult=1;
while(fm/mult>=m)++tim,mult*=m;
while(1){
ans.push_back(fm/mult);
fm%=mult;
if(mult==1)break;
mult/=m;
}
cout<<ans.size()<<'\n';
for(ri i=ans.size()-1;~i;--i)cout<<ans[i]<<' ';
return 0;
}
T2 加特林轮盘赌
题意：nnn个人坐在一个圆桌上，轮流把加特林对着自己的头，扣动扳机一秒钟。中枪的自动退出，坚持到最后的就是胜利者，每个人在每回合中枪的概率是完全相同的P0P_0P0,给出P0P_0P0和nnn，询问kkk号长脖子鹿最终成为唯一幸存者的概率PkP_kPk。
思路：
定义状态fi,jf_{i,j}fi,j表示iii个人玩，算上当前这个人距离第kkk个人还有jjj回合成为赢家的概率。
我们可以推出几个显然的式子：
fi,1=(1−P0)∗fi,nf_{i,1}=(1-P_0)*f_{i,n}fi,1=(1−P0)∗fi,n
fi,2=P0fi−1,1+(1−P0)fi,1f_{i,2}=P_0f_{i-1,1}+(1-P_0)f_{i,1}fi,2=P0fi−1,1+(1−P0)fi,1
fi,3=P0fi−1,2+(1−P0)fi,2f_{i,3}=P_0f_{i-1,2}+(1-P_0)f_{i,2}fi,3=P0fi−1,2+(1−P0)fi,2
fi,4=P0fi−1,3+(1−P0)fi,3f_{i,4}=P_0f_{i-1,3}+(1-P_0)f_{i,3}fi,4=P0fi−1,3+(1−P0)fi,3
......\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ ...... ......
fi,i−1=P0fi−1,i−2+(1−P0)fi,i−2f_{i,i-1}=P_0f_{i-1,i-2}+(1-P_0)f_{i,i-2}fi,i−1=P0fi−1,i−2+(1−P0)fi,i−2
fi,i=P0fi−1,i−1+(1−P0)fi,i−1f_{i,i}=P_0f_{i-1,i-1}+(1-P_0)f_{i,i-1}fi,i=P0fi−1,i−1+(1−P0)fi,i−1
然后发现这个转移式是带环的。
我们设fi,n=xf_{i,n}=xfi,n=x，那么把fi,jf_{i,j}fi,j都表示成Ax+BAx+BAx+B的形式，最后解出xxx即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int RLEN=1<<18|1;
inline char gc(){
static char buf[RLEN],*ib,*ob;
(ib==ob)&&(ob=(ib=buf)+fread(buf,1,RLEN,stdin));
return ib==ob?-1:*ib++;
}
inline int read(){
int ans=0;
char ch=gc();
while(!isdigit(ch))ch=gc();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=gc();
return ans;
}
const int N=10005;
long double f[2][N],p;
int n,k,tmp;
struct coe{
long double a,b;
coe(long double _a=0,long double _b=0):a(_a),b(_b){}
friend inline coe operator+(const coe&a,const coe&b){return coe(a.a+b.a,a.b+b.b);}
friend inline coe operator*(const coe&a,const long double&b){return coe(a.a*b,a.b*b);}
}g[N];
inline void solve(int pos){
g[1]=coe(1-p,0);
for(ri i=2;i<=pos;++i)g[i]=(coe){0,p*f[tmp^1][i-1]}+g[i-1]*(1-p);
double X=g[pos].b/(1-g[pos].a);
for(ri i=1;i<=pos;++i)f[tmp][i]=g[i].a*X+g[i].b;
}
int main(){
cin>>p>>n>>k;
if(p==0)return puts("0.0000000000"),0;
f[tmp=1][1]=1;
for(ri i=2;i<=n;++i)tmp^=1,solve(i);
printf("%.10Lf",f[tmp][k]);
return 0;
}
T3 东京夏日相会
题意：平面上面有nnn个圆，给出它们的圆心和半径，现在要你找出一个圆，使得它覆盖平面上所有的圆且其半径最小，要求输出圆心坐标和半径（保留两位小数）
思路：
好像可以模拟退火？
其实可以用一个多边形来拟合每个小圆，然后跑最小覆盖圆。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
const int N=2e5+5;
struct pot{
double x,y;
friend inline pot operator+(const pot&a,const pot&b){return (pot){a.x+b.x,a.y+b.y};}
friend inline pot operator-(const pot&a,const pot&b){return (pot){a.x-b.x,a.y-b.y};}
friend inline pot operator/(const pot&a,const double&b){return (pot){a.x/b,a.y/b};}
inline double mod(){return sqrt(x*x+y*y);}
inline double sqr()const{return x*x+y*y;}
}O,a[30000000];
int n=0,m;
const double pi=acos(-1.0);
inline double dist(const pot&a,const pot&b){return (a-b).mod();}
inline void add_point(double x,double y,double r){
if(!r){a[++n]=(pot){x,y};return;}
double det=max(360.0*acos(1-0.003/r)/pi,1.0);
for(register double ang,i=0;i<360;i+=det)ang=i*pi/180.0,a[++n]=(pot){x+r*cos(ang),y+r*sin(ang)};
}
inline void Set(const pot&a,const pot&b,const pot&c){
double a1=(a.x-b.x)*2,b1=(a.y-b.y)*2,c1=a.sqr()-b.sqr();
double a2=(a.x-c.x)*2,b2=(a.y-c.y)*2,c2=a.sqr()-c.sqr();
O=(pot){(c1*b2-c2*b1)/(a1*b2-a2*b1),(c1*a2-c2*a1)/(b1*a2-b2*a1)};
}
int main(){
scanf("%d",&m);
double x,y,r,R;
while(m--)scanf("%lf%lf%lf",&x,&y,&r),add_point(x,y,r);
random_shuffle(a+1,a+n+1);
O=a[1],R=0;
for(ri i=1;i<=n;++i)if(dist(a[i],O)>R){
O=a[i],R=0;
for(ri j=1;j<i;++j)if(dist(a[j],O)>R){
O=(a[i]+a[j])/2.0,R=dist(a[i],O);
for(ri k=1;k<j;++k)if(dist(a[k],O)>R)Set(a[i],a[j],a[k]),R=dist(O,a[i]);
}
}
printf("%.2lf %.2lf %.2lf",O.x,O.y,R);
return 0;
}
T4 第二代图灵机
题意：
有一条长度为nnn的纸带，每个位置有一个数字和一种颜色
有两种修改：
- 在纸带上的一格写数字.
- 在纸带上的一段区间着色.
有两种询问：
- 求[l,r][l,r][l,r]中包含所有(一共ccc种)颜色，数字和最小的子区间的数字和。
- 求[l,r][l,r][l,r]中没有重复颜色，数字和最大的子区间的数字和。
你需要为第二代图灵机编写算法，使他能通过所有的图灵试验。为保证试验的正确性，所有数据都是随机生成的。
思路：
注意到数据随机
直接上ODT+ODT+ODT+线段树维护区间最值+++树状数组维护区间和即可。
代码：
#include<bits/stdc++.h>
#define ri register int
using namespace std;
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<1)+(ans<<3)+(ch^48),ch=getchar();
return ans;
}
const int N=1e5+5;
int n,m,c,a[N],b[N];
struct Node{
int l,r;
mutable int v;
Node(int l,int r=-1,int v=0):l(l),r(r),v(v){}
friend inline bool operator<(const Node&a,const Node&b){
return a.l<b.l;
}
};
set<Node>S;
typedef set<Node>::iterator It;
inline It split(int pos){
It it=S.lower_bound(pos);
if(it!=S.end()&&it->l==pos)return it;
--it;
if(pos>it->r)return S.end();
int l=it->l,r=it->r,v=it->v;
S.erase(it);
S.insert(Node(l,pos-1,v));
return S.insert(Node(pos,r,v)).first;
}
inline void assign(int l,int r,int v){
It R=split(r+1),L=split(l);
S.erase(L,R),S.insert(Node(l,r,v));
}
namespace Bit{
int bit[N];
inline int lowbit(const int&x){return x&-x;}
inline void update(int x,int v){for(ri i=x;i<=n;i+=lowbit(i))bit[i]+=v;}
inline int query(int x){int ret=0;for(ri i=x;i;i^=lowbit(i))ret+=bit[i];return ret;}
inline int query(int l,int r){return query(r)-query(l-1);}
}
namespace SGT{
#define lc (p<<1)
#define rc (p<<1|1)
#define mid (l+r>>1)
int mn[N<<2],mx[N<<2];
inline void pushup(int p){mx[p]=max(mx[lc],mx[rc]),mn[p]=min(mn[lc],mn[rc]);}
inline void build(int p,int l,int r){
if(l==r){mx[p]=mn[p]=a[l];return;}
build(lc,l,mid),build(rc,mid+1,r),pushup(p);
}
inline int query(int p,int l,int r,int ql,int qr,bool f){
if(ql<=l&&r<=qr)return f?mn[p]:mx[p];
if(qr<=mid)return query(lc,l,mid,ql,qr,f);
if(ql>mid)return query(rc,mid+1,r,ql,qr,f);
return f?min(query(lc,l,mid,ql,qr,f),query(rc,mid+1,r,ql,qr,f)):max(query(lc,l,mid,ql,qr,f),query(rc,mid+1,r,ql,qr,f));
}
inline void update(int p,int l,int r,int k){
if(l==r){mx[p]=mn[p]=a[l];return;}
k<=mid?update(lc,l,mid,k):update(rc,mid+1,r,k),pushup(p);
}
#undef lc
#undef rc
#undef mid
}
inline int query1(int l,int r){
static int vis[101],cnt=0;
if(c==1)return SGT::query(1,1,n,l,r,1);
It R=split(r+1),L=split(l);
int ret=-1;
for(ri i=1;i<=c;++i)vis[i]=0;
cnt=0;
It ll=L,rr=L,tmp=R;
--rr;
--tmp;
for(;ll!=R;){
while(rr!=tmp&&cnt!=c){
++rr;
++vis[rr->v];
if(vis[rr->v]==1)++cnt;
}
if(cnt^c)break;
while(cnt==c){
--vis[ll->v];
if(vis[ll->v]==0){
if(ret==-1)ret=Bit::query(ll->r,rr->l);
else ret=min(ret,Bit::query(ll->r,rr->l));
--cnt;
}
++ll;
}
}
return ret;
}
inline int query2(int l,int r){
static int vis[101];
It R=split(r+1),L=split(l);
int ret=SGT::query(1,1,n,l,r,0);
It ll=L,rr=L;
++rr;
for(ri pos;rr!=R;){
vis[ll->v]=pos=ll->r;
It tmp=ll;
while(rr!=R){
if(vis[rr->v]){
ret=max(ret,Bit::query(max(vis[rr->v],pos),rr->l-1));
ret=max(ret,Bit::query(max(pos,vis[rr->v]+1),rr->l));
if(rr->l!=rr->r)break;
pos=max(pos,vis[rr->v]+1);
while(tmp->r!=vis[rr->v]){if(vis[tmp->v]==tmp->r)vis[tmp->v]=0;++tmp;}
vis[rr->v]=rr->r;
++rr;
continue;
}
ret=max(ret,Bit::query(pos,rr->l));
if(rr->l!=rr->r)break;
vis[rr->v]=rr->r;
++rr;
}
for(It tt=ll;tt!=rr;++tt)vis[tt->v]=0;
ll=rr,++rr;
if(ll==R)break;
}
return ret;
}
int main(){
n=read(),m=read(),c=read();
for(ri i=1;i<=n;++i)a[i]=read(),Bit::update(i,a[i]);
S.insert(Node(0,0,0));
for(ri i=1;i<=n;++i)b[i]=read(),S.insert(Node(i,i,b[i]));
S.insert(Node(n+1,n+1,c+1));
SGT::build(1,1,n);
for(ri op,l,r,x,y;m;--m){
op=read();
switch(op){
case 1:{
x=read(),y=read();
Bit::update(x,y-a[x]),a[x]=y,SGT::update(1,1,n,x);
break;
}
case 2:{
l=read(),r=read();
assign(l,r,read());
break;
}
case 3:{
l=read(),r=read();
cout<<query1(l,r)<<'\n';
break;
}
case 4:{
l=read(),r=read();
cout<<query2(l,r)<<'\n';
break;
}
}
}
return 0;
}