A. Skip
斜率一窍不通，先咕着.
B. String
改不出来，先咕着.
C. Permutation
数学题，找规律推式子.
C_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
#define ll long long int
#define lf double
#define ull unsigned ll
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define FILE(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
inline ll read(){
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=1e6+21,mod=1e9+7;
ll m,n,s,ans;
ll frc[N];
inline ll ksm(ll a,ll b,ll c){
a%=c; ll res=1;
while(b){
if(b&1) res=(res*a)%c;
a=(a*a)%c,b>>=1;
}
return res%c;
}
inline ll C(ll a,ll b){
if(a>b) return 0;
return frc[b]*ksm(frc[a]*frc[b-a],mod-2,mod)%mod;
}
signed main(){
FILE(perm);
n=read(),s=read();
if((m=read())==1) printf("%lld\n",n-s+m-1),exit(0);
frc[0]=1,n-=s-m,s=m;
for(ll i=1;i<=1e6;i++) frc[i]=frc[i-1]*i%mod;
for(ll i=2;i<=s;i++) ans=(ans+C(s-i+2,n-i))%mod;
for(ll i=2;i<=n;i++) ans=(ans+C(s-2,n-i-1)*(i-1)%mod)%mod;
printf("%lld\n",ans%mod),exit(0);
}
D. 小P的生成树
其实比较暴力的思想就是枚举 \(0\) ~ \(2*\pi\) 每个弧度，
然后把所有向量都投影到上面.
然而这样可以 \(A\)..
每次枚举\(0.0001\)，可以过..
改成每次枚举\(0.06\)，依旧可以过，复杂度变成\(O(100*mlogn)\)，快的飞起..
正解的话就是把每个能使任意两个向量的相对大小都改变一下，
其实就是把所有情况都枚举了一遍.
因为最值生成树只关心相对大小.
另外，还可以维护凸包.
D_code
#include<bits/stdc++.h>
using namespace std;
namespace BSS {
#define ll long long int
#define lf double
#define ull unsigned ll
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define Fill(x,y) memset(x,y,sizeof x)
#define Copy(x,y) memcpy(x,y,sizeof x)
#define File(x,y) freopen(#x,"r",stdin),freopen(#y,"w",stdout)
#define FILE(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
inline ll read(){
ll ss=0; bool cit=1; char ch;
while(!isdigit(ch=getchar())) if(ch=='-') cit=0;
while(isdigit(ch)) ss=(ss<<3)+(ss<<1)+(ch^48),ch=getchar();
return cit?ss:-ss;
}
} using namespace BSS;
const ll N=209;
const lf pi=acos(-1.0);
lf now,ans;
lf horn[N*N*N];
ll m,n,cnt;
ll fa[N];
struct I { ll u,v,x,y; lf w,h; } e[N];
ll find(ll x){ return x==fa[x] ? x : fa[x]=find(fa[x]); }
inline bool comp(I i,I j){ return i.w>j.w; }
inline void Kruscal(){
for(int i=1;i<=n;i++) fa[i]=i;
for(int i=1;i<=m;i++){
e[i].w=e[i].x*cos(now)+e[i].y*sin(now);
}
sort(e+1,e+1+m,comp); ll u,v,R=0,I=0;
for(int i=1;i<=m;i++){
u=e[i].u,v=e[i].v;
if(find(u)==find(v)) continue ;
R+=e[i].x,I+=e[i].y,fa[find(v)]=find(u);
}
// cout<<R<<' '<<I<<endl;
ans=max(ans,sqrt(1.0*R*R+1.0*I*I));
}
signed main(){
FILE(mst);
n=read(),m=read(); ll u,v; lf x,y;
for(int i=1;i<=m;i++){
e[i].u=read(),e[i].v=read(),e[i].x=read(),e[i].y=read();
e[i].h=1.0*e[i].y/e[i].x; // tan
}
for(int i=1;i<=m;i++){
for(int j=i+1;j<=m;j++){
x=atan(e[i].h),y=atan(e[j].h);
if(e[i].y==e[j].y){
horn[++cnt]=atan(pi/2.0),horn[++cnt]=atan(pi*3.0/2.0);
}
else{
horn[++cnt]=atan(1.0*(e[i].x-e[j].x)/(e[j].y-e[i].y));
horn[++cnt]=atan(1.0*(e[i].x-e[j].x)/(e[j].y-e[i].y))+pi;
}
}
}
sort(horn+1,horn+1+cnt),cnt=unique(horn+1,horn+1+cnt)-horn-1;
horn[cnt+1]=horn[1];
for(int i=1;i<=cnt;i++){
now=(horn[i]+horn[i+1])/2.0;
Kruscal();
now=(horn[i]+horn[i+1])/2.0+pi;
Kruscal();
}
printf("%.6lf\n",ans),exit(0);
}