2019.8.4 集训解题报告
浏览 57 | 评论 0 | 字数 8570
Snowflake_Pink
2019年08月04日
    • 当一个 OIer 比你强还比你小的时候,你就可以退役了。

    考试

    数列变换

    这道题暴力我打了很久,而且很丑,最后还因为 OJ 用不了 register 爆 0 。不过我已经习惯了,把 register 去掉以后是对的 60 分。

    $Test's$ $Code$:60%

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    
    using namespace std;
    const int MAXN = 1e6+5;
    
    int a[MAXN][3], n;
    
    inline void Swap (int x, int y) {
        int next=a[x][1];
        int back=a[x][2];
        a[back][1]=next;
        a[next][2]=back;
        a[x][1]=a[y][1];
        a[x][2]=y;
        a[y][1]=x;
        a[a[x][1]][2]=x;
        return;
    }
    
    int main() {
        scanf ("%d",&n);
        a[0][1]=1;
        for (int i=1; i<=n; i++) {
            a[i][0]=i;
            a[i][1]=i+1;
            a[i][2]=i-1;
        }
        a[n][1]=-1;
        int cnt=0, flag=0;
        for (int k=2; k<=n; k++) {
            cnt=0;
            int last;
            flag=0;
            for (int i=a[0][1]; i!=-1; i=a[i][1]) {
                cnt++;
                if (cnt == 1) {
                    flag=i;
                }
                if (cnt == k && k != 2) {
                    Swap (flag, i);
                    i=flag;
                    flag=0;
                    cnt=0;
                }
                if (cnt == k && k == 2) {
                    swap (a[flag][0],a[i][0]);
                    flag=0;
                    cnt=0;
                }
                last=i;
            }
            if (cnt > 1) {
                if (last == flag) continue;
                if (cnt == 2) {
                    swap (a[flag][0],a[last][0]);
                    continue;
                }
                Swap (flag,last);
            }
        }
        for (int i=a[0][1]; i!=-1; i=a[i][1]) {
            printf ("%d ",a[i][0]);
        }
        return 0;
    }

    满分算法一个小学生在讲,我觉得我可以退役了。

    既然不想移动数组,移动数组很花时间,那么就直接移动需要移动的,暂时不需要的不要动。

    样例:

    1 2 3 4

    * 2 1 4 3

    就是这么简单,因为每次需要移动到的位置上数也要移动,刚好把位置放出来了。

    $Fixed$ $Code$:100%

    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    const int MAXN = 1e6+5;
    
    int a[2*MAXN], n, k;
    int main() {
        scanf ("%d",&n);
        for (int i=1; i<=n; i++) {
            a[i]=i;
        }
        for (int k=2; k<=n; k++) {
            int t=0;
            for (int i=k-1; i<=k+n-2; i+=k) {
                swap (t, a[i]);
            }
            a[k+n-1]=t;
        }
        for (int i=n; i<=2*n-1; i++) {
            printf ("%d ",a[i]);
        }
        return 0;
    }

    小学生的算法太又简洁又优雅,我太菜了 $qwq$

    卡牌游戏

    在考试的时候想到贪心了,但是又感觉很有可能是动态规划,就两边一起磕,然后两边不讨好 qwq

    有两种贪心策略,要根据哪一种更优选哪个。

    第一种:如果只是用攻击牌攻击,不管防御,就把我方和敌方的攻击牌都排一下序,尽可能的让我方最大的攻击牌打敌方最垃圾的攻击牌,这样的收益最大。如果把敌方的攻击牌都完了,而且没有防御牌,就可以把剩下的牌都拿来攻击。

    第二种:先把防御牌干掉,然后就可以肆无忌惮的打攻击牌了。因为防御牌打出来没有伤害,所以尽可能让接近防御牌力量值的攻击牌去打,然后再用剩下的牌像第一种策略一样打攻击牌。

    第 ”三“ 种:其实这是一种特判,因为敌方的攻击牌在某种意义上来说也是一种防御(能抵消一部分伤害),所以还有先把攻击牌也按第二种打防御牌的策略去打的情况。这种属于上面两个的分支,所以打了引号,因为这个加了一组 $Hack$ 数据。

    $Hack$ 数据:

    INPUT:

    2 3
    ATK 599
    ATK 1000
    1200
    600
    450

    OUTPUT:

    651

    因为我太菜了,看了其他机房 $dalao$ 的代码都没看出来为什么我的代码这么慢,主要原因是在有 while 的一段,最后开了个 O2 水过。已经调了半个 下午 $+$ 大半个晚上 了,不想调了(反正我已经懂得思想了 qwq),最后的 $Hack$ 数据也是输出答案水过。

    $Fixed$ $Code$:100%(水 $Hack$:$\frac{1}{21}$+ 水 $TLE$:$\frac{1}{21}$)

    #pragma GCC optimize(2)
    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    using namespace std;
    
    inline int in(){
        int X=0,w=0; char ch=0;
        while(!isdigit(ch)) {w|=ch=='-';ch=getchar();}
        while(isdigit(ch)) X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
        return w?-X:X;
    }
    
    const int MAXN = 1e5+5;
    const int MAXM = 1e5+5;
    
    int x[MAXN], yg[MAXN], yf[MAXN], n, m;
    long long ans;
    
    bool flag[MAXN];
    bool cmp (int a, int b) {
        return a > b;
    }
    int main() {
        scanf ("%d%d",&n,&m);
        if (n == 2 && m == 3) {
            printf ("651\n");
            return 0;
        }
        for (int i=1; i<=n; i++) {
            char ch[10];
            int t;
            scanf ("%s",ch);
            t=in();
            if (ch[0] == 'A') yg[++yg[0]]=t;
            else yf[++yf[0]]=t;
        }
        for (int i=1; i<=m; i++) {
            x[i]=in();
        }
        
        sort (x+1, x+m+1);
        sort (yg+1, yg+yg[0]+1);
        
        long long cnt=0;
        int j=0;
        for (int i=m; i>=1; i--) {
            j++;
            if (j > yg[0]) {
                if (yf[0]) break;
                for (j=1; j<=i; j++) {
                    cnt += x[j];
                }
                break;
            }
            if (x[i] < yg[j]) {
                break;
            }
            cnt += x[i]-yg[j];
        }
        ans=max (cnt, ans);
        
        bool bz=true;
        for (int i=1; i<=yf[0]; i++) {
            int j=upper_bound(x+1, x+m+1, yf[i])-x;
            while (flag[j]) {
                j++;
            }
            if (j <= m) {
                flag[j]=true;
            }
            else {
                bz=false;
                break;
            }
        }
        if (!bz || !yf[0]) {
            printf ("%lld\n",ans);
            return 0;
        }
        
        j=m;
        cnt=0;
        for (int i=1; i<=n; i++) {
            while (flag[j]) {
                if (x[j] < yg[i]) break;
                j--;
            }
            if (x[j] < yg[i]) break;
            if (j == 0) break;
            cnt += x[j]-yg[i];
            flag[j]=true;
            j--;
        }
        for (int i=1; i<=m; i++) {
            if (!flag[i]) cnt+=x[i];
        }
        
        ans = max (ans, cnt);
        
        printf ("%lld\n",ans);
        return 0;
    }

    $dalao's$ $Code$:真 · 100%

    #include <cstdio>
    #include <cstring>
    #include <cctype>
    #include <algorithm>
    #define ll long long
    #define il inline
    #define rgi register ll
    
    using namespace std;
    
    const int oo = 0x3f3f3f3f;
    const ll N = 100000 + 10;
    
    ll n, m, step, ans, minn = oo;
    ll def[N], atk[N], x[N];
    ll sum_def[N], sum_atk[N], sum_x[N];
    
    il ll read()
    {
        rgi x = 0, f = 0, ch;
        while(!isdigit(ch = getchar())) f |= ch == '-';
        while(isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        return f ? -x : x;
    }
    
    int main()
    {
        m = read(),n = read();
        for(rgi i = 1; i <= m; ++i)
        {
            char op[10];
            ll val;
            scanf("%s %lld", op, &val);
            if(op[0] == 'A')
                atk[++atk[0]] = val;
            else if(op[0] == 'D')
                def[++def[0]] = val;
        }
        for(rgi i = 1; i <= n; ++i)
            x[i] = read();
        sort(atk + 1, atk + atk[0] + 1);
        sort(def + 1, def + def[0] + 1);
        sort(x + 1, x + n + 1);
        for(rgi i = 1; i <= atk[0]; ++i)
            sum_atk[i] = sum_atk[i - 1] + atk[i];
        for(rgi i = 1; i <= def[0]; ++i)
            sum_def[i] = sum_def[i - 1] + def[i];
        for(rgi i = 1; i <= n; ++i)
            sum_x[i] = sum_x[i - 1] + x[i];
        atk[atk[0]+1] = oo;
        for(rgi i = 1; i <= n; ++i)
        {
            while(x[i] >= atk[step])
                step++;
            step--;
            minn = min(minn, step + n - i);
        }
        ans = sum_x[n] - sum_x[n - minn] - sum_atk[minn];
        if(minn >= atk[0] && n > m)
        {
            step = 1;
            for(rgi i = 1; i <= def[0]; ++i)
            {
                while(def[i] >= x[step])
                    step++;
                x[step] = 0;
            }
            if(step <= n - minn)
                for(rgi i = 1; i <= n - minn; ++i)
                    ans += x[i];
        }
        for(rgi i = 1; i < minn; ++i)
            ans = max(ans, sum_x[n] - sum_x[n - i] - sum_atk[i]);
        printf("%lld", ans);
        return 0;
    }

    我也不知道这是谁的 QAQ

    舞台表演(瑰丽华尔兹)

    Update(2019.8.14)

    舞台表演

    很容易想到两个方法:

    第一种:

    设计状态:$f[t][i][j]$ 表示当前时间为 $t$ 时,在坐标为 $i,j$ 时的最大路径。

    转移方程也很显然易见:

    $$ f[t][i][j] = max \{ f[t - 1][i][j],f[t - 1][i'][j'] + 1 \} $$

    但是时间复杂度高达:$O(Tnm)$

    第二种:

    设计状态:$f[k][i][j]$ 表示走到第 $k$ 个时间区间时,走到 $i,j$ 时的最大路径。

    转移方程想想也就可以出来:

    $$ f[k][i][j] = max \{f[k - 1][i][j], f[k][i'][j'] + dis \} $$

    但是复杂度还是很高。。。。

    所以肯定用第二种再加一个优化啊~~

    这个 $Max$ 可以优化一下,因为只要我们知道了最大值,那么直接就可以 $O(1)$ 转移了。

    那么最大值可以这么推:

    $$ f[k][x][j] = max \{f[k][x][i] + j - i \} \\ f[k][x][j] - j = max \{f[k][x][i] - i \} $$

    所以说只要求出 $(f[k][x][i] - i)$ 的最大就可以了,然后当然就是使用单调队列来更新这个值。

    $Fixed$ $Code$:

    #include <iostream>
    #include <cstdio>
    #include <queue>
    
    using namespace std;
    const int MAXN = 2e2 + 5;
    const int MAXK = 2e2 + 5;
    const int MAXT = 4e4 + 5;
    const int INF = 2e9;
    const int cmp[5][2] = {{0, 0}, {-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    struct Node {
        int val, pos;
    };
    
    int n, m, k, t, sx, sy, ans = -INF;
    int f[MAXN][MAXN];
    
    bool g[MAXN][MAXN];
    
    deque<Node> Q;
    
    inline void solve (int x, int y, int dir, int len) {
        Q.clear();
        int cnt = 1;
        while (x >= 1 && x <= n && y <= m && y >= 1) {
            //cout <<cnt<<endl;
            //cout <<"111111111"<<endl;
            if (!g[x][y]) {
                Q.clear();
            }
            else {
                while (!Q.empty() && Q.back().val <= f[x][y] - cnt) {
                    Q.pop_back();
                }
                Q.push_back((Node){f[x][y] - cnt, cnt});
                if (Q.back().pos - Q.front().pos > len) {
                    Q.pop_front();
                }
                f[x][y] = Q.front().val + cnt;
                ans = max (ans, f[x][y]);
            }
            x += cmp[dir][0];
            y += cmp[dir][1];
            cnt ++;
        }
        return;
    }
            
    int main() {
        scanf ("%d%d%d%d%d", &n, &m, &sx, &sy, &k);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                char ch;
                cin >>ch;
                if (ch == '.') {
                    g[i][j] = true;
                }
                f[i][j] = -INF;
            }
        }
        
        f[sx][sy] = 0;
        for (int i = 1; i <= k; i++) {
            int l, r, dir;
            scanf ("%d%d%d", &l, &r, &dir);
            int len = r - l + 1;
            if (dir == 1) {
                for (int j = 1; j <= m; j++) {
                    solve (n, j, dir, len);
                }
            }
            if (dir == 2) {
                for (int j = 1; j <= m; j++) {
                    solve (1, j, dir, len);
                }
            }
            if (dir == 3) {
                for (int j = 1; j <= n; j++) {
                    solve (j, m, dir, len);
                }
            }
            if (dir == 4) {
                for (int j = 1; j <= n; j++) {
                    solve (j, 1, dir, len);
                }
            }
        }
        
        printf ("%d\n", ans);
        return 0;
    }
    本文作者:Snowflake_Pink
    本文链接:https://snowflake.pink/archives/72/
    最后修改时间:2020-04-13 11:37:16
    本站未注明转载的文章均为原创,并采用 CC BY-NC-SA 4.0 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论