十五天集训总结（附模拟考总结）

87 阅读 0 评论 58 点赞

我是靠谱客的博主冷艳大山，最近开发中收集的这篇文章主要介绍十五天集训总结（附模拟考总结），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

模拟考总结

T1-小R 与三角形

小 R 所在的小镇有 n 个村落，这 n 个村落分布在一个圆周上，这些村落之
间两两有直达的小路，小路可能相交，但不存在三条路交于一点。现在小 R 正好
放暑假了，每天都在村落间游荡。一天，他发现可以从一个非村落的点出发，在
不经过村落的情况下经过三条小路再回到这个点。于是他很好奇，一共有多少个
这样的回路呢

解题思路

简单推一下就知道只要从n个点里选6个就一定能构成不同的三角形
所以答案就是 $C_n^6$ ，十分钟就A掉了

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
long long C[N][N];
void init(int n)
{
for(int i=0;i<=n;i++)
C[i][0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=i;j++)
{
C[i][j]=C[i-1][j-1]+C[i-1][j];
}
}
}
int main()
{
freopen("triangle.in","r",stdin);
freopen("triangle.out","w",stdout);
int n;
cin>>n;
init(n);
cout<<C[n][6]<<endl;
return 0;
}

T2-小R与硬币

小 R 暑假很闲，有一天来到火星上，他有收集硬币的习惯。于是他将火星
上所有的硬币都收集起来了，一共有 n 个：面值分别为 a1,a2… an。小 R 在机
场看到了一个特别喜欢的礼物，想买来送给小 L，这个礼物的价格是 X 元。小 R
很想知道为了买这个礼物他的哪些硬币是必须被使用的，即小 R 必须放弃收集好
的哪些硬币种类。飞机场不提供找零，只接受恰好 X 元

解题思路

原本只想写40分的，结果数据水变成了60分，
也就是枚举每个数是否能不选，然后做背包

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f[20020];
int n,x;
int a[1000020];
int vis[120020];
int top=0,ans[120000];
bool cmp(int x,int y)
{
return x<y;
}
int main()
{
freopen("coin.in","r",stdin);
freopen("coin.out","w",stdout);
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++)
{
f[0]=1;
for(int k=1;k<=x;k++)
f[k]=0;
for(int j=1;j<=n;j++)
{
if(j==i) continue;
for(int k=x;k>=a[j];k--)
f[k]+=f[k-a[j]];
}
if(f[x]==0&&vis[a[i]]==0)
{
vis[a[i]]=1;
ans[++top]=a[i];
}
}
printf("%dn",top);
for(int i=1;i<=top;i++)
printf("%d ",ans[i]);
return 0;
}

正解

代填：

T3-小R 与回家

小 R 在火星玩累了，打算回家，这是一个时空旅行的故事。
小 R 要从火星（编号为 1）回到地球（编号为 n），宇宙中一共有 n 个星球，
星球之间有一些航线，但是有些星球间的航线可能导致时间倒流，并且星球之间
的航线并不保证可逆（即 a 到 b 的时间和 b 到 a 的时间不一定相同）。时空旅行
要求不能再出发时间之前到达最终目的地，否则会导致时空错乱，危及生命。
小 R 的飞船上有速度调节装置，可以用来改变星球间飞行的时间，即可以将
整次时空旅行中两两星球之间的时间增加或减少同一个整数。小 R 很想家，你能
帮助他找到最快回家的路吗

解题思路

无，写了个20分的特殊情况还挂了
不粘代码了

T4-小 R 与模除

模除,一种不具交换性的二元运算可写作有时也称作，该运算表示求两个数字相除的余数，也称取余运算。在语言中用“%”来表示。
小构造了一个长度为n的数组，的第个元素（a数组的下标从开始计算）。比如当时，现在小要进行组询问，每次查询给定两个参数。问。对于每个查询，请告诉小从到中数组元素的最大值。

解题思路：

40%可以用st表预处理
然后考试时推出了一个规律，但是数组开小了，只有40pts
但是开大之后也只有70pts，不明原因WA

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL LN=1e5+500;
LL n,m;
LL st[LN][22];
void prework(LL n)
{
for(LL i=1;i<=n;i++)
st[i][0]=(n%i);
LL t=log(n)/log(2)+1;
for(LL j=1;j<t;j++)
for(LL i=1;i<=n-(1<<j)+1;i++)
st[i][j]=max(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
LL query(LL l,LL r)
{
LL t=log(r-l+1)/log(2);
return max(st[l][t],st[r-(1<<t)+1][t]);
}
LL get_range(LL x)
{
LL l=2,r=n+1,mid,ans=-1;
while(l<=r)
{
LL mid=(l+r)>>1;
if(n/mid+1<=x)
{
ans=mid;
r=mid-1;
}
else l=mid+1;
}
return ans;
}
int main()
{
freopen("Modulus.in","r",stdin);
freopen("Modulus.out","w",stdout);
scanf("%lld%lld",&n,&m);
if(n<=1e5)
{
prework(n);
while(m--)
{
LL l,r;
scanf("%lld%lld",&l,&r);
printf("%lldn",query(l,r));
}
}
else
{
prework(100050);
while(m--)
{
LL l,r;
scanf("%lld%lld",&l,&r);
if(l==r)
{
printf("%lldn",(n%l));
continue;
}
if(r<=1e5)
{
printf("%lldn",query(l,r));
continue;
}
LL posl=get_range(l);
LL posr=get_range(r);
if(posl==posr)
{
printf("%lldn",n%l);
continue;
}
else
{
printf("%lldn",max(n%l,n%(n/posr+1)));
continue;
}
}
}
return 0;
}

总结

基本把能打的分打了，但是还不够细心