2019-08-04 纪中NOIP模拟赛B组

时间:2021-04-11 09:49:31

T1 [JZOJ3403] 数列变换

题目描述

  小X看到堆成山的数列作业十分头疼,希望聪明的你来帮帮他。考虑数列A=[A1,A2,...,An],定义变换f(A,k)=[A2,A3,...,Ak,A1,Ak+2,Ak+3,...,A2k,Ak+1,...],也就是把A分段,每段k个(最后如果不足k个,就全部分到新的一段里),然后将每段的第一个移动到该段的最后一个。

  现在,小X想知道f(f(f(f([1,2,3,...,n],2),3),...),n)的结果。

数据范围

  对于 $60 \%$ 的数据,$1 \leq n \leq 10^3$

  对于 $100 \%$ 的数据,$1 \leq n \leq 10^6$

分析

  如果我们在原数组中暴力移动数字,那么时间复杂度为 $O(n^2)$

  但手推一下会发现,每次移动时大部分项的位置是不变的,只有每段第一个数的位置发生改变

  所以每次只需要将每段的第一项向后移动,这时数组会整体向后移动一项,因此要开一个两倍长的数组

  时间复杂度为 $O(n \sum\limits_{i=2}^{n} \frac{n}{i}) \doteq O(n \, ln \, n)$

2019-08-04 纪中NOIP模拟赛B组2019-08-04 纪中NOIP模拟赛B组
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 1000005

int n;
int a[2 * N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) a[i + 1] = i;
    for (int i = 2; i <= n; i++) {
        int j = i + n / i * i;
        a[i + n] = a[j];
        for (j -= i; j >= i; j -= i) a[j + i] = a[j];
    }
    for (int i = n + 1; i <= 2 * n; i++)
        printf("%d ", a[i]);
    
    return 0;
}
View Code

T2 [JZOJ3404] 卡牌游戏

题目描述

  小X为了展示自己高超的游戏技巧,在某一天兴致勃勃地找小Y玩起了一种卡牌游戏。每张卡牌有类型(攻击或防御)和力量值两个信息。

  小Y有n张卡牌,小X有m张卡牌。已知小X的卡牌全是攻击型的。

  游戏的每一轮都由小X进行操作,首先从自己手上选择一张没有使用过的卡牌X。如果小Y手上没有卡牌,受到的伤害为X的力量值,否则小X要从小Y的手上选择一张卡牌Y。若Y是攻击型(当X的力量值不小于Y 的力量值时才可选择),此轮结束后Y消失,小Y受到的伤害为X的力量值与Y的力量值的差;若Y是防御型(当X的力量值大于Y的力量值时才可选择),此轮结束后Y消失,小Y不受到伤害。

  小X可以随时结束自己的操作(卡牌不一定要用完)。希望聪明的你帮助他进行操作,使得小Y受到的总伤害最大。

数据范围

  对于 $30 \%$ 的数据,$1 \leq n,m \leq 6$

  对于 $60 \%$ 的数据,$1 \leq n,m \leq 10^3$

  对于 $100 \%$ 的数据,$1 \leq n,m \leq 10^5$,力量值均为不超过 $10^6$ 的非负整数

分析

  第一眼看到题目,这不是个二分图最大权匹配??!

  结果看完数据范围,发现这个显然不是正解,而且B组题显然也不会考这个算法

  看了许久以后,我还是没有想到什么复杂度更优秀的做法,于是决定试一试二分图最大权匹配

  然而过了一个多小时,我发现我在考场上根本码不出这种东西

  然后我把代码全删了,重新开始思考,感觉这种决策性的东西似乎可以贪心

  最后写了个玄学贪心,结果得了 $60 \, pts$

  后来发现那 $40 \, pts$ 是因为没有开 $long \, long$,很惨...

  不过那个贪心显然是错误的,很快就被大佬 $hack$ 了,只是测试数据比较水...

  实际上在这个游戏中,有两种方式可能达到最优

  一种是不打对方的防御牌,只用自己最大的攻击牌打对方最小的攻击牌

  一种是打完对方的所有牌,然后就可以用剩下的牌疯狂打对方的脸

  第一种方式很容易实现,第二种因为消耗对方攻击牌的力量值之和是固定的,而且可以用完自己所有的牌,所以应该尽量选用力量值接近(即力量值最小)的牌去打对方的牌,但是这种方式的前提是能够消耗完对方所有的牌,不然打对方的防御牌是无意义的,不可能最优

2019-08-04 纪中NOIP模拟赛B组2019-08-04 纪中NOIP模拟赛B组
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100005

int n, m, cnt, cnt1, cnt2;
int x1[N], x2[N], y1[N], y2[N], used[N];
char s[10];
ll ans;

ll Max(ll a, ll b) {
    if (a > b) return a;
    return b;
}

bool ATK_DEF() {
    int now = 1;
    for (int i = 1; i <= cnt2; i++) {
        while (now <= m && x1[now] <= y2[i]) now++;
        if (now > m) return false;
        used[now] = 1; now++;
    }
    return true;
}

ll ATK_ATK() {
    ll sum = 0;
    int xl = 1, xr = m, yl = 1, yr = cnt1;
    while (xl <= xr && yl <= yr && x1[xr] >= y1[yl])
        sum += x1[xr] - y1[yl], xr--, yl++;
    return sum;
}

ll ATK_FACE() {
    memset(used, 0, sizeof used);
    int now = 1; ll sum = 0;
    for (int i = 1; i <= cnt1; i++) {
        while (now <= cnt && x2[now] < y1[i]) now++;
        if (now > cnt) return sum;
        sum += x2[now] - y1[i];
        used[now] = 1; now++; 
    }
    for (int i = 1; i <= cnt; i++)
        if (!used[i]) sum += x2[i];
    return sum;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s);
        if (s[0] == 'A') scanf("%d", y1 + (++cnt1));
        else scanf("%d", y2 + (++cnt2));
    }
    for (int i = 1; i <= m; i++)
        scanf("%d", x1 + i);
    sort(x1 + 1, x1 + m + 1);
    sort(y1 + 1, y1 + cnt1 + 1);
    sort(y2 + 1, y2 + cnt2 + 1);
    ans = ATK_ATK();
    if (ATK_DEF()) {
        for (int i = 1; i <= m; i++)
            if (!used[i]) x2[++cnt] = x1[i];
         ans = Max(ans, ATK_FACE());
    }
    printf("%lld\n", ans);
    
    return 0;
}
View Code

T3 [JZOJ3405] 舞台表演

题目描述

   小X终于找到了自己的舞台,希望进行一次尽兴的表演。

  不妨认为舞台是一个n行m列的矩阵,矩阵中的某些方格上堆放了一些装饰物,其他的则是空地。小X可以在空地上滑动,但不能撞上装饰物或滑出舞台,否则表演就失败了。

  小Y为了让小X表演得尽量顺畅,提前为小X写好了每一段时间的移动方向。每个时刻,听话的小X都会依据小Y写好的所在时间段的方向(东、西、南、北)向相邻的方格滑动一格。由于小Y之前没有探查过舞台的情况,如果小X直接按照小Y写好的来移动,很容易表演失败。

  不过,小Y是个天使,拥有让小X停在原地的魔法,也就是某一时刻,小X以为自己移动了实际上没有移动。为了让小X表演得尽量完美,小Y想使小X在舞台上滑行的路程尽量长(当然不能中途表演失败)。可惜小Y的智商不足以完成这么复杂的计算,希望你来帮助她决定哪些时刻该使用魔法。当然,她关心的首先是最长的路程是多少。

数据范围

  保证输入的时间段是连续的,即 $s_1=1$,$s_i=e_{i-1}+1$,$e_k=t$(第 $k$ 段时间为 $[s_k,e_k]$)

  对于 $30 \%$ 的数据,$1 \leq t \leq 20$

  对于 $60 \%$ 的数据,$1 \leq t \leq 200$

  对于 $100 \%$ 的数据,$1 \leq n,m,k \leq 200$,$1 \leq t \leq 10^5$

分析

  开始的时候看了下题,看这个数据范围应该是个DP

  但由于上一题的某种不可控因素,最后所剩无几的时间里我三分钟打了个暴力就放弃推DP了

  不过这题确实是个DP,并且其中 $60 \, pts$ 是非常可做的

  设 $f[k][i][j]$ 表示过了 $k$ 段时间在位置 $(i,j)$ 上时经过的最长路程

  因为已知这一段时间中的移动方向,所以通过枚举第 $k$ 段时间中的所有可能的位置,就很容易得到状态转移方程

  这个做法的时间复杂度为 $O(nmt)$(实际上及时排除一些不合法状态,在这样的数据下是可以 $AC$ 的)

  这时候我们就需要用单调队列优化了

  因为在一段时间中移动方向是一定的,所以在可以这一行/列上维护一个前缀状态中最优决策的单调队列,如果遇到了装饰物,就需要把单调队列清空,这样枚举前缀位置的操作就优化为了 $O(1)$,总的时间复杂度也就是 $O(nmk)$

2019-08-04 纪中NOIP模拟赛B组2019-08-04 纪中NOIP模拟赛B组
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 205

int n, m, k, ex, ey, t1, t2, d, ans;
int g[N][N], f[N][N][N], q[N], p[N];
int nxt[5][2] = {0, 0, -1, 0, 1, 0, 0, -1, 0, 1};
char s[N];

void dp(int t, int x, int y, int len, int dir) {
    int l = 1, r = 0, s = 1;
    while (x >= 1 && x <= n && y >= 1 && y <= m) {
        if (g[x][y]) l = 1, r = 0;
        else {
            while (l <= r && f[t - 1][x][y] - s >= q[r]) r--;
            q[++r] = f[t - 1][x][y] - s; p[r] = s;
            while (l <= r && s - p[l] > len) l++;
            if (l <= r) f[t][x][y] = q[l] + s;
            ans = max(ans, f[t][x][y]);
        }
        x += nxt[dir][0]; y += nxt[dir][1]; s++;
    }
}

int main() {
    scanf("%d%d%d%d%d", &n, &m, &ex, &ey, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s + 1);
        for (int j = 1; j <= m; j++)
            if (s[j] == 'x') g[i][j] = 1;
    }
    memset(f, 0x80, sizeof f);
    f[0][ex][ey] = 0;
    for (int i = 1; i <= k; i++) {
        scanf("%d%d%d", &t1, &t2, &d);
        if (d == 1) for (int j = 1; j <= m; j++) dp(i, n, j, t2 - t1 + 1, d);
        if (d == 2) for (int j = 1; j <= m; j++) dp(i, 1, j, t2 - t1 + 1, d);
        if (d == 3) for (int j = 1; j <= n; j++) dp(i, j, m, t2 - t1 + 1, d);
        if (d == 4) for (int j = 1; j <= n; j++) dp(i, j, 1, t2 - t1 + 1, d);
    }
    printf("%d\n", ans);
    
    return 0;
}
View Code