Educational Codeforces Round 133 (Rated for Div. 2) ABD

A. 2-3 Moves

题意：从0，每次 +2 -2 +3 - 3选一个，问多少次能到 n

由于对称性，先让 n = abs(n)

0只用0次，1只用1次

t = n / 3；

如果n % 3 == 1 ,说明t - 1 次 + 3 ，再来一次 +2 ，就可以了

如果 n % 3 == 0,说明t 次 +3 就可以了

如果n % 3 == 2,说明 t 次 +3 ，一次+2就可以额

void solve()
{
//    cin>>n>>m;
    cin>>n;
    int i = n;
    if(i == 0) {
        cout<<0<<endl; rt
    } else if(abs(i) == 2 || abs(i) == 3) {
        cout<<1<<endl;rt
    } else if(abs(i) == 1) {
        cout<<2<<endl;rt;
    }
    
    n = abs(n);
    int t = n / 3;
    if(n % 3 == 1) {
        cout<<t + 1<<endl;
    } else if(n % 3 == 0){
        cout<<t<<endl; 
    } else {
        cout<<t + 1<<endl;
    }
}

B. Permutation Chain

题意：让固定点逐渐减少，输出每个序列

先输出 1-n，

然后每次把最前面的 数和 n 替换，这样每次减少一个固定点

//#define int ll
const int N = 1e5+10;
int n,m;
int a[N];
void solve()
{
//    
    cin>>n;
    int j = 1;
    fo(i,1,n) a[i] = i;
    cout<<n<<endl;
    fo(k,1,n) {
        fo(i,1,n) {
            cout<<a[i]<<' ';
        } cout<<endl;
        swap(a[j],a[n]);
        j ++ ;    
    }
    
}

D. Chip Move

题意：给n，k，从0开始，每次增加 k + i，i是当前的次数，问最终到达 1-n有多少种方案

n根号n

最多的次数是 k 等于0，n = 2e5，次数是 i * (i+1) / 2

且枚举到每次，当前的增量是 k + i - 1 。这样总次数是 i * (k + (k + i - 1)) / 2 > n 

也就是总共是根号n

ans[N] ，是从0 开始 经过各种数最终到达 i 的总方案数

sum[N]是这一轮，从0开始一直走到 i 的总方案数

枚举 1 - n，先上一轮的总方案数更新成这一轮，增量为 t 的总方案数：如果小于 增量 t ，说明这一轮没办法一次性到达 t ，

如果大于等于 t ，增量可以从 当前枚举到的位置 j 之前的第 t 个转移，sum[j] = sum[j] + sum[j-t]

最后让ans累加上sum：ans[i] += sum[i-t]

#define int ll
const int N = 2e5+10,mod = 998244353 ;
int n,m,k;
int f[N];
int ans[N];
int sum[N];
void solve()
{
//    cin>>n>>m;
    cin>>n>>k;
    f[0] = 1;
    for(int i = 1;;i++) {
        int t = k + i - 1;
        fo(j,0,n) {
            sum[j] = f[j];
            if(j - t >= 0) sum[j] = (sum[j] + sum[j-t]) % mod;
        }
        fo(j,0,t-1) f[j] = 0;
        fo(j,t,n) f[j] = sum[j-t];
        fo(j,t,n) ans[j] = (ans[j] + f[j]) % mod;
        if(1ll * i * (2 * k + i - 1) > n * 2) break;
    }
    fo(i,1,n) {
        cout<<ans[i]<<" \n"[i==n];
    }
}