2017 Multi-University Training Contest

rank 103/766

1003 Kanade's sum

拿链表维护每个数前面比它大的数的位置，乘法原理搞一搞即可。注意链表可以从1开始依次删点，做到O(1)维护每个操作。

#include <bits/stdc++.h>
#define maxn 500010
#define inf 0x3f3f3f3f
#define REP(i,x,y) for(int i=x;i<(y);i++)
#define RREP(i,x,y) for(int i=x;i>(y);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n,k,a[maxn],pos[maxn],dpL[85],dpR[85];
int nex[maxn],last[maxn];
int main()
{
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&k);
        for(int j=0;j<=k;j++) dpL[j]=dpR[j]=0;
        REP(i,1,n+1) {
            scanf("%d",&a[i]);
            pos[a[i]]=i;
        }
        for (int i = 1; i<=n; i++) {
            nex[i] = i+1;
            last[i] = i-1;
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            int now = pos[i];
            int t1 = now;
            int tmp = now;
            for(int j=1;j<=k;++j){
                tmp=t1;t1 = nex[t1];
                if(t1==n+1) {dpR[j]=(n-(tmp)+1);break;}
                else
                    dpR[j]=((t1)-(tmp));
            }
            t1 = now;
            for(int j=1;j<=k;++j){
                tmp=t1;t1 = last[t1];
                if(0==t1) {dpL[j]=(tmp);break;}
                else{
                    dpL[j]=((tmp)-(t1));
                }
            }
            nex[last[now]] = nex[now];
            last[nex[now]] = last[now];
            for(int j=1;j<=k;++j)
                ans+=1LL*i*dpL[j]*dpR[k+1-j];
            for(int j=0;j<=k;++j) dpL[j]=dpR[j]=0;
        }
        printf("%I64d
",ans);
    }
}

View Code

1005 RXD and dividing

注意是求最大值。对于每个子树，它的节点个数为Q，将它分成min(Q,K)份，dfs一遍维护答案即可。

#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <iostream>
using namespace std;
typedef pair<int,long long> pil;
typedef pair<long long,int> pli;
const int maxn=1000005;
int a,b,n,K;
long long c,sz[maxn],depth[maxn],res;
vector<pil> G[maxn];
priority_queue<pli> que;
void dfs(int u,int fa,long long dep) {
    depth[u]=dep;
    for (int i=0;i<(int)G[u].size();++i) {
        int v=G[u][i].first;
        if (v==fa)
            continue;
        dfs(v,u,G[u][i].second);
        sz[u]+=sz[v];
    }
    ++sz[u];
    res+=dep*min(1LL*K,sz[u]);
}
int main()
{
    while (scanf("%d%d",&n,&K)==2) {
        memset(sz,0,(n+1)*sizeof sz[0]);
        memset(depth,0,(n+1)*sizeof depth[0]);
        for (int i=0;i<=n;++i)
            G[i].clear();
        for (int i=0;i<n-1;++i) {
            scanf("%d%d%I64d",&a,&b,&c);
            G[a].push_back(pil(b,c));
            G[b].push_back(pil(a,c));
        }
        res=0;
        dfs(1,-1,0);
        cout<<res<<endl;
    }
    return 0;
}

View Code

1008 RXD and math

打表发现答案就是n^k，快速幂求一下。

#include <bits/stdc++.h>
using namespace std;
int cas;
const long long mod=1e9+7;
long long ksm(long long x,long long n) {
    long long ret=1;
    while (n) {
        if (n&1)
            ret=ret*x%mod;
        n>>=1;
        x=x*x%mod;
    }
    return ret;
}
int main()
{
    long long n,k;
    while (scanf("%I64d%I64d",&n,&k)==2) {
        ++cas;
        printf("Case #%d: %I64d
",cas,ksm(n%mod,k));
    }
    return 0;
}

View Code

1010 RXD, tree and sequence

可以把问题转化为区间相邻LCA最小值

#include <bits/stdc++.h>
const long long mod = 1e9+7;
const double ex = 1e-10;
#define inf 0x3f3f3f3f
using namespace std;
int n,K;
struct edge{
    int to,nxt;
}E[355555];
int deep[355555],head[355555],tot,a[355555],p[355555][30],dp[5][355555];
void addedge (int x,int y){
    E[tot] = (edge){y,head[x]};
    head[x] = tot++;
}
inline void dfs(int u)
{
  for(int i=head[u];i!=-1;i=E[i].nxt){
    int v = E[i].to;
    if (!deep[v]){
      deep[v] = deep[u]+1;
      p[v][0] = u;
      dfs(v);
    }
  }
}
void init()
{
  int i,j;
  for(j=1;(1<<j)<=n;j++)
    for(i=1;i<=n;i++)
      if(p[i][j-1]!=-1)
        p[i][j]=p[p[i][j-1]][j-1];
}
int lca(int a,int b)
{
  if (a==0||b==0) return 0;
  int i,j;
  if(deep[a]<deep[b])swap(a,b);
  for(i=0;(1<<i)<=deep[a];i++);
  i--;
  for(j=i;j>=0;j--)
    if(deep[a]-(1<<j)>=deep[b])
      a=p[a][j];
  if(a==b)return a;
  for(j=i;j>=0;j--)
  {
    if(p[a][j]!=-1&&p[a][j]!=p[b][j])
    {
      a=p[a][j];
      b=p[b][j];
    }
  }
  return p[a][0];
}
int main()
{
    deep[0] = inf;
    while (scanf("%d%d",&n,&K)==2){
        memset(head,-1,sizeof(head));tot = 0;
        memset(a,0,sizeof(a));
        for (int i = 1 ; i <= n ;i++){
            scanf("%d",&a[i]);
        }

        for (int i = 1 ;i < n; i++){
            int x,y;
            scanf("%d%d",&x,&y);
            addedge(x,y);
            addedge(y,x);
        }
        memset(deep,0,sizeof(deep));
        deep[1] = 1;dfs(1);init();
        memset(dp,inf,sizeof(dp));
        dp[0][0] = 0;
        for (int i = 1; i<=n; i++){
            dp[i%3][0] = 0;

            for (int j = 1;j <=min(i,K);j++){
                dp[i%3][j] = min(dp[i%3][j],dp[(i+2)%3][j-1]+deep[a[i]]);
                if (i>1) dp[i%3][j] = min(dp[i%3][j],dp[(i+2)%3][j]);
                if (i-2>=0)dp[i%3][j] = min(dp[i%3][j],dp[(i+1)%3][j-1]+deep[lca(a[i],a[i-1])]);
            }
        }
        cout << dp[n%3][K]<<endl;
    }
    return 0;
}

1010

1011 RXD's date

签到题。输出小于等于35的数的个数。

#include <bits/stdc++.h>
#define maxn 100010
#define inf 0x3f3f3f3f
#define REP(i,x,y) for(int i=x;i<(y);i++)
#define RREP(i,x,y) for(int i=x;i>(y);i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int t;
int main()
{
    while(scanf("%d",&t)!=EOF){
        int cnt=0;
        REP(i,1,t+1) {
            int tmp;scanf("%d",&tmp);
            if(tmp<=35) cnt++;
        }
    printf("%d
",cnt);
    }
}

View Code