有欧阳师者，一笑且考之

曰：日也长也,noipcsps日近矣

年年岁岁，算法尽学

此皆模板，一“易”字足以盖之

 

呜呼哉，LL不学新算法已多年

奈何欧阳教屡屡考以玄学

然则模板之易怎敌未学之难

哀耶，叹耶，

立而望之，不如灼灼新学

---

 

最小得分和

[题目描述]

给定一个长度为N的正整数序列{ }，设数对（i，j）的得分Sij=|ai-aj|，你需要找出K对数，使得这K对数的得分之和最小。

[输入格式]

第一行有两个正整数N，K，如题所述。

接下来一行有N个正整数，表示序列中的数。

[输出格式]

只有一个数，表示最小的得分之和。

[样例输入]

5 55 3 1 4 2

[样例输出]

6

[样例解释]

以下括号里的数表示下标。

选择（1，4），（2，4），（2，5），（3，5）这4对数，得分之和为4。

再从（1，2），（2，3），（4，5）中任选1对，因为这3对的得分都一样，都为2。

选择的数对（i，j）中i，j不能相等，且（i，j），（j，i）表示同一个数对，也就是说只能选其中一个。

[数据范围]

数据编号	N	K
1	10	40
2~4	2000	≤ C2nCn2
5~7	100000	≤ 100000
8	500000	500000
9	100000	≤ C2nCn2
10	1000000	≤ C2nCn2

对于100%的数据：ai≤108108，保证答案不超过long long范围。

 

作为我水到最高分的题，我只能说80pts是真心水

因为从看到这道题开始，我就只想到这种暴力

但是要受K的影响

注定不能拿到所有分

#include
      
       #define re return#define ll long long#define inc(i,l,r) for(ll i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}const int maxn=1000005;ll n,K,a[maxn],sum[maxn];inline bool check(ll jd){    ll j=1,cnt=0;    inc(i,2,n)    {        while(a[i]-a[j]>jd)++j;        cnt+=i-j;        if(cnt>=K)re 1;    }    re 0;}int main(){    //freopen("in.txt","r",stdin);    rd(n),rd(K);    inc(i,1,n)    rd(a[i]);        sort(a+1,a+n+1);    ll l=0,r=a[n]-a[1];    while(l<=r)    {        ll mid=(l+r)>>1;        if(check(mid))r=mid-1;        else l=mid+1;    }    ll ans=0;    ll j=1,cnt=0;    sum[1]=a[1];    inc(i,2,n)    {        while(a[i]-a[j]>l)++j;        cnt+=i-j;        ans+=a[i]*(i-j)-sum[i-1]+sum[j-1];         sum[i]=sum[i-1]+a[i];    }        if(cnt>K)ans-=(cnt-K)*l;    printf("%lld",ans);    re 0;}
       
      

 总统竞选

[题目描述]

眼看宇宙总统竞选之日即将来临，ly心急如焚，与往年竞选不同，今年来了一个强大的对手——Neroysq，Neroysq爱国爱民，一身正气，救灾排难，勤俭节约，坚持从群众中来、到群众中去的指导方针，深得人心……为了能够蝉联宇宙总统之席位，ly决定在某地建立一些供水渠道，使当地每个村庄都有水渠能用来浇灌田地，以赢得民心。作为宇宙的统治者和宇宙智慧的象征，他需要用一种非常优雅的修建方案。

经过几天的学习之后，他终于制定出了一个计划。他把当地每个村庄抽象成三维坐标系上的点（xi，yi，zi）（xi，yi，zi），水可以通过渠道从一个村庄送往任何直接相连的村庄，修建后必须使得任意两个村庄直接或间接有水渠相连，且使得水渠条数尽可能小。经过他的计算，一条水渠的花费为其两端点村庄高度差|zi–zj||zi–zj|，两村庄距离D=(xi−xj)2+(yi−yj)2−−−−−−−−−−−−−−−−−√(xi−xj)2+(yi−yj)2 。

他想让这些渠道的平均花费，即总花费与总距离的比值尽可能小。

[输入格式]

本题有多组数据，设数据组数为T。对于每组数据，第一行1个正整数N，表示村庄数。接下来N行，每行三个非负整数，表示村庄坐标。数据以0结束。

[输出格式]

仅一个实数，表示总花费与总距离的比值。

[样例输入]

40 0 00 1 11 1 21 0 30

[样例输出]

1.000

[数据范围]

对于30%的数据：N≤7。

对于60%的数据：N ≤100。

对于90%的数据：N ≤ 300。

对于100%的数据：N≤1000，0≤xi，yi≤104，0≤zi≤107，T≤5，允许精度误差10−3N≤1000，0≤xi，yi≤104，0≤zi≤107，T≤5，允许精度误差10−3。

 

这不就是最优比率生成树吗

虽然作为一只不会01规划的蒟蒻

但我也只想到； 贪心

10pts

至少没爆0

 

话说01规划为何这么水？

#include
      
       #define MIN(a,b) (a)<(b)?(a):(b) #define re return#define R register #define ll long long#define inc(i,l,r) for(register int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);    if(f)x=-x;}#define D doubleconst int maxn=1005;const double EPS=0.00001; int n,vis[maxn];D dis[maxn],h[1005][1005],d[1005][1005],f[1005][1005];struct node{    int x,y,z;}pos[1005]; inline double cala(R int x,R int y){    re sqrt(x*x+y*y);} inline void Get_dis(){    inc(i,1,n)    inc(j,i+1,n)    {        d[i][j]=cala(pos[i].x-pos[j].x,pos[i].y-pos[j].y);        h[i][j]=abs(pos[i].z-pos[j].z);    }}inline bool check(D L){    inc(i,1,n)    inc(j,i+1,n)    f[j][i]=f[i][j]=h[i][j]-L*d[i][j];        dis[0]=0x3f3f3f3f;    inc(i,1,n)dis[i]=f[1][i],vis[i]=0;        D sum=0;        inc(i,1,n-1)    {        int u=0;        inc(j,2,n)        if(!vis[j]&&dis[j]
        
         EPS)        {            D mid=(l+r)/2;            if(check(mid))r=mid;            else l=mid;         }        printf("%.3lf\n",r);    }    re 0;}
        
       
      

位运算

[题目描述]

给定一个长为N的非负整数序列{ }，另有M个操作，每个操作都是如下三种中的一个：

1.将一段区间上的所有数and K。

2.将一段区间上的所有数or K。

3.查询一段区间上的所有数的xor值。

请设计一种算法，支持以上三种操作。

[输入格式]

第一行两个正整数N，M。

接下来一行，包含N个非负整数，表示初始序列。

接下来M行，每行首先一个数为操作编号，然后两个正整数L，R，表示需要处理的区间。若编号为1或2，接下来包含一个非负整数K。

[输出格式]

对于每个操作3，按顺序输出答案。

[样例输入]

5 51 2 3 4 53 2 41 1 4 53 2 52 3 4 43 3 5

[样例输出]

504

[数据范围]

对于10%的数据：N，M ≤ 10000，时限1s。

对于50%的数据：N，M ≤ 50000，时限3s。

对于100%的数据：N，M，K ≤ 200000，1 ≤L≤ R ≤N，时限1s。

 

虽然很生气，由于开小了数组掉了50pts

但是总比某wu姓同学开大数组保0好

线段树+位运算=水题

#include
      
       #define re return#define inc(i,l,r) for(register int i=l;i<=r;++i)using namespace std;template
       
        inline void rd(T&x){    char c;bool f=0;    while((c=getchar())<'0'||c>'9')if(c=='-')f=1;    x=c^48;    while((c=getchar())>='0'&&c<='9')x=x*10+(c^48);}const int maxn=1000005;int n,m,K[20],a,ans[20];bool tr[maxn][20];int lazy[maxn][20];//tr个数,lazy懒标记 #define lson rt<<1#define rson rt<<1|1inline void pushup(int rt){    inc(i,0,19)    tr[rt][i]=tr[lson][i]^tr[rson][i];}inline void build(int rt,int l,int r){    if(l==r)    {        rd(a);        inc(i,0,19)        tr[rt][i]=(a>>i)&1;        re ;    }        int mid=(l+r)>>1;    build(lson,l,mid);    build(rson,mid+1,r);    pushup(rt);}inline void pushdown(int rt,int l,int r,int mid){    inc(i,0,19)    if(lazy[rt][i])    {        lazy[lson][i]=lazy[rson][i]=lazy[rt][i];        if(lazy[rt][i]==1)            tr[lson][i]=tr[rson][i]=0;        else         {            tr[lson][i]=(mid-l+1)&1;            tr[rson][i]=(r-mid)&1;        }        lazy[rt][i]=0;    }}inline void modify_and(int rt,int l,int r,int x,int y){    if(x<=l&&r<=y)    {        inc(i,0,19)        if(!K[i])        {            tr[rt][i]=0;            lazy[rt][i]=1;//区间赋0         }        re ;    }    int mid=(l+r)>>1;    pushdown(rt,l,r,mid);    if(x<=mid)modify_and(lson,l,mid,x,y);    if(y>mid)modify_and(rson,mid+1,r,x,y);        pushup(rt);}inline void modify_or(int rt,int l,int r,int x,int y){    if(x<=l&&r<=y)    {        int f=(r-l+1)&1;        inc(i,0,19)        if(K[i])        {            tr[rt][i]=f;            lazy[rt][i]=2;//区间赋1         }        re ;    }    int mid=(l+r)>>1;    pushdown(rt,l,r,mid);    if(x<=mid)modify_or(lson,l,mid,x,y);    if(y>mid)modify_or(rson,mid+1,r,x,y);        pushup(rt);}inline void ask(int rt,int l,int r,int x,int y){    if(x<=l&&r<=y)    {        inc(i,0,19)        ans[i]^=tr[rt][i];        re ;    }    int mid=(l+r)>>1;    pushdown(rt,l,r,mid);    if(x<=mid)ask(lson,l,mid,x,y);    if(y>mid) ask(rson,mid+1,r,x,y);}int main(){    //freopen("in.txt","r",stdin);    rd(n),rd(m);    build(1,1,n);        int opt,k,l,r,ansnow;    inc(i,1,m)    {        rd(opt);        if(opt==3)        {            rd(l),rd(r);            ansnow=0;            ask(1,1,n,l,r);            inc(j,0,17)            if(ans[j])            {                ansnow|=(1<
        
         >j)&1;            if(opt==1)modify_and(1,1,n,l,r);                else modify_or(1,1,n,l,r);        }        }    re 0;}