QAQ 又是一套水题集合
然后忧伤的故事是老师把时间调到了四个小时半
我又因为想要出道题花了半个小时写了一些其他的东西
然后最后没有写完题！QAQ
不然第三题可能多拿点分
上午的时候把所有题目的正解都想了出来
唯一美中不足的是自己想的第三题是O(n^4*300)的是时间复杂度
实际上离散化区间之后只会有n个区间，时间复杂度就是O(n^5)了QAQ
先说题解把
第一题 决战圆锥曲线
显然给定你的那个函数a*x+b*y+c*x*y对于x，y是相对等价的
又因为题目的输入具有随机性，显然可以通过维护线段树在线段树上做kd_tree的查询来完成
注意到x，y都是正整数，而且x的范围就区间的范围，所以我们利用线段树维护y的最大值就可以完成类似kd_tree的查询了
时间复杂度略微有些玄学，听说随机数据下O(nlog^2n)？
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=100010;
const LL oo=1LL<<60;
int n,m,x,p,v,le,re;
int A,B,C;
int a[maxn];
int mx[maxn<<2];
int mn[maxn<<2];
bool vis[maxn<<2];
LL ans;
int Get_R(){
x=(1LL*100000005*x+20150609)%998244353;
return x/100;
}
void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
void build(int o,int L,int R){
if(L==R){
mx[o]=mn[o]=a[L];
return;
}
int mid=(L+R)>>1;
build(o<<1,L,mid);
build(o<<1|1,mid+1,R);
mx[o]=max(mx[o<<1],mx[o<<1|1]);
mn[o]=min(mn[o<<1],mn[o<<1|1]);
}
void down(int o,int l,int r){
int Mn,Mx;
vis[l]^=1;vis[r]^=1;
Mn=mn[l];Mx=mx[l];
mx[l]=100000-Mn;mn[l]=100000-Mx;
Mn=mn[r];Mx=mx[r];
mx[r]=100000-Mn;mn[r]=100000-Mx;
vis[o]=false;
}
void UPD(int o,int L,int R){
if(L==R){mx[o]=mn[o]=v;return;}
int mid=(L+R)>>1;
int l=(o<<1),r=(l|1);
if(vis[o])down(o,l,r);
if(p<=mid)UPD(l,L,mid);
else UPD(r,mid+1,R);
mx[o]=max(mx[l],mx[r]);
mn[o]=min(mn[l],mn[r]);
}
void modify(int o,int L,int R){
if(L>=le&&R<=re){
vis[o]^=1;
int Mn=mn[o],Mx=mx[o];
mx[o]=100000-Mn;
mn[o]=100000-Mx;
return;
}
int mid=(L+R)>>1;
int l=(o<<1),r=(l|1);
if(vis[o])down(o,l,r);
if(re<=mid)modify(l,L,mid);
else if(le>mid)modify(r,mid+1,R);
else modify(l,L,mid),modify(r,mid+1,R);
mx[o]=max(mx[l],mx[r]);
mn[o]=min(mn[l],mn[r]);
}
LL Get_ans(int o,int L,int R){
int tmp=mx[o];LL k=(A+1LL*C*tmp);
return k*R+1LL*B*tmp;
}
void kd_ask(int o,int L,int R){
if(L==R){
ans=max(ans,1LL*A*L+1LL*B*mn[o]+1LL*C*L*mn[o]);
return;
}
int mid=(L+R)>>1;
int l=(o<<1),r=(l|1);
if(vis[o])down(o,l,r);
LL d1=Get_ans(l,L,mid);
LL d2=Get_ans(r,mid+1,R);
if(d1>d2){
if(d1>ans)kd_ask(l,L,mid);
if(d2>ans)kd_ask(r,mid+1,R);
}else{
if(d2>ans)kd_ask(r,mid+1,R);
if(d1>ans)kd_ask(l,L,mid);
}return;
}
void ask(int o,int L,int R){
if(L>=le&&R<=re){
kd_ask(o,L,R);
return;
}
int mid=(L+R)>>1;
int l=(o<<1),r=(l|1);
if(vis[o])down(o,l,r);
if(re<=mid)ask(l,L,mid);
else if(le>mid)ask(r,mid+1,R);
else ask(l,L,mid),ask(r,mid+1,R);
}
int main(){
freopen("conic.in","r",stdin);
freopen("conic.out","w",stdout);
read(n);read(m);read(x);
for(int i=1;i<=n;++i)a[i]=Get_R()%100001;
build(1,1,n);
while(m--){
char ch=getchar();
while(ch<'!')ch=getchar();
if(ch=='C'){
p=Get_R()%n+1;v=Get_R()%100001;
UPD(1,1,n);
}else if(ch=='R'){
le=Get_R()%n+1;re=Get_R()%n+1;
if(le>re)swap(le,re);
modify(1,1,n);
}else{
read(A);read(B);read(C);
ans=-oo;
le=Get_R()%n+1;re=Get_R()%n+1;
if(le>re)swap(le,re);
ask(1,1,n);
printf("%lld
",ans);
}
}return 0;
}
第二题
显然有30分是白送给状态压缩或者插头DP的
之前有一道题目是最小割我用插头DP骗了90分，那么考虑这道题能不能用网络流解决
不难发现如果两个B可以消掉，这两个B的行的奇偶性一定不一样
这样对于B来说具有二分图的性质，但是还有考虑A的影响
而且我们的每个流都要表示一个B-A-B的方案
仔细思考后可以得到如下建图：
我们的S向行数是偶数的B连边，行数是奇数的B向T连边
对于行数是偶数的B我们向四个方向的A连边
对于每个A拆点限流
之后行数是偶数的A向左右两个方向的B连边
行数是奇数的A向上下两个方向的B连边
不难发现每个流都代表一个可行的L
那么求最大流即可，由于边权都是1，所以网络流跑的飞快
QAQ考试的时候心虚还写了个插头DP对拍QAQ
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<queue>
using namespace std;
const int maxn=500010;
const int oo=0x7fffffff;
int n,m,S,T,ans;
int c[510][510];
int idx[510][510],tot=0;
int h[maxn],cnt=1;
int vis[maxn];
struct edge{
int to,next,w;
}G[8000010];
queue<int>Q;
void add(int x,int y,int z){
++cnt;G[cnt].to=y;G[cnt].next=h[x];G[cnt].w=z;h[x]=cnt;
++cnt;G[cnt].to=x;G[cnt].next=h[y];G[cnt].w=0;h[y]=cnt;
}
void read(int &num){
num=0;char ch=getchar();
while(ch<'!')ch=getchar();
while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
}
bool BFS(){
Q.push(S);
for(int i=S;i<=T;++i)vis[i]=-1;
vis[S]=0;
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
if(vis[v]==-1&&G[i].w>0){
vis[v]=vis[u]+1;
Q.push(v);
}
}
}return vis[T]!=-1;
}
int DFS(int x,int f){
if(x==T||f==0)return f;
int w,used=0;
for(int i=h[x];i;i=G[i].next){
if(vis[G[i].to]==vis[x]+1){
w=f-used;
w=DFS(G[i].to,min(w,G[i].w));
G[i].w-=w;G[i^1].w+=w;
used+=w;if(used==f)return used;
}
}
if(!used)vis[x]=-1;
return used;
}
void dinic(){
ans=0;
while(BFS())ans+=DFS(S,oo);
}
int main(){
freopen("molecule.in","r",stdin);
freopen("molecule.out","w",stdout);
read(n);read(m);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)read(c[i][j]);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(c[i][j]==0)continue;
idx[i][j]=++tot;
if(c[i][j]==1)++tot;
}
}S=0;T=tot+1;
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(c[i][j]==0)continue;
if(i&1){
if(c[i][j]==2){
add(S,idx[i][j],1);
if(j-1>=1&&c[i][j-1]==1)add(idx[i][j],idx[i][j-1],1);
if(j+1<=m&&c[i][j+1]==1)add(idx[i][j],idx[i][j+1],1);
if(i-1>=1&&c[i-1][j]==1)add(idx[i][j],idx[i-1][j],1);
if(i+1<=n&&c[i+1][j]==1)add(idx[i][j],idx[i+1][j],1);
}else{
add(idx[i][j],idx[i][j]+1,1);
if(i-1>=1&&c[i-1][j]==2)add(idx[i][j]+1,idx[i-1][j],1);
if(i+1<=n&&c[i+1][j]==2)add(idx[i][j]+1,idx[i+1][j],1);
}
}else{
if(c[i][j]==2)add(idx[i][j],T,1);
else{
add(idx[i][j],idx[i][j]+1,1);
if(j+1<=m&&c[i][j+1]==2)add(idx[i][j]+1,idx[i][j+1],1);
if(j-1>=1&&c[i][j-1]==2)add(idx[i][j]+1,idx[i][j-1],1);
}
}
}
}dinic();
printf("%d
",ans);
return 0;
}
第三题
我们注意到不能单独计算i比j强的概率并装包
因为概率之间会相互影响
所以我们不妨枚举每个点在那个区间里
不难发现其他点对于这个点只会有三种情况
win，lose，in(在区间里)
不妨设f(i,j)表示有i个点比当前点强且有j个点和当前点在一个区间里
转移的时候分情况装包就可以了
之后我们注意到对于一个状态f(i,j)，当前点的排名可能是i+1->i+j+1
而且概率都是f(i,j)*P/(j+1) P是当前点在这个区间的概率
然后贡献给Ans(i)就可以了
时间复杂度O(n^5),考试的时候时间不够没有调出来(现在貌似被OJ卡了常数?
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define eps 1e-10
#define fastcall __attribute__((optimize("-O3")))
#define IL __inline__ __attribute__((always_inline))
using namespace std;
const int maxn=162;
int n,cnt=0;
int d[maxn];
struct OP{
int L,R;
}c[maxn];
double g[maxn];
double f[82][82];
fastcall IL int Get_pos(int v){
int L=1,R=cnt;
while(L<R){
int mid=L+((R-L+1)>>1);
if(d[mid]<=v)L=mid;
else R=mid-1;
}return L;
}
double Min(double L,double R){return L<R?L:R;}
double Max(double L,double R){return L>R?L:R;}
fastcall IL double Get_win(int L,int R,int i){
if(c[i].L>=L)return 0;
return (double)(Min(c[i].R,L)-c[i].L)/(c[i].R-c[i].L);
}
fastcall IL double Get_lose(int L,int R,int i){
if(c[i].R<=R)return 0;
return (double)(c[i].R-Max(c[i].L,R))/(c[i].R-c[i].L);
}
fastcall IL double Get_in(int L,int R,int i){
if(c[i].L>=R||c[i].R<=L)return 0;
return (double)(Min(c[i].R,R)-Max(c[i].L,L))/(c[i].R-c[i].L);
}
fastcall IL void Get_f(int L,int R,int now){
double P=(double)(R-L)/(c[now].R-c[now].L);
memset(f,0,sizeof(f));f[0][0]=1;
for(int i=1;i<=n;++i){
if(i==now)continue;
double p1=Get_win(L,R,i);
double p2=Get_lose(L,R,i);
double p3=Get_in(L,R,i);
for(int j=i;j>=0;--j){
for(int k=i-j;k>=0;--k){
f[j][k]=f[j][k]*p1;
if(j>=1)f[j][k]=f[j][k]+f[j-1][k]*p2;
if(k>=1)f[j][k]=f[j][k]+f[j][k-1]*p3;
}
}
}
for(int i=0;i<n;++i){
for(int j=0;j<n-i;++j){
double tmp=f[i][j];
if(fabs(tmp)<eps)continue;
tmp=tmp*P/(j+1);
for(int k=0;k<=j;++k){
g[i+k]=g[i+k]+tmp;
}
}
}return;
}
int main(){
freopen("gg.in","r",stdin);
freopen("gg.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d%d",&c[i].L,&c[i].R);
d[++cnt]=c[i].L;d[++cnt]=c[i].R;
}sort(d+1,d+cnt+1);
cnt=unique(d+1,d+cnt+1)-d-1;
for(int i=1;i<=n;++i){
memset(g,0,sizeof(g));
int L=Get_pos(c[i].L),R=Get_pos(c[i].R);
for(int j=L;j<R;++j)Get_f(d[j],d[j+1],i);
for(int j=0;j<n;++j)printf("%.6lf ",g[j]);
printf("
");
}return 0;
}
最近两天的题目没什么好说的QAQ
都是很基础的东西，推一推就可以写了
基本上拍过了就A了QAQ
概率还是弱，如果上午一遍写对的话就AK了
有时间补补概率。。