首页 > 其他分享 >[游记]暑假集训6-2022

[游记]暑假集训6-2022

时间:2022-08-18 21:27:06浏览次数:59  
标签:ch return 2022 int double WR 暑假 include 集训

久违的Rank1

A.  接力比赛

比较显然的 $\operatorname{DP}$,两个 $01$ 背包解决问题

 

 

#include<cstdio>
#include<cstring>
#include<string>
#define WR WinterRain
#define int long long
using namespace std;
const int WR=1001000,INF=1e18;
struct Lets_Find_A_Good_Student{
    int w,v;
}a[WR],b[WR];
int n,m,ans;
int dp1[WR],dp2[WR];
int sum1[WR],sum2[WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;
}
signed main(){
    // freopen("game.in","r",stdin);
    // freopen("game.out","w",stdout);
    n=read(),m=read();
    memset(dp1,-0x3f,sizeof(dp1));
    memset(dp2,-0x3f,sizeof(dp2));
    dp1[0]=dp2[0]=0;
    for(int i=1;i<=n;i++) a[i].w=read(),a[i].v=read(),sum1[i]=sum1[i-1]+a[i].w;
    for(int i=1;i<=m;i++) b[i].w=read(),b[i].v=read(),sum2[i]=sum2[i-1]+b[i].w;
    for(int i=1;i<=n;i++){
        for(int j=sum1[i];j>=a[i].w;j--){
            dp1[j]=max(dp1[j],dp1[j-a[i].w]+a[i].v);
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=sum2[i];j>=b[i].w;j--){
            dp2[j]=max(dp2[j],dp2[j-b[i].w]+b[i].v);
        }
    }
    for(int i=0;i<=max(sum1[n],sum2[m]);i++) ans=max(ans,dp1[i]+dp2[i]);
    printf("%lld\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
View Code

 

B.  树上竞技


按照边去考虑,如果在一条边 $E$ 的两侧分别有 $x$ 和 $m-x$ 个关键点,

不妨令 $x\leqslant m-x$ 那么最后的汇聚点一定在 $m-x$ 这个方向,

这样可以只让 $x$ 条边经过 $E$,代价较小

然后设某条边两侧分别共有 $s$ 和 $n-s$ 个点,容易发现我们需要求

$$\sum\limits_{i=1}^{m-1}\min\{i,m-i\}\times C_{s}^{i}C_{n-s}^{m-i}$$

发现 $\min$ 不是很好处理,考虑把它拆开来,还要加上 $m$ 为偶数的情况,用 $\operatorname{DFS}$ 预处理节点子树大小,原式可以化成

$$ans=\sum\limits_{u=2}^{n}\sum\limits_{i=1}^{\frac{m-1}{2}}i\times C_{size[u]}^{i}C_{n-size[u]}^{m-i}+i\times C_{size[u]}^{m-i}C_{n-size[u]}^{i}+[m\%2==0]\frac{m}{2}\times C_{s}^{\frac{m}{2}}C_{n-s}^{\frac{m}{2}}$$

后面的一小点式子可以暴力硬扫,考虑前面的怎样优化

不妨设 $k=\frac{m}{2}$,发现比较显然地,$\sum\limits_{i=1}^{k}i\times C_{s}^{i}C_{n-s}^{m-i}=s\sum\limits_{i=1}^{k}C_{s-1}^{i-1}C_{n-s}^{m-i}$

不妨令 $f(s)=\sum\limits_{i=1}^{k}C_{s-1}^{i-1}C_{n-s}^{m-i}$,那么答案就是 $\sum\limits_{u=2}^{n}f(size[u])+ f(n-size[u])$

考虑如何求出 $f(s)$,发现它的组合意义是 $n-1$ 个物品里选择了 $m-1$ 个,前面 $s-1$ 个物品中选择了 $k-1$ 个的方案数

如何递推 $f(s)$ ?

不难发现,$f(s)$ 变成 $f(s+1)$ 变少的部分就是前 $s-1$ 个点中选择 $k-1$ 个,选择了 $s$ 为第 $k$ 个点,后面 $n-s-1$ 个点里选择了 $m-k-1$ 个点

这是为什么呢?我们考虑如果没有选择 $s$ 作为第 $k$ 个点

那么前 $s$ 个点中选择 $k-1$ 个点和前 $s-1$ 个点中选择 $k-1$ 个是等价的

所以必须让 $s$ 作为第 $k$ 个点被选择,多出来的方案数根据乘法原理就是 $C_{s-1}^{k-1}C_{n-s-1}^{m-k-1}$

也就是说 $f[s+1]=f[s]+C_{s-1}^{k-1}C_{n-s-1}^{m-k-1}$

统计答案即可

题解好像有点毛病=_=

 

#include<cstdio>
#include<cstring>
#include<string>
#define WR WinterRain
#define int long long
using namespace std;
const int WR=2001000,INF=1e18,mod=1e9+7;
struct Edge{
    int pre,to;
}edge[WR];
int n,m,ans;
int head[WR],tot;
int sze[WR];
int f[WR];
int g[WR],ny[WR];
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;
}
int quick_pow(int a,int b){
    int base=a,res=1;
    while(b){
        if(b&1) res=res*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return res;
}
void add(int u,int v){
    edge[++tot].pre=head[u];
    edge[tot].to=v;
    head[u]=tot;
}
void dfs(int u,int root){
    // printf("%lld %lld\n",u,root);
    sze[u]=1;
    for(int i=head[u];i;i=edge[i].pre){
        int v=edge[i].to;
        if(v==root) continue;
        dfs(v,u);
        sze[u]+=sze[v];
        }
}
int C(int n,int m){
    if(m>n||m<0||n<0) return 0;
    // printf("%lld %lld\n",n,m);
    return g[n]*ny[m]%mod*ny[n-m]%mod;
}
signed main(){
    freopen("meeting.in","r",stdin);
    freopen("meeting.out","w",stdout);
    g[0]=ny[0]=1;
    for(int i=1;i<WR;i++) g[i]=g[i-1]*i%mod;
    ny[WR-1]=quick_pow(g[WR-1],mod-2);
    for(int i=WR-2;i>=1;i--) ny[i]=ny[i+1]*(i+1)%mod;
    // for(int i=1;i<=100;i++) printf("%lld\n",ny[i]);
    n=read(),m=read();
    for(int i=1;i<n;i++){
        int fa=read();
        add(fa,i+1);add(i+1,fa);
    }
    dfs(1,0);
    if(m%2==0){
        for(int i=2;i<=n;i++){
            ans=(ans+C(sze[i],m/2)*C(n-sze[i],m/2)%mod*(m/2)%mod)%mod;
        }
    }
    int k=(m-1)/2;
    if(k) f[1]=C(n-1,m-1);
    for(int i=1;i<n;i++){
        f[i+1]=(f[i]-C(i-1,k-1)*C(n-i-1,m-k-1)%mod+mod)%mod;
    }
    for(int i=1;i<=n;i++) f[i]=f[i]*i%mod;
    for(int i=2;i<=n;i++) ans=(ans+f[sze[i]]+f[n-sze[i]])%mod;
    printf("%lld\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}   
View Code

 

C. 虚构推理

题解里说的方法很好,但我直接暴力

首先枚举小时,再枚举分针偏角

找 $\operatorname{lower_bound}$ 然后查询就行

 

#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define WR WinterRain
#define int long long
using namespace std;
const int WR=1001000;
struct Clock{
    int h,m,s;
}clc[WR];
int n;
double mnt[WR],hor[WR];
double ans;
int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){
        if(ch=='-') w=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        s=(s<<1)+(s<<3)+ch-48;
        ch=getchar();
    }
    return s*w;
}
signed main(){  
    freopen("unreal.in","r",stdin);
    freopen("unreal.out","w",stdout);
    n=read();ans=1e9;
    for(int i=1;i<=n;i++) clc[i].h=read(),clc[i].m=read(),clc[i].s=read();
    for(int i=1;i<=n;i++){
        mnt[i]=clc[i].s*0.1+clc[i].m*6.0;
        hor[i]=clc[i].h%12*30.0+mnt[i]/12.0;
    }
    sort(hor+1,hor+n+1);
    sort(mnt+1,mnt+n+1);
    for(int i=0;i<=360;i+=30){
        for(double j=0;j<=360;j+=0.01){
            int tmphor=lower_bound(hor+1,hor+1+n,(i+j/12)>180?i+j/12-180:i+j/12+180)-hor-1;
            int tmpmnt=lower_bound(mnt+1,mnt+1+n,j>180?j-180:j+180)-mnt-1;
            int nxthor=tmphor+1,nxtmnt=tmpmnt+1;
            if(nxthor>n) nxthor=1; 
            if(nxtmnt>n) nxtmnt=1;
            if(tmphor==0) tmphor=n; 
            if(tmpmnt==0) tmpmnt=n;
            double reshor1=fabs(hor[tmphor]-(i+j/12)),reshor2=fabs(hor[nxthor]-(i+j/12));
            if(reshor1>180.0) reshor1=360.0-reshor1;
            if(reshor2>180.0) reshor2=360.0-reshor2;
            double reshor=max(reshor1,reshor2);
            double resmnt1=fabs(mnt[tmpmnt]-j),resmnt2=fabs(mnt[nxtmnt]-j);
            if(resmnt1>180.0) resmnt1=360.0-resmnt1;
            if(resmnt2>180.0) resmnt2=360.0-resmnt2;
            double resmnt=max(resmnt1,resmnt2);
            ans=min(ans,max(reshor,resmnt));
        }
    }
    printf("%.8lf\n",ans);
    fclose(stdin);
    fclose(stdout);
    return 0;
}
View Code

 

正解放在下面

 

 

 

 

 

这里是zcy大佬的题解

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
using namespace std;
const int maxn=5e4+10;
const double eps=1e-6;
int N,ftop=0;double a[maxn<<1],b[maxn<<1],ans=180,f[maxn];
deque<double>q;
int qd(){
    int rt=0;char c=getchar();
    while(c<'0'||c>'9')  c=getchar();
    while('0'<=c&&c<='9')  rt=(rt<<3)+(rt<<1)+c-48,c=getchar();
    return rt;
}
void _m(double &x,const double &y){x=x-y*((int)x/(int)y);}
void change(double l,double r){
    if(ftop&&f[ftop]>=l)  f[ftop]=r;
    else f[++ftop]=l,f[++ftop]=r;
}
bool ask(double l,double r){
    if(!ftop)  return 0;
    if(r-l>=30)  return 1;
    l*=12,r*=12;_m(l,360),_m(r,360);
    if(r<l)  r+=360;
    int t=lower_bound(f+1,f+ftop+1,l)-f;
    if(t<=ftop&&(!t&1||r>=f[t+1]))  return 1;
    l+=360,r+=360;
    t=lower_bound(f+1,f+ftop+1,l)-f;
    if(t<=ftop&&(!t&1||r>=f[t+1]))  return 1;
    return 0;
}
int calc(double t){
    q.clear();ftop=0;
    for(int i=1;i<=2*N;i++){
        q.push_front(b[i]);
        while(!q.empty()&&q.front()-q.back()>2*t)  q.pop_back();
        if(q.size()>=N)  change(q.front()-t,q.back()+t);
    }
    if(!ftop)  return 0;
    q.clear();
    for(int i=1;i<=2*N;i++){
        q.push_front(a[i]);
        while(!q.empty()&&q.front()-q.back()>2*t)  q.pop_back();
        if(q.size()>=N&&ask(q.front()-t,q.back()+t))  return 1;
    }
    return 0;
}
int main(){
    freopen("unreal.in","r",stdin);
    freopen("unreal.out","w",stdout);
    N=qd();
    for(int i=1;i<=N;i++){
        int x=qd(),y=qd(),z=qd();
        a[i]=(x%12)*30+y/2.0+z/120.0;_m(a[i],360);
        b[i]=y*6+z/10.0;_m(b[i],360);
    }
    sort(a+1,a+N+1);sort(b+1,b+N+1);
    for(int i=1;i<=N;i++)  a[N+i]=a[i]+360,b[N+i]=b[i]+360;
    for(double x=180;x>=eps;x/=2)  if(ans>=x&&calc(ans-x))  ans-=x;
    printf("%.5lf\n",ans);
    return 0;
}
View Code

 

D. 记忆碎片

 

 

 

 不会,贺的

 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double db;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const int mod=1e9+7;
const ull bs=131;
inline int read(){
    int x=0,w=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c<='9'&&c>='0'){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*w;
}
int n;
int tot;
vector<int> S[40005],tmp;
map<vector<int>,int> mp;
int cnt_edge[40005];
bool mark[1605];
void dfs(int l,int r){
    if(!r){
        S[++tot]=tmp;
        mp[S[tot]]=tot;
        for(int i:S[tot]){
            cnt_edge[tot]+=i*(i-1)/2;
        }
        return;
    }
    if(l>r) return;
    for(int i=l;i<=r;++i){
        tmp.push_back(i);
        dfs(i,r-i);
        tmp.pop_back();
    }
}
ll dp[1605][40005];
int main(){
    freopen("tree.in","r",stdin);
    freopen("tree.out","w",stdout);
    n=read();
    for(int i=1;i<n;++i) mark[read()]=1;
    dfs(1,n);
    dp[0][1]=1;
    for(int i=1;i<=n*(n-1)/2;++i){
        for(int j=1;j<=tot;++j){
            if(!dp[i-1][j]) continue;
            if(mark[i]){
                //树边合并
                for(int x=0;x<S[j].size();++x){
                    for(int y=x+1;y<S[j].size();++y){
                        tmp.clear();
                        tmp.push_back(S[j][x]+S[j][y]);
                        for(int z=0;z<S[j].size();++z){
                            if(z!=x&&z!=y) tmp.push_back(S[j][z]);
                        }
                        sort(tmp.begin(),tmp.end());
                        int nxt=mp[tmp];
                        dp[i][nxt]=(dp[i][nxt]+dp[i-1][j]*S[j][x]%mod*S[j][y]%mod)%mod;
                    }
                }
            }
            else{
                //非树边随便连一条
                dp[i][j]=(dp[i][j]+dp[i-1][j]*(cnt_edge[j]-(i-1))%mod)%mod;
            }
        }
    }
    printf("%lld\n",dp[n*(n-1)/2][tot]);
    return 0;
}
SoyTony大佬的代码

 

标签:ch,return,2022,int,double,WR,暑假,include,集训
From: https://www.cnblogs.com/WintersRain/p/16599897.html

相关文章

  • 2022-08-18 第二小组 张鑫 学习笔记
    实训四十天1.学习重点1.MySQL常用函数2.数据库设计3.JDBC2.学习心得今天的内容主要是JDBC,四天没有用idea,属实有点生疏了,要多多练习才行3.学习内容MySQL常用函数......
  • 【考后总结】8.18 暑假模拟27
    概述又名:暑假集训6得分:\(40+20+20+10=90\)rk11赛时打得比较懵,很多部分分想了很久才打出来。题解T1接力游戏题意给序列\(a,b\),每个序列包含两个属性\(w,v\),从......
  • 2022-08-18 第二小组 张晟源(JDBC)
    JDBC一,JDBC数据的持久化把数据永久的保存起来,主要的方式是存在硬盘上。持久化的实现过程大部分是通过数据库来完成的 JDBC1.数据库的驱动导入外部驱动需要引入my......
  • 2022-8-18第一组孙乃宇JDBC
    JDBC概念:JavaDataBaseconnectivityJava数据库连接,Java语言操作数据库JDBc本质∶其实是官方(sun公司)定义的一套操作所有关系型数据库的规则,即接口。各个数据库商......
  • 2022/8/18 总结
    A.P2587[ZJOI2008]泡泡堂好家伙,久违的贪心所以说挂了;Solution古人的智慧;但实际上这道题和田忌赛马有所区别,已知有一种比较优的方法是用己方最鶸的换掉敌方最强......
  • 2022-08-18 第四组 王佳齐 学习笔记
    思维导图MySQL常用函数聚合函数count:计数。count(*)≈count(1)>count(主键)count(*):MySQL对count(*)底层优化,count(0)。count(1)count(主键)count(字段)min:最......
  • 2022-08-18 第二组刘禹彤 学习笔记
    打卡35天  ###学习内容MySQL常用函数聚合函数count:计数------------count(*)≈count(1)>count(主键)>count(字段)count(*):MySQL对count(*)底层优化----count(min:最小值......
  • IntelliJ IDEA 2022解决控制台中文乱码
    1.打开设置单击Settings  2.在Editor下面FileEncodings中的projectencoding设置为GBK其他设置为UTF-8  3.在General下面的Console里DefaultEncoding更改为......
  • 2022巅峰极客初赛 Misc wp
    一开始做misc1没啥思路,转去misc2,结果一下子给电脑搞废了,太哈人了,以后对注册表都有心理阴影了,还好队友给力,躺进决赛,这里的wp都是今早修完电脑后再复现的。。。easy_Forensi......
  • 8.18集训
    回到了Luogu,继续刷COCI……上午事实证明后三题是可做题,前三题不大可做。T1P6405开始码了一个相邻的树木连边,边权设为相等的时间,然后点边互换跑连通块算大小,默认恒等......