2019-10-22 15:48 已编辑北京航空航天大学 C++

关注

NOIP2014提高组题解报告

D1

T1 无线网路发射器选址

题目大意：找一个矩形，使其覆盖的目标点最大。

~~题目过水~~，直接暴力搞过去，代码就不贴了。
但我TM居然有个地方SB了，调了半天才发现输入有问题：

scanf("%d%d%d",&x,&y,&t[x][y]);//这是我原来的写法.....

T2 寻找道路

题目大意：给你一个有向图，找一条从起点到终点的最短路径，且路径上的所有点的出边所指向的点都直接或间接与终点连通。

先处理出所有满足条件的点，然后在上面跑~~死了的~~ $spfa$ 即可。
注意这里我们不是直接去找与终点相连的点，因为这样会漏掉一些点（~~别问我怎么知道的~~）。
所以我们可以用到不了终点的点去跟新其它点即可。

$Code：$

const int N=2e5+5;
vector<int>G1[N],G2[N];
//G1正图  G2反图
bool T[N],f[N];
int n,m,x,y,s,t,d[N];
queue<int>q;
inline void bfs()
{
    q.push(t);T[t]=f[t]=1;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(rg int i=0;i<G2[x].size();++i)
        {
            int v=G2[x][i];
            if(!T[v]) T[v]=f[v]=1,q.push(v);
        }
    }
    for(rg int i=1;i<=n;++i)
        if(!T[i])
            for(rg int j=0;j<G2[i].size();++j)
            {
                int v=G2[i][j];
                if(f[v]) f[v]=0;
            }
    while(!q.empty()) q.pop();
    q.push(s);memset(d,0x3f,sizeof d);d[s]=0;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(rg int i=0;i<G1[x].size();++i)
        {
            int v=G1[x][i];
            if(f[v] && d[v]>d[x]+1)
            {
                d[v]=d[x]+1;
                q.push(v);
            }
        }
    }
}

T3 解方程

题目大意：求给定一元 $n$ 次方程在 $[1,m]$ 上的整数解。

我最开始还以为要打高精度，其实可以用秦九韶算法来解决。
这个算法可以将一元 $n$ 次多项式的求值问题转化为 $n$ 个一次式的算法，然后……~~自己看度娘吧~~
总之，这个算法可以让我们在 $O(nm)$ 的时间内解决该问题。（过程中可以随便膜一个数如192*****来简化运算）

$Code:$

#include<cstdio>
#include<vector>
using namespace std;
#define int long long
const int p=19260817;
int n,m,a[105];
vector<int>Ans;
inline int read()//骚气读入
{
    int f=1,x=0;register char c=getchar();
    while(c>'9' || c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c>='0' && c<='9') x=((x<<3)+(x<<1)+(c^'0'))%p,c=getchar();
    return x*f%p;//记得取膜
}
signed main()
{
    n=read(),m=read();
    for(int i=0;i<=n;++i) a[i]=read();
    for(int i=1;i<=m;++i)
    {
        int ans=0;
        for(int j=n;j>=1;--j)
            ans=(ans+a[j])*i%p;
        ans=(ans+a[0])%p;
        if(!ans) Ans.push_back(i);
    }
    printf("%lld\n",(int)Ans.size());
    for(int i=0;i<(int)Ans.size();++i) printf("%lld\n",Ans[i]);
    return 0;
}

D2

T1 生活大爆炸版石头剪刀布

题目大意：石头剪刀布

巨水的模拟，贴一下代码就行了~~

$Code：$

#include<cstdio>
using namespace std;
const int N=205;
int n,na,nb,a[N],b[N],c[5][5],cnta,cntb;
//0表示“剪刀”，1表示“石头”，2表示“布”，3表示“蜥蜴人”，  4表示“斯波克
int main()
{
    scanf("%d%d%d",&n,&na,&nb);
    for(int i=1;i<=na;++i) scanf("%d",&a[i]);
    for(int i=1;i<=nb;++i) scanf("%d",&b[i]);
    c[1][0]=c[2][1]=c[0][2]=c[0][3]=c[1][3]=c[2][4]=c[3][4]=c[3][2]=c[4][0]=c[4][1]=1;
    for(int i=1;i<=n;++i)
    {
        int A=i%na,B=i%nb;
        if(!A) A=na;
        if(!B) B=nb;
        // printf("%d %d\n",a[A],b[B]);
        cnta+=c[a[A]][b[B]],cntb+=c[b[B]][a[A]];
        // printf("cnt:%d %d\n",cnta,cntb);
    }
    printf("%d %d",cnta,cntb);
    return 0;
}

T2 联合权值

题目大意：给你一颗树，边权均为 $1$ ,每个点有点权 $w_i$ ( $w_i \le 2 \times 10^4$ )，求 $Max_{dis(u,v)==2}(w[u] \times w[v])$ 以及 $\sum_{dis(u,v)==2} w[u] \times w[v]$ （ $n \le 2 \times 10^5$ ）

直接 $O(n^2)$ 暴力枚举是肯定过不了的，要想一些~~奇技淫巧~~来优化。

要求 $u,v$ 之间距离为 $1$ ，又是在树上，那么它们之间必然有 $1$ 个中转点。于是我们可以枚举该点。

但 $n$ 的范围巨大，怎么能高效地跟新答案呢？这里有一个神奇的公式：

设 $S = \sum_{i=1}^n a_i$ ，则有

$( (S - a_1) + (S - a_2) + \cdots + (S - a_n) ) \times 2 = (a_1+a_2+ \cdots +a_{n-1}+a_n)^2 - (a_1^2+a_2^2+ \cdots +a_{n-1}^2+a_n^2)$

因为我们加的是双向边，所以对于一个节点 $x$ ，与它相连的所有点之间都可以互相构成联合权值

将其表示出来：

令 $S$ 为与它相连的所有点的权，那么任意一个点能形成的联合权值为 $S - a_i$
那么以该点为中转点所形成的联合权值，为 $( (S - a_1) + (S - a_2) + \cdots + (S - a_n) ) \times 2$ ...这不就是上式吗？于是，我们就得到了一个优秀的 $O(n)$ 做法。

$Code：$

#include<cstdio>
#include<vector>
#include<algorithm>
#define rg register
#define ll long long
struct ios{
    template<typename TP>
    inline ios operator >> (TP &x)
    {
        TP f=1;x=0;rg char c=getchar();
        for(;c>'9' || c<'0';c=getchar()) if(c=='-') f=-1;
        for(;c>='0' && c<='9';c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
        x*=f;
        return *this;
    }
    template<typename TP>
    inline ios operator << (TP x)
    {
        char s[66];rg int cnt=0;
        if(!x) putchar('0');
        if(x<0) x=-x,putchar('-');
        while(x) ++cnt,s[cnt]=x%10+'0',x/=10;
        while(cnt) putchar(s[cnt]),--cnt;
        return *this;
    }
    inline ios operator << (char x)
    {
        putchar(x);
        return *this;
    }
}io;
const int N=2e5+5;
std::vector<int>G[N];
const int p=10007;
int n,a,b,w[N],ans,sum;
int main()
{
    io>>n;
    for(rg int i=1;i<n;++i)
    {
        io>>a>>b;
        G[a].push_back(b),G[b].push_back(a);
    }
    for(rg int i=1;i<=n;++i) io>>w[i];
    // for(rg int i=1;i<=n;++i) io<<w[i]<<' ';
    // io<<'\n';
    /*--------------------------以某个节点为中转点的联合权值之和等于权值和的平方减去权值的平方和----------------------*/
    for(rg int i=1;i<=n;++i)
    {
        int max_1=0,max_2=0;
        int he=0,pf=0;
        for(int k=0;k<(int)G[i].size();++k)
        {
            int v=G[i][k];
            // io<<i<<' '<<G[i].size()<<' '<<k<<' '<<v<<'\n';
            if(w[v]>max_1) max_2=max_1,max_1=w[v];
            else if(w[v]>max_2) max_2=w[v];
            he=(he+w[v])%p,pf=(pf+w[v]*w[v])%p;
        }
        he=he*he%p;
        // io<<'h'<<'h'<<max_1<<' '<<max_2<<'\n';
        ans=std::max(ans,max_1*max_2);
        sum=(sum+he-pf+p)%p;//注意he-pf可能为负数
    }
    io<<ans<<' '<<sum;
    return 0;
}

T3 飞扬的小鸟

题目大意：（首先，请确保你知道 $CodeVs-flappy bird$ ）给你每个位置点击上升的距离和不点击下降的距离、每个管道的位置。求能不能通过以及如果能通过，最少点击数为多少。

~~很显然~~可以看出，这题是 $DP$ （求最优解，数据范围比较大，还不能贪心，除了 $DP$ ，还真就没有做法了）

用 $dp[i][j]$ 表示横坐标为 $i$ 时高度为 $j$ 的最少点击次数，用 $+ \infty$ 来表示不可能达到这个状态。
每个管道的位置不能走，其他地方就按照规则来走，注意小鸟撞到天花板不会挂，只有高度为 $0$ 是才会挂，所以特判一下。

$Code：$

#include<cstdio>
#include<algorithm>
#include<cmath>
#define rg register
#define ll long long
#define cg c=getchar()
using namespace std;
struct ios{
    template<typename TP>
    inline ios operator >> (TP &x)
    {
        TP f=1;x=0;rg char cg;
        for(;c>'9' || c<'0';cg) if(c=='-') f=-1;
        for(;c>='0' && c<='9';cg) x=(x<<3)+(x<<1)+(c^'0');
        x*=f;
        return *this;
    }
    template<typename TP>
    inline ios operator << (TP x)
    {
        char s[66];rg int cnt=0;
        if(x<0) x=-x,putchar('-');
        if(!x) putchar('0');
        while(x) s[++cnt]=x%10+'0',x/=10;
        while(cnt) putchar(s[cnt--]);
        return *this;
    }
    inline ios operator << (char s)
    {
        putchar(s);
        return *this;
    }
}io;
const int N=1e4;
const int M=1e3;
const int inf=0x3f3f3f3f;
int n,m,k,cnt=1;
struct node{
    int x,y;
}a[N];
struct Node{
    int pos,L,H;
    inline bool operator < (const Node b) const {
        return pos<b.pos;
    }
}g[N];
int dp[N][M],vis[N][M];
int main()
{
    io>>n>>m>>k;
    for(rg int i=0;i<n;++i) io>>a[i].x>>a[i].y;
    for(rg int i=1;i<=k;++i)
    {
        io>>g[i].pos>>g[i].L>>g[i].H;
        for(int j=1;j<=g[i].L;++j) vis[g[i].pos][j]=1;
        for(int j=g[i].H;j<=m;++j) vis[g[i].pos][j]=1;
    }
    sort(g+1,g+k+1);
    //io<<'h'<<'h'<<'h'<<'\n';
    for(rg int i=1;i<=n;++i)
        for(rg int j=1;j<=m;++j) dp[i][j]=inf;
    for(rg int i=1;i<=n;++i)
    {
    //    io<<'h'<<'h'<<'h'<<'\n';
        int L=1,R=m;
        if(g[cnt].pos==i) L=g[cnt].L+1,R=g[cnt].H-1,++cnt;
        // if(i==5) io<<L<<' '<<R<<'\n';
        int x=a[i-1].x,y=a[i-1].y;
        for(rg int j=L;j<=R;++j)
        {
            if(j==m)
            {
                for(rg int l=1;l<=m;++l)
                {
                    if(!vis[i-1][l])
                    {
                        int w=ceil(1.0*(m-l)/x);
                        if(j==l) w=1;
                        dp[i][j]=min(dp[i][j],dp[i-1][l]+w);
                    }
                }
                continue;
            }
            // if(i==5) io<<j+y<<' '<<y<<'\n';
            if(j+y<=m && !vis[i-1][j+y]) dp[i][j]=min(dp[i][j],dp[i-1][j+y]);
            int w=j/x;
            for(rg int l=1;l<=w;++l)
                if(j-x*l>0 && !vis[i-1][j-x*l])
                    dp[i][j]=min(dp[i][j],dp[i-1][j-x*l]+l);
        }
    //    io<<'h'<<'h'<<'h'<<'\n';
    }
    int ans=inf;
    // for(int i=m;i>=0;--i)
    // // for(int i = 0; i <= n; ++i)
    // {
    //     // for (int j = 0; j <= m; ++j)
    //     for(int j=0;j<=n;++j)
    //     {
    //         if(dp[j][i]==inf) io<<'*'<<' ';
    //         else io<<dp[j][i]<<' ';
    //     }
    //     io<<'\n';
    // }
    for(rg int i=1;i<=m;++i) ans=min(ans,dp[n][i]);
    if(ans==inf)
    {
        io<<0<<'\n';
        for(rg int i=1;i<=k;++i)
        {
            int p=g[i].pos;
            for(rg int j=1;j<=m;++j)
            {
                if(dp[p][j]!=inf) break;
                if(j==m)
                {
                    io<<i-1<<'\n';
                    return 0;
                }
            }
        }
    }
    io<<1<<'\n'<<ans;
    return 0;
}

然鹅你发现这个达不到上界的 $O(nm^2)$ 的 $DP$ 只能水 $80$ 分。（~~不过联赛时有 $80$ 分也不错了~~）
那该如何优化呢？
我们发现，小鸟每次上升多次，但只能下降一次（保证不超边界时）。
上升多次，不就相当于是多重背包吗？
那么下降一次，就可以看做 $01$ 背包。
有了这个思路，我们就可以成功地把复杂度将为 $O(nm)$ 了

$Code：$

#include<cstdio>
#include<cstring>
#include<algorithm>
#define rg register
#define ll long long
#define cg c=getchar()
using namespace std;
struct ios{
    template<typename TP>
    inline ios operator >> (TP &x)
    {
        TP f=1;x=0;rg char cg;
        for(;c>'9' || c<'0';cg) if(c=='-') f=-1;
        for(;c>='0' && c<='9';cg) x=(x<<3)+(x<<1)+(c^'0');
        x*=f;
        return *this;
    }
    template<typename TP>
    inline ios operator << (TP x)
    {
        char s[66];rg int cnt=0;
        if(x<0) x=-x,putchar('-');
        if(!x) putchar('0');
        while(x) s[++cnt]=x%10+'0',x/=10;
        while(cnt) putchar(s[cnt--]);
        return *this;
    }
    inline ios operator << (char s)
    {
        putchar(s);
        return *this;
    }
}io;
const int N=1e4+5;
const int M=1e3+5;
const int inf=0x3f3f3f3f;
int n,m,k;
struct node{
    int x,y;
}a[N];
int dp[N][M<<1],vis[N],L[N],R[N];
int main()
{
    // freopen("1.in","r",stdin);
    io>>n>>m>>k;
    for(rg int i=1;i<=n;++i) io>>a[i].x>>a[i].y,L[i]=1,R[i]=m;
    for(rg int i=1;i<=k;++i)
    {
        int a,b,c;io>>a>>b>>c;
        vis[a]=1,L[a]=b+1,R[a]=c-1;
    }
    memset(dp,0x3f,sizeof dp);
    for(rg int i=1;i<=m;++i) dp[0][i]=0;
    for(rg int i=1;i<=n;++i)
    {
        int x=a[i].x,y=a[i].y;
        for(rg int j=x+1;j<=m+x;++j)
            dp[i][j]=min(dp[i-1][j-x]+1,dp[i][j-x]+1);
        for(rg int j=m+1;j<=m+x;++j)
            dp[i][m]=min(dp[i][m],dp[i][j]);
        for(rg int j=1;j+y<=m;++j)
            dp[i][j]=min(dp[i][j],dp[i-1][j+y]);
        // io<<i<<' '<<L<<' '<<R<<'\n';
        for(rg int j=1;j<=L[i]-1;++j) dp[i][j]=inf;
        for(rg int j=R[i]+1;j<=m;++j) dp[i][j]=inf;
    }
    int ans=inf;
    // io<<inf<<'\n';
    // for(int i=m;i>=0;--i)
    // // for(int i = 0; i <= n; ++i)
    // {
    //     // for (int j = 0; j <= m; ++j)
    //     for(int j=0;j<=n;++j)
    //       {
    //         if(dp[j][i]==inf) io<<'*'<<' ';
    //         else io<<dp[j][i]<<' ';
    //     }
    //     io<<'\n';
    // }
    for(rg int i=1;i<=m;++i) ans=min(ans,dp[n][i]);
    if(ans>=inf)
    {
        io<<0<<'\n';
        int i,j;
        for(i=n;i>=1;--i)
        {
            for(j=1;j<=m;++j)
            {
                if(dp[i][j]<inf) break;
            }
            if(j<=m) break;
        }
        ans=0;
        for(int j=1;j<=i;++j)
            if(vis[j]) ++ans;
        io<<ans;
    }
    else io<<1<<'\n'<<ans;
    return 0;
}

全部评论

推荐最新楼层

昨天 15:00

西南民族大学 Java

26双非本，春招收获零蛋,基本没面试，是我简历有问题吗？

没招了，4月22了，基本没几个面试，有的面试也都是一些很垃圾的深圳7k，有一个山东济南6.5k的，是给医院开发系统的，好难受，工资太低了。上一家实习工资都给6.5k，现在找一个8k的都找不到呜呜呜呜呜。简历也让别人看了，说是没什么问题，现在春招也基本结束了才想着过来发，就当给大伙看个乐子吧。

点赞评论收藏

昨天 15:39

浙江大学算法工程师

滴滴二面 C++ 复盘

今天整理了一下滴滴二面的整体流程和高频考察点，明显能感觉到二面和一面的区别还是很大的。一面更偏基础和项目经历的初步了解，二面则会继续深挖项目细节、工程思维、技术选型、问题定位能力，以及 C++ 核心知识和手撕代码能力。很多题目表面上不难，但如果项目细节不熟、底层原理说不清、回答不够结构化，就很容易卡住。这篇复盘主要把这次面试中出现的题目整理出来，方便后面继续针对性准备。题目介绍一下你参加过的竞赛，遇到的最大挑战是什么？竞赛项目中你是如何做技术选型的？为什么选这个方案而不是其他方案？你的项目中是如何保证代码质量和可维护性的？项目中遇到过内存泄漏或崩溃问题吗？你是怎么定位和解决的？C++ 虚函数的...

查看14道真题和解析

点赞评论收藏

03-03 23:12

已编辑

北京邮电大学 Java

27届找暑期，简历求拷打

书海为家：我来给一点点小建议，因为毕竟还在学校不像工作几年的老鸟有丰富的项目经验，面试官在面试在校生的时候更关注咱们同学的做事逻辑和思路，所以最好在简历中描述下自己做过项目的完整过程，比如需求怎么来的，你对需求的解读，你想到的解决办法，遇到困难如何找人求助，最终项目做成了什么程度，你从中收获了哪些技能，你有什么感悟。

你的简历改到第几版了

点赞评论收藏