百度之星初赛第三场 2 4 6

感觉B和D都有问题，但是就按照正常思路写吧。。

B：如果是平方数，且该数的根是质数，就是YES，否则NO；

#define int ll
const int N= 1000010;
int n;
int primes[N], cnt;
bool st[N];

void get_primes(){
    for(int i=2;i<=N;i++){
        if(!st[i]) primes[cnt++]=i;
        for(int j=0;primes[j]<=N/i;j++){
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
    }
}

void solve()
{
//    cin>>n>>m;
    cin>>n;
    st[1] = 1;
    while(n -- ) {
        ll a;cin>>a;
        ll t = sqrt(a);
        if(t * t != a) {
            NO;
            continue;
        }
        if(!st[t]) {
            YES;
        } else {
            NO;
        }
    }
}

D：如果有空洞连续出现，就删掉。然后遍历所有联通块，看看这些联通块中有多少空洞

//#define int ll
const int N = 1010;
int n,m,ans1,ans2,ans3;

char mp[N][N]; 
bool vis[N][N];
bool del[N][N];

void bfs(int x,int y) {
    queue<pii> q;
    q.push({x,y});
    int ans = 0;
    while(q.size()) {
        auto tmp = q.front();q.pop();
        if(vis[tmp.x][tmp.y]) continue;
        vis[tmp.x][tmp.y] = 1;
        fo(i,0,3) {
            int xx = tmp.x + dx[i],yy = tmp.y + dy[i];
            if(xx <= 0 || yy <= 0 || xx > n || yy > m) continue;
            if(mp[xx][yy] == '.' && !del[xx][yy]) {
                ans ++ ;
                del[xx][yy] = 1;
            }
            if(vis[xx][yy] || mp[xx][yy] == '.' || del[xx][yy]) continue;
            mp[xx][yy] = '.';
            del[xx][yy] = 1;
            q.push({xx,yy});
        }
    }
    
    if(ans == 0) {
        ans1++;
    }
    else if(ans == 1) ans2 ++ ;
    else if(ans == 2) ans3 ++ ; 
}

void dell(int x,int y) {
    queue<pii>q;
    q.push({x,y});
    bool f = 0;
    fo(i,0,3) {
        auto tmp = q.front();
        int xx = tmp.x + dx[i],yy = tmp.y + dy[i];
        if(mp[xx][yy] == '.') f = 1;
    }
    if(!f) return;
    del[x][y] = 1;
    while(q.size()) {
        auto tmp = q.front();q.pop();
        if(vis[tmp.x][tmp.y]) continue;
        vis[tmp.x][tmp.y] = 1;
        fo(i,0,3) {
            int xx = tmp.x + dx[i],yy = tmp.y + dy[i];
            if(xx <= 0 || yy <= 0 || xx > n || yy > m) continue;
            if(vis[xx][yy] || mp[xx][yy] == '#') continue;
            del[xx][yy] = 1;
            q.push({xx,yy});
        }
    }
}

void solve()
{
    cin>>n>>m;
    fo(i,1,n) {
        fo(j,1,m) {
            cin>>mp[i][j];
        }
    }
    ms(vis,0);
    fo(i,1,n){
        fo(j,1,m) {
            if(mp[i][j] == '.') {
                dell(i,j);
            }
        }
    }
    
    
    ms(vis,0);
    fo(i,1,n) {
        fo(j,1,m) {
            if(mp[i][j] == '#') {
                bfs(i,j);
            }
        }
    }
    cout<<ans1<<' ' <<ans2<<' ' <<ans3<<endl;
}

6.区间最大值

先预处理数前缀和 sum[i] 

用单调栈，预处理出每个点后面离它最近的比它大的数的位置pos。

[ i , pos - 1 ] 之间的最大值就是 a[i] 。

倒序遍历结果 计算每个 [i, n] 之间的总结果 suf[i] = suf[pos]  + a[i] * (sum[pos - 1] - sum[i-1] )

将 l 和 r 离线下来在倒序遍历的时候记录答案就可以了，maxx 表示 l 到 r 的区间最大值，pos 表示 区间最大值的位置 ，las[pos] 表示比 pos 还要大的数的位置

ans = suf[l] - suf[las[pos]] + maxx * (sum[r] - sum[las[pos] - 1]);

//#define int ll
const int N = 5e5+10,M = 1e6+10,inf = 1e6;
int n,q,a[N],top,sta[N],las[N];
ll suf[N],pre[N];

int mx[N<<2];

void build(int now ,int l,int r) {
    if(l ==r ) {
        mx[now] = a[l];
        rt;
    }
    int mid = l + r >> 1;
    build(now << 1,l,mid);
    build(now<<1|1,mid+1,r);
    mx[now] = max(mx[now<<1],mx[now<<1|1]);
}

int query_max(int now,int l,int r,int ml,int mr) {
    if(ml <= l && mr <= r) return mx[now];
    if(ml > r || mr < l) return 0;
    int mid = l + r >> 1;
    return max(query_max(now<<1,l,mid,ml,mr),query_max(now<<1|1,mid+1,r,ml,mr));
}

int query_pos(int now,int l,int r,int ml,int mr,int val) {
    if(l == ml && r == mr) {
        if(mx[now] < val) return -1;
        if(l == r) return 1;
        int mid = l + r>> 1;
        if(mx[now*2] == val) {
            return query_pos(now * 2,l,mid,l,mid,val);
        } else {
            return query_pos(now * 2 + 1,mid + 1,r,mid+1,r,val);
        }
    }
    int mid = l + r >> 1;
    if(mr <= mid) {
        return query_pos(now<<1,l,mid,ml,mr,val);
    } else if(mr > mid) {
        return query_pos(now<<1|1,mid+1,r,ml,mr,val);
    } else {
        int res = query_pos(now<<1,l,mid,ml,mid,val);//如果左半边没有 
        if(res == -1) {
            res = query_pos(now * 2 + 1,mid+1,r,mid+1,mr,val);
        }
        return res;
    }
}
void solve()
{
//    cin>>n>>m;
    cin>>n>>q;
    pre[0] = 0;
    fo(i,1,n) {
        cin>>a[i];
        pre[i] = pre[i-1] + a[i];
    }
    top = 0;
    sta[++top] = n + 1;
    a[n+1] = inf;
    of(i,n,1) {
        while(top > 0 && a[sta[top]] < a[i]) { 
            -- top;
        }
        las[i] = sta[top];
        sta[++top] = i;
    }
    suf[n+1] = 0;
    of(i,n,1) {
        suf[i] = suf[las[i]] + 1ll * a[i] * (pre[las[i] - 1] - pre[i-1]);
    }
    build(1,1,n);
    fo(i,1,q) {
        int l,r;cin>>l>>r;
        ll ans = suf[l];
        int maxx = query_max(1,1,n,l,r);
        int pos = query_pos(1,1,n,l,r,maxx);
        ans -= suf[las[pos]];
        ans -= 1ll * maxx * (pre[las[pos] - 1] - pre[r]);
        cout<<ans<<endl;
    }
}