以前一直没有做过非传统题
于是便有了这个练习
codeforces 679A
题目大意:
有一个数在([2,100])，有不超过20次询问某个数是不是它的约数，判断这个数是不是素数。
题解:
[2,100]之间不是素数就是合数(废话)
每个合数的唯一分解式一定是两个及以上的素数
所以枚举所有的素数，由于还有可能是某个素数的平方
所以还要枚举素数的平方,一共询问19次
#include <cstdio>
#include <cstring>
#include <algorithm>
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<b ? a:b;}
int p[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,4,9,25,49};
char s[10];
int main(){
int cnt = 0;
for(int i=0;i<19;++i){
printf("%d
",p[i]);
fflush(stdout);
scanf("%s",s);
if(!strcmp(s,"yes")) ++ cnt;
}
if(cnt >= 2) puts("composite");
else puts("prime");
fflush(stdout);
getchar();getchar();
return 0;
}
Codeforces 714D
题目大意:
在一个(n*n)的矩形二维平面里有两个不交叉重叠的整点小矩形。通过不超过200次操作获得小矩形的顶点坐标。每次操作可以询问一个那两个小矩形有几个全部在给定矩形内。(n leq 2^{16})
题解:
没什么可说的
二分八次(8*16 = 128 < 200)
#include <cstdio>
#include <cstring>
#include <algorithm>
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<b ? a:b;}
inline int query(int a,int b,int c,int d){
printf("? %d %d %d %d
",a,b,c,d);
fflush(stdout);
int x;read(x);
return x;
}
int main(){
int n;read(n);
int l = 1,r = n;
int x1=0,x2=0,y1=0,y2=0,x3=0,x4=0,y3=0,y4=0;
while(l <= r){
int mid = l+r >> 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
",x1,y1,x2,y2,x3,y3,x4,y4);
fflush(stdout);
getchar();getchar();
return 0;
}
Codeforces 727C
题目大意:
给定一个正整数n((n ge 3)),猜一个长为n的序列，最多询问n次某两个数的和.要求输出这个序列
题解:
构造一个方程组即可
#include <cstdio>
#include <cstring>
#include <algorithm>
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<b ? a:b;}
const int maxn = 5010;
int a[maxn],x[maxn];
inline int get(int i,int j){
printf("? %d %d
",i,j);
fflush(stdout);
int y;read(y);
return y;
}
int main(){
int n;read(n);
for(int i=1;i<n;++i){
x[i] = get(i,i+1);
}
x[0] = get(1,3);
a[2] = (x[1] + x[2] - x[0])>>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('
');
fflush(stdout);
getchar();getchar();
return 0;
}
APIO2016 Gap
题目大意:
猜一个严格递增序列的最大的相邻元素之差,提供操作MinMax(s,t)查询这个序列中数值属于([s,t])的元素的最大值和最小值。
//至于两个子任务什么的的自己看吧。。
题解:
- 子任务一:
- 只能查询(frac{N+1}{2})次
- 我们知道每次查询一定可以确定两个在序列中的元素
- 所以我们查询这么多次，确定下所有的元素即可。
- 子任务二:
- 限制了我们查询到的元素的个数
- 那么上一个方法就不可行了。。
- 主要原因在于我们可能反复查询到很密集的一些点
- 但是这些点又不对实际答案做出贡献
- 所以我们考虑去除对于不做贡献的点的查询
- 假设我们已经知道了整个区间的(max)和(min)
- 由抽屉原理我们一定有(ans < ceil(frac{max - min}{N-1}))
- 所以我们以这个值为间隔跳跃查询即可
#include "gap.h"
#include <cstdio>
#include <cstring>
#include <algorithm>
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<N;++i) ans = max(ans,q[i+1] - q[i]);
}else{
ll s = 0,t = 1LL<<60,mn,mx,lim1,lim2;
MinMax(s,t,&lim1,&lim2);
ll tmp = (lim2-lim1)/N;
int cnt = 0;
q[++cnt] = lim1;
for(s = lim1+1,t = s+tmp;s < lim2;s = t+1,t = s+tmp){
MinMax(s,min(t,lim2-1),&mn,&mx);
if(mn == -1) continue;
q[++cnt] = mn;q[++cnt] = mx;
}q[++cnt] = lim2;
for(int i=1;i<cnt;++i) ans = max(ans,q[i+1] - q[i]);
}
return ans;
}