NOIP 2017普及グループ問題解

老年tg选手来发传达组题解啦!!!新しいblogバージョンリンク
T1
ひょうめんばんそうゲート
直接シミュレーションして、多く言わないで、公式もカードの精度がなくて、あなたがプログラミングすることができるかどうかを考察します

#include
#include
#include
#include
#include
#include
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else 
#define LL "%lld"
#endif
using namespace std;
inline ll read()
{
    ll f=1,x=0;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    int a,b,c;
    cin>>a>>b>>c;
    cout<0.2+b*0.3+c*0.5<return 0;
}

T2
ひょうめんばんそうゲート
水の問題を模擬して、図書番号によって小さいから大きいまで並べ替えて、それから直接調べて判断して、TLEのができません

#include
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
int n,q,len,ans,a[1000006],s;
int main()
{
    cin>>n>>q;
    rep(i,1,n)cin>>a[i];
    sort(a+1,a+1+n);
    while(q--){
        ans=-1;
        cin>>len>>s;
        int t=1;
        while(len--)t*=10;
        rep(i,1,n)
            if(a[i]%t==s){
                ans=a[i];
                break;
            }
        printf("%d
",ans);
    }
    return 0;
}

T3
ひょうめんばんそうゲート
最初はDPに行きたかったのですが、書き終わったらDPの非効率性に満足していないことに気づきました.
そしてdfs+記憶化に着手します.bfsも走れるみたい?(私は問題を押さえたのではないでしょうか.前に四十五中にbfsのような問題を出したことがあります)しかし、複雑さが大きすぎて、TLEができます.
正解は、すでに有色の格子を4つの異なる方向に探索し、未染色のものを染色し、その後探索する
必ず境界の判断に注意しましょう!

#include
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define inf 0x3f3f3f
using namespace std;
const int maxn=1006,dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
int n,m,x,y,opt,Map[maxn][maxn],f[maxn][maxn];
void dfs(int x,int y,int p){
    rep(i,0,3){
        int nowx=x+dx[i],nowy=y+dy[i];
        if(nowx>n||nowx<1||nowy>n||nowy<1)continue;
        if(~Map[nowx][nowy]){
            if((~Map[x][y]?Map[x][y]:p)==Map[nowx][nowy])
            {
                if(f[nowx][nowy]>f[x][y])f[nowx][nowy]=f[x][y],dfs(nowx,nowy,Map[nowx][nowy]);
            }
            else{
                if(f[nowx][nowy]>f[x][y]+1)f[nowx][nowy]=f[x][y]+1,dfs(nowx,nowy,Map[nowx][nowy]);
            }
        }
        else{
            if(Map[x][y]==-1)continue;
            else if(f[nowx][nowy]>=f[x][y]+2)f[nowx][nowy]=f[x][y]+2,dfs(nowx,nowy,Map[x][y]);
        }
    }
}
int main()
{
    mem(Map,-1);
    mem(f,inf);
    cin>>n>>m;
    rep(i,1,m){
        cin>>x>>y>>opt;
        Map[x][y]=opt;
    }
    f[1][1]=0;
    dfs(1,1,0);
    if(f[n][n]==1061109567)cout<<"-1
";
    else cout<return 0;
}

T4
ひょうめんばんそうゲート
pj組でこの問題を置くのは少し難しいのではないかと感じて、難易度はNOIP 2015 D 2 T 1のあの跳石より大きいです
老套路先二分答案+DP
f[i]はジャンプ前のi個の格子を表し、i番目の格子の最大点数に止まる.
sc[i]はi番目の格子の点数を表す.
遷移:f[i]=max(f[j])+sc[i]jからiにジャンプできることを前提とする
明らかに、この時間は複雑すぎます.
単調キュー最適化の再使用が必要
遷移中のjの位置はiの右シフトに伴って右シフトすることが分かった
格子jに対して,dis[i]−dis[j]>=ロボットが跳べる最小距離であれば,f[j]は明らかにキューに入ることができる.
しかし、キュー全体を単調に減らすには、毎回直接キューに行けばいいです.
最小値を極小にしないとWAになりますのでご注意ください

#include
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
using namespace std;
const ll maxn=5e5+6,inf=1844387848000;
ll dis[maxn],sc[maxn],f[maxn],n,d,k,x,y;
bool check(int x)
{
    dequeque;
    ll from=0,stepl=max(d-x,(ll)1),stepr=d+x;
    rep(i,1,n){
        while(dis[from]+stepl<=dis[i]){
            while(!que.empty()&&f[que.back()]<=f[from])que.pop_back();
            que.push_back(from++);
        }
        while(!que.empty()&&dis[que.front()]+steprif(!que.empty())f[i]=f[que.front()]+sc[i];
        else f[i]=-inf;
        if(f[i]>=k) return 1;
    }
    return 0;
}
int main()
{
    cin>>n>>d>>k;
    ll sum=0;
    rep(i,1,n){
        cin>>x>>y;
        dis[i]=x;sc[i]=y;
        if(y>0)sum+=y;
    }
    if(sumcout<<"-1
";return 0;}
    int l=1,r=dis[n],mid;
    while(l0);
        mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    cout<return 0;
}