Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] 题解

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=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=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 (Mql=ql,this->qr=qr;

        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=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; }

Codeforces Round #320 (Div. 1) [Bayan Thanks-Round] 题解

归档

功能