以前一直没有做过非传统题
于是便有了这个练习
题目大意:
有一个数在\([2,100]\)，有不超过20次询问某个数是不是它的约数，判断这个数是不是素数。
题解:
[2,100]之间不是素数就是合数(废话)
#include#include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;char ch;bool flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}inline int cat_max(const int &a,const int &b){return a>b ? a:b;}inline int cat_min(const int &a,const int &b){return a = 2) puts("composite"); else puts("prime"); fflush(stdout); getchar();getchar(); return 0;}
题目大意:
在一个\(n*n\)的矩形二维平面里有两个不交叉重叠的整点小矩形。通过不超过200次操作获得小矩形的顶点坐标。每次操作可以询问一个那两个小矩形有几个全部在给定矩形内。\(n \leq 2^{16}\)
题解:
没什么可说的
二分八次\(8*16 = 128 < 200\)#include#include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;char ch;bool flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}inline int cat_max(const int &a,const int &b){return a>b ? a:b;}inline int cat_min(const int &a,const int &b){return a > 1; int x = query(1,1,n,mid); if(x) r = mid-1,y2 = mid; else l = mid+1; } l = 1;r = n; while(l <= r){ int mid = l+r >> 1; int x = query(1,1,mid,y2); if(x) r = mid-1,x2 = mid; else l = mid+1; } l = 1;r = x2; while(l <= r){ int mid = l+r >> 1; int x = query(mid,1,x2,y2); if(x) l = mid+1,x1 = mid; else r = mid-1; } l = 1;r = y2; while(l <= r){ int mid = l+r >> 1; int x = query(x1,mid,x2,y2); if(x) l = mid+1,y1 = mid; else r = mid-1; } l = 1;r = n; while(l <= r){ int mid = l+r >> 1; int x = query(1,1,mid,n); if((x1>=1&&x1<=mid)&&(x2>=1&&x2<=mid)&&(y1>=1&&y1<=n)&&(y2>=1&&y2<=n)) --x; if(x) r = mid-1,x4 = mid; else l = mid+1; } l = 1;r = x4; while(l <= r){ int mid = l+r >> 1; int x = query(mid,1,x4,n); if((x1>=mid&&x1<=x4)&&(x2>=mid&&x2<=x4)&&(y1>=1&&y1<=n)&&(y2>=1&&y2<=n)) --x; if(x) l = mid+1,x3 = mid; else r = mid-1; } l = 1;r = n; while(l <= r){ int mid = l+r >> 1; int x = query(x3,1,x4,mid); if((x1>=x3&&x1<=x4)&&(x2>=x3&&x2<=x4)&&(y1>=1&&y1<=mid)&&(y2>=1&&y2<=mid)) --x; if(x) r = mid-1,y4 = mid; else l = mid+1; } l = 1;r = y4; while(l <= r){ int mid = l+r >> 1; int x = query(x3,mid,x4,y4); if((x1>=x3&&x1<=x4)&&(x2>=x3&&x2<=x4)&&(y1>=mid&&y1<=y4)&&(y2>=mid&&y2<=y4)) --x; if(x) l = mid+1,y3 = mid; else r = mid-1; } printf("! %d %d %d %d %d %d %d %d\n",x1,y1,x2,y2,x3,y3,x4,y4); fflush(stdout); getchar();getchar(); return 0;}
题目大意:
给定一个正整数n(\(n \ge 3\)),猜一个长为n的序列，最多询问n次某两个数的和.要求输出这个序列
题解:
构造一个方程组即可
#include#include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;char ch;bool flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}inline int cat_max(const int &a,const int &b){return a>b ? a:b;}inline int cat_min(const int &a,const int &b){return a >1; a[1] = x[1] - a[2]; for(int i=3;i<=n;++i){ a[i] = x[i-1] - a[i-1]; } putchar('!'); for(int i=1;i<=n;++i){ printf(" %d",a[i]); }putchar('\n'); fflush(stdout); getchar();getchar(); return 0;}
题目大意:
猜一个严格递增序列的最大的相邻元素之差,提供操作MinMax(s,t)查询这个序列中数值属于\([s,t]\)的元素的最大值和最小值。
//至于两个子任务什么的的自己看吧。。题解:
- 子任务一:
- 只能查询\(\frac{N+1}{2}\)次
- 我们知道每次查询一定可以确定两个在序列中的元素
- 所以我们查询这么多次，确定下所有的元素即可。
- 子任务二:
- 限制了我们查询到的元素的个数
- 那么上一个方法就不可行了。。
- 主要原因在于我们可能反复查询到很密集的一些点
- 但是这些点又不对实际答案做出贡献
- 所以我们考虑去除对于不做贡献的点的查询
- 假设我们已经知道了整个区间的\(max\)和\(min\)
- 由抽屉原理我们一定有\(ans < ceil(\frac{max - min}{N-1})\)
- 所以我们以这个值为间隔跳跃查询即可
#include "gap.h"#include#include #include using namespace std;typedef long long ll;const int maxn = 1000010;ll findGap(int T, int N){ static ll q[maxn<<1]; ll ans = 0; int n = 0; if(T == 1){ ll l = 0,r = N+1,s = 0,t = 1LL<<60,mn,mx; while(l < r-1){ MinMax(s,t,&mn,&mx); q[++l] = mn; q[--r] = mx; s = mn+1,t=mx-1; } for(int i=1;i