暑假集训练习赛题解

比赛链接：http://acm.nyist.net/JudgeOnline/problemset.php?cid=205

对于第一道题 UFS（Union  Find  Set） ，请参见http://blog.csdn.net/u011632342/article/details/37814289，题目大意一样，解法一样，不过后台测试数据还没整太多，数据比较弱。。。

对于第二道题STR（STRing），本来是想着给大家”送福利“呢，可能由于我的题目表述能力不太好或者样例数据的特殊性或者其他等等的原因，好多人被”坑“了

解题思路：就是把我们平时的排序方式变化一下下就可以A了，另外还要注意输入输出格式

代码如下：

 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
using namespace std;

string s[5000],s1[5000];
bool cmp1(string a,string b)
{
    return a+b>b+a;
}
bool cmp2(string a,string b)
{
    return a+b<b+a;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
       int t;
       scanf("%d",&t);
       getchar();
       for(int j=1;j<=t;j++)
       {
           if(j>1) printf("\n");
           if(j==1) getchar();
           string co;
           int cnt=0;
           while(getline(cin,co) && co.length()>0)
           {
               s[cnt]=co;s1[cnt++]=co;
               //cout<<co.length()<<endl;
           }
           sort(s,s+cnt,cmp1);
           sort(s1,s1+cnt,cmp2);
           for(int i=0;i<cnt;i++)
            cout<<s[i];
            cout<<endl;
           for(int i=0;i<cnt;i++)
            cout<<s1[i];
       }
       return 0;
}

对于最后一道题ST（Segment Tree），直接套线段树模板就可以水过，只需要在每次成段更新时顺便更新这个节点所辖范围内sum和odd的值。

模板如下：

 
#include<cstdio>
#include<algorithm>
using namespace std;

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
const int N=111111;

LL sum[N<<2],add[N<<2],odd[N<<2];

void pushup(int rt)
{
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    odd[rt]=odd[rt<<1]+odd[rt<<1|1];
}
void pushdown(int rt,LL m)
{
    if(add[rt])
    {
        add[rt<<1]+=add[rt];
        add[rt<<1|1]+=add[rt];
        sum[rt<<1]+=add[rt]*(LL)(m-(m>>1));
        sum[rt<<1|1]+=add[rt]*(LL)(m>>1);
        if(add[rt]%2)
            {odd[rt<<1]=m-(m>>1)-odd[rt<<1];
            odd[rt<<1|1]=(m>>1)-odd[rt<<1|1];}
        add[rt]=0;
    }
}
void build(int l,int r,int rt)
{
    add[rt]=0;
    if(l==r)
    {
        scanf("%lld",&sum[rt]);
        if(sum[rt]%2) odd[rt]=1;
        else odd[rt]=0;
        return;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    pushup(rt);
}
void update(int L,int R,int c,int l,int r,int rt)
{
    if(L<=l&&R>=r)
    {
        add[rt]+=c;
        sum[rt]+=(LL)c*(r-l+1);
        if(c%2)
            odd[rt]=(r-l+1)-odd[rt];
        return;
    }
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    if(L<=m) update(L,R,c,lson);
    if(R>m)  update(L,R,c,rson);
    pushup(rt);
}
LL query(int L,int R,int l,int r,int rt,int mark)
{
    if(L<=l&&R>=r&&mark==1)
        return sum[rt];
    if(L<=l&&R>=r&&mark==2)
        return odd[rt];
    pushdown(rt,r-l+1);
    int m=(l+r)>>1;
    LL ret=0;
    if(L<=m) ret+=query(L,R,lson,mark);
    if(R>m) ret+=query(L,R,rson,mark);
    return ret;
}
int main()
{
    //freopen("F:ST.txt","r",stdin);
    //freopen("F:in.txt","w",stdout);
    int n,m,x,y,z;
    while(~scanf("%d%d",&n,&m)&&m&&n)
    {
        build(1,n,1);
        for(int i=0; i<m; i++)
        {
            char s[2];
            scanf("%s",s);
            if(s[0]=='Q')
            {
                scanf("%d%d",&x,&y);
                printf("%lld\n",query(x,y,1,n,1,2));
            }
            else if(s[0]=='A')
            {
                scanf("%d%d%d",&x,&y,&z);
                update(x,y,z,1,n,1);
            }
            else
            {
                scanf("%d%d",&x,&y);
                printf("%lld\n",query(x,y,1,n,1,1));
            }
            /*for(int i=1;i<=25;i++)
                    printf("%d ",odd[i]);
                printf("\n\n");*/
        }
    }
    return 0;
}

总体来说，这三道应该算是最水的了吧，不过限于出题人的水平和表达能力，对题意方面造成的困惑请谅解。