Codeforces Round #576 (Div. 2) 题解

A.City Day

题意

题解

水题，模拟即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,x,y,s[100005];

signed main()
{
    n=read(); x=read(); y=read();
    for (int i=1;i<=n;i++) s[i]=read();
    for (int i=1;i<=n;i++)
    {
        bool flag=1;
        for (int j=max(1,i-x);j<=min(n,i+y);j++) if (j!=i) flag&=s[j]>s[i];
        if (flag) return !printf("%d",i);
    }
    return 0;
}

B.Water Lily

题意

题解

小学数学题，用勾股定理可以知道答案为 $\dfrac{L^2-H^2}{2H}$ 。

#include<bits/stdc++.h>

using namespace std;

double h,l;

signed main()
{
    cin>>h>>l;
    cout<<fixed<<setprecision(10)<<(l*l-h*h)/h/2;
    return 0;
}

C.MP3

毒瘤阅读题。

题意

题解

令 $k=\dfrac{m\times 8}{n}$ 可以发现不同的数最多为 $2^k$ 。排序后离散化，然后枚举左端点，就可以确定右端点，答案取端点之外长度的最小值即可。

注意 $m\le 10^8$ ，直接算长度会爆。不过 $2^{19}\geq 4\times 10^5$ ，如果 $k\geq 19$ 答案就是 $0$ 。

#include<bits/stdc++.h>
#define ll long long

using namespace std;

inline ll read()
{
    char ch=getchar(); ll f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

map <ll,ll> mp;
ll n,m,id,ans=1e9,s[400005],L[400005];

signed main()
{
    n=read(); m=read()*8/n;
    for (ll i=1;i<=n;i++) s[i]=read();
    sort(s+1,s+n+1);
    for (ll i=1;i<=n;i++)
    {
        if (!mp.count(s[i]))
        {
            mp[s[i]]=++id;
            L[id]=i; //数值的左端点
        }
    }
    if (m>=19) return 0&puts("0");
    const ll len=1<<m;
    for (ll i=1;i<=id;i++)
    {
        int r=(i+len<=id) ? L[i+len] : n+1;
        ans=min(ans,L[i]-1+n-r+1);
    }
    return !printf("%lld",ans);
}

D.Welfare State

题意

题解

线段树裸题，维护最小值，单点修改和区间修改。

注意 $2$ 操作每次都要取 $\max$ ，否则连续多次操作会锅。

#include<bits/stdc++.h>
 
using namespace std;
 
inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}
 
const int N=200005;
struct Tree{
    int left,right,mn;
    bool delta;
} tree[N<<2];
int n,m,s[N],a,b,c;
 
inline void pushup(int x) { tree[x].mn=min(tree[x<<1].mn,tree[x<<1|1].mn); }
 
inline void pushdown(int x)
{
    if (tree[x].mn>tree[x<<1].mn)
    {
        tree[x<<1].mn=tree[x].mn;
        tree[x<<1].delta=1;
    }
    if (tree[x].mn>tree[x<<1|1].mn)
    {
        tree[x<<1|1].mn=tree[x].mn;
        tree[x<<1|1].delta=1;
    }
    tree[x].delta=0;
}
 
void build(int x,int l,int r)
{
    tree[x].left=l;
    tree[x].right=r;
    if (r-l==1) tree[x].mn=s[l];
    else
    {
        int mid=(l+r)>>1;
        build(x<<1,l,mid);
        build(x<<1|1,mid,r);
        pushup(x);
    }
}
 
void upd(int x,int l,int d)
{
    if (l<=tree[x].left && l+1>=tree[x].right) tree[x].mn=d;
    else
    {
        if (tree[x].delta) pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1;
        if (l<mid) upd(x<<1,l,d);
        if (l+1>mid) upd(x<<1|1,l,d);
        pushup(x);
    }
}
 
int query(int x,int l)
{
    int r=l+1;
    if (l<=tree[x].left && r>=tree[x].right) return tree[x].mn;
    else
    {
        if (tree[x].delta) pushdown(x);
        int mid=(tree[x].left+tree[x].right)>>1,ans=1e9;
        if (l<mid) ans=min(ans,query(x<<1,l));
        if (r>mid) ans=min(ans,query(x<<1|1,l));
        return ans;
    }
}
 
signed main()
{
    n=read();
    for (int i=1;i<=n;i++) s[i]=read();
    build(1,1,n+1);
    m=read();
    while (m--)
    {
        a=read(); b=read();
        if (a==1)
        {
            c=read();
            upd(1,b,c);
        }
        else
        {
            tree[1].mn=max(tree[1].mn,b);
            tree[1].delta=1;
        }
    }
    for (int i=1;i<=n;i++) printf("%d ",query(1,i));
    return 0;
}

F.Rectangle Painting 1

题意

题解

常规的二维区间DP，用 $f[l][r][x][y]$ 表示在左下角 $(l,x)$ ，右上角 $(r,y)$ 的区域中覆盖所有 # 最优解。转移就对横纵分别枚举中间点。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,f[55][55][55][55];
char s[55][55];

int dfs(int l,int r,int x,int y)
{
    if (l==r && x==y) return s[l][x]=='#';
    int &ans=f[l][r][x][y];
    if (~ans) return ans;
    ans=max(r-l,y-x)+1;
    for (int i=l;i<r;i++) ans=min(ans,dfs(l,i,x,y)+dfs(i+1,r,x,y));
    for (int i=x;i<y;i++) ans=min(ans,dfs(l,r,x,i)+dfs(l,r,i+1,y));
    return ans;
}

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) scanf("%s",s[i]+1);
    memset(f,-1,sizeof(f));
    return !printf("%d",dfs(1,n,1,n));
}