2017-2018 ACM-ICPC Southeastern European Regional Programming Contest (SEERC 2017)

A Concerts

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+11;
const int maxm = 300+11;
const int mod = 1e9+7;
char s1[maxn],s2[maxn];
int  h[maxn];
int  hh[maxn];
typedef long long LL;
int  dp[maxn][maxm];
int n,k;
LL solve(){
  dp[0][0] = 1;
  LL ans = 0;
  for(int i = 1;i <= n; ++i){
    for(int j = 0;j <= k; ++j){
       int  &a = dp[i][j];
       int  b = 0;
       a = b = 0;
       a += dp[i-1][j];
       a %= mod;
        if(s1[i] == s2[j]&&j > 0&&i > hh[j-1])
        {
          b =  dp[i-hh[j-1]-1][j-1];
        }
        if(j ==k )
          ans = (ans+b)%mod;
        a = (a+b)%mod;
    }
  }
  // cout<<dp[3][1][0]<<endl;
  // cout<<dp[4][2][1]<<endl;
  return ans;
}

int main(void){

  scanf("%d%d",&k,&n);
  for(int i = 1;i <= 26; ++i)
    scanf("%d",&h[i]);
  // if(k == 0) return 0*printf("%d\n",1);
  // if(n == 0) return 0*printf("%d\n",0);
  scanf(" %s",s2+1);
  for(int i =1;i <= k; ++i)
    hh[i] = h[s2[i]-'A'+1];
  scanf(" %s",s1+1);
  printf("%lld\n",solve());
  return 0;
}

J Cunning Friends

K - Escape Room

序列是唯一的


#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int a[maxn];
std::vector<int> G[maxn];

int main(void){
  int n;
  cin>>n;
  for(int i = 1,v;i <= n; ++i){
    scanf("%d",&v);
    G[v].push_back(i);
  }
  int cnt = n;
  for(int i = 1;i <= n; ++i){
    if(G[i].empty()) continue;
    for(int j = 0;j < (int)G[i].size(); ++j)
      a[G[i][j]] = cnt--;
  }
  for(int i = 1;i <= n; ++i){
    printf("%d%c",a[i]," \n"[i==n]);
  }
  return 0;
}

G - Robots

排序即可

D - Harry Potter and The Vector Spell

F - Binary Transformations

贪心，首先1-0 按权值大的排序，0-1权值小的排序
这当然是不对的喽
还有可能是1-> 0 ->1 ,从打到小枚举这种情况就ok了

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

char a[maxn],b[maxn];
typedef long long LL;
LL cost[maxn];
LL v1[maxn],v2[maxn];
LL v3[maxn];
typedef pair<LL,LL> P;
int n;

int main(void){
      // freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for(int i = 1;i <= n;++i){
        scanf("%lld",&cost[i]);
    }
    scanf(" %s",a+1);
    scanf(" %s",b+1);
    set<P> s2;
    set<P,greater<P> >s1,s3;
    LL sum = 0;
    for(int i = 1;i <= n; ++i){
        if(a[i] == '1' && a[i] == b[i])
            sum += cost[i],s3.insert(P(cost[i],i));
        if(a[i] == '1' && a[i] != b[i])
            s1.insert(P(cost[i],i));
        if(a[i] == '0' && a[i] != b[i])
            s2.insert(P(cost[i],i));
    }

    int len1 = s1.size();
    int len2 = s2.size();
    // cout<<len1<<" "<<len2<<endl;
    int len3 = s3.size();
    LL ans = 1e18;
    auto it = s3.begin();
    // cout<<*it<<endl;
    for(int i = 0;i < len3+1; ++i){
        LL ans1 = 0;
        ans1 += sum*(len1+len2);
        // cout<<ans1<<endl;
        LL tmp = 0;
        for(auto c:s1)
            tmp += c.first;
        for(auto c: s1){
            tmp -= c.first;
            ans1 += tmp;
        }
        for(auto c: s2){
            tmp += c.first;
            ans1 += tmp;
        }
        // cout<<sum<<endl;
        // cout<<ans1<<endl;
        ans = min(ans,ans1);
        if(it == s3.end()) break;
        sum -= (*it).first;
        s1.insert(*it),len1++;

        s2.insert(*it),len2++;
        it++;
    }

    cout<<ans<<endl;

    return 0;
}