CCPC-Wannafly Winter Camp Day3 Div2

二十四点

夏威夷手算答案,然后让我从890开始交,然后到891就过了,嘿嘿嘿,我觉得我还挺欧的,夏威夷真的牛逼,讲题的时候jls对他竖起了大拇指说了句牛逼

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n;
    scanf("%d",&n);
    if(n == 6)printf("32\n");
    else printf("891\n");
    return 0;    
}

小清新数论

杜教筛留个坑。。。以后再推

#include <bits/stdc++.h>

const long long MAXN = 10000000,MOD = 998244353;

using namespace std;

long long n,cnt;
long long mu[MAXN+5],prime[MAXN+5],f[MAXN+5];
bool vis[MAXN+5];

inline void pre()
{
    mu[1] = 1;
    for(int i = 2;i <= MAXN;i++){
        if(!vis[i]){
            prime[++cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1;j <= cnt && i * prime[j] <= MAXN;j++){
            vis[i*prime[j]] = true;
            if(i%prime[j] == 0){
                mu[i*prime[j]] = 0;
                break;
            }else{
                mu[i*prime[j]] = -mu[i];
            }
        }
    }
}

inline long long g(long long x)
{
    if(f[x]) return f[x];
    for(long long i = 1; i <= x; ++i){
        f[x] += mu[i]*(x/i)*(x/i);
        if(f[x] >= MOD) f[x] %= MOD;
    }
    return f[x];
}

int main()
{
    scanf("%lld",&n);
    pre();
    
    long long ans = 0;
    
    for(long long i = 1; i <= n; ++i)
    {
        ans += mu[i] * g(n/i);
        if(ans >= MOD) ans %= MOD;
    }
    ans %= MOD;
    ans += MOD;
    ans %= MOD;
    
    printf("%lld\n",ans);
    return 0;
}

排列

题解:队友写的,等我研究研究

#include<bits/stdc++.h>

using namespace std;
const int N = 100005;
int n;
int sum[N];
int ans[N];
int a[N];
int flag[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
        if(a[i] == a[i-1]+1){
            flag[a[i]] = 1;
        }
    }
    int s = 0;
    for(int i = n;i>=1;--i){
        if(flag[i])s+=1;
        if(flag[i]==0){
            sum[i] = s;
            s = 0;
        }
    }
    int maxx = n;
    int minn = 1;
    for(int i=1;i<=n;++i){
        if(ans[a[i]] != 0)continue;
        ans[a[i]] = minn;
        ++minn;
        for(int j=a[i]+sum[a[i]];j>a[i];--j){
            ans[j] = maxx;
            maxx--;
        }
    }
    for(int i=1;i<=n;++i){
        printf("%d ",ans[i]); 
    }
    return 0;
}
Last modification:January 28th, 2019 at 08:12 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment