3.16 noip模拟赛

t1 浇花

考场代码：

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
#define X (c^48)
#define C c=getchar()
using namespace std;
template <typename T> void inline rd(T&x){char c;int f=1;while(!isdigit(C))if(c=='-')f=-1;x=X;while(isdigit(C))x=x*10+X;x*=f;}
void wr(int x){if(x<0){putchar('-');x=-x;}if(x>9)wr(x/10);putchar(x%10+'0');}
#define ll long long
#define N 1010
int n,minn=0,pos=0,min_h=1e9;
int mincf[N][N],ans[N],h[N],cf[N];
int main()
{
    freopen("read.txt","r",stdin);
    rd(n);
    rep(i,1,n)
    {
        rd(h[i]);
        if(h[i]<min_h)
        {
            min_h=h[i];
            pos=i;
        }
        cf[i]=h[i]-h[i-1];
        ans[i]++;
    }

    rep(i,1,n)
    {
        if(cf[i]>0)
            ans[i-1]++;
        else ans[i]++;
    }

    rep(i,1,n)
    {
        if(h[i]<h[i-1] && h[i]<h[i+1])ans[i]++;
        else if(h[i-1]<h[i] && h[i-1]<h[i+1])ans[i-1]++;
        else if(h[i+1]<h[i] && h[i+1]<h[i-1])ans[i+1]++;
    }
    rep(i,1,n)
    {
        if(h[i]<h[i-1] && h[i]<h[i+1] && h[i]<h[i+2])ans[i]++;
        else if(h[i-1]<h[i] && h[i-1]<h[i+1] && h[i-1]<h[i+2])ans[i-1]++;
        else if(h[i+1]<h[i] && h[i+1]<h[i-1] && h[i+1]<h[i+2])ans[i+1]++;
        else if(h[i+2]<h[i] && h[i+2]<h[i-1] && h[i+2]<h[i+1])ans[i+2]++;
    }
    if(pos==1)ans[1]=n;
    if(pos==n)ans[n]==n;
    ans[pos]++;
    /*rep(l,1,n)//当前区间长度
        rep(i,1,n)//当前区间起点
            for(int j=i+l;i<=n;++i)//终点
            {
                anss[i][j]=min(h[i],h[j]);
            }
    */
    rep(i,1,n)
        printf("%d ",ans[i]);
    return 0;
}

正解：

思路：

根据乘法原理，一个数被统计的次数==(i-l[i])* (r[i]-r)

l[i]:i左边第一个<i的数

r[i]:i左边第一个<i的数

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
#define X (c^48)
#define C c=getchar()
using namespace std;
template <typename T> void inline rd(T&x){char c;int f=1;while(!isdigit(C))if(c=='-')f=-1;x=X;while(isdigit(C))x=x*10+X;x*=f;}
void wr(int x){if(x<0){putchar('-');x=-x;}if(x>9)wr(x/10);putchar(x%10+'0');}
#define ll long long
#define N 1000010
int n;
int a[N],l[N],r[N];
map<int,long long>h;
int main()
{
    freopen("read.txt","r",stdin);
    rd(n);
    rep(i,1,n)
    {
        rd(a[i]);
        l[i]=i-1,r[i]=i+1;//注意要初始化
    }
    rep(i,1,n)
        while(a[l[i]]>a[i])
            l[i]=l[l[i]];//更新l[i]
    dwn(i,n,1)
        while(a[r[i]]>a[i])
            r[i]=r[r[i]];//更新r[i]
    rep(i,1,n)
        printf("%lld ",(long long)(i-l[i])*(r[i]-i));
        //注意一定要转long long！！！！乘积有可能会爆掉int
    return 0;
}

---

t2 ABCDEF

思路：

• (a × b + c) ÷ d – e = f 变形成(a * b+c)==(f+e) * d,省去除法（浮点数懒得判断）

• 使用map<int,long long>h，哈希表来做等式两边的中转

• 十年OI一场空，不开long long 见祖宗

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
#define X (c^48)
#define C c=getchar()
using namespace std;
template <typename T> void inline rd(T&x){char c;int f=1;while(!isdigit(C))if(c=='-')f=-1;x=X;while(isdigit(C))x=x*10+X;x*=f;}
void wr(int x){if(x<0){putchar('-');x=-x;}if(x>9)wr(x/10);putchar(x%10+'0');}
#define ll long long
#define N 110
int n;
map<int,long long>h;
int x[N];
ll ans;

int main()
{
    freopen("readda.txt","r",stdin);
    rd(n);
    rep(i,1,n)rd(x[i]);

    rep(a,1,n)
        rep(b,1,n)
            rep(c,1,n)
                h[x[a]*x[b]+x[c]]++;
    rep(d,1,n)
        rep(e,1,n)
            rep(f,1,n)
            {
                if(x[d]==0)continue;
                ans+=h[(x[f]+x[e])*x[d]];
            }

    printf("%lld",ans);
    return 0;
}

---

t3奶牛健美操

题目大意：

给定一棵树，可以删掉s条边，求删掉后森林中所有树直径的最大值的最小值

思路：

• 最大值最小，典型的二分答案

• 此题我们二分树的直径，每次二分DFS一次，对于每个节点统计出所有子树删边后的dis，排序，贪心删掉最大的，直到最大的两个子树相加不会超过二分的答案为止

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i)
#define X (c^48)
#define C c=getchar()
using namespace std;
template <typename T> void inline rd(T&x){char c;int f=1;while(!isdigit(C))if(c=='-')f=-1;x=X;while(isdigit(C))x=x*10+X;x*=f;}
const int N=1e5+10;

struct Edge{int v,next;}e[N<<1];

int n,s,tot,ans,head[N],a[N],f[N];

void add(int x,int y){e[++tot].v=y;e[tot].next=head[x];head[x]=tot;}

void dfs(int u,int fa,int limit)
{
    int cnt=0;
    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa)continue;
        dfs(e[i].v,u,limit);
    }

    for(int i=head[u];i;i=e[i].next)
    {
        int v=e[i].v;
        if(v==fa)continue;
        a[++cnt]=f[v]+1;
    }

    sort(a+1,a+cnt+1);

    while(cnt && a[cnt]+a[cnt-1]>limit)
        cnt--,ans++;
    f[u]=a[cnt];
}

inline bool check(int x)
{
    ans=0;
    dfs(1,0,x);
    return ans<=s;
}

int main()
{
    freopen("input.txt","r",stdin);
    rd(n),rd(s);
    rep(i,1,n-1)
    {
        int u,v;rd(u),rd(v);
        add(u,v),add(v,u);
    }
    int l=0,r=n,mid,ans;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check(mid))
        {
            ans=mid;
            r=mid-1;
        }
        else
            l=mid+1;
    }
    printf("%d",ans);
    return 0;
}

---

分数与总结：

t1 0pts
t2 30pts
t3 0pts
考试的时候心态崩了，t1、t3都写挂了，只拿了t2的暴力分……我ｓｋｒ　ｚｚ

暴露出的问题：

• map
• 单调栈
• 树形DP+二分