作者： | 来源：互联网 | 2023-10-10 18:36
篇首语：本文由编程笔记#小编为大家整理，主要介绍了noip2005提高组 题解相关的知识，希望对你有一定的参考价值。
水 正经题解
最多的奖学金
https://www.luogu.com.cn/problem/P1051
就水题，但我还是wa了一个点[？？]
大概就是排序的时候把“>"换成 "<"就过了，应该是输出时优先输出排前面的[无可奈何]
代码就不贴了
过河
https://www.luogu.com.cn/problem/P1052
这道题状态转移方程很显然。
f[i]表示到第i个点经过的最少石子数：f[i]=min(f[i],f[i-j]+a[i])；j取s~t，a[i]表示当前点是否有石子。
f注意要取到l+t。
因为可以直接跳过第l个点。如果第l个点为石子的话，会对结果产生影响。
但是！！
这道题的范围很大 109，直接dp肯定会爆掉。
所以就有个小优化。（听说叫什么离散化？我也不知道）
考虑到虽然l范围很大，但题目给的m只有100，s、t都不大于10。很显然：
一定有至少两个石子隔得很远，中间都是可以随便跳的，对我们求石子的结果是没有影响的。
所以，我们只需要把隔得很远的石子中间路程减掉，就可以大大的优化了。
至于怎么减掉。考虑到s、t处于1到10之间，可以剪掉而对结果无影响的，就是s、t的倍数，取模就行了。
于是，2520这个神奇的数字就出现啦！（1~10的最小公倍数 我一开始就是这里搞错了）。
附上代码
#include
using namespace std;
int a[105],d[105],st[500000];
int f[500000];
int main()
{
// freopen("river.in","r",stdin);
// freopen("river.out","w",stdout);
int l,s,t,m;
cin>>l>>s>>t>>m;
for(int i=1;i<=m;i++)
cin>>a[i];
sort(a+1,a+m+1);
for(int i=1;i<=m;i++)
d[i]=(a[i]-a[i-1])%2520;
for (int i=1;i<=m;i++)
{
a[i]=a[i-1]+d[i];
st[a[i]]=1;
}
l=a[m];
for(int i=0;i<=l+t;i++) f[i]=m;
f[0]=0;
for(int i=1;i<=l+t;i++)
{
for(int j=s;j<=t;j++)
{
if(i-j>=0)
f[i]=min(f[i],f[i-j]);
f[i]+=st[i];
}
}
int ans=m;
for(int i=l;i ans=min(ans,f[i]);
cout< return 0;
}
篝火晚会
https://www.luogu.com.cn/problem/P1053
这道题乍一看无从下手，但是仔细多品味一下，会发现就题目意思比较坑而已。
本质模拟？
就判断一下左右两边能否和谐地安排好同一个人，然后再从正反两种顺序判断是不是已经达到目标状态，再输出所需步数更小的那个。
为什么要正反都判断呢？大概是因为它是个圈？[muji]
直接贴代码吧
#include
using namespace std;
const int N=50005;
int l[N],r[N],a[N],b[N],c[N];
bool vis[N];
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&l[i],&r[i]);
a[1]=1,a[2]=l[1];
for(int i=2;i<=n;i++)
{
if(a[i-1]==l[a[i]]) a[i+1]=r[a[i]];
else if(a[i-1]==r[a[i]]) a[i+1]=l[a[i]];
else
{
cout<<-1;
return 0;
}
}
for(int i=1;i<=n;i++)
{
b[(a[i]-i+n)%n]++;
c[(a[n-i+1]-i+n)%n]++;
}
int ans=0;
for(int i=0;i ans=max(ans,max(b[i],c[i]));
cout< return 0;
}
等价表达式
https://www.luogu.com.cn/problem/P1054
就是栈的一个应用 两个栈 一个保存符号，一个保存数字。
如果当前运算符优先级小于栈顶的，就进行一次运算。结果入栈。知道大于等于了。
如果是"("就直接入栈好了，直到碰到一个‘‘)‘‘。
这道题我最纠结的是a怎么处理。其实用一个质数的话就没太大问题了（当然如果一定要用2这种素数的话呢也是无可奈何的）。
没有附代码的原因绝对不是因为我还没有打完……我真的没打完，它看着容易，其实很难打的。
求放过[诚恳]。
磨磨蹭蹭一晚上，在电脑重启两次的情况下我终于写完啦！！
第一篇博客，贴上轰总照片纪念一下吧 不是私欲
京公网安备 11010802041100号