NOIP 2018

铺设道路

题目
一个非常可行的做法是最小值分治。
正解就是一个贪心：从前往后扫，如果当前这个坑比前面那个深，那么就消耗当前深度减前面的深度的代价，否则当前这个会被直接覆盖，不需要代价。

#include<bits/stdc++.h>
using namespace std;
int n,a,last,ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        if(a>last) ans+=(a-last);
        last=a;
    }
    cout<<ans;
    return 0;
}

货币系统

题目
先升序排序，然后从小到大枚举，如果当前的值能被之前的表示就跳过，否则答案加一。
具体实现完全背包就行了。

#include<bits/stdc++.h>
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
const int M=25001,N=101;
int f[M],a[N];
int main()
{
    for(int T=read(),n,ans,i,j;T;--T)
    {
        memset(f,0,sizeof f),n=read(),ans=0;
    for(i=1;i<=n;++i) a[i]=read();
    sort(a+1,a+n+1),f[0]=1;
    for(i=1;i<=n;++i) if(!f[a[i]]) for(++ans,j=a[i];j<=a[n];++j) f[j]|=f[j-a[i]];
        printf("%d\n",ans);
    }
}

赛道修建

题目
先二分一个长度\(lim\)。
然后每个点开一个multiset记录子树中传上来的链的长度。
\(\le lim\)的部分可以直接统计进答案。
其它的我们从小到大枚举，二分找到最小的满足两个加起来\(\le lim\)的，然后把两个统计进答案。
然后把集合中剩下的最长的链加上自己到父亲的距离传给父亲。
这个贪心的正确性是显然的。

#include<bits/stdc++.h>
#define pi pair<int,int>
#define pb push_back
using namespace std;
int read(){int x=0,c=getchar();while(!isdigit(c))c=getchar();while(isdigit(c))x=x*10+c-48,c=getchar();return x;}
const int N=50007;
vector<pi>E[N];int n,m,lim,ans;
int dfs(int u,int fa)
{
    multiset<int>s;
    for(auto[v,w]:E[u])
    if(v^fa)
        s.insert(dfs(v,u)+w);
    for(auto it=s.lower_bound(lim);it!=s.end();++it,s.erase(prev(it))) ++ans;
    for(auto it=s.begin();it!=s.end();)
    {
    auto p=s.lower_bound(lim-*it);
    if(p==it) ++p;
    if(p==s.end()){++it;continue;}
    ++ans,s.erase(p),++it,s.erase(prev(it));
    }
    return s.size()? *prev(s.end()):0;
}
int check()
{
    dfs(1,ans=0);
    return ans>=m;
}
int main()
{
    n=read(),m=read();int i,u,v,w,l=1,r=0;
    for(i=1;i<n;++i) u=read(),v=read(),r+=w=read(),E[u].pb(pi(v,w)),E[v].pb(pi(u,w));
    for(r/=m;l<=r;) lim=l+r>>1,check()? l=lim+1:r=lim-1;
    printf("%d",r);
}

旅行

题目
\(O(n^2)\)的做法还是不难想的，基环树的情况我们发现一定会有一条边不走。
先给边排个序，枚举删哪条边然后做就好了。
需要一定的剪枝/优化。这里就不写了。

#include<bits/stdc++.h>
#define pi pair<int,int>
#define pb push_back
using namespace std;
int read(){int x;scanf("%d",&x);return x;}
const int N=5007;
vector<pi>E[N];int ans[N],tmp[N],vis[N],ban,cnt;
void dfs(int u,int fa){vis[tmp[++cnt]=u]=1;for(auto[v,id]:E[u]) if(v^fa&&id^ban&&!vis[v]) dfs(v,u);}
void upd(int n)
{
    if(cnt^n)return;
    for(int i=1;i<=n;++i) if(tmp[i]<ans[i]) return swap(tmp,ans); else if(tmp[i]>ans[i]) return ;
}
int main()
{
    int n=read(),m=read(),i,u,v;memset(ans,0x3f,sizeof ans);
    for(i=1;i<=m;++i) u=read(),v=read(),E[u].pb(pi(v,i)),E[v].pb(pi(u,i));
    for(i=1;i<=n;++i) sort(E[i].begin(),E[i].end());
    if(m==n-1){dfs(1,0);for(i=1;i<=n;++i) printf("%d ",tmp[i]);return 0;}
    for(i=1;i<=n;++i) memset(vis,0,sizeof vis),ban=i,cnt=0,dfs(1,0),upd(n);
    for(i=1;i<=n;++i) printf("%d ",ans[i]);
}

填数游戏

题目
打表题，不想说啥了。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    register int x=0;
    register char ch=getchar();
    while(ch<'0'||ch>'9')
    ch=getchar();
    while(ch>='0'&&ch<='9')
    x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return x;
}
const int p=1e9+7;
inline int power(register int a,register int b){register int r=1;for(;b;b>>=1,a=1ll*a*a%p)if(b&1)r=1ll*a*r%p;return r;}
int main()
{
    register int n=read(),m=read();
    if(n>m)
    swap(n,m);
    switch(n)
    {
    case 1:
    return cout<<power(2,m),0;
    case 2:
    return cout<<4ll*power(3,m-1)%p,0;
    case 3:
    return cout<<112ll*power(3,m-3)%p,0;
    case 4:
    if(m==4)
        return cout<<912,0;
    else
        return cout<<2688ll*power(3,m-5)%p,0;
    case 5:
    if(m==5)
        return cout<<7136,0;
    else
        return cout<<21312ll*power(3,m-6)%p,0;
    case 6:
    if(m==6)
        return cout<<56768,0;
    else
        return cout<<170112ll*power(3,m-7)%p,0;
    case 7:
    if(m==7)
        return cout<<453504,0;
    else
        return cout<<1360128ll*power(3,m-8)%p,0;
    case 8:
    if(m==8)
        return cout<<3626752,0;
    else
        return cout<<10879488ll*power(3,m-9)%p,0;
    }
}

NOIP 2018

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/11850330.html