CCF全国信息学奥林匹克联赛（NOIP2016）复赛模拟提高组 day2 解题报告

时间：2022-09-04 21:31:20

从昨天开始就进入了一天一考的可怕时间。
还有17天就考试了啊。

CCF全国信息学奥林匹克联赛

（NOIP2016）

复赛模拟提高组 day2 解题报告

1. Sequence

Limits
Time: 1000ms per test case
Memory: 131072KiB
Java class name: Main
Judge mode: Normal

怎么说呢，是一个大水题，标算是一个贪心，我也写的贪心，但我只有10分啊233333333。
好像也有30分算法

  • 【30分算法】

暴力暴力，枚举每个排列。

  • 【满分算法一】

贪心
有两种情况。
我们将这一列数排序，从小到大依次为a1、a2、a3、……an。
则有以下两种最大值情况
1）…… a(n-3) a(n-1) a1 an a2 a(n-2) a(n-4) ……
2）…… a(n-2) a2 an a1 a(n-1) a3 ……

【核心代码】

int cal()
{
int p=n/2+1,ans=0;
    b[p]=a[n];
for(int i=p-1;i>=1;i-=2) b[i]=a[p-i];
for(int i=p-2;i>=1;i-=2) b[i]=a[n-(p-i-1)];
for(int i=p+1;i<=n;i+=2) b[i]=a[i-p+1];
for(int i=p+2;i<=n;i+=2) b[i]=a[n-(i-p)];
for(int i=2;i<=n;i++)
       ans+=abs(b[i]-b[i-1]);
return ans;
}
int main()
{
int t;
cin>>t;
for (int tt=1;tt<=t;tt++)
    {
cin>>n;
for (int i=1;i<=n;i++) cin>>a[i];
       sort(a+1,a+n+1);
int ans=0,ret=0;
       ans=cal();
for (int i=1;i<=n/2;i++) swap(a[i],a[n-i+1]);
       ret=cal();
cout<<"Case "<<tt<<": "<<max(ans,ret)<<endl;
    }
return 0;
}

  1. 【满分算分二】

    来自廖弘毅的神奇最小生成树算法。
    【代码】

#include<bits/stdc++.h>
using namespace std;
int n;
int num[60];
int fa[60];
int use[60];
struct EDGE {
int a,b,c;
  EDGE(int _a=0,int_b=0,int_c=0):a(_a),b(_b),c(_c) {
  }
bool operator>(const EDGE& e) const{
return c>e.c;
  }
}Edge[4000];
int getf(int i) {
return fa[i]==i?i:(fa[i]=getf(fa[i]));
}
bool Connect(int i,int j) {
return getf(i)==getf(j);
}
void Union(int i,int j) {
  i=getf(i);
  j=getf(j);
if(i^j) {
    fa[i]=j;
  }
}
int Calc() {
int sum=0;
int tot=0;
for(int i=1;i<=n;++i) {
    fa[i]=i;
    use[i]=0;
for(int j=i+1;j<=n;++j){
      Edge[tot++]=EDGE(i,j,abs(num[i]-num[j]));
    }
  }
  sort(Edge,Edge+tot,greater<EDGE>());
int p=0;
int cnt=1;
while(cnt^n) {
while(Connect(Edge[p].a,Edge[p].b)||use[Edge[p].a]==2||use[Edge[p].b]==2) 
    {
      ++p;
    }
    Union(Edge[p].a,Edge[p].b);
    ++cnt;
    sum+=Edge[p].c;
    ++use[Edge[p].a];
    ++use[Edge[p].b];
  }
return sum;
}
int main()
{
  ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin>>t;
for(int _=1;_<=t;++_) 
  {
cin>>n;
for(int i=1;i<=n;++i) 
cin>>num[i];
cout<<"Case "<<_<<": "<<Calc()<<endl;
  }
return 0;
}

2. Cut

Limits
Time: 1000ms per test case
Memory: 131072KiB
Java class name: Main
Judge mode: Normal

也是水题啊233，不过我考场上只有50分，在check函数中把范围设错了。
既然是二分，就直接给满分算法了吧。

  • 【满分算分】
#include<bits/stdc++.h>
#define end exit(0);
using namespace std;
int m,sum[510][510],n,g,h,a[510][510];
int head,tail,inf=1200000000;
int work(int l,intr,int x)
{
int left=1,right=1,cas=0;
while(right<=m)
    {
int now=sum[r][left]-sum[l-1][left];
while(now<x&&right<m) right++,now+=sum[r][right]-sum[l-1][right];
if(now>=x) cas++;
       left=right+1,right=left;
    }
return cas;
}
bool check(int x)
{
int l=1,r=1,cas=0;
while(r<=n)
    {
while(work(l,r,x)<h&&r<n) r++;
if(work(l,r,x)>=h) cas++;
       l=r+1,r=l;
    }
return cas>=g;
}
void angelbeats()
{
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
cin>>a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
            sum[i][j]=sum[i-1][j]+a[i][j];
}
int main()
{
cin>>n>>m>>g>>h;
    angelbeats();
    head=0,tail=inf;
while(head!=tail)
    {
int mid=(head+tail)/2;
if(check(mid)) head=mid+1;
else tail=mid;
    }
while(!check(head)&&head>=0)head--;
if(head==-1) cout<<0,end;
cout<<head;
}

Cut

Limits
Time: 1000ms per test case
Memory: 131072KiB
Java class name: Main
Judge mode: Normal

  • 【补充】

Xor，即异或，a xor b意思是如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。

  • 【解题报告】

确实是最难的题，不过徐宏图还是拿了满分。Orz。
数据范围很详细。
有一个点在1000以内，所以暴力也可以拿到。
还有四个点的数据是一条链 ，可以直接将前缀的xor值丢进一个二叉树里，当查询的时候就尽量可能往反方向走。
对于所有数据点，这里有一条性质：
a xor b xor b= a
所以一条树上路径的Xor和即为相应的两个节点root的xor值的xor值（lcr以上的部分相互抵消），再用链的做法，既可以解决这道题。

  • 【65分代码】
    附上来自谯雨的神奇随机代码。

【核心代码】

#include<bits/stdc++.h>
using namespace std;
struct P
{
int to;
int next;
int len;
}a[201000];
int tot,first[101000];
int n,f[101000][20],g[101000][20],dep[101000];
int maxx;
inline int max(inti1,int i2)
{
return i1>i2?i1:i2;
}
inline int getint()
{
int i=0,f=1;
char c;
for(c=getchar();c<'0'||c>'9';c=getchar())
if(c=='-') f=-1;
for(;c>='0'&&c<='9';c=getchar())
        i=(i<<3)+(i<<1)+(c^'0');
return i*f;
}
inline void f1(inti1,int i2,inti3)
{
    ++tot;
    a[tot].to=i2;
    a[tot].len=i3;
    a[tot].next=first[i1];
    first[i1]=tot;
}
void dfs(int cur,intfather)
{
for(int u=first[cur];u;u=a[u].next)
    {
if(a[u].to!=father)
       {
           dep[a[u].to]=cur;
           f[a[u].to][0]=cur;
           g[a[u].to][0]=a[u].len;
           maxx=max(maxx,a[u].len);
           dfs(a[u].to,cur);
       }
    }
}
inline int f2(intx,int y)
{
int i,t,sum=0,sum2=0;
if(dep[x]<dep[y]){t=x; x=y; y=t;}
for(i=19;i>=0;--i)
if(dep[f[x][i]]<=dep[y])
        {
           maxx=max(maxx,sum^=g[x][i]);
           x=f[x][i];
        }
if(x==y) return sum;
for(i=19;i>=0;--i)
if(f[x][i]!=f[y][i])
        {
           maxx=max(maxx,sum^=g[x][i]);
           maxx=max(maxx,sum2^=g[y][i]);
           x=f[x][i];
           y=f[y][i];
        }
    maxx=max(maxx,sum^=f[x][0]); maxx=max(maxx,sum2^=f[y][0]);
    sum^=sum2;
return sum;
}
int main()
{
//freopen("xor.in","r",stdin);
//freopen("xor.out","w",stdout);
int i,j,i1,i2,i3;
    srand(time(0));
    n=getint();
for(i=1;i<n;++i)
    {
       i1=getint(); i2=getint();i3=getint();
       f1(i1,i2,i3);
       f1(i2,i1,i3);
    }
    dep[1]=1;
    dfs(1,1);
for(j=1;j<=19;++j)
for(i=1;i<=n;++i)
        {
           f[i][j]=f[f[i][j-1]][j-1];
           g[i][j]=g[i][j-1]^g[f[i][j-1]][j-1];
           maxx=max(maxx,g[i][j]);
        }
if(n<=1000)
    {
for(i=1;i<=n;++i)
for(j=i+1;j<=n;++j)
               maxx=max(maxx,f2(i,j));
    }
else
    {
for(i=1;i<=n;++i)
           maxx=max(maxx,f2(i,1));
for(i=1;i<=n;++i)
       {
           i1=rand()%n+1; i2=rand()%n+1;
           maxx=max(maxx,f2(i1,i2));
       }
    }
cout<<maxx<<"\n";
return 0;
}
  • 【满分算法】

那么下面就是正解了

【核心代码】

#include<bits/stdc++.h>
#define INF (int)1e9
using namespace std;
struct LINE
{
int end;
int next;
int len;
}line[200001];
struct TRIE
{
int son[2];
}trie[5000001];
int n;
int u;
int v;
int c;
int ans;
int tot;
int size;
int head;
int tail;
int sum[100001];
int que[100001];
int first[100001];
bool pd;
bool vis[100001];
void add(int u,intv,int w)
{
    size++;
    line[size].next=first[u];
    first[u]=size;
    line[size].end=v;
    line[size].len=w;
}
void ins(int x)
{
int b[33];
for(int i=1;i<=31;i++){b[i]=(x&1);x>>=1;}
int pos=1;
for(int i=31;i>=1;i--)
    {
if(!trie[pos].son[b[i]])trie[pos].son[b[i]]=++tot;
       pos=trie[pos].son[b[i]];
    }
}
int query(int x)
{
int ret=0;
int b[33];
for(int i=1;i<=31;i++){b[i]=(x&1);x>>=1;}
int pos=1;
for(int i=31;i>=1;i--)
    {
if(trie[pos].son[(b[i]^1)])
       {
           ret+=(1<<(i-1));
           pos=trie[pos].son[(b[i]^1)];
       }
else pos=trie[pos].son[b[i]];
    }
return ret;
}
void BFS()
{
memset(vis,0,sizeof(vis));
    head=tail=0;tot=1;ins(0);
    vis[1]=true;
    que[tail++]=1;
while(head^tail)
    {
       ans=max(query(sum[que[head]]),ans);
       ins(sum[que[head]]);
int u=first[que[head]];
while(u)
       {
if(!vis[line[u].end])
           {
              sum[line[u].end]=(sum[que[head]]^line[u].len);
              que[tail++]=line[u].end;
              vis[line[u].end]=true;
           }
           u=line[u].next;
       }
       head++;
    }
}
int main ()
{
//freopen("xor.in","r",stdin);
//freopen("xor.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<n;i++)
    {
scanf("%d%d%d",&u,&v,&c);
       add(u,v,c);add(v,u,c);
    }
    BFS();
cout<<ans;
}
标签：

相关文章