NOIp2017提高组游记

NOIp2017提高组游记

NOIp2017提高组游记

前言

NOIp2017已经结束了,由于复赛结束后我没有机会写游记,到这个周末才补上。虽然下个星期期中考

初赛日期2017/10/14,复赛2017/11/11和12,今年还是衢州。本文只包含复赛。

值得一提的是,复赛day1双十一和马拉松,day(-1)和day0是学校秋季运动会,当然我们甚至没机会去看开幕式。

day0

上午有一场两个半小时的模拟赛,题目确实不难,但是我只有230,而很多人都300,没什么信心。

T3给定一棵树,求保留最少的边使得覆盖的点不少于K,由于一条边可以覆盖1或2个点,可以用树形DP或贪心求出最多有几条边可以覆盖2个点,而我却写了二分图匹配,还写错了。还好交了暴力的30分。

12:30我们准时从西门出发,预计三个小时到,最终到四点左右才到达衢州饭店。路上基本也没干什么。

衢州饭店还是比较好的,我们住在三号楼一楼,要走过很长的走廊。矿泉水一个人一小瓶,杯子倒是很多。拖鞋是循环使用的,所以不能带走。我选了靠窗的床,事实证明还是很对的,因为可以方便放东西。无线网不太稳定,反而还是旁边的比较好。

从旅馆到衢州二中堵了很长时间,到学校领袋子,晚饭在学校吃。回去就快多了。晚上看了洛谷模板,包括(下次可以参考)

  • SSSP
  • KMP(看完认为还是滚回hash吧)
  • Dinic(初赛暗示网络流?)
  • 可并堆(还是不太会)
  • LCA(上午刚写过)
  • 树剖
  • 匈牙利
  • Tarjan割边割点
  • Lucas
  • exgcd(初赛前也看过)

我看了一会儿WARRIORS:Omen of The Stars #6 The Last Hope,再来一句StarClan, light my path, please. 规划好day1要带的物品后,我们十点多睡觉。

day1

6:20起床,去吃自助餐,并不是很好。我在9号考场,要走不少路才能到,不过去年也一样。

OS是Windows 7,我打开了仪表盘。果然没有Notepad++。

小凯的疑惑(math)

题意

给定\(a,b\vert (a,b)=1\),求\(ax+by\vert x,y\in\mathbb N\)不能表示的最大的数,保证有解。

3 7
11

数据范围

  • 对于30%的数据,\(a,b\le50\)
  • 对于60%的数据,\(a,b\le10,000\)
  • 对于100%的数据,\(1\le a,b\le10^9\)

思路

看到这题我立刻想到了一道USACO的题目,猜想答案应该不大于\(ab+a+b\)。对于\(ax+by=1\),用exgcd求出\(x_0,y_0\),然后枚举\(c\),解为\(cx_0+kb,cy_0-kb\),强制\(x\ge0\),如果\(y<0\)显然无解。不过我不知道复杂度,后来还列出了一个带上取整的不等式,解出的结果只含有\(a,b\),但是样例都不对,于是我放弃了。直接从\(ab\)向下枚举,输出第一个无解的数。好像\(a,b\le10^6\)都能很快算出。

时间复杂度\(\mathcal O(?)\),预计得分60/60+


结束后才知道大部分人都做出了这题,答案是\(ab-a-b\)。所以我的时间复杂度为\(\mathcal O(a+b)\)

代码

用来对拍的暴力:

时间复杂度(complexity)

题意

给定一个\(L\)行只含有for循环的程序,初值和末值可以是常数或\(n\),判断其复杂度分析是否正确。可能存在循环不匹配和变量重名错误需要判断。多组数据。

8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

数据范围

  • 对于30%的数据,数据保证小明给出的每个程序的前\(L/2\)行一定为以F开头的语句,第\(L/2+1\)行至第\(L\)行一定为以E开头的语句,\(L\le10\)
  • 对于50%的数据,若\(x,y\)均为整数,\(x\)一定小于\(y\),且只有\(y\)有可能为\(n\)
  • 对于70%的数据,不存在语法错误。
  • 对于100%的数据,\(L\le100\)

思路

麻烦的题目,不过我自认为有优势,看起来有点像COWBASIC。\(n\)和常数怎么判断呢?不过我很快想到了数值法,把很大的数代入\(n\),求一下实际复杂度和理论复杂度,如果误差是很小的则认为正确。

接下来的问题在于确定\(n\)的值。一开始我以为最多有50层循环,后来发现由于字母的限制最多只有25层。一开始我选择了\(\{500,1000\}\),后来发现太小了。最终我选择了\(\{10^9,2\times10^9\}\),用double计算。最大误差取\(0.01\)

还有表达式计算的问题,我发现每层栈里应该保存该层循环次数和该层累计的数值。

时间复杂度\(\mathcal O(L)\),预计得分100


结束后才得知只需要模拟一下,因为每层循环只能执行\(0\),\(\Theta(1)\)\(\Theta(n)\)次。注意判断执行\(0\)次时的问题即可。

代码

很长……调了不少时间

#include <fstream>
#include <string>
#include <cstring>
#include <sstream>
#include <algorithm>
#include <cmath>
using namespace std;
ifstream fin("complexity.in");
ofstream fout("complexity.out");
const int N = 105, vn[] = {1000000000, 2000000000};
double s[N][2], res[2];
bool vis[26];
struct line
{
    int opt, l, r;
} prog[N];
int str2int(const string &s)
{
    stringstream ss(s);
    int x;
    ss >> x;
    return x;
}
double calc(const line &p, int n)
{
    int l = p.l, r = p.r;
    if (l == 1000)
        l = n;
    if (r == 1000)
        r = n;
    return max(r - l + 1, 0);
}
int main()
{
    int t;
    fin >> t;
    while (t--)
    {
        int l;
        string comp;
        fin >> l >> comp;
        memset(vis, 0, sizeof(vis));
        bool valid = true;
        string st;
        for (int i = 1; i <= l; i++)
        {
            char opt;
            fin >> opt;
            if (opt == 'F')
            {
                char var;
                string l, r;
                fin >> var >> l >> r;
                if (vis[var - 'a'])
                    valid = false;
                vis[var - 'a'] = true;
                st += var;
                prog[i].opt = 1;
                if (l == "n")
                    prog[i].l = 1000;
                else
                    prog[i].l = str2int(l);
                if (r == "n")
                    prog[i].r = 1000;
                else
                    prog[i].r = str2int(r);
            }
            else
            {
                if (st == "")
                    valid = false;
                else
                {
                    vis[st[st.length() - 1] - 'a'] = false;
                    st.erase(st.length() - 1, 1);
                }
                prog[i].opt = 2;
            }
        }
        if (st != "")
            valid = false;
        if (!valid)
        {
            fout << "ERR\n";
            continue;
        }
        for (int t = 0; t < 2; t++)
        {
            s[0][1] = .0;
            int sp = 0;
            for (int i = 1; i <= l; i++)
                if (prog[i].opt == 1)
                {
                    s[++sp][0] = calc(prog[i], vn[t]);
                    s[sp][1] = .0;
                }
                else
                {
                    if (s[sp][1] == .0)
                        s[sp][1] = 1.;
                    s[sp - 1][1] += s[sp][0] * s[sp][1];
                    sp--;
                }
            double th;
            if (comp == "O(1)")
                th = 1.;
            else
                th = pow(vn[t], str2int(comp.substr(4, comp.length() - 5)));
            if (s[0][1] == .0)
                s[0][1] = 1.;
            res[t] = s[0][1] / th;
        }
        if (fabs(1 - res[0] / res[1]) < 0.01)
            fout << "Yes\n";
        else
            fout << "No\n";
    }
    return 0;
}

逛公园(park)

题意

求有向图中\(1->N\)长度不超过\(d+K\)的路径数,其中\(d\)\(1->N\)的最短路长度,可能有0边,如果有无穷条合法路径输出\(-1\)。多组数据

2
5 7 2 10
1 2 1
2 4 0
4 5 2
2 3 2
3 4 1
3 5 2
1 5 3
2 2 0 10
1 2 0
2 1 0
3
-1

数据范围

测试点编号 \(T\) \(N\) \(M\) \(K\) 是否有0边
1 5 5 10 0
2 5 1000 2000 0
3 5 1000 2000 50
4 5 1000 2000 50
5 5 1000 2000 50
6 5 1000 2000 50
7 5 100000 200000 0
8 3 100000 200000 50
9 3 100000 200000 50
10 3 100000 200000 50

思路

T2用了较多时间。毫无思路,当然\(K=0\)就是最短路计数,而\(K>0\)好像可以用K短路之类的方法。于是我还求了\(N\)为起点的最短路,然后从\(1\)开始dfs,如果当前距离+最短路\(>d+K\)剪枝。不知道有多少分。

时间复杂度\(\begin{cases}\mathcal O((n+m)\log n)&K=0\\ \mathcal O(?)&K>0\end{cases}\),预计得分30/30+

代码

这份代码没有包含functional,在VC++下std::greater<state>未定义。

#include <fstream>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("park.in");
ofstream fout("park.out");
const int N = 100005, M = 200005, INF = 1e9;
int n, m, k, p, head[N], v[M], w[M], nxt[M], e, d[N], f[N];
int rhead[N], rv[M], rw[M], rnxt[M], re, rd[N], ans;
bool vis[N];
inline void add_edge(int u, int v, int w)
{
    ::v[++e] = v;
    ::w[e] = w;
    nxt[e] = head[u];
    head[u] = e;
}
inline void radd_edge(int u, int v, int w)
{
    ::rv[++re] = v;
    ::rw[re] = w;
    rnxt[re] = rhead[u];
    rhead[u] = re;
}
void dfs(int u, int dist)
{
    if (dist + rd[u] > d[n] + k)
        return;
    if (u == n)
    {
        ans = (ans + 1) % p;
        return;
    }
    for (int i = head[u]; i; i = nxt[i])
        dfs(v[i], dist + w[i]);
}
int main()
{
    int t;
    fin >> t;
    while (t--)
    {
        fin >> n >> m >> k >> p;
        e = re = 0;
        fill(head + 1, head + n + 1, 0);
        fill(rhead + 1, rhead + n + 1, 0);
        while (m--)
        {
            int u, v, w;
            fin >> u >> v >> w;
            add_edge(u, v, w);
            radd_edge(v, u, w);
        }
        typedef pair<int, int> state;
        fill(d + 1, d + n + 1, INF);
        d[1] = 0;
        priority_queue<state, vector<state>, greater<state>> Q;
        Q.push(make_pair(0, 1));
        fill(f + 1, f + n + 1, 0);
        f[1] = 1;
        fill(vis + 1, vis + n + 1, false);
        while (!Q.empty())
        {
            state k = Q.top();
            Q.pop();
            if (vis[k.second])
                continue;
            vis[k.second] = true;
            for (int i = head[k.second]; i; i = nxt[i])
                if (d[k.second] + w[i] < d[v[i]])
                {
                    f[v[i]] = f[k.second];
                    Q.push(make_pair(d[v[i]] = d[k.second] + w[i], v[i]));
                }
                else if (d[k.second] + w[i] == d[v[i]])
                    (f[v[i]] += f[k.second]) %= p;
        }
        if (k == 0)
            fout << f[n] << endl;
        else
        {
            fill(rd + 1, rd + n + 1, INF);
            rd[n] = 0;
            priority_queue<state, vector<state>, greater<state>> Q;
            Q.push(make_pair(0, n));
            fill(vis + 1, vis + n + 1, false);
            while (!Q.empty())
            {
                state k = Q.top();
                Q.pop();
                if (vis[k.second])
                    continue;
                vis[k.second] = true;
                for (int i = rhead[k.second]; i; i = rnxt[i])
                    if (rd[k.second] + rw[i] < rd[rv[i]])
                        Q.push(make_pair(rd[rv[i]] = rd[k.second] + rw[i], rv[i]));
            }
            ans = 0;
            dfs(1, 0);
            fout << ans << endl;
        }
    }
    return 0;
}

剩下的时间

听说很多人都会做T1和T3,大多200+,我感到很绝望,希望T2不要炸。听说T1是小学奥数题,以及有人做过原题。而T3则是“图论算法集合”?

下午没看几页书,晚饭据说从学校打包到旅馆,还必须在员工餐厅里吃,不过zyy好像早跑了。晚上看了一集下午的《自然传奇》,心态好了很多。fks提出敲一下[ZJOI2008]树的统计,他很快就A了,我很害怕没去写,万一真的考了树剖呢。不过吸取一下把int开成char的教训。睡得比前一天早。

day2

奶酪(cheese)

题意

一块长宽无限高为\(h\)的奶酪里有\(n\)个半径均为\(r\)的空洞,下表面\(z=0\),上表面\(z=h\)。两个空洞相交或相切可以从一个到达另一个,与表面相交或相切则可以从表面到达空洞。求能否从下表面到达上表面。多组数据

3
2 4 1
0 0 1
0 0 3
2 5 1
0 0 1
0 0 4
2 5 2
0 0 2
2 0 4
Yes
No
Yes

数据范围

  • 对于20%的数据,\(n=1\)
  • 对于40%的数据,\(n\le8\)
  • 对于80%的数据,\(h,r,\vert x\vert,\vert y\vert,\vert z\vert\le10,000\)
  • 对于100%的数据,\(1\le n\le1,000,1\le h,r,\vert x\vert,\vert y\vert,\vert z\vert\le10^9\)

思路

计算几何,吃笔记本稳了?分治?不过看到\(n\le1,000,T\le20\)就很简单了,不就是直接bfs。注意一下long long应该就可以了吧。不会卡常吧?

时间复杂度\(\mathcal O(Tn^2)\),预计得分100


果然那么简单还是有陷阱的,\((2\times10^9)^2\times3=12\times10^{18}>2^{63}\)!所以要unsigned long long或者把左边的一项移到不等式右边。只有80了。

让我欣慰的是,有人直接用浮点数开根,可能被卡常,还有人用了int……另外据说\(z\ge0\)

代码

宝藏(treasure)

题意

给定一张无向图,需要选定一个点\(s\),每条边的代价\(c_i=w_i\times(\min(dist_{s,u_i},dist_{s,v_i})+1)\),求生成树最小代价和。

4 5
1 2 1
1 3 3
1 4 1
2 3 4
3 4 1
4

数据范围

  • 对于20%的数据,保证输入是一棵树
  • 对于40%的数据,所有\(w_i\)相等
  • 对于70%的数据,\(n\le8,w_i\le5,000\)
  • 对于100%的数据,\(1\le n\le12,0\le m\le1,000,w_i\le500,000\)

思路

重边显然取min,这样边数只有\(\frac{n(n-1)}2\),但好像基于边比较难做。似乎暴力也很难写,但我yy出了一种奇怪的做法:类似Prim,每次选择一个不在生成树中的点加入,更新最短路,然后继续搜。具体见代码。如果无解怎么办?

时间复杂度\(\mathcal O(n^3n!)\),预计得分70


应该是状压DP,还有人写了多项式复杂度的贪心。

代码

列队(phalanx)

题意

给定一个\(n\times m\)的矩阵\(A\)\(A_{i,j}=(i-1)m+j\)\(q\)次操作(\(n,m,q\le3*10^5\)),每次删除一个位置\((x,y)\),然后将第\(x\)行向左补齐,再将第\(m\)列向前补齐,最后在\(A_{n,m}\)填上删除的数。求每次删除的数。

2 2 3
1 1
2 2
1 2
1
1
4

数据范围

思路

果然有数据结构题,然而并不会做。不过部分分很丰富,有点天天爱跑步的感觉。

前30%直接暴力,而50%比较有趣,\(q\le500\),远小于矩阵规模,可见很多行除第\(m\)列外根本不会变。那么可以在每次询问时如果\(x\)行第一次出现,暴力构建,再进行操作,当然也要维护第\(m\)列的数。每行的数据可以用一个指针数组或者std::vector记录。

再考虑\(n=1\)的情况,问题简化为一个数列,每次删除一个数,把它放在最后。随机访问的链表?好像不太对。不过如果不删除数,只是简单的打标记\(flag_y\),然后最后新增,问题就转换为求第一个\(i\vert i-\sum_{j=1}^i flag_j=y\),显然可以二分。前缀和可以用树状数组维护,\(\log^2 n\),如果线段树树上二分可以做到\(\log n\),完美解决。具体实现时,发现不必写递归版的线段树,非递归的更简单。

如果只有\(x=1\),发现只要用队列维护第\(m\)列即可。

好像输入输出很大,想到模拟赛fstream被卡常的经历,我还写了输入输出优化。

时间复杂度\(\begin{cases}\mathcal O(q\log m)&x=1\\ \mathcal O((n+m)q)&\text{otherwise}\end{cases}\),预计得分80

代码

#include <cstdio>
#include <cctype>
#include <queue>
using namespace std;
const int N = 50005, N2 = 600005, SZ = 1e6;
unsigned last[N], *a[N];
int tree[N2 * 4];
long long val[N2];
FILE *fin = fopen("phalanx.in", "r"), *fout = fopen("phalanx.out", "w");
char ibuf[SZ], *ip = ibuf, *iend = ibuf, obuf[SZ], *op = obuf, *oend = obuf + SZ;
inline char nextchar()
{
    if (ip == iend)
    {
        iend = ibuf + fread(ibuf, 1, SZ, fin);
        ip = ibuf;
    }
    return *ip++;
}
inline void nextchar(char c)
{
    if (op == oend)
    {
        fwrite(obuf, 1, SZ, fout);
        op = obuf;
    }
    *op++ = c;
}
template <typename Int>
inline void read(Int &x)
{
    char c;
    for (c = nextchar(); isspace(c); c = nextchar())
        ;
    x = 0;
    for (; isdigit(c); c = nextchar())
        x = x * 10 + c - '0';
}
int dig[20];
template <typename Int>
inline void writeln(Int x)
{
    int len = 0;
    do
        dig[++len] = x % 10;
    while (x /= 10);
    for (; len; len--)
        nextchar(dig[len] + '0');
    nextchar('\n');
}
int main()
{
    int n, m, q;
    read(n);
    read(m);
    read(q);
    if (n <= 5e4 && m <= 5e4 && q <= 500)
    {
        for (int i = 1; i <= n; i++)
            last[i] = 1u * i * m;
        while (q--)
        {
            int x, y;
            read(x);
            read(y);
            if (!a[x])
            {
                a[x] = new unsigned[m + 1];
                for (int i = 1; i < m; i++)
                    a[x][i] = 1u * (x - 1) * m + i;
            }
            a[x][m] = last[x];
            unsigned tmp = a[x][y];
            for (int i = y + 1; i <= m; i++)
                a[x][i - 1] = a[x][i];
            for (int i = x + 1; i <= n; i++)
                last[i - 1] = last[i];
            last[n] = tmp;
            writeln(tmp);
        }
        for (int i = 1; i <= n; i++)
            if (a[i])
                delete[] a[i];
    }
    else
    {
        //solve x=1
        queue<long long> last;
        for (int i = 1; i <= n; i++)
            last.push(1ll * i * m);
        for (int i = 1; i <= m; i++)
            val[i] = i;
        for (int t = 1; t <= q; t++)
        {
            int x, y;
            read(x);
            read(y);
            int id = 1, l = 1, r = m + q, sum = 0;
            while (l < r)
            {
                int mid = (l + r) / 2;
                if (mid - tree[id * 2] - sum >= y)
                {
                    r = mid;
                    id *= 2;
                }
                else
                {
                    sum += tree[id * 2];
                    l = mid + 1;
                    id = id * 2 + 1;
                }
            }
            long long tmp = val[l];
            tree[id] = 1;
            while (id > 1)
                tree[id /= 2]++;
            last.pop();
            last.push(tmp);
            val[m + t] = last.front();
            writeln(tmp);
        }
    }
    fwrite(obuf, 1, op - obuf, fout);
    return 0;
}

剩下的时间

我感觉day2比day1简单,听说不少人T1出现了一些偏差。而T3我也很高兴拿了这么多部分分。快到时,选手程序已经公开,cfb在洛谷上交他的程序,车上气氛活跃。大约16点回到学校西门。

我们去机房交自己的程序,看洛谷的数据。我手忙脚乱的改输入输出,还CE了一次。所幸我的成绩没有太大的偏差,反而高了。洛谷比赛结束时有3.4K用户参加排名,其中有45个AK。

几天后

洛谷455,绍一490,学军420,波动比较大。不过据说洛谷的分数比较准确。

初测440,浙江省Rank125,学校Rank18,年段第六。浙江一等奖分数线据说大约395。

math complex park cheese treasure phalanx 总分
60 100 30 100 70 80 440

浙江省分数线360,共305人获奖,大约53%……因为特派员已经被提高了5分……

按照公式有理有据,自从历年一等奖不占名额后,一等奖人数大幅增加。明年350人应该没问题了。

评论