10.1 模拟赛-白红宇

10.1 模拟赛

阅读量：5162 次

发布时间：2019-06-13

本文共 3157 字，大约阅读时间需要 10 分钟。

由于算错了inf 又ak失败了过于菜

T1 年轮蛋糕 loj 2758

题目大意：

n个数构成的环把这个环分成三段使最小的最大

求这个最小段的和的最大值

思路：

可以想到二分因为log方可以过

所以可以二分长度后lower_bound找断点

或者使用滑动窗口

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              10 #define inf 213906214311 #define ll long long12 #define MAXN 20010013 using namespace std;14 inline int read()15 {16 int x=0,f=1;char ch=getchar();17 while(!isdigit(ch)) { if(ch=='-')f=-1;ch=getchar();}18 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}19 return x*f;20 }21 ll n,g[MAXN],s[MAXN],l,r,mid,ans;22 bool cheque(ll x)23 {24 ll a,b,c,ax,bx;25 if(x>s[n]/2) return 0;26 for(int i=1;i<=n;i++)27 {28 a=lower_bound(s+1,s+2*n+1,x+s[i-1])-s,ax=s[a]-s[i-1];29 if(a
               
                >1;44 if(cheque(mid)) ans=mid,l=mid+1;45 else r=mid-1;46 }47 printf("%lld",ans);48 }

View Code

T2 最佳团体 bzoj 4753

题目大意：

在树上选k个人（联通且于根相连）使这写人的a权值和/b权值和最大

思路：

分数规划二分之后dp

树上背包dp即可

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              #define inf 1001000#define ll long long#define MAXN 2600#define eps 1e-5using namespace std;inline int read(){ int x=0,f=1;char ch=getchar(); while(!isdigit(ch)) { if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();} return x*f;}int k,n,prc[MAXN],val[MAXN],fa[MAXN],sz[MAXN];double v[MAXN],dp[MAXN][MAXN];int nxt[MAXN],fst[MAXN],to[MAXN],cnt;void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}void dfs(int x){ sz[x]= x>0?1:0,dp[x][sz[x]]=v[x]; for(int i=fst[x];i;i=nxt[i]) { dfs(to[i]); for(int j=min(sz[x],k);j>=0;j--) for(int o=min(sz[to[i]],k);o>=0;o--) if(j+o<=k) {dp[x][j+o]=max(dp[x][j+o],dp[x][j]+dp[to[i]][o]);} sz[x]+=sz[to[i]]; }}bool cheque(double x){ for(int i=0;i<=n;i++) for(int j=0;j<=k+1;j++) dp[i][j]=-inf; for(int i=1;i<=n;i++) v[i]=val[i]-prc[i]*x; dfs(0);return dp[0][k]>=0;}int main(){ k=read(),n=read(); for(int i=1;i<=n;i++) {prc[i]=read(),val[i]=read(),fa[i]=read();add(fa[i],i);} double l=0.0,r=1000.0,ans,mid; while(l

View Code

T3 起床困难综合症

题目大意：

给n个运算求在0-m中的所有数经过运算后的最大值

思路：

按位贪心每一位设该位初值为0/1 模拟即可

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              10 #define inf 213906214311 #define ll long long12 #define MAXN 30010013 #define MOD 100000000714 using namespace std;15 inline int read()16 {17 int x=0,f=1;char ch=getchar();18 while(!isdigit(ch)) { if(ch=='-')f=-1;ch=getchar();}19 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}20 return x*f;21 }22 int n,m,opt[MAXN],g[MAXN],ans,res,x,y,tmp;23 int main()24 {25 n=read(),m=read();char s[6];26 for(int i=1;i<=n;i++)27 {28 scanf("%s",s);if(s[0]=='A') opt[i]=0;29 else opt[i]= s[0]=='O'?1:2;30 g[i]=read();31 }32 for(int t=30;t>=0;t--)33 {34 x=0,y=(1<