Lvat_s Blog

首先我们知道答案是$C(n,m)*Perm(n-m)$

$Perm(x)$表示为$x$的错排方案数

($n$个数里面选$m$个数作为稳定点，其余点均不在自己的位置上)

错排公式:$Perm(x)=(x-1)Perm(x-1)Perm(x-2)$

考场上这个想了很久。。。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;

const int N=1000005;
const long long Mod=1e9+7;
const long double eps=1e-10;

int T;
long long Pv[N+1],Px[N+1],Cu[N+1],m,n;

long long Qpow(long long A,long long B){
long long base=A,ans=1;
while(B){
	if(B&1)ans=ans*base%Mod;
	base=base*base%Mod;
	B>>=1;
}
return ans;
}

void Prepare(){
long long s=1;
Px[0]=1;
Pv[0]=1;
for(int i=1;i<=N;i++){
	s=s*i%Mod;
	Pv[i]=s;
	Px[i]=Qpow(s,Mod-2);
}
Cu[0]=1;
Cu[1]=0;
Cu[2]=1;
for(long long i=3;i<=N;i++)Cu[i]=(Cu[i-1]+Cu[i-2])%Mod*(i-1)%Mod;
}

long long C(long long a,long long b){
return Pv[a]*Px[b]%Mod*Px[a-b]%Mod;
}

int main(){
freopen("4517.in","r",stdin);
freopen("4517.out","w",stdout);
scanf("%d",&T);
Prepare();
while(T--){
	scanf("%lld %lld",&n,&m);
	printf("%lld\n",C(n,m)*Cu[n-m]%Mod);
}
return 0;
}

神转化。。。

首先我们考虑因为每一次只会知道奇偶性，所以我们对于一个区间[l,r]是否有球至少保证要知道[l...r]全部的奇偶性才可以判定每个杯子下面是否有球。（意味着如果每个杯子抽象成点，那么这些点之间必须全部连通才会知道每个杯子下面是否有球）

因为要费用最少，所以我们每次选择费用最小且有用的边加上去

然后就变成了最小生成树了。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int n,en,h[2005],cnt,f[2005];
long long ans=0;

struct Edge{
int a,b,v;
friend bool operator<(Edge a,Edge b){return a.v<b.v;}
}e[4000005];

void AddEdge(int sa,int sb,int sc){
e[++en].a=sa;
e[en].b=sb;
e[en].v=sc;
}

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){f[sb]=sa;}

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

int main(){
freopen("3714.in","r",stdin);
freopen("3714.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
	for(int j=i;j<=n;j++){
		int x;
		scanf("%d",&x);
		AddEdge(i,j+1,x);
	}
}
sort(e+1,e+en+1);
for(int i=1;i<=n+1;i++)f[i]=i;
for(int i=1;i<=en && cnt<=n;i++){
	if(Find(e[i].a)!=Find(e[i].b)){Union(Find(e[i].a),Find(e[i].b));ans+=(long long)e[i].v;cnt++;}
}
printf("%lld\n",ans);
return 0;
}

今天考试考了一个斜率优化DP，一大群人A了。。

这让从没写过斜率优化的我情何以堪

所以我就把这题写了。。

感觉还是很好理解的：维护最优决策，再维护决策单调性

顺便Orz lyz rky今天AK了省选模拟

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
 
int n,first,last;
long long L,s[50005],dp[50005],q[500005],C;
 
bool DelFirst(int a,int b,int c){
return dp[a]+(s[c]-s[a]-C)*(s[c]-s[a]-C)>dp[b]+(s[c]-s[b]-C)*(s[c]-s[b]-C);
}
 
bool DelLast(int a,int b,int c){
return (dp[a]-dp[b]+s[a]*s[a]-s[b]*s[b])*(s[c]-s[b])<(dp[b]-dp[c]+s[b]*s[b]-s[c]*s[c])*(s[b]-s[a]);
}
 
int main(){
freopen("1010.in","r",stdin);
freopen("1010.out","w",stdout);
scanf("%d %d",&n,&L);
C=L+1;
for(int i=1;i<=n;i++){
    long long x;
    scanf("%lld",&x);
    s[i]=s[i-1]+x;
}
for(int i=1;i<=n;i++)s[i]+=i;
first=1;
last=0;
q[++last]=0;
for(int i=1;i<=n;i++){
    while(first<last && DelFirst(q[first],q[first+1],i))first++;
    dp[i]=dp[q[first]]+(s[i]-s[q[first]]-C)*(s[i]-s[q[first]]-C);
    while(first<last && DelLast(q[last-1],q[last],i))last--;
    q[++last]=i;
}
printf("%lld\n",dp[n]);
return 0;
}

首先，如果一个串可以被分割成两个串且这两个串均满足条件，那么这个串一定满足条件。

证明:$a=0(mod$ $m)$,$b=0(mod$ $m)$则$a*x+b*y=0(mod$ $m)$（显然）

那么我们只要统计有多少种满足情况的子串就可以了，设数目为$k$，然后方案数就是$2^k$

注意如果最后原串不满足条件就要输出0（显然原串不满足那么拆成的子串中至少有一个不满足该性质）

说了这么多，其实特别好写。。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

int n,m,ans=0,len;
const int Mod=1e9+7;

int main(){
freopen("4421.in","r",stdin);
freopen("4421.out","w",stdout);
scanf("%d %d",&n,&m);
char ch;
while((ch=getchar())<'0' || ch>'9');
if((ch-'0')%m==0)ans=1;
len=ch-'0';
while((ch=getchar())>='0' && ch<='9'){
	len=(len*10+ch-'0')%m;
	if(len==0){
		if(ans==0)ans=1;
		else ans=ans*2%Mod;
	}
}
printf("%d\n",len==0?ans:0);
return 0;
}

Hash乱搞大法好

我先用一个伪随机序列然后每次排序随便判断

每次记录三个哈希值然后进行奇怪的运算就A掉了

怀疑很容易被卡掉。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int Smod=999973;
const long long Lmod1=666666666666667ll,Lmod2=233333333333333ll;

int cnt,en,m,h[1000005],H[55],n;
long long rnd[105],sum[105];

struct Hash{
long long lhash1,lhash2;
int next,v;
}ha[10000005];

void AddHash(int s,long long l1,long long l2,int x){
ha[++cnt].lhash1=l1;
ha[cnt].lhash2=l2;
ha[cnt].v=x;
ha[cnt].next=h[s];
h[s]=cnt;
}

int FindHash(int s,long long l1,long long l2){
for(int i=h[s];i;i=ha[i].next){
	if(ha[i].lhash1==l1 && ha[i].lhash2==l2)return i;
}
return 0;
}

struct Edge{
int b,next;
}e[1005];

void AddEdge(int sa,int sb){
e[++en].b=sb;
e[en].next=H[sa];
H[sa]=en;
}

void Dfs(int u,int fa){
long long St[105];
int siz=0;
St[++siz]=233;
for(int i=H[u];i;i=e[i].next){
    int v=e[i].b;
    if(v==fa)continue;
    Dfs(v,u);
    St[++siz]=sum[v];
}
sort(St+1,St+siz+1);
sum[u]=0;
for(int i=1;i<=siz;i++)sum[u]+=St[i]*rnd[i];
}

int main(){
freopen("4337.in","r",stdin);
freopen("4337.out","w",stdout);
scanf("%d",&m);
rnd[0]=233;
for(int i=1;i<=100;i++)rnd[i]=rnd[i-1]*99973ll+7;
for(int i=1;i<=m;i++){
	en=0;
	memset(H,0,sizeof(H));
	memset(sum,0,sizeof(sum));
	scanf("%d",&n);
	for(int j=1;j<=n;j++){
		int x;
		scanf("%d",&x);
		if(x){AddEdge(x,j);AddEdge(j,x);}
	}
	int ans1=0;
	long long ans2=0,ans3=77;
	for(int j=1;j<=n;j++){Dfs(j,0);ans1=ans1+sum[j];ans2=ans2^sum[j];ans3=ans3*sum[j];}
	ans1=max(ans1,-ans1);
	ans1=ans1%Smod+7;
	int dx=FindHash(ans1,ans2,ans3);
	if(!dx){AddHash(ans1,ans2,ans3,i);printf("%d\n",i);}
	else printf("%d\n",ha[dx].v);
}
return 0;
}

暴力的计算几何

暴力求出每一条线段，暴力比较是否能构成矩形

注意要long long不要double否则会炸精度

#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
using namespace std;
 
const int N=1505;
typedef long long LL;
 
int n,cnt;
LL ans; 
 
struct Point{
LL x,y;
Point(){}
Point(LL xs,LL ys){x=xs;y=ys;}
friend bool operator==(Point A,Point B){return A.x==B.x & A.y==B.y;}
friend Point operator+(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
friend Point operator-(Point A,Point B){return Point(A.x-B.x,A.y-B.y);}
friend LL operator*(Point A,Point B){return A.y*B.x-A.x*B.y;}
friend bool operator<(Point A,Point B){return A.x<B.x || (A.x==B.x && A.y<B.y);}
}poi[N];
 
LL Dist(Point A,Point B){return (A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y);}
Point MidPoint(Point A,Point B){return Point(A.x+B.x,A.y+B.y);}
 
struct Line{
Point a,b,mid;
LL dis;
Line(){}
Line(Point A,Point B,Point MID,LL DIS){a=A;b=B;mid=MID;dis=DIS;}
friend bool operator<(Line A,Line B){
return A.dis<B.dis || (A.dis==B.dis && A.mid<B.mid) || (A.dis==B.dis && A.mid==B.mid && A.a<B.a);
}
}line[N*N];
 
LL Abs(LL x){return x>0?x:-x;}
 
int main(){
freopen("2338.in","r",stdin);
freopen("2338.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
    scanf("%lld %lld",&poi[i].x,&poi[i].y);
}
for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        line[++cnt]=Line(poi[i],poi[j],MidPoint(poi[i],poi[j]),Dist(poi[i],poi[j]));
    }
}
sort(line+1,line+cnt+1);
for(int i=2;i<=cnt;i++){
    int j=i-1;
    while(line[j].mid==line[i].mid && line[j].dis==line[i].dis){
        ans=max(ans,Abs((line[i].a-line[j].a)*(line[i].a-line[j].b)));
        j--;
    }
}
printf("%lld\n",ans);
return 0;
}

用二分图建图再跑最大费用最大流就可以了

考场上建图写炸了。。。sad

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
 
const long long INF=1000000000000000ll;
 
int n,en,S,T,h[10005],flag[10005],Back[10005],Tag,tab[100005],cnt,X[10005],Y[10005],xs=0,ys=0;
long long A[2005],B[2005],C[2005],D[10005],Cost=0;
queue<int> Q;
 
struct Edge{
int b,back,next;
long long f,c;
}e[2000005];
 
void AddEdge(int sa,int sb,long long sc,long long sd){
e[++en].b=sb;
e[en].back=en+1;
e[en].f=sc;
e[en].c=sd;
e[en].next=h[sa];
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].back=en-1;
e[en].f=0;
e[en].c=-sd;
e[en].next=h[sa];
h[sa]=en;
}
 
bool SPFA(){
memset(D,-80,sizeof(D));
memset(flag,0,sizeof(flag));
memset(Back,0,sizeof(Back));
D[S]=0;
Q.push(S);
flag[S]=1;
while(!Q.empty()){
    int u=Q.front();
    Q.pop();
    flag[u]=0;
    for(int i=h[u];i;i=e[i].next){
        int v=e[i].b;
        if(D[u]+e[i].c>D[v] && e[i].f){
            D[v]=D[u]+e[i].c;
            Back[v]=i;
            if(!flag[v]){
                flag[v]=1;
                Q.push(v);
            }
        }
    }
}
return D[T]>-INF;
}
 
long long Flow(){
long long ans=INF,Co=0;
int Tx=Back[T];
while(Tx){
    ans=min(ans,e[Tx].f);
    Co+=e[Tx].c;
    Tx=Back[e[e[Tx].back].b];
}
while(Cost+ans*Co<0)ans--;if(ans<=0){Tag=1;return 0;}
Tx=Back[T];
while(Tx){
    e[Tx].f-=ans;
    e[e[Tx].back].f+=ans;
    Cost+=ans*e[Tx].c;
    Tx=Back[e[e[Tx].back].b];
}
return ans;
}
 
long long MaxCost(){
long long ans=0;
while(SPFA()){
    ans+=Flow();
    if(Tag)break;
}
return ans;
}
 
bool Test(int x){
if(x==1 || x==0)return 0;
for(int i=2;i*i<=x;i++){
    if(x%i==0)return 0;
}
return 1;
}
 
bool Testx(long long x){
if(x==1 || x==0)return 0;
for(int i=1;tab[i]*tab[i]<=x && i<=cnt;i++){
    if(x%tab[i]==0)return 0;
}
return 1;
}
 
void Prime(){
for(int i=2;i<=40000;i++){
    if(Test(i)){tab[++cnt]=i;}
}
}
 
int Count(long long x){
int px=0;
for(int i=1;tab[i]*tab[i]<=x && i<=cnt;i++){
    while(x%tab[i]==0){px++;x/=tab[i];}
}
if(x>1)px++;
return px;
}
 
int main(){
freopen("4514.in","r",stdin);
freopen("4514.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
for(int i=1;i<=n;i++)scanf("%lld",&B[i]);
for(int i=1;i<=n;i++)scanf("%lld",&C[i]);
Prime();
S=n+1;T=n+2;
for(int i=1;i<=n;i++){if(Count(A[i])&1)X[++xs]=i;else Y[++ys]=i;}
for(int i=1;i<=xs;i++)AddEdge(S,X[i],B[X[i]],0);
for(int i=1;i<=ys;i++)AddEdge(Y[i],T,B[Y[i]],0);
for(int i=1;i<=xs;i++){
    for(int j=1;j<=ys;j++){
        if(A[X[i]]%A[Y[j]]==0 && Testx(A[X[i]]/A[Y[j]])){AddEdge(X[i],Y[j],INF,C[X[i]]*C[Y[j]]);}
        if(A[Y[j]]%A[X[i]]==0 && Testx(A[Y[j]]/A[X[i]])){AddEdge(X[i],Y[j],INF,C[X[i]]*C[Y[j]]);}
    }
}
printf("%lld\n",MaxCost());
return 0;
}

一道简单的期望DP题。。但是我这种题还要看别人的题解。。毕竟DP能力太差

考虑我们已经确定好了前k-1位的期望得分，那么当前第k位有两种情况:

1.操作成功为1，这么做的贡献就等于前面连续1的个数加上1后再三次方的得分然后减去前面的得分期望

2.操作失败为0，那么贡献为0

然后我们需要维护x,x²两个量，然后因为期望的线性性，我们每一次直接加上就好了

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;

int n;
double a[100005],x[100005],x2[100005],dp[100005];

int main(){
freopen("4318.in","r",stdin);
freopen("4318.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lf",&a[i]);
for(int i=1;i<=n;i++){
	x[i]=(x[i-1]+1)*a[i];
	x2[i]=(x2[i-1]+2*x[i-1]+1)*a[i];
	dp[i]=dp[i-1]+(3*x2[i-1]+3*x[i-1]+1)*a[i];
}
printf("%.1lf\n",dp[n]);
return 0;
}

二分时间，跑实数网络流就可以了

貌似速度还很快- -

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;

const int INF=2100000000;
const double eps=1e-6;

int n,m,level[5005],h[5005],cur[5005],S,T,en,Mt[55][55];
double A[55],B[55],Sum;
queue<int> Q;

struct Edge{
int b,back,next;
double f;
}e[100005];

double Abs(double x){return x>0?x:-x;}

void AddEdge(int sa,int sb,double sc){
e[++en].b=sb;
e[en].f=sc;
e[en].next=h[sa];
e[en].back=en+1;
h[sa]=en;
swap(sa,sb);
e[++en].b=sb;
e[en].f=0;
e[en].next=h[sa];
e[en].back=en-1;
h[sa]=en;
}

int BFS(){
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
	int u=Q.front();
	Q.pop();
	for(int i=h[u];i;i=e[i].next){
		int v=e[i].b;
        if(e[i].f<eps || level[v])continue;
        level[v]=level[u]+1;
        Q.push(v);
	}
}
return level[T];
}

double DFS(int u,double flow){
if(u==T)return flow;
double f=flow;
for(int &i=cur[u];i;i=e[i].next){
    int v=e[i].b;
    double fl;
    if(level[v]==level[u]+1 && e[i].f && (fl=DFS(v,min(f,e[i].f)))>eps){
		f-=fl;
		e[i].f-=fl;
		e[e[i].back].f+=fl;
		if(f<eps)return flow;
    }
}
return flow-f;
}

double Dinic(){
double ans=0;
while(BFS()){for(int i=1;i<=T;i++)cur[i]=h[i];ans+=DFS(S,(double)INF);}
return ans;
}

bool Test(double Ts){
memset(h,0,sizeof(h));
en=0;
S=n+m+1;
T=n+m+2;
for(int i=1;i<=m;i++)AddEdge(S,i,Ts*B[i]);
for(int i=1;i<=n;i++)AddEdge(i+m,T,A[i]);
for(int i=1;i<=m;i++){
	for(int j=1;j<=n;j++){
		if(Mt[i][j])AddEdge(i,j+m,INF);
	}
}
return Abs(Dinic()-Sum)<eps;
}

double Div(){
double l=0,r=100000000,ans;
while(r-l>eps){
	double mid=l/2+r/2;
	if(Test(mid)){ans=mid;r=mid;}
	else l=mid;
}
return ans;
}

int main(){
freopen("3993.in","r",stdin);
freopen("3993.out","w",stdout);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){scanf("%lf",&A[i]);Sum+=A[i];}
for(int i=1;i<=m;i++){scanf("%lf",&B[i]);}
for(int i=1;i<=m;i++){
	for(int j=1;j<=n;j++){
		scanf("%d",&Mt[i][j]);
	}
}
printf("%lf\n",Div());
return 0;
}

还有几天就AHOI了呢。。

虽然进队希望=0，但是还是停课准备了。。

cyd和dhp没有停课，理由是今年进不了队，停课影响文化课，但我其实是不太资瓷这么做的，毕竟省选一年只有一次，高中也只有2次，你不认真对待省选，那么省选也不会认真对待你

不说了。。天天零爆爆底垫垫，今年省选估计要爆0。。

还是不要立flag为好

总之，Bless All!我不会虚度这4天的停课的光阴的！