USACO 2020 Open - Gold

KronoX · 2020-05-16 08:50:26 · 个人记录

T1. Haircut

#include <bits/stdc++.h>
#define lb(p) (p&(-p))
using namespace std;

const int maxn=100005;

long long n,ans,a[maxn],tree[maxn],s[maxn]; //记得开 long long

//树状数组模板
void add(long long x) { while (x<=n+1) tree[x]++, x+=lb(x); }
long long find(long long x) { long long ret=0; while (x>0) ret+=tree[x], x-=lb(x); return ret; }

int main()
  {
    scanf("%lld",&n);
    for (int i=1;i<=n;i++) scanf("%lld",&a[i]), a[i]++;
    for (int i=1;i<=n;i++)
      {
        s[a[i]]+=find(n+1)-find(a[i]); //a[i] - n+1
        add(a[i]);
      }
    for (int i=1;i<=n;i++) printf("%lld\n",ans), ans+=s[i];
    return 0;
  }

T2. Favorite Colors

T3. Exercise

#include <bits/stdc++.h>
using namespace std;

long long ans,n,m,cnt,F[500005],pri[500005];

int main()
  {
    scanf("%lld%lld",&n,&m);

    //暴力筛素数
    for (int i=2;i<=n;i++)
      {
        bool flag=true;
        for (int j=2;j<=sqrt(i);j++) if (i%j==0)
          {
            flag=false;
            break;
          }
        if (flag) pri[++cnt]=i;
      }

    //DP
    F[0]=1;
    for (int i=1;i<=cnt;i++)
      for (int j=n;j>=pri[i];j--)
        {
          int t=pri[i];
          while (t<=j)
            {
              F[j]=(F[j]+F[j-t]*t%m)%m;
              t*=pri[i];
            }
        }

    for (int i=0;i<=n;i++) ans=(ans+F[i])%m;
    return printf("%lld",ans)&0;
  }

【SCOI2009】游戏