A. Vasya and Petya’s Game
题意: Vasya和Petya在玩一个游戏。 Vasya在1~n中任意选一个数x，并且Petya要来猜这个数x。 Petya可以进行诸如此类的询问:”x能否被y整除”，Vasya只会回答yes或者no。 询问: Petya最少需要问几次才能确定数x，并且输出他询问的数都是什么，有多种顺序输出一种即可。 解析: 这显然是个找规律题… 我们发现对于一个能够分出来两个不同质因数的数我们只要对质因数及质因数的几次幂进行询问即可确定该数。 所以我们把目光放在质因数上。 假设我们询问了n以下所有质因数的一次幂，形如 如果紧接着询问了所有质因数的二次幂，形如 所以经由上面的规律寻找大概猜测我们要询问所有质因子的x次幂，并且该质因子的x次幂小于等于n。 大概脑补可以想象正确性。 直接暴力搞就行(为了尊重题我写了个线性筛素数23333) 代码:
;int n;int cnt;int print[N];int tot;int prime[N];int v[N];void sieve(){for(int i=2;i<=n;i++){if(!v[i]){prime[++tot]=i;}for(int j=1;j<=tot&&i*prime[j]<=n;j++){v[i*prime[j]]=1;if(i%prime[j]==0)continue;}}}int main(){scanf(“%d”,&n);sieve();for(int i=1;i<=tot;i++){int tmp=prime[i];while(tmp<=n){print[++cnt]=tmp;tmp*=prime[i];}}printf(“%d\n”,cnt);for(int i=1;i<=cnt;i++)printf(“%d “,print[i]);puts(“”);}B. Invariance of Tree
题意: 有一棵大小为n的无向树，我们称一棵树也在这棵树上。 询问: 给定序列求该树，不存在则输出NO,否则输出YES并且输出任意一种情况。 解析: 既然是一棵树，那么一定无环，也就是说不能没有大小为1或者2的置换，如果没有的话该树一定存在环，所以我们只需要寻找是否存在大小为1或者2的置换就好了。 如果存在大小为1的置换的话，即把所有其他的点连向它即可。 如果不存在大小为1的置换，反而存在大小为2的置换的话，首先将二者的边连上。 然后枚举其他置换。 我们发现其他置换的奇数点与第一个点连的话，那么所有的奇数点的下一个点都应该与第二个点连。(或者相反:D) 所以如果其他置换中有一个置换的大小为奇数则不能满足题意，输出NO。 否则按照如上方法输出边即可。 如果大小为1，大小为2的置换均不存在直接输出NO即可。 代码:
;int n;int a[N];int v[N];int sta[N];int tag[N];int main(){scanf(“%d”,&n);for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);int flag=0;for(int i=1;i<=n;i++){if(a[i]==i){flag=1;puts(“YES”);for(int j=1;j<=n;j++)if(j!=i)printf(“%d %d\n”,i,j);break;}}if(flag)return 0;int tmp=-1;for(int i=1;i<=n;i++){if(a[a[i]]==i){tmp=i;break;}}if(tmp==-1){puts(“NO”);return 0;}v[tmp]=v[a[tmp]]=1;for(int i=1;i<=n;i++){if(!v[i]){int top=0;while(!v[i]){sta[++top]=i;v[i]=1;i=a[i];}if(top&1){puts(“NO”);return 0;}for(int j=1;j<=top;j++){if(j&1)tag[sta[j]]=1;else tag[sta[j]]=2;}}}puts(“YES”);printf(“%d %d\n”,tmp,a[tmp]);for(int i=1;i<=n;i++){if(tag[i]==1)printf(“%d %d\n”,tmp,i);else if(tag[i]==2)printf(“%d %d\n”,a[tmp],i);}}C. Points on Plane
题意: 左下角为个点。 询问 求一个 定义的曼哈顿距离 且 (md点少或者密集的时候不就是随便输出一个排列么2333) 解析 这个是有内涵的！ 我们把这个矩阵切成1000个如下的小矩阵。
然后我们将这些小矩阵按照顺序编上号。 所有奇数号内部的点按照纵坐标升序，偶数号内部的点按照纵坐标降序。 之后我们来考虑这种做法的最糟总和。 显然最糟跨越x是再多一些来回弹的可能性？所以应该比这个要大一两个数量级。 跨越y最糟是每次内部 所以大概最糟可以达到，完全满足题中要求，我们只需要把点按照这种方式排序输出即可。 代码:
;int n;struct Point{int x,y,no;friend istream& operator >> (istream &_,Point &a){scanf(“%d%d”,&a.x,&a.y);return _;}}pt[N];int get_dis(Point a,Point b){return abs(a.x-b.x)+abs(a.y-b.y);}bool cmp(Point a,Point b){return a.x<b.x;}bool cmp2(Point a,Point b){return a.y<b.y;}bool cmp3(Point a,Point b){return a.y>b.y;}int main(){scanf(“%d”,&n);for(int i=1;i<=n;i++){cin>>pt[i];pt[i].no=i;}sort(pt+1,pt+n+1,cmp);int la=0,flag=1,lano=0;for(int i=1;i<=n;i++){if(pt[i].x-la>=1000){if(flag)sort(pt+lano+1,pt+i+1,cmp2);else sort(pt+lano+1,pt+i+1,cmp3);lano=i;flag^=1;la+=1000;}}for(int i=1;i<=n;i++)printf(“%d “,pt[i].no);puts(“”);}D. Flights for Regular Customers只有他的好身体，没有地方可去，只想到处流浪、人生就像一场旅行，
