2019.8.4 集训解题报告

2019 年 8 月 4 日 星期日
/ , , , ,
2

2019.8.4 集训解题报告

  • 当一个 OIer 比你强还比你小的时候，你就可以退役了。

考试

数列变换

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

Test′sTest's CodeCode：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

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

FixedFixed CodeCode：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;
}

小学生的算法太又简洁又优雅，我太菜了 qwqqwq

卡牌游戏

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

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

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

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

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

HackHack 数据：

INPUT:

2 3 ATK 599 ATK 1000 1200 600 450

OUTPUT:

651

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

FixedFixed CodeCode：100%（水 HackHack：121\frac{1}{21}+ 水 TLETLE：121\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′sdalao's CodeCode：真 · 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]f[t][i][j] 表示当前时间为 tt 时，在坐标为 i,ji,j 时的最大路径。

转移方程也很显然易见： f[t][i][j] = max { f[t - 1][i][j],f[t - 1][i'][j'] + 1 } 但是时间复杂度高达：O(Tnm)O(Tnm)

第二种：

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

转移方程想想也就可以出来： f[k][i][j] = max {f[k - 1][i][j], f[k][i'][j'] + dis } 但是复杂度还是很高。。。。

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

这个 MaxMax 可以优化一下，因为只要我们知道了最大值，那么直接就可以 O(1)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)(f[k][x][i] - i) 的最大就可以了，然后当然就是使用单调队列来更新这个值。

FixedFixed CodeCode：

#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;
}

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...