A 题： 说的是在（LR） 之间找出ab互质 bc 互质 ac 不互质的 3个数 数据量小直接暴力
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> using namespace std; typedef long long ll; ll gcd(ll a, ll b){ return b==0?a:(gcd(b,a%b)); } int main() { ll L,R; while(scanf("%I64d%I64d",&L,&R)==2){ bool falg=false; for(ll i=L; i<=R-2; ++i){ for(ll j=i+1; j<=R-1; ++j){ ll f= gcd(i,j); if(f!=1) continue; for(ll e = j+1; e<=R; ++e){ f = gcd(e,j); if(f!=1) continue; f=gcd(i,e); if(f==1) continue; falg=true; printf("%I64d %I64d %I64d ",i,j,e); break; } if(falg) break; } if(falg) break; } if(falg==false) puts("-1"); } return 0; }
B 题： 说的是找出cnt1 + cnt2 个质数然后 他们各不相同 cnt1 个不是x倍数的 cnt2 个不是y倍数的，分配完这些数后最大值最小
这样二分最大值，假设在mid 内 x 倍数为 px y的为py xy的为pxy 那么优先将 px-pxy的分给cnt2 把 py-pxy分给cnt1 这样接下来判段剩下的是否可以分配给cnt1和cnt2 剩余的 这样不断二分下去
#include <cstdio> #include <string.h> #include <algorithm> #include <iostream> using namespace std; typedef long long ll; ll cnt1,cnt2,x,y; ll maxv(ll a, ll b){ return a>b?a:b; } bool solve(ll mid){ ll a1 = mid/x; ll b1 = mid/y; ll c1 = mid/(x*y); ll acnt1 = maxv(cnt1 - (b1-c1),0LL); ll acnt2 = maxv(cnt2 - (a1-c1),0LL); ll lest = mid-(a1+b1-c1); if(lest>=(acnt1+acnt2)) return true; else return false; } int main() { while(scanf("%I64d%I64d%I64d%I64d",&cnt1,&cnt2,&x,&y)==4){ ll R = 9223372036854775807LL; ll L=0; ll ans; while(R>=L){ ll mid = (R+L)/2; if(solve(mid)){ ans=mid; R=mid-1; }else{ L=mid+1; } } printf("%I64d ",ans); } return 0; }
C 题： 输的是给了n个数 你写出n的一个排列使得 相邻的数的差值有k个不同的值，然后这n个数必须是1—n 不能重复，这样不断的往两边取 直到有k个不同的
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> #include <set> using namespace std; typedef long long ll; const int maxn = 100005; int ans[maxn]; set<int>Q; int main() { int n,k; while(scanf("%d%d",&n,&k)==2){ int L=1; int num=1; int R=n+1; int now=1; ans[0]=1; for(int i=1; i<k; ++i){ now=1-now; if(now==1){ L++; ans[num]=L; num++; }else{ R--; ans[num]=R; num++; } } if(num<n){ if(now==0){ for(int i=R-1; i>L; i--) ans[num++]=i; }else{ for(int i=L+1; i<R; i++) ans[num++]=i; } } for(int i=0; i<n; ++i){ printf("%d%c",ans[i],i==(n-1)?' ':' '); } } return 0; }
D题： 说的是给了n个数 m次操作 然后给了他们区间&后的值 这样问他们与后是否是合法的，我们知道给了区间& 的结果 也就是区间内的值每个都|上了这个值才能保证他们都具有相同的值
这样然后 将给的区间全部或上 q 然后 最后在按照 题目给的& 上一次 一旦出现与答案不符就证明是错误的
#include <iostream> #include <cstdio> #include <algorithm> #include <string.h> using namespace std; const int maxn = 100005; int cL,cR,W,b,n; struct Itree{ int V[maxn*4]; void pushdown(int o){ V[o*2]|=V[o]; V[o*2+1]|=V[o]; V[o]=0; } void build(int o, int L, int R){ if(L==R) return ; pushdown(o); int mid=(L+R)/2; build(o*2,L,mid); build(o*2+1,mid+1,R); V[o]=V[o*2]&V[o*2+1]; } void update(int o, int L, int R){ if(cL<=L&&R<=cR){ V[o]|=W; return; } pushdown(o); int mid=(L+R)/2; if(cL<=mid) update(o*2, L, mid); if(cR>mid) update(o*2+1,mid+1,R); } void query(int o, int L, int R){ if(cL<=L&&R<=cR){ if(b==0) W=V[o]; else W=W&V[o]; b=1; return ; } int mid=(L+R)/2; if(cL<=mid) query(o*2,L,mid); if(cR>mid) query(o*2+1,mid+1,R); } void print(int o, int L, int R){ if(L==R){ printf("%d%c",V[o],L==n?' ':' '); return ; } int mid = (L+R)/2; print(o*2, L, mid); print(o*2+1,mid+1,R); } }T; int LL[maxn],RR[maxn],QQ[maxn]; int main() { int m; while(scanf("%d%d",&n,&m)==2){ memset(T.V,0,sizeof(T.V)); for(int i=0; i<m; ++i){ scanf("%d%d%d",&LL[i],&RR[i],&QQ[i]); cL=LL[i]; cR=RR[i]; W=QQ[i]; T.update(1,1,n); } bool falg=true; T.build(1,1,n); for(int i=0; i<m; ++i){ b=0; cL=LL[i]; cR=RR[i]; T.query(1,1,n); if(QQ[i]!=W){ falg=false; break; } } if(falg==false){ printf("NO "); }else { printf("YES "); T.print(1,1,n); } } return 0; }
E 题说的 你把每个串从其他串中区别出来的期望步数， 状态压缩live[S] 表示 S 这个状态中有多少个串需要在选字母，然后dp[S] 表示到达这个状态的概率 ，对于每个一个S 有相应的期望
#include <iostream> #include <cstdio> #include <string.h> #include <algorithm> using namespace std; double dp[1<<22]; char str[55][22]; long long live[1<<22]; int main() { int n; while(scanf("%d",&n)==1){ memset(live,0,sizeof(live)); memset(dp,0,sizeof(dp)); for(int i=0; i<n; ++i){ scanf("%s",str[i]); } int m=strlen(str[0]); for(int i=0; i<n; ++i){ for(int j=i+1; j<n; ++j ) { int S=0; for(int k=0; k<m; ++k) if(str[i][k]==str[j][k]) S|=(1<<k); live[S]|=(1LL<<i)|(1LL<<j); } } for(int S = (1<<m)-1; S>0; --S){ for(int i=0; i<m; ++i) if(S&(1<<i)) live[S^(1<<i)]|=live[S]; } dp[0]=1; double ans=0; for(int S=0; S<1<<m; ++S){ int num=0; for(int i=0; i<n; ++i) if(live[S]&(1LL<<i)) num++; ans+=dp[S]*num; num=0; for(int i=0; i<m; ++i) if(S&(1<<i)) num++; for(int i=0; i<m; ++i) if( (S&(1<<i)) == 0 ) dp[ S|(1<<i) ]+= dp[S]/(m-num); } printf("%.15lf ",ans/n); } return 0; }