2015-08-11NOIP模拟赛

这次考得还好，还看得过去吧：

第一题：

Description

万众瞩目的《跨时代》专辑发行之后，周杰伦又开始了他的世界巡回演唱会《超时代》。小鸿是周董的铁杆粉丝，这种机会她当然不愿错过，她认为电视机前哪怕1nm的距离与在现场1km的距离相比都差多了，这是两种截然不同的感觉。所以小鸿就计划着带小y去看周杰伦的演唱会。
小鸿到达现场后碰巧赶上演唱会布置道具，而为了布置道具自然要有一个空地，而且还得是矩形的。
演唱会主办方临时跟消防局借了n个栏杆，想要用这n个栏杆围出一个尽量大的矩形以满足粉丝们的各种要求，然而麻烦的是这些栏杆长度不一，给围场地带来了一定难度。
身为神犇的小鸿对于这种问题自然觉得是小case，她用自己的脑子就能算出最大面积。
可是很不幸她第一次来到周董的演唱会，激动得脑子断了路，所以小y向你求救：请你来编写一个程序，计算用这n个栏杆所能围成矩形的最大面积。
（注：必须要刚好围成一个矩形，即不能出现多余的边长，且不能切断栏杆，但所给栏杆不一定要全部用上）。

Input

第一行一个正整数n，表示栏杆的数量。
第二行n个正整数，表示每根栏杆的长度li。

Output

仅一行一个正整数，表示用给出的栏杆围成最大矩形的面积。如果不能围成矩形，输出”No Solution”（不包含引号，严格区分大小写与空格）。

Sample Input

Sample Output

    #1 
   
 1 
   
 #2 
   
 No Solution

Hint

20%的数据：li全部相等。
60%的数据：1≤n≤10。
100%的数据：1≤n≤16,1≤li≤15。

Analyse

这是一道坑题，看到题让人不由得想起了POJ的传奇小木棍经典搜索剪枝大法，可惜对于这题只有WA了。

先慢慢讲：

20%的数据，裸暴力，N/4放在边上多两条+ 的时候拼长方形

60%的数据，大暴力，N^3枚举，判断某条边在长上，宽上还是不选，枚举完成后+DFS搜索判断。

100%的数据，同60%的数据枚举完成后用背包判断就AC了。

TIP：可以先把表打好再枚举，打表大法好。

第二题：

Description

MT神牛非常喜欢出Xor的题，在WC2011的时候，MT神牛出了一道非常经典的Xor最大路径题。
Bird向MT神牛学习，思考了许多关于Xor路径的问题，有一天，Bird想到了一个问题，给出一个序列，求这个序列的连续子序列的Xor值最大。
如1 3 4 8，最大的Xor子序列当然是3 xor 4 xor 8=15了。
Bird实在太强大了，这个问题怎么能难住他呢？于是Bird又开始思考了，如果是一颗树呢，如何求出这棵带边权的树的一条最大Xor路径呢？但是谁都知道Bird实在太强大了，马上想到了解决这个问题的高效算法，但是Bird总是不愿去机房写代码，于是他把这个easy的问题，交给了你，希望你能尽快帮他写完代码。

Input

第一行，一个整数N，表示一颗树有N个节点，接下来N-1行，每行三个整数a,b,c表示节点a和节点b之间有条权值为c的边。

Output

输出仅一行，即所求的带边权树的Xor最大路径。

Sample Input

Sample Output

7

Hint

40%的数据：数据退化为一条链；
除上述的40%的数据外，还有10%的数据N≤1000；
100%的数据：2≤n≤100000，1<a,b≤N，c≤2^31-1。

Analye

Xor是一种神奇的运算，他有很多奇妙的性质，比如：求区间Xor的值可以打Xor前缀表。

Xor也具有自反性，这也很神。

对于这题Trie树+贪心才是正解！！（看标称吧）

关于这类问题，武森大神在他的某篇论文讲“0”“1”时提到过。

第三题：

Description

Kelukin是一个做外贸生意的土豪。这天他要把 N个货物卖给 Lxc ，他需要把这N个货物装到若干个箱子中 (箱子从0开始标号)，每个箱子中的货物数为1~9。由于货物有许多，所以 Lxc 不可能一个个去数货物，他只能派M个检查员去检查货物，第i个检查员会检查第firi+0*periodi，firi+1*periodi，firi+2*periodi...个箱子，然后数出每个检查的箱子中物品数，然后他会用（Σ看到的物品数）*总箱子数/（检查的箱子数）来估算总货物数(注意：如果一个人没有检查任何箱子，则他估算的结果为0)，然后 Lxc 会用所有检查员估算的总货物数的平均数来估算总货物数。现在 Kelukin 知道这M个检查员的firi和periodi，虽然 Kelukin 是一名土豪，但他还是想让 Lxc 估算的总货物数尽可能的多。现在 Kelukin 可以自己定箱子数以及每个箱子中的货物数(要满足每个箱子里的货物数为 1~9 个)，求 Lxc 估算的货物数最大值。

Input

第一行包含 2个正整数 N和M，第二行包含M个数表示 firi，第三行包含 M个数表示 periodi。

Output

包含一个实数(保留到小数点后 5位)，表示 Lxc 估算的货物数最大值。

Sample Input

Sample Output

Sample Explanation

#1中用4个箱子，在2号箱子中放3个，其余箱子中放1个。

Hint

20% 的数据：1≤n≤10；
60% 的数据：1≤n≤2000；
100% 的数据：1≤n≤100000，1≤m≤5，firi,periodi≤100000。

Analyse

这题20%的数据刷过。

60%的数据坑了，每次给箱子编个号，判断被查了几次，效率低。

100%的就奇了！考虑每个箱子会被哪些人检查，共有2 m 种情况，统计每种情况的箱子的个数，然后直接对着2 m 种情况排序，贪心即可，可以一边枚举一边统计个数与贡献。

代码：

T1：

#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <string>
#include <string.h>
#include <time.h>
#include <memory.h>
#include <stdio.h>
#include <cmath>
#include <stdlib.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstdio>
#include <climits>

using namespace std;

const char NO_ANS[]="No Solution";
const int MAXN=17;

int Len[MAXN],N;
bool Used[MAXN],Can[1<<MAXN],g[1<<MAXN];
int Now,Total,suma,sumb,num,Ans=-1,Tag[MAXN];
int now1,now2;

void DP (int sum,int now)
{
     if (now==0 || sum&1) return;
     int i,j;
     memset(g,0,sizeof(g));
     g[0]=1;
     for (i=0;i<N;i++)
     {
         if ((now&(1<<i))==0) continue;
         for (j=(sum>>1);j>=Len[i];j--)
         g[j]=(g[j]|g[j-Len[i]]);
     }
     if (g[sum>>1]) Can[now]=true;
}

void Pre (int dep,int sum,int now)
{
     if (dep==N)
     {DP (sum,now);return ;}
     Pre (dep+1,sum+Len[dep],now+(1<<dep));
     Pre (dep+1,sum,now);
}

void DFS (int dep,int now1,int sum1,int now2,int sum2)
{
     if (dep==N)
     {
         if (Can[now1] && Can[now2])  Ans=max(Ans,sum1*sum2/4);
         return ;
     }
     DFS (dep+1,now1,sum1,now2,sum2);
     DFS (dep+1,now1+(1<<dep),sum1+Len[dep],now2,sum2);
     DFS (dep+1,now1,sum1,now2+(1<<dep),sum2+Len[dep]);
}

void init ()
{
	int i;
	scanf ("%d",&N);
	for (i=0;i<N;i++)
	scanf ("%d",&Len[i]);
}

int main()
{
	init ();
	Pre (0,0,0);
    DFS (0,0,0,0,0);
    if (Ans>0)
    printf ("%d",Ans);
    else
    cout<<NO_ANS;
}

T2：首次写Trie树哦

#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <string>
#include <string.h>
#include <time.h>
#include <memory.h>
#include <stdio.h>
#include <cmath>
#include <stdlib.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstdio>
#include <climits>

#define intmin -2147483640
#define intmax 2147483640

using namespace std;

const int MAXN=100010;
const int START=1<<30;

typedef struct Graph_Node_Tp
{
    int v,w,next;
}node;

node Edge[MAXN<<1];

typedef struct Trie_Node_Tp
{
    int next[2];
}trie_;
trie_ Trie[MAXN<<8];

int Edge_num=1,L=1,Ans=0;
int Head[MAXN],Used[MAXN],num[MAXN];

void AddEdge(int u,int v,int w)
{
    Edge[Edge_num].v=v,Edge[Edge_num].w=w,Edge[Edge_num].next=Head[u],Head[u]=Edge_num++;
    Edge[Edge_num].v=u,Edge[Edge_num].w=w,Edge[Edge_num].next=Head[v],Head[v]=Edge_num++;
}

void DFS (int x,int w)
{
    num[x]=w;
    Used[x]=1;
    int a;
    for(a=Head[x];a;a=Edge[a].next)
    {
        if(Used[Edge[a].v]) continue;
        DFS(Edge[a].v,w^Edge[a].w);
    }
}
void Insert (int num)
{
    int i,a,p=0;
    for(i=30;i>=0;i--)
    {
        a=(num&(1<<i))?1:0;
        if(!Trie[p].next[a])
            Trie[p].next[a]=++L,
            Trie[L].next[0]=Trie[L].next[1]=0;
        p=Trie[p].next[a];
    }
}

int Find(int num)
{
    int i,a,p=0,w=0;
    for(i=30;i>=0;i--)
    {
        a=num&(1<<i)?0:1;
        if(Trie[p].next[a])
            w|=1<<i,p=Trie[p].next[a];
        else
        p=Trie[p].next[!a];
    }
    return w;
}

int main()
{
    int i,u,v,w,N;
    scanf("%d",&N);
    for(i=1;i<N;i++)
        scanf("%d%d%d",&u,&v,&w),
        AddEdge(u,v,w);
    DFS(1,0);
    Trie[0].next[0]=Trie[0].next[1]=0;
    for(i=0;i<N;i++)
        Insert(num[i]),u=Find(num[i]),
        Ans=max(Ans,u);
    printf("%d\n",Ans);
}

T3：惭愧……代码是错地，还没改。求大神修正……

#include <iostream>
#include <vector>
#include <bitset>
#include <cmath>
#include <iomanip>
#include <string>
#include <string.h>
#include <time.h>
#include <memory.h>
#include <stdio.h>
#include <cmath>
#include <stdlib.h>
#include <algorithm>
#include <stack>
#include <queue>
#include <cstdio>
#include <climits>

using namespace std;

const int MAXN=100010;
const int MAXM=7;
const int QL[MAXM]={0,1,2,4,8,16};

typedef struct Man
{
    int fir,per;
    bool operator < (const Man &Y) const
    {return per<Y.per;}
}man;

man A[MAXM];
int N,M;
int Boxn[40];
double ans=-1;
int Give[40];
int Che[MAXM],See[MAXN];

void init ()
{
	int i;
	scanf ("%d%d",&N,&M);
	for (i=1;i<=M;i++)
	scanf ("%d",&A[i].fir);
	for (i=1;i<=M;i++)
	scanf ("%d",&A[i].per);
	
	sort (A+1,A+1+M);
}

void Calc (int t)
{
     int i,j,tmp=t;
     for (i=0;i<=31;i++)
     cout<<Boxn[i]<<"   ";cout<<endl;
     for (i=(1<<M)-1;i>=0;i--)
       Give[i]=Boxn[i],tmp-=Boxn[i];
     for (i=(1<<M)-1;tmp;i--)
       if (tmp>=8*Boxn[i])
         Give[i]=9*Boxn[i],tmp-=8*Boxn[i];
       else
         Give[i]+=tmp,tmp=0;
     for (i=31;i>=0;i--)
       for (j=1;j<=M;j++)
         if (Give[j]&(1<<M))
           Che[j]+=Give[i],See[j]+=Boxn[i];
     for (i=0;i<=31;i++)
     cout<<Give[i]<<"   ";cout<<endl;
     double tmpt=0;
     for (i=1;i<=5;i++)
     tmpt+=1.0*t*Che[i]/See[i];
     printf ("%lf\n",tmpt);
     ans=max(ans,tmpt);
}

void work ()
{
     int now,i,tag=0;
     for (now=1;now<=(N-1)/9;now++)
     {
         tag=0;
         for (i=1;i<=M;i++)
           if (now>=A[i].fir && (now-A[i].fir)%A[i].per==0)
             tag+=QL[i];
         cout<<now<<"    "<<tag<<endl;
         Boxn[tag]++;
     }
     
     for (now=(N-1)/9+1;now<=N;now++)
     {
         tag=0;
         for (i=1;i<=M;i++)
           if (now>=A[i].fir && (now-A[i].fir)%A[i].per==0)
             tag|=QL[i];
         cout<<now<<"    "<<tag<<endl;
         Boxn[tag]++;
         Calc (now);
     }
     printf ("%.4lf",ans);
}

int main()
{
    init ();
    work ();
}

秒客网

2015-08-11NOIP模拟赛