广州二中NOI2018模拟赛（四十一）
本场比赛试题：ProblemSet
乱搞大赛
A.修序列1
看到这题应该要非常高兴，因为题目只输入一个数！
然后就可以愉快地打表了！打出前500的表，可以拿40分
求区间方差相信小学生都会，就不说了
因为打出的表长达47KB，所以要看源码，请点这里
下面是用来打表的程序
#include<bits/stdc++.h>
using namespace std;
double a[2000];
double f[2000000];
int size=0;
void insert(double x)
{
for(int i=1;i<=size;i++)
if(fabs(f[i]-x)<=1e-8) return;
f[++size]=x;
}
int main()
{
freopen("gao.out","w",stdout);
srand(time(0));int cnt=58,xx=0;
for(int fk=1;fk<=500;)
{
int n=cnt;size=0;
for(int i=1;i<=n;i++) a[i]=rand()%n+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n-i+1;j++)
{
double ave=0;
for(int k=j;k<=j+i-1;k++) ave+=a[k];
ave/=(double)i;
double dafa=0;
for(int k=j;k<=j+i-1;k++)
dafa+=(a[k]-ave)*(a[k]-ave);
dafa/=(double)i;
insert(dafa);
}
if(size==fk)
{
printf("if(k==%d){puts(\"%d\");puts(\"",fk,n);
for(int i=1;i<=n;i++) printf("%.0lf ",a[i]);
puts("\");}");fk++;cnt=58;xx=0;
fflush(stdout);
}
xx++;
if(xx%700==0&&cnt<fk) cnt++;
}
return 0;
}
然后70分是一个神秘的分数，除我之外没有人拿到了这个分数，要么是40，要么是100，但是我研究出了一个神秘的方法，可以拿到70分这个神秘分数
首先要想到，假如你知道n以及大致的值域，然后去随机一个长度为n的序列，就会很快得到答案，这个自己试一下就知道
但现在的问题是怎么根据k快速地得到n和值域
我们上面打了一个表，表里面包含了500以内k与n的对应关系，于是我们可以用一些点来拟合n关于k函数。经过使用各种不同的函数进行尝试，最终确定了函数模型：lg-lg函数，即lg(y)=a+b*lg(x)
然后拟合，得到一个近似的函数：
这个函数在k>2200时会不准确，我们引入纠偏：
值域对方差的影响应该是：值域范围越大，区间方差越多
值域我们可以钦定为2n，然后随着rand出来的结果进行调整：如果rand出来的方差比k小，就让值域扩大n/8，如果比k大就让值域缩小n/8
为了防止我们拟合出的n还不够准确，我们在运算过程中再次引入纠偏。容易想到，如果值域已经很大了，却仍然得不到我们想要的答案，那肯定是序列长度出了问题。而序列长度越大，区间方差越多。所以如果值域扩的太大了，就让序列长度+1；如果值域缩的太小了，就让序列长度-1。调整了序列长度后应该让值域恢复成2n
方差数量的统计可以使用map，然后手写一个浮点数比较的仿函数
#include<bits/stdc++.h>
using namespace std;
double a[1000];
int size=0;
double lg(double x){return log(x)/log(10);}
struct cmp
{
bool operator () (const double &x,const double &y) const
{
return x<=y-1e-8;
}
};
map<double,bool,cmp> f;
void insert(double x)
{
if(f.count(x)) return;
f[x]=1;size++;
}
int main()
{
srand(time(0));
int n,k;
scanf("%d",&k);
if(k==1){puts("1");puts("1 ");}
if(k==2){puts("2");puts("2 1 ");}
if(k<=2) return 0;
n=(int)round(pow(10,0.285919598401854+0.460726827413394*lg((double)k)));
if(k>=2200) n+=k/1000-1;
int t=16,cnt1=0,cnt2=0;
cout<<n<<endl;
while(true)
{
size=0;f.clear();
for(int i=1;i<=n;i++) a[i]=rand()%(n*t/8)+1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n-i+1;j++)
{
double ave=0;
for(int kk=j;kk<=j+i-1;kk++) ave+=a[kk];
ave/=(double)i;
double dafa=0;
for(int kk=j;kk<=j+i-1;kk++)
dafa+=(a[kk]-ave)*(a[kk]-ave);
dafa/=(double)i;
insert(dafa);
if(size>k){i=n+1;break;}
}
if(size==k)
{
printf("%d\n",n);
for(int i=1;i<=n;i++) printf("%.0lf ",a[i]);
break;
}
if(size>k&&t>0) t--;
if(t==0) n--;
if(size<k-10) t++;
if(t>64) n++;
}
return 0;
}
100分需要有一些钦定的思想
假如有一个长度为n的随机序列，然后我们往后面插入了一个很大的数，我们就可以钦定这个序列多了n个区间方差，理由是每个包含了这个很大的数的区间，方差八成是不一样的
如果我们要弄出一些重复的区间方差，那肯定要让值域小一些，才能撞到相同方差
于是我们可以先随机一个长度短、值域小的序列，然后算出它的答案。接着我们往后面加入很大的数，并钦定每加入一个数，答案都会加上当前序列长度减1
不断往后面加数，如果什么时候当前答案=k了，就验算一下，如果没问题就直接输出这个序列。如果当前答案大于k了，就重新来一遍上述过程
根据实测结果，很快就能得到答案。
但不知道为什么，我的代码计算那些k很小的序列时会很慢，于是我加入了之前打表的一部分
#include<bits/stdc++.h>
using namespace std;
double a[1010];
int k;
struct cmp{bool operator () (const double &x,const double &y) const{return x<=y-1e-8;}};
map<double,bool,cmp> f;
int check(int n)
{
f.clear();
for(int i=1;i<=n;i++)
for(int j=1;j<=n-i+1;j++)
{
double ave=0;
for(int kk=j;kk<=j+i-1;kk++) ave+=a[kk];
ave/=(double)i;
double dafa=0;
for(int kk=j;kk<=j+i-1;kk++)
dafa+=(a[kk]-ave)*(a[kk]-ave);
dafa/=(double)i;
f[dafa]=1;
}
return f.size();
}
void little(int k)
{
if(k==1){puts("1");puts("1 ");}
if(k==2){puts("2");puts("2 1 ");}
if(k==3){puts("3");puts("3 2 2 ");}
if(k==4){puts("3");puts("1 3 2 ");}
if(k==5){puts("4");puts("1 2 3 3 ");}
if(k==6){puts("4");puts("2 4 3 3 ");}
if(k==7){puts("4");puts("4 1 3 2 ");}
if(k==8){puts("5");puts("2 3 5 2 2 ");}
if(k==9){puts("5");puts("2 5 4 2 3 ");}
if(k==10){puts("5");puts("5 5 1 4 2 ");}
exit(0);
}
int main()
{
srand(time(0));
scanf("%d",&k);
if(k<=10) little(k);
while("STO wzt dalao")
{
int pre=rand()%50+1;
for(int i=1;i<=pre;i++) a[i]=rand()%5;
int now=check(pre);
while(now<k)
{
a[++pre]=rand()%2333333;
now+=(pre-1)?(pre-1):1;
if(now==k)
{
if(check(pre)!=k) break;
printf("%d\n",pre);
for(int i=1;i<=pre;i++) printf("%.0lf ",a[i]);
return 0;
}
}
}
return 0;
}
B.修序列2
题目中好像说什么“本题测试点较多，建议不会的选手在subtask#2特判一下退出”？傻逼才这么干
如果不限定询问长度，那就是一道小学生都会的大水题。我就搞一个01序列，每次枚举所有位置，然后往那里插入0或者1，如果在某个位置插入某个数成功了，就继续向更长扩展。
怎样算成功了呢？把搞出的这个序列拿去询问一下不就好了！
代入计分公式算一下，发现这个傻逼方法可以拿到31分
#include<bits/stdc++.h>
#include"hidden.hpp"
#define pb push_back
using namespace std;
std::vector<int> guess(int n)
{
vector<int> dafa;
for(int k=1;k<=n;k++)
{
vector<int> tmp=dafa;
for(int i=0;i<=tmp.size();i++)
{
tmp.insert(tmp.begin()+i,1,0);
if(is_subsequence(tmp)){dafa=tmp;break;}
tmp[i]=1;
if(is_subsequence(tmp)){dafa=tmp;break;}
tmp.erase(tmp.begin()+i);
}
}
return dafa;
}
正解还是要有一些乱搞思想的
我们将原序列中出现较少的数作为“分隔符”，然后去算每个“分隔符”的左边有多少个“异教徒”（“异教徒”就是不同于“分隔符”的那个数字）
计算“异教徒”时要注意控制询问串长度，如果左边算过去会超过限制长度，就从右边算过去试试
然后根据每个“分隔符”左边的“异教徒”数量，就可以确定整个01序列了
感觉也没什么好说的。这题只要想到了“分隔符”就是一道水题了
#include<bits/stdc++.h>
#include"hidden.hpp"
#define sub is_subsequence
using namespace std;
int len,limit,falun1,falun2,k;
int dafa[110];
int chk1(int x,int p)
{
vector<int> a(p,falun1);
a.insert(a.end(),k-x+1,falun2);
if(a.size()>limit) return -1;
else return sub(a);
}
int chk2(int x,int p)
{
vector<int> a(x,falun2);
a.insert(a.end(),p,falun1);
if(a.size()>limit) return -1;
else return sub(a);
}
int gao(int x)
{
int p1=0,p2=0;
while("STO wzt dalao")
{
int tmp=chk1(x,p1+1);
if(tmp==-1){p1=-1;break;}
if(tmp) p1++;
else break;
}
while("STO wzt dalao")
{
int tmp=chk2(x,p2+1);
if(tmp==-1){p2=-1;break;}
if(tmp) p2++;
else break;
}
if(~p1) return p1;
else if(~p2) return len-k-p2;
else return limit-(k-x+1);
}
vector<int> guess(int n)
{
len=n;limit=n/2+1;
if(sub(vector<int>(limit,1))) falun1=1,falun2=0;
else falun1=0,falun2=1;
k=n/2;
while(k&&(!sub(vector<int>(k,falun2)))) k--;
if(k==0){return vector<int>(n,falun1);}
for(int i=1;i<=k;i++) dafa[i]=gao(i);
dafa[k+1]=n-k;
for(int i=0;i<=k;i++) dafa[i]=dafa[i+1]-dafa[i];
vector<int> res(dafa[0],falun1);
for(int i=1;i<=k;i++)
res.push_back(falun2),res.insert(res.end(),dafa[i],falun1);
return res;
}
C.修墙
20分可以乱搞
模拟题目给出的迭代方法，构造出300*300的图，然后每次询问遍历子图就好了
遍历顺序从上到下，从左到右，遍历过程中进行染色，如果某个白格子上面或左边有白格子，那么颜色就与那个格子相同，否则就新建一种颜色。容易想到，按这样的顺序更新，绝对不会使得同一个连通块内格子的颜色不同，更不可能漏掉某个连通块
#include<bits/stdc++.h>
using namespace std;
bool mp[520][520];
int color[310][310];
void build(int p)
{
for(int i=1;i<=p;i++)
for(int j=p+1;j<=(p<<1);j++)
mp[i][j]=mp[i][j-p];
for(int i=p+1;i<=(p<<1);i++)
for(int j=1;j<=p;j++)
mp[i][j]=mp[i-p][j];
for(int i=p+1;i<=(p<<1);i++)
for(int j=p+1;j<=(p<<1);j++)
mp[i][j]=0;
}
int main()
{
mp[1][1]=1;
for(int i=0;i<=8;i++) build(1<<i);
int q,x1,x2,y1,y2;
scanf("%d",&q);
while(q--)
{
memset(color,0,sizeof(color));
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
int dafa=0;
for(int i=x1;i<=x2;i++)
for(int j=y1;j<=y2;j++)
if(mp[i][j])
{
if(i>x1&&mp[i-1][j]) color[i][j]=color[i-1][j];
else if(j>y1&&mp[i][j-1]) color[i][j]=color[i][j-1];
else color[i][j]=++dafa;
}
printf("%d\n",dafa);
}
return 0;
}
也许我离100分的做法差个脑洞……
观察这个图，发现白格子从左上角开始，形成了一个分形结构！而且这个分形结构是我们所熟悉的二叉树！
如果我们将左上角那个格子的坐标定为(0,0)，不难推出，一个格子(x,y)是白格子，当且仅当x&y=0，黑格子反之
这是一个非常优秀的性质。至少不弄出图也能拿20分啦
继续利用一下这个性质，然后差分处理询问，就很容易想到本题的正解了（其实是我懒得写了）
#include<bits/stdc++.h>
using namespace std;
namespace IO
{
const int S=1<<16;
//Input Correlation
char buf[S],*H,*T;
inline char Get()
{
if(H==T) T=(H=buf)+fread(buf,1,S,stdin);
if(H==T) return -1;return *H++;
}
void read(){}
template<typename I,typename... Is>
inline void read(I& x,Is&... xs)
{
x=0;char c=Get();
while(!isdigit(c)) c=Get();
while(isdigit(c)) x=x*10+c-'0',c=Get();
read(xs...);
}
//Output Correlation
char obuf[S],*oS=obuf,*oT=oS+S-1,c,qu[55];int qr;
inline void flush()
{
fwrite(obuf,1,oS-obuf,stdout);
oS=obuf;
}
inline void putc(char x)
{
*oS++ =x;
if(oS==oT) flush();
}
inline void print(int x)
{
if(!x) putc('0');
while(x) qu[++qr]=x%10+'0',x/=10;
while(qr) putc(qu[qr--]);
putc('\n');
}
}
using namespace IO;
inline bool white(const int &x,const int &y){return !(x&y);}
inline bool black(const int &x,const int &y){return x&y;}
int query(int x,int y)
{
int dafa=1,falun=1;
for(int i=0;(1<<i)<=y;i++)
{
if(white(x,1<<i)&&black(y,1<<i)) dafa+=falun-white(x,(1<<i)-1);
if(black(x,1<<i)&&black(y,1<<i)) dafa=falun;
if(white(x,1<<i)) falun=(falun<<1)-white(x,(1<<i)-1);
}
return dafa;
}
inline int gao(int x,int l,int r)
{
if(l==0) return query(x,r);
return query(x,r)-query(x,l-1)+(white(l-1,x)&&white(l,x));
}
int main()
{
int q,x1,x2,y1,y2;
for(read(q);q;q--)
{
read(x1,y1,x2,y2);x1--;x2--;y1--;y2--;
print(gao(x1,y1,y2)+gao(y1,x1,x2)-white(x1,y1));
}
flush();
return 0;
}