A. Counterexample
http://codeforces.com/contest/483/problem/A
在l,r范围中求出任意a,b,c组合l ≤ a < b < c ≤ r.使得a,b b,c 互质 a,c不互质
看到
r - l ≤ 50于是就想到先打表 t[i][j]存储 a+i,a+j是不是互质
然后搜i，j，k就行了
1 #include <iostream> 2 using namespace std; 3 long long a,b; 4 bool iscop(long long x,long long y) 5 { 6 if (y==0) return false; 7 if (y==1) return true; 8 return iscop(y,x%y); 9 } 10 bool is[60][60]; 11 int main() 12 { 13 cin>>a>>b; 14 if (b-a<2) {cout<<"-1";return 0;} 15 else 16 { 17 for (long long i=0; i<=b-a; i++) 18 for (long long j=0;j<=b-a; j++) 19 { 20 is[i][j]=iscop(a+i,a+j); 21 } 22 for (long long i=0; i<b-a-1; i++) 23 for (long long j=i+1;j<b-a; j++) 24 for (long long k=j+1;k<=b-a; k++) 25 { 26 if(is[i][j]&&is[j][k]&&!is[i][k]) { 27 cout<<a+i<<" "<<a+j<<" "<<a+k; 28 return 0; 29 } 30 } 31 } 32 cout<<"-1"; 33 return 0; 34 }
C. Diverse Permutation
http://codeforces.com/contest/483/problem/C
给出n, k 创建一个由1~n组成的数组(顺序未知)pi，满足
|p1 - p2|, |p2 - p3|, ..., |pn - 1 - pn| 这些数有k种不同
首先要知道最大不同种类是n-1种 方案类画圆圈
/*
2 1 3 2
3 1 4 2 3
4 1 5 2 4 3
*/
所以对于一个K要求，就先构造一个k要求 剩下的只要跟在后面不动就行了
1 #include <iostream> 2 3 using namespace std; 4 void fun1(int n) 5 { 6 int now=1; 7 cout<<now; 8 int ccc=1; 9 for (int i=n;i>0;i--){ 10 now+=i*ccc; 11 cout<<" "<<now; 12 ccc*=-1; 13 } 14 } 15 int main() 16 { 17 int n,k; 18 while(cin>>n>>k) 19 { 20 fun1(k); 21 for (int i=k+2;i<=n;i++) 22 cout<<" "<<i; 23 cout<<endl; 24 } 25 return 0; 26 }
B [转
B. Friends and Presents
http://codeforces.com/contest/483/problem/b
求一个最小数x 有至少cnt1个数qi 满足 x%qi!=0并且有至少cnt2个数pi 满足 x%pi!=0 任意pi！=qi x y互质
其实直接二分就行了,但是我分类了好一会儿,直接算的
首先,必须要满足以下条件
设pos(x)=x>0?x:0
则(pos(cnt2-tb)+pos(cnt1-tc))<=ta
因为最大公倍数很麻烦所以最开始去掉影响,
大概就在(cnt1+cnt2)/(na+nb+nc)或者cnt2/(na+nb)和cnt1/(na+nc)某个最大的后面,其实去不去无所谓
分别假设第一个pos为0,第二个为0,两个都不为0,要加上的值为r,
则pos(cnt2-tb-r/x)+pos(cnt2-tc-r/y)<=ta+r-r/x-r/y
检验条件并更新要加上的值即可
值得一提的是,
因为r/x.r/y都是整数,所以只能约掉,在只有一个pos为0的情况下,我先算了一个直接用分数解等式,再对答案倒退了一个x求得可能的新加值,之后检验新加值是不是满足/x=(int)原加值/x-1,如果是的话就可以用来更新这个情况下的原加值
1 #include<cstdio> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 typedef long long ll; 6 ll x,y,cnt1,cnt2; 7 ll pos(ll a){ 8 if(a>=0)return a; 9 return 0; 10 } 11 int main(){ 12 scanf("%I64d%I64d%I64d%I64d",&cnt1,&cnt2,&x,&y); 13 ll lcm=x*y; 14 ll na=lcm-lcm/x-lcm/y+1; 15 ll nb=lcm/x-1; 16 ll nc=lcm/y-1; 17 ll sumn=na+nb+nc; 18 ll t=(cnt1+cnt2)/sumn; 19 t=max(t,cnt2/(na+nb)); 20 t=max(t,cnt1/(na+nc)); 21 ll ta=na*t; 22 ll tb=nb*t; 23 ll tc=nc*t; 24 ll ans=lcm*t; 25 if((pos(cnt2-tb)+pos(cnt1-tc))<=ta)ans--; 26 else { 27 ll r=0x7fffffff; 28 ll r0=pos(cnt2-tb)+pos(cnt1-tc)-ta; 29 if(r0>=0&&cnt2>=tb&&cnt1>=tc)r=min(r,r0); 30 31 ll r1=x*(cnt1-tc-ta)/(x-1); 32 ll tr11=cnt1-tc-ta+(r1/x-1); 33 if(tr11/x==r1/x-1)r1=min(r1,tr11); 34 r1=max(r1,x*(cnt2-tb)); 35 if(cnt1>=tc+ta)r=min(r,r1); 36 ll r2=y*(cnt2-tb-ta)/(y-1); 37 ll tr2=cnt2-tb-ta+(r2/y-1); 38 if(tr2/y==r2/y-1)r2=min(r2,tr2); 39 r2=max(r2,y*(cnt1-tc)); 40 if(cnt2>=tb+ta)r=min(r,r2); 41 ans+=r; 42 } 43 printf("%I64d ",ans); 44 return 0; 45 }
happy everyday :) !