【题解】NOIP 2017 题解

于由XZYQvQ发布

只是来水水博客，在 NOIP 2018 退役前多写点东西，表示自己存在过。。。

D1 T1 小凯的疑惑

传送门=￣ω￣=

这题的话有个定理：

小凯的疑惑这题的答案是多少？
——答案是 $a \times b – a – b$

是真的有这个定理的，上次 ZYJay 学长（传送门里的那个老 Jay 型の吹逼狗）证了，然而我并不是很想证。

不过这题很有启发性：有时候 NOIP 真的需要打表。

代码：

#include <bits/stdc++.h>

using namespace std;

int a, b;

int main()
{
    scanf("%d%d", &a, &b);
    printf("%lld\n", 1ll * a * b - a - b);
    return 0;
}

D1 T2 时间复杂度

传送门=￣ω￣=

暴力模拟，搞个栈呗。。。

这题告诉我们一定要细心。

一年前的代码：

#include <bits/stdc++.h>
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}
template<typename _Tp>inline void SPIN(_Tp&dig)
{
    char c;dig=0;
    while(c=getchar(),(!isdigit(c))&&c!='n');
    if(c=='n'){dig=-1;return;}
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct F{char v;int a,b;};
int T,L,w,ans;
bool hash[30];
char buff[1000];
stack<F> st;
void read_O()
{
    scanf("%s",buff);
    if(buff[2]=='1'){w=0;return;}
    int tmp=0;
    w=0;
    while(!isdigit(buff[tmp]))tmp++;
    while(isdigit(buff[tmp]))w=w*10+buff[tmp]-'0',tmp++;
}
void getl()
{
    char c;
    while(c=getchar(),c!='\n'&&c!='\r'&&c!=EOF);
}
int main()
{
    IN(T);
    while(T--)
    {
        IN(L),read_O(),ans=0,memset(hash,0,sizeof(hash));
        while(!st.empty())st.pop();
        for(int line=1,tmp=0,v0=0;line<=L;line++)
        {
            scanf("%s",buff);
            if(buff[0]=='F')
            {
                scanf("%s",buff);
                if(hash[buff[0]-'a'])
                {
                    puts("ERR");
                    for(int i=line;i<=L;i++)getl();
                    goto end;
                }
                hash[buff[0]-'a']=1;
                F p=(F){buff[0],0,0};
                SPIN(p.a),SPIN(p.b),st.push(p);
                if(p.a>=0&&p.b<0)tmp++;
                else if(p.a<0&&p.b>=0)v0++;
                else if(p.a>p.b)v0++;
            }
            else
            {
                if(st.empty())
                {
                    puts("ERR");
                    for(int i=line;i<=L;i++)getl();
                    goto end;
                }
                F p=st.top();st.pop();
                hash[p.v-'a']=0;
                if(!v0)ans=max(ans,tmp);
                if(p.a>=0&&p.b<0)tmp--;
                else if(p.a<0&&p.b>=0)v0--;
                else if(p.a>p.b)v0--;
            }
        }
        if(st.size())puts("ERR");
        else
        {
            if(ans==w)puts("Yes");
            else puts("No");
        }
        end:continue;
    }
    return 0;
}

D1T3 逛公园

传送门=￣ω￣=

可以发现如果有零环则答案为 $-1$

若无零环：

设 $dis[i]$表示 $i->n$的最短路长度

设 $f[i][j]$表示从 $i$出发的长度 $\leq dis[i] + j$的路径条数

可以想到通过一条 $u->v$，长度为 $w$的有向边转移后，$f[u][j]$可以转移到 $f[v][dis[v]+w-dis[u]]$上

用记忆化搜索的话就是 $f[u][j] += f[v][dis[v]+w-dis[u]]$

答案就是 $f[1][k]$

那么零环怎么办呢？

如果某个状态 $(i, j)$在 Dfs 的栈中出现了两次则说明有零环。。。

这题告诉我们如果发现一整天都没有 Dp 可以往 Dp 上想想。。。

代码：

#include <bits/stdc++.h>

#define NS (100005)
#define MS (200005)
#define KS (55)
#define FIR first
#define SEC second

using namespace std;

typedef pair<int, int> PII;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

struct Graph
{
    int head[NS], nxt[MS], to[MS], w[MS], sz;
    void init() {memset(head, -1, sizeof(head)), sz = 0;}
    Graph() {init();}
    void push(int a, int b, int c)
    {
        nxt[sz] = head[a], to[sz] = b, w[sz] = c, head[a] = sz++;
    }
    int operator [] (const int a) const {return to[a];}
} g, G;

int T, n, m, k, p, dis[NS];

bool vis[NS];

priority_queue<PII, vector<PII>, greater<PII> > pq;

void Dij()
{
    memset(vis, 0, sizeof(vis)), memset(dis, 127, sizeof(dis));
    dis[n] = 0, pq.push(PII(0, n));
    while (!pq.empty())
    {
        int F = pq.top().SEC; pq.pop();
        if (vis[F]) continue;
        vis[F] = 1;
        for (int i = g.head[F]; ~i; i = g.nxt[i])
            if (dis[g[i]] > dis[F] + g.w[i])
                dis[g[i]] = dis[F] + g.w[i], pq.push(PII(dis[g[i]], g[i]));
    }
}

int f[NS][KS];

bool book[NS][KS];

int Dfs(int a, int x)
{
    if (book[a][x]) return -1;
    int& F = f[a][x];
    if (F != -1) return F;
    book[a][x] = 1;
    if (a == n) F = 1; else F = 0;
    for (int i = G.head[a], j; ~i; i = G.nxt[i])
    {
        j = dis[G[i]] + G.w[i] - dis[a];
        if (j <= x)
        {
            j = Dfs(G[i], x - j);
            if (j == -1) return -1;
            F = (F + j) % p;
        }
    }
    book[a][x] = 0; return F;
}

int main(int argc, char const* argv[])
{
    IN(T);
    while (T--)
    {
        IN(n), IN(m), IN(k), IN(p), g.init(), G.init();
        for (int i = 1, a, b, c; i <= m; i += 1)
            IN(a), IN(b), IN(c), G.push(a, b, c), g.push(b, a, c);
        Dij(), memset(f, -1, sizeof(f)), memset(book, 0, sizeof(book));
        printf("%d\n", Dfs(1, k));
    }
    return 0;
}

D2T1 奶酪

传送门=￣ω￣=

没啥好说的，就是一个 Bfs

然而我当时出来以后在洛谷上测爆零了，最后也只拿了 70 分，感谢出题人不杀之恩 Orz

当时我忘记特判上下界被一个空心直接联通的情况了。。。

这题告诉我们要注意细节与特殊情况 QvQ

一年前的代码：

#include<bits/stdc++.h>
using namespace std;
int t,n,h,r,u;
int x[1005],y[1005],z[1005];
int ansz,maxz=-0x7fffffff;
int minz=0x7ffffff;
int ans[25],visited[1005];
double dis[1005][1005];
double diss(int a,int b)
{
    double p;
    p=sqrt(pow(abs(double(x[a])-double(x[b])),2)+pow(abs(double(y[a])-double(y[b])),2)+pow(abs(double(z[a])-double(z[b])),2));
    return p;
}
int search(int g)
{
    for(int i=1;i<=n;i++)
    {
        if((i!=g)&&(dis[i][g]<=(2*double(r)))&&(!visited[i]))
        {
            if(z[i]>ansz){ansz=z[i];visited[i]=1;}
            if((z[i]+r)>=h){u=1;break;}
        }
    }
    return 0;
}
int main()
{
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        scanf("%d%d%d",&n,&h,&r);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d",&x[i],&y[i],&z[i]);
            if(z[i]>maxz)maxz=z[i];
            if(z[i]<minz)minz=z[i];
            for(int j=1;j<=i-1;j++)
                dis[i][j]=dis[j][i]=diss(i,j);
        }
        if(((maxz+r)<h)||((minz-r)>0)){ans[k]=0;continue;}
        for(int i=1;i<=n;i++)
        {
            if(((z[i]-r)<=0)&&!u)
            {
                ansz=z[i];
                if((ansz+r)>=h){u=1;break;}
                visited[i]=1;
                search(i);
                memset(visited,0,sizeof(visited));
            }
            if(u)break;
        }
        if(u)ans[k]=1;
        else ans[k]=0;
        u=0;
    }
    for(int i=1;i<=t;i++)
    {
        if(ans[i])printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

D2T2 宝藏

传送门=￣ω￣=

题解见：https://www.mina.moe/archives/9443

这题告诉我们 NOIP 也是有难题的。。。

代码：

#pragma GCC optimize("Ofast,no-stack-protector")

#include <bits/stdc++.h>

#define NS (12)

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

typedef long long LL;

int n, m, d[NS][NS], dis[NS];

int v[1 << NS][1 << NS], f[NS][1 << NS], ans = INT_MAX;

int main(int argc, char const* argv[])
{
    IN(n), IN(m), memset(d, 63, sizeof(d)), memset(v, 63, sizeof(v));
    if (n == 1) puts("0"), exit(0);
    for (int i = 1, a, b, c; i <= m; i += 1)
    {
        IN(a), IN(b), IN(c), a--, b--;
        d[a][b] = d[b][a] = min(d[a][b], c);
    }
    for (int i = (1 << n) - 1; i > 1; i -= 1)
        for (int j = ((i - 1) & i); j; j = ((j - 1) & i))
        {
            memset(dis, 63, sizeof(dis)), v[j][i] = 0;
            for (int x = 0; x < n; x += 1) if ((j >> x) & 1)
                for (int y = 0; y < n; y += 1)
                    if (((i >> y) & 1) && !((j >> y) & 1))
                        dis[y] = min(dis[y], d[x][y]);
            for (int y = 0; y < n; y += 1)
                if (((i >> y) & 1) && !((j >> y) & 1))
                {
                    if (dis[y] > 1e9) {v[j][i] = 1e9; break;}
                    else v[j][i] += dis[y];
                }
        }
    for (int x = 0; x < n; x += 1)
    {
        memset(f, 63, sizeof(f)), f[0][1 << x] = 0;
        for (int i = 1; i < n; i += 1)
        {
            for (int s = (1 << n) - 1; s > 1; s -= 1)
                for (int z = ((s - 1) & s); z; z = ((z - 1) & s))
                    f[i][s] = min((LL)f[i][s], (LL)f[i - 1][z] + (LL)i * v[z][s]);
            ans = min(ans, f[i][(1 << n) - 1]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

D2T3 列队

传送门=￣ω￣=

因为每次操作以后被改变的只有第 $x$行、第 $m$列

那就搞 $n$个数据结构维护每行的前 $m – 1$个元素，再搞一个数据结构维护第 $m$列

这个数据结构要支持取出某个元素并删除，并支持尾部插入。

并且因为这题数据范围很大我们需要用到一个优化就是有的元素一直是相邻的我们就把它们作为一个节点。

也就是我们开始的时候一整个行/列都是一个节点，然后某次查询就从查询处断开该节点，分成三个节点。。。

这样感觉好难打啊。。。

于是乎我就打了个线段树的做法。

线段树动态开点，维护每个区间有多少个元素被删除了。

这样通过线段树上二分就可以找到你想要的元素的位置，然后把这个位置的删除数目+1

然后对于新加入这一行/列的元素用个 vector 存起来，每次找到位置后如果发现位置大于这一行/列的大小就去 vector 里查。。。

真是奇妙。

这道题告诉我们 NOIP 也会有比较数据结构的题。。。要耐下性子。。。

代码：

#include <bits/stdc++.h>

#define NS (300005)

typedef long long LL;

using namespace std;

template <typename _Tp> inline void IN(_Tp& dig)
{
    char c; bool flag = 0; dig = 0;
    while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
    while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
    if (flag) dig = -dig;
}

int n, m, q, M, root[NS], del[NS * 20], s[NS * 20][2], sz;

vector<LL> g[NS];

int Query(int x, int l, int r, int a)
{
    if (l == r) return l;
    int mid = (l + r) >> 1, tmp = mid - l + 1 - del[s[a][0]];
    if (tmp >= x)
        return Query(x, l, mid, s[a][0]);
    return Query(x - tmp, mid + 1, r, s[a][1]);
}

void Del(int x, int l, int r, int& a)
{
    if (!a) a = ++sz;
    del[a]++;
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (x <= mid) Del(x, l, mid, s[a][0]);
    else Del(x, mid + 1, r, s[a][1]);
}

LL Rm(int x, LL v)
{
    int pos = Query(x, 1, M, root[n + 1]); LL res = 0;
    Del(pos, 1, M, root[n + 1]);
    if (pos <= n) res = 1ll * pos * m;
    else res = g[n + 1][pos - n - 1];
    if (v) g[n + 1].push_back(v);
    else g[n + 1].push_back(res);
    return res;
}

void Work(int x, int y)
{
    int pos = Query(y, 1, M, root[x]);
    Del(pos, 1, M, root[x]);
    LL tmp = 0;
    if (pos < m) tmp = 1ll * (x - 1) * m + pos;
    else tmp = g[x][pos - m];
    g[x].push_back(Rm(x, tmp)), printf("%lld\n", tmp);
}

int main(int argc, char const* argv[])
{
    IN(n), IN(m), IN(q), M = max(n, m) + q;
    int x, y;
    while (q--)
    {
        IN(x), IN(y);
        if (y < m) Work(x, y);
        else printf("%lld\n", Rm(x, 0));
    }
    return 0;
}
分类： 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

老K · 2018年10月26日 10:53 上午

奶酪这题…. 我去年发现会爆 ll 然后无脑 ull(甚至包括%llu)

然后就洛谷爆 0 了

最后 80

回复

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注