Codeforces Round #151 (Div. 2)

A：构造一组数据

显然第一个数只能比较一次，构造前两个数最大，而且相等即可

B：求出总和，如果是n的倍数，说明总能构造出所有数相等，如果不是n的倍数，那么总可以利用一个数，将其它n-1个数构造相等

C：卡了好久的题。注意K的范围(n+1)*n/2，明显是1+2……n

将数列倒序，a0,a1,a2,a3 (ai>ai+1)

考虑只取一个数，那么有n种可能，而且这n种互不相同

考虑取两个数，其中a0必取，从剩下的n-1个数中取一个，有n-1种可能，这n-1种互不相同，另外考虑与前n种比较，前n种的最大值显然是a0,而后n-1种a0+ai>a0，所以不相同

同理取三个数，取四个数，取n个数

对于取i个数，总是前i-1大的数必取。

所以总共的情况为n+n-1+n-2……+2+1

D：直接暴力，用set就行了

E：递归离线一直RE，哭

在线也可以，遍历整棵树，标号，对于结点u，所有后代的标号总在(left[u],right[r])区间内。

对于一个查询，可以通过二分定位这层的区间

可能有重复查询，map记录一下，不然会T

[cpp]
vector<int>e[N];
map<pair<int,int>,int>ans;
int n;
char str[105];
string name[N];
int Left[N],Right[N];
int depth[N],idx=0;
int max_depth=-1;
vector<int>dep[N];
void dfs(int u,int h)
{
    max_depth=max(max_depth,h);
    depth[u]=h;
    dep[h].pb(u);
    Left[u]=idx++;
    for(int i=0;i<e[u].size();i++) dfs(e[u][i],h+1);
    Right[u]=idx++;
}
int query(int u,int k,int l,int r)
{
    int h=depth[u]+k;
    if(h>max_depth) return 0;
    if(dep[h].empty()) return 0;
    if(ans.find(mp(u,k))!=ans.end()) return ans[mp(u,k)];
    int low=0,high=dep[h].size()-1,mid,L=N,R=-1;
    while(low<=high){
        mid=(low+high)>>1;
        if(Left[dep[h][mid]]>l){
            high=mid-1;
            L=mid;
        }
        else low=mid+1;
    }
    low=0,high=dep[h].size()-1;
    while(low<=high){
        mid=(low+high)>>1;
        if(Left[dep[h][mid]]<r){
            low=mid+1;
            R=mid;
        }
        else high=mid-1;
    }
    set<string>s;
    while(L<=R) s.insert(name[dep[h][L]]),L++;
    return ans[mp(u,k)]=s.size();
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%s%d",str,&k);
        name[i]=string(str,strlen(str));
        e[k].pb(i);
    }
    dfs(0,0);
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int u,k;
        scanf("%d%d",&u,&k);
        printf("%d\n",query(u,k,Left[u],Right[u]));
    }
    return 0;
}

vector<int>e[N];
map<pair<int,int>,int>ans;
int n;
char str[105];
string name[N];
int Left[N],Right[N];
int depth[N],idx=0;
int max_depth=-1;
vector<int>dep[N];
void dfs(int u,int h)
{
    max_depth=max(max_depth,h);
    depth[u]=h;
    dep[h].pb(u);
    Left[u]=idx++;
    for(int i=0;i<e[u].size();i++) dfs(e[u][i],h+1);
    Right[u]=idx++;
}
int query(int u,int k,int l,int r)
{
    int h=depth[u]+k;
    if(h>max_depth) return 0;
    if(dep[h].empty()) return 0;
    if(ans.find(mp(u,k))!=ans.end()) return ans[mp(u,k)];
    int low=0,high=dep[h].size()-1,mid,L=N,R=-1;
while(low<=high){
  mid=(low+high)>>1;
  if(Left[dep[h][mid]]>l){
   high=mid-1;
   L=mid;
  }
  else low=mid+1;
}
low=0,high=dep[h].size()-1;
while(low<=high){
  mid=(low+high)>>1;
  if(Left[dep[h][mid]]<r){
   low=mid+1;
   R=mid;
  }
  else high=mid-1;
}
set<string>s;
while(L<=R) s.insert(name[dep[h][L]]),L++;
return ans[mp(u,k)]=s.size();
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int k;
        scanf("%s%d",str,&k);
        name[i]=string(str,strlen(str));
        e[k].pb(i);
    }
    dfs(0,0);
    int q;
    scanf("%d",&q);
    while(q--)
    {
        int u,k;
        scanf("%d%d",&u,&k);
        printf("%d\n",query(u,k,Left[u],Right[u]));
    }
    return 0;
}

补充：软件开发 , C++ ,