NOIP模拟66
2024-08-31 13:38:50
T1 接力比赛
解题思路
其实就是一个背包 DP ，也没啥好说的也就是一个优化，每次枚举之前的前缀和。
比较妙的就是一个 random_shuffle 可以整掉部分卡人的数据（但是好像 sort 一下效果更好。）
然而就算上面的方法不用也可以愉快的水过。。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=1e3+10,M=N*N;
int n,m,ans,f1[M],f2[M],pre1[N],pre2[N];
struct Node{int w,v;}a[N],b[N];
signed main()
{
freopen("game.in","r",stdin); freopen("game.out","w",stdout);
n=read(); m=read();
for(int i=1;i<=n;i++) a[i].w=read(),a[i].v=read(),pre1[i]=pre1[i-1]+a[i].w;
for(int i=1;i<=m;i++) b[i].w=read(),b[i].v=read(),pre2[i]=pre2[i-1]+b[i].w;
memset(f1,-1,sizeof(f1)); memset(f2,-1,sizeof(f2)); f1[0]=f2[0]=0;
for(int i=1;i<=n;i++)
for(int j=pre1[i-1];j>=0;j--)
if(~f1[j]) f1[j+a[i].w]=max(f1[j+a[i].w],f1[j]+a[i].v);
for(int i=1;i<=m;i++)
for(int j=pre2[i-1];j>=0;j--)
if(~f2[j]) f2[j+b[i].w]=max(f2[j+b[i].w],f2[j]+b[i].v);
for(int i=1;i<=max(pre1[n],pre2[m]);i++)
if((~f1[i])&&(~f2[i]))
ans=max(ans,f1[i]+f2[i]);
printf("%lld",ans);
return 0;
}
T2 树上竞技
解题思路
对于一条边而言两侧有 \(x,y\) 个关键点且一定满足 \(x+y=m\) 假设 \(x<y\) 那么一定会让那 \(x\) 个点经过这条边。
假设一条边的两边分别有 \(s,n-s\) 个点 答案就是 \(\sum\limits_{i=1}^{m-1}\binom{i}{s}\binom{m-i}{n-s}\min(i,m-i)\)
\[\displaystyle ans=\sum_{i=1}^{\min(\frac{m-1}{2},s)}\binom{i}{s}\binom{m-i}{n-s}+\sum_{i=1}^{\min(\frac{m-1}{2},n-s)}\binom{i}{s}\binom{m-i}{n-s}+[m\bmod 2=0]\times\binom{\frac{m}{2}}{s}\binom{\frac{m}{2}}{n-s}\frac{m}{2}
\]
\]
对于柿子的最后一项直接暴算就可以，设 \(g(s)=\sum\limits_{i=1}^{\min(\frac{m-1}{2},s)}\binom{i}{s}\binom{m-i}{n-s}\)
于是我们只需要递推出 \(g(s)\) 就好了 \(g(s)=\sum\limits_{i=1}^{\min(\frac{m-1}{2},s)}\binom{s-1}{i-1}\binom{m-i}{n-s}\) 发现对于 \(g(s)\) 和 \(g(s+1)\) 而言两个柿子是有公共部分的。
设 \(k=\frac{m-1}{2}\) 就有 \(g(s)=g(s-1)-\binom{k-1}{s-2}\binom{m-k-1}{n-i}\)
接下来就直接干柿子就好了。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int mod=1e9+7,N=1e6+10,INF=1e18;
int n,m,ans,k,g[N],siz[N],fac[N],ifac[N],fa[N];
int tot,head[N],ver[N<<1],nxt[N<<1];
void add_edge(int x,int y)
{
ver[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
int power(int x,int y,int p=mod)
{
int temp=1;
while(y)
{
if(y&1) temp=temp*x%mod;
x=x*x%mod; y>>=1;
}
return temp;
}
int C(int x,int y){if(x<y) return 0;return fac[x]*ifac[y]%mod*ifac[x-y]%mod;}
void dfs(int x)
{
siz[x]=1;
for(int i=head[x];i;i=nxt[i])
{
int to=ver[i],temp=0; dfs(to);
siz[x]+=siz[to];
ans=(ans+g[siz[to]]*siz[to]%mod+g[n-siz[to]]*(n-siz[to])%mod)%mod;
if(!(m&1)) ans=(ans+C(siz[to],m/2)*C(n-siz[to],m/2)%mod*(m/2))%mod;
}
}
signed main()
{
freopen("meeting.in","r",stdin); freopen("meeting.out","w",stdout);
n=read(); m=read(); k=(m-1)/2;
for(int i=2;i<=n;i++) fa[i]=read(),add_edge(fa[i],i);
fac[0]=ifac[0]=1; for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
ifac[n]=power(fac[n],mod-2); for(int i=n-1;i>=1;i--) ifac[i]=ifac[i+1]*(i+1)%mod;
if(k>0) g[1]=C(n-1,m-1); for(int i=2;i<=n;i++) g[i]=(g[i-1]-C(i-2,k-1)*C(n-i,m-k-1)%mod+mod)%mod;
dfs(1); printf("%lld",ans);
return 0;
}
T3 虚构推理
解题思路
关于正解二分。。。不会。。
但是仔细观察题目好像是相对误差，因此我们可以尝试卡精度，枚举每一个时间，然后暴算。
具体思路就是现对于给出的时间求出来相应的时针分针的角度，然后分别进行排序。
对于每一个枚举到的时间同样也要算出时针分针的角度（注意这里以及以下的角度都是相对于十二点而言的）
然后对于距离某一种指针最远的指针，我们取他加或者减去 \(180^。\) 的角度，然后在之前排好序的数组上面二分一个前驱后继。
这前驱后继就是距离当前指针最远的点，为了防止某些玄学情况，我们设 a[0]=a[n],a[n+1]=a[1]
由于计算的时候搞一些度数有些麻烦，因此我们先不管正负，到最后统一恢复成正数并且判断是大角还是小角。。
code
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"<<endl
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=5e4+10,INF=1e9;
int n;
double a[N],b[N],ans=INF;
struct Node{int h,m,sec;}s[N];
void solve(double x,double y,double z)
{
double h=30.0*x+0.5*y+0.5*z/60.0,m=6.0*y+0.1*z,h2,m2;
h2=h; if(h2<180.0) h2+=180.0; else h2-=180.0;
m2=m; if(m2<180.0) m2+=180.0; else m2-=180.0;
int pos1=upper_bound(a+1,a+n+1,h2)-a-1;
int pos2=upper_bound(b+1,b+n+1,m2)-b-1;
double tmp1=180.0-h2+a[pos1],tmp3=180.0-m2+b[pos2];
double tmp2=180.0-a[pos1+1]+h2,tmp4=180.0-b[pos2+1]+m2;
if(tmp1<0) tmp1+=360.0; if(tmp1>=360) tmp1-=360.0;
if(tmp2<0) tmp2+=360.0; if(tmp2>=360) tmp2-=360.0;
if(tmp3<0) tmp3+=360.0; if(tmp3>=360) tmp3-=360.0;
if(tmp4<0) tmp4+=360.0; if(tmp4>=360) tmp4-=360.0;
tmp1=min(tmp1,360.0-tmp1); tmp2=min(tmp2,360.0-tmp2);
tmp3=min(tmp3,360.0-tmp3); tmp4=min(tmp4,360.0-tmp4);
ans=min(ans,max(max(tmp1,tmp2),max(tmp3,tmp4)));
}
signed main()
{
freopen("unreal.in","r",stdin); freopen("unreal.out","w",stdout);
n=read();
for(int i=1;i<=n;i++) s[i].h=read()%12,s[i].m=read(),s[i].sec=read();
for(int i=1;i<=n;i++) a[i]=s[i].h*30.0+s[i].m*0.5+s[i].sec*0.5/60.0,b[i]=s[i].m*6.0+s[i].sec*0.1;
sort(a+1,a+n+1); a[n+1]=a[1]; a[0]=a[n];
sort(b+1,b+n+1); b[n+1]=b[1]; b[0]=b[n];
for(int i=0;i<12;i++)
for(int j=0;j<60;j++)
for(double k=0;k<60;k+=0.01)
solve(i,j,k);
printf("%.6lf",ans);
return 0;
}
T4 记忆碎片
解题思路
先算出来 \(n\) 的所有整数划分，然后暴扫每一种权值。
对于某一权值情况只有两种，一种是已经联通的块之间的连边，直接计算方案数即可。
另一种就是将两个联通块链接起来的边，连完之后的集合也可以在整数划分中找到。
枚举整数划分以及查找的时候可以开一个 map 对于每一种划分映射一个编号，对于编号转移。
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define f() cout<<"Failed"
using namespace std;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
const int N=50,M=4e4+10,mod=1e9+7;
int n,m,all,f[N*N][M],e[M];
bool vis[N*N];
vector<int> v,s[M];
map<vector<int>,int> mp;
void dfs(int las,int res)
{
if(!res)
{
s[++all]=v; mp.insert(make_pair(v,all));
for(int i=0;i<v.size();i++)
e[all]=(e[all]+v[i]*(v[i]-1)/2)%mod;
return ;
}
for(int i=las;i<=res;i++)
{
v.push_back(i);
dfs(i,res-i);
v.pop_back();
}
}
signed main()
{
freopen("tree.in","r",stdin); freopen("tree.out","w",stdout);
n=read(); m=n*(n-1)/2;
for(int i=1,x;i<n;i++) x=read(),vis[x]=true;
dfs(1,n); f[0][1]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=all;j++)
if(f[i-1][j])
{
if(!vis[i]){f[i][j]=(f[i][j]+f[i-1][j]*(e[j]-i+1))%mod;continue;}
for(int p=0;p<s[j].size();p++)
for(int q=p+1;q<s[j].size();q++)
{
vector<int> temp;
int x=s[j][p],y=s[j][q];
temp.push_back(x+y);
for(int k=0;k<s[j].size();k++)
if(k!=p&&k!=q)
temp.push_back(s[j][k]);
sort(temp.begin(),temp.end());
int pos=mp.find(temp)->second;
f[i][pos]=(f[i][pos]+x*y%mod*f[i-1][j])%mod;
}
}
printf("%lld",f[m][all]);
return 0;
}
最新文章
- 由ArrayList构造函数源码引出的问题
- linux打开文件数量的查看方法
- [Android Exception A] – 1-The following classes could not be instantiated
- HUST 1010 The Minimum Length（KMP，最短循环节点，即i-Next[i]）
- linq性能剖析
- Oracle数据库之动态SQL
- GCD - Extreme (II)
- [转]Hibernate映射的基本操作
- u盘烧写后实际容量变小了
- 如何在关闭ssh连接的情况下，让程序继续运行？
- Mybatis入门1
- MySQL中InnoDB锁不住表的原因
- 2，linux入门到上手-ssh安装配置及虚拟机基本使用
- 20155208徐子涵《网络对抗》Exp2 后门原理与实践
- centos 支持安装libsodium
- 深入解密.NET（GC垃圾回收）
- Ubuntu下RabbitMQ安装
- 100-days: Six
- python SQLAlchemy对象映射和json.dumps无法序列化问题解决
- ping 命令 指定特定网卡 发送 ICMP 数据包