《2021/5/20》

P1052 [NOIP2005 提高组] 过河：

这个题挺好的，首先很明显是dp。但是这里距离太长了不好搞。

所以就要思考去处理这个距离，我一开始就从lcm思考，然后想去跳下个位置的[a[i + 1] - 10,a[i + 1] + 10]的距离，但是发现这样想不做背包跑到有点困难。

这里其实lcm(1,10) = 2520。所以我们拿出任意的>= 1(1，10)之内的数都是能走到2520的。那么对于超过2520 * 2的距离，我们都减去k * 2520，把距离缩到2520 * 2之内即可。

然后我们就可以暴力跑dp了。

这题还有个缩小到100之内的exgcd证明法，但是真要想到证明出来其实挺难的。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 1e4 + 5;
const int M = 1e5 + 5;
const LL Mod = 998244353;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
}
using namespace FASTIO;

//2520 - lcm(1 ~ 10)
int a[105];
int dp[N * 200];
bool vis[N * 200];
int main() {
    int L,s,t,n;L = read(),s = read(),t = read(),n = read();
    for(int i = 1;i <= n;++i) a[i] = read();
    sort(a + 1,a + n + 1);
    memset(dp,0x3f3f3f,sizeof(dp));
    int mx = 0;
    for(int i = 1;i <= n;++i) {
        int dis = a[i] - a[i - 1];
        if(dis > 5040) {
            int ma = dis / 5040 - (dis % 5040 == 0);
            a[i] -= ma * 5040;
        }
        mx = max(mx,a[i]);
        vis[a[i]] = 1;
    }
    dp[0] = 0;
    for(int i = 0;i <= mx + t;++i) {
        if(vis[i] == 1) dp[i]++;
        for(int j = s;j <= t;++j) {
            dp[i + j] = min(dp[i + j],dp[i]);
        }
    }
    int ans = INF;
    for(int i = mx + 1;i <= mx + 2 * t;++i) ans = min(ans,dp[i]);
    printf("%d
",ans);
    //system("pause");
    return 0;
}
/*
1 2 3 4
133466 42121 661245 665365
*/

View Code

CF: D. Sequence and Swaps：

这个题也挺好的，一开始想的是dp做，但是想到了可能交换的顺序是乱序的，所以就做不了。

但是这里交换的顺序其实是按序的。

因为这里a[i] > x才可以交换，那么我们对一段进行操作之后，其实就是抬低了一段的值。

并且我们可以发现，如果1 ~ j已经抬低完毕，那么对于原来就是非降的j + 1 ~ n。

肯定不能再去交换了。因为x 肯定 < max(1 ~ x)。如果我们再去交换那么只会导致错误。

所以我们可以得出，我们从左向右扫1 ~ j，如果i位置可以换，我们就交换a[i]。

如果1 ~ j都完成交换后整个序列还是不满足，那么肯定不满足了。

注意一点就是如果本来就有序就不做操作了。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,int> pii;
const int N = 1e5 + 5;
const int M = 1e5 + 5;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 0x3f3f3f
#define dbg(ax) cout << "now this num is " << ax << endl;
namespace FASTIO{
    inline LL read(){
        LL x = 0,f = 1;char c = getchar();
        while(c < '0' || c > '9'){if(c == '-') f = -1;c = getchar();}
        while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
        return x*f;
    }
}
using namespace FASTIO;

int a[505];
int main() {
    int ca;ca = read();
    while(ca--) {
        int n,x;n = read(),x = read();
        for(int i = 1;i <= n;++i) a[i] = read();
        int pos = 0;
        for(int i = n;i >= 1;--i) {
            if(a[i] < a[i - 1]) {
                pos = i;
                break;
            }
        }
        if(pos == 0) printf("0
");
        else {
            int ans = 0,now = x;
            for(int i = 1;i <= pos - 1;++i) {
                if(a[i] > now) {
                    swap(a[i],now);
                    ans++;
                }
            }
            for(int i = 1;i <= n - 1;++i) {
                if(a[i] > a[i + 1]) ans = -1;
            }
            printf("%d
",ans);
        }
    }
    
    //system("pause");
    return 0;
}

View Code