首页 > 编程学习 > 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];
    }
}

 

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号