A.
There is a polyline going through points (0, 0) – (x, x) – (2x, 0) – (3x, x) – (4x, 0) – ... - (2kx, 0) – (2kx + x, x) – ....
We know that the polyline passes through the point (a, b). Find minimum positive value x such that it is true or determine that there is no such x.
题解：所有线的斜率均为\(k=\pm1\)
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i< =n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x< <1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define eps (1e-10)
#define F (100000007)
typedef long long ll;
typedef double ld;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
ld a,b;
int main()
{
// freopen("A.in","r",stdin);
// freopen(".out","w",stdout);
cin>>a>>b;
if (a
B."Or" Game
已知n个数，执行k次操作：将任意一个数乘x，求最大or和
(1 ≤ n ≤ 200 000, 1 ≤ k ≤ 10, 2 ≤ x ≤ 8).
解法：由于 \(x\geqslant2\) 我们应该将位数最大的那个1挪到尽可能高位，因此，应反复乘同一个数
用线段树预处理区间or和，然后枚举执行操作的数即可
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i< =n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x< <1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define MAXN (200000+10)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
ll a[MAXN],x;
int n,k;
class SegmentTree
{
ll minv[MAXN*4];
int n;
public:
SegmentTree(){MEM(minv) }
SegmentTree(int _n):n(_n){ MEM(minv) }
void mem(int _n)
{
n=_n;
MEM(minv)
}
void build(int x,int L,int R)
{
int M=(L+R)>>1;
if (L==R) {minv[x]=a[L];return;}
else
{
if (L< =M) build(Lson,L,M);
if (M
if (ql>qr) return 0;
return _query_min(1,1,n);
}
ll _query_min(int x,int L,int R)
{
if (ql< =L&&R<=qr) return minv[x];
ll ans=0,M=(L+R)>>1;
if (ql< =M) ans|=_query_min(Lson,L,M);
if (M< qr) ans|=_query_min(Rson,M+1,R);
return ans;
}
}S;
int main()
{
// freopen("B.in","r",stdin);
// freopen(".out","w",stdout);
cin>>n>>k>>x;
For(i,n) scanf("%I64d",&a[i]);
sort(a+1,a+1+n);
S.mem(n);
S.build(1,1,n);
ll e=0;
For(i,n)
{
ll ans=0;
ans|=S.query_min(1,i-1);
ans|=S.query_min(i+1,n);
ll t=a[i];
For(i,k) t*=x;
ans|=t;
e=max(e,ans);
}
cout<
C .已知序列a1, a2, ..., an (|ai| ≤ 10 000,1 ≤ n ≤ 200 000). 求x,
使序列a1 - x, a2 - x, ..., an - x 的子段和的绝对值最小.
解法：二分x，如果最大子段和与最小子段和平均值\(\geqslant 0\),则说明x太大.
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define For(i,n) for(int i=1;i< =n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i
#define Forp(x) for(int p=pre[x];p;p=next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=next[p])
#define Lson (x< <1)
#define Rson ((x<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define eps (1e-8)
#define MAXN (200000+10)
typedef long long ll;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int n;
double a[MAXN];
double ans;
bool check(double x)
{
double mins=a[1]-x,maxs=a[1]-x;
double t1=0,t2=0;
For(i,n) {
t1=max(t1+a[i]-x,a[i]-x);
maxs=max(maxs,t1);
t2=min(t2+a[i]-x,a[i]-x);
mins=min(mins,t2);
}
ans=maxs;
return (mins+maxs)/2 <0;
}
int main()
{
// freopen("c.in","r",stdin);
// freopen(".out","w",stdout);
cin>>n;
For(i,n) scanf("%lf",&a[i]);
double l=-2000000000,r=2000000000;
int k=150;
while (k--)
{
double m=(l+r)/2;
if (check(m)) r=m;
else l=m;
}
check((l+r)/2);
printf("%.7lf\n",ans);
return 0;
}
