JZTXT

牛客练习赛110

发布时间 2023-04-22 19:48:12作者: 星陨光逝

A.嘤嘤的签到

双指针+算贡献

用cnt[]来记录当前维护区间1和4的数量，当当前区间不满足要求则移动左指针直到满足要求，再加上贡献即可。

当然也可以记录最后的1和4的位置，这样他们位置中较小的那一个的后一个位置就是能满足要求的区间的最左端的左指针，

但是该方法就没上一个那么通用了。

B.嘤嘤的猫娘

贪心：按价格从大到小排列即可，数量随意。

C.嘤嘤的风车

注意圆心与半径，同时注意对称性。

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'
typedef long long LL;
typedef pair<int,int> PII;
const int INF=0x3f3f3f3f;

int o,r;//圆心,半径

void dfs(int n,vector<string>&g){
    if(!n)return;
    r=2<<n;
    if(n&1){
        for(int i=-r/2;i<=0;i++)
            g[o+i-r/2][o+i+r/2]=g[o-i+r/2][o-i-r/2]=g[o+i][o-i-r]=g[o-i][o+i+r]='*';
    }else{
        for(int i=-r/2;i<=0;i++)
            g[o+i-r/2][o-i-r/2]=g[o-i+r/2][o+i+r/2]=g[o+i][o+i+r]=g[o-i][o-i-r]='*';
    }
    dfs(n-1,g);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    o=r=2<<n;
    vector<string>g(o*2+1,string(o*2+1,' '));
    for(int i=-r;i<=r;i++)g[o+i][o]=g[o][o+i]='*';
    for(int i=-r/2;i<=r/2;i++)g[o+i][o+i]=g[o+i][o-i]='*';
    dfs(n,g);
    for(auto s:g){
        cout<<s<<endl;
    }
    return 0;
}

D.