叉姐的魔法训练（第一课）----初级魔法练习

POJ 2443 Set Operation

有1000个集合每个集合有10000个元素，给出每个集合所有的元素和Q组询问，问元素x和y是否属于同一个集合。

手抽写了个集合类出来，效率低了。其实用元素开数组，压缩所属的集合效率更高。

#include 
#include 
#include 
#include 
using namespace std;
const int maxn=1111;
typedef unsigned int uint;
const int Size=30;
class SetOperation{
private:
    uint st[400];
    int getIdx(int num){
        return num/Size;
    }
    int getLft(int num){
        return num%Size;
    }
public:
    SetOperation(){
        init();
    }
    void init(){
        memset(st,0,sizeof(st));
    }
    void addVal(int num){
        st[getIdx(num)]|=(1<    }
    void delVal(int num){
        st[getIdx(num)]&=~(1<    }
    void chgVal(int num){
        st[getIdx(num)]^=(1<    }
    bool inSet(int num){
        return st[getIdx(num)]&(1<    }
}a[maxn];
int main()
{
    int n,m;
    while (~scanf("%d",&n)){
        for (int i=1;i<=n;i++){
            a[i].init();
            scanf("%d",&m);
            while (m--){
                int num;
                scanf("%d",&num);
                a[i].addVal(num);
            }
        }
        scanf("%d",&m);
        while(m--){
            int x,y;
            bool flag=false;
            scanf("%d%d",&x,&y);
            for (int i=1;i<=n;i++){
                if (a[i].inSet(x)&&a[i].inSet(y)){
                    flag=true;
                    break;
                }
            }
            if (flag) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

---------------------------------

POJ 3244 Difference between Triplets

//数学好题
//定义两个三元组I(xi,yi,zi)和J(xj,yj,zj),(可以看做是空间中的点)
//他们的距离为D(I,J)=max{xi-xj,yi-yj,zi-zj}-min{xi-xj,yi-yj,zi-zj}，
//给定n个三元组（n<=200000）,求任意两个三元组的差的和
//抽化出来的模型是 max(a,b,c)-min(a,b,c)，这个东西吧他放在数轴上 a,b,c
//我们要求最大和最小的差就是这三个点构成的线段的距离，那么我们这里再变通下 是不是端点到中间那个点的距离
//其实画出这个图的时候，就可以看到这个距离为(|a-b|+|b-c|+|c-a|)/2，这样我们并不需要关心中间的那个
//对应到题目中的原型，就是(|(xi-xj)-(yi-yj)|+|(yi-yj)-(zi-zj)|+|(zi-zj)-(xi-xj)|)/2;
//对应到同一个点上就是(|(xi-yi)-(xj-yj)|+|(yi-zi)-(yj-zj)|+|(zi-xi)-(zj-xj)|)/2;
//设a=(xi-yi),b=(yi-zi),c=(zi-xi),原问题等价为(|ai-aj|+|bi-bj|+|ci-cj|)/2;
//然后三个可以完全分开完全独立的计算，并不影响其他两元，这里要加个优化，就是按从小到大排序出来
//我们只需要算出每个位置上，他贡献了多少次加法，贡献了多少次减法即可
//举个例子，目前把a的部分排序了,对于第i个，他前面的比它小，所以在和i点比较时i点贡献了i次加，对后面的n-i个点
//向他们贡献了n-i次减法

#include 
#include 
#include 
#include 
using namespace std;
const int maxn=411111;
typedef long long LL;
LL a[maxn],b[maxn],c[maxn];
int n;

int main()
{
    while (~scanf("%d",&n)){
        if (n==0) break;
        for (int i=0;i            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            a[i]=x-y;
            b[i]=y-z;
            c[i]=z-x;
        }
        sort(a,a+n);
        sort(b,b+n);
        sort(c,c+n);
        LL ans=0;
        for (int i=0;i            ans+=(a[i]+b[i]+c[i])*(2*i-n+1);
        }
        printf("%I64d\n",ans/2);
    }
    return 0;
}

---------------------------------

POJ 3685 Matrix

打表后可以发现矩阵存在单调的性质。

F(i)=i^2+100000*i+j^2-100000*j+i*j 对i求导

F'(i)=2*i+100000+j>0 恒成立，所以每一列都是单调递增的。

要求出矩阵中第K大的数。

首先二分矩阵中的数X，判断它是不是比K个以上的数大。

然后枚举每一列，对于每一列，二分求出比X小的数的个数。

累加得到矩阵中比X小的数的个数sum。若sum>=K则X比K个以上的数大。

最后得到比矩阵中K个以上的数大的数中最小的数ans，则ans-1即为答案。

#include 
#include 
#include 
#include 
using namespace std;
typedef __int64 LL;
const LL INFF=1LL<<50;
int n;
LL m;
LL f(LL i,LL j){
    return i*i+100000*i+j*j-100000*j+i*j;
}
bool can(LL x){
    int i;
    LL sum,l,r,res,mid;
    sum=0;
    for (i=1;i<=n;i++){
        l=1,r=n;
        res=n+1;
        while (l<=r){
            mid=(l+r)>>1;
            if (f(mid,i)>=x){
                res=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        sum+=res-1;
    }
    return sum>=m;
}

int main()
{
    int T;
    LL l,r,ans,mid;
    scanf("%d",&T);
    while (T--){
        scanf("%d%I64d",&n,&m);
        l=-INFF,r=INFF;
        ans=0;
        while (l<=r){
            mid=(l+r)>>1;
            if (can(mid)){
                ans=mid;
                r=mid-1;
            }
            else{
                l=mid+1;
            }
        }
        printf("%I64d\n",ans-1);
    }
    return 0;
}

---------------------------------