牛客练习赛51 A-E

深藏阁楼爱情的钟 2024-04-18 13:01 64阅读 0赞

### 目录 ###

*  \[A - abc\](https://ac.nowcoder.com/acm/contest/1083/A)
 *  \[B - 子串查询\](https://ac.nowcoder.com/acm/contest/1083/B)
 *  \[C - 勾股定理\](https://ac.nowcoder.com/acm/contest/1083/C)
 *  \[D - 羊吃草\](https://ac.nowcoder.com/acm/contest/1083/D)
 *  \[E - 数列\](https://ac.nowcoder.com/acm/contest/1083/E)

# [A - abc][] #

水

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 1e5+7;
    
    int a[MAXN],c[MAXN];
    char s[MAXN];
    int main() {
        
            scanf("%s",s);
            int len = strlen(s);
            memset(a,0,sizeof(a));
            memset(c,0,sizeof(c));
            ll ans = 0;
    
            for(int i=0;i<len;++i)
                    if(s[i]=='a')   a[i] = a[i-1]+1;
                    else            a[i] = a[i-1];
            for(int i=len-1;i>0;--i)
                    if(s[i]=='c')   c[i] = c[i+1]+1;
                    else            c[i] = c[i+1];
            for(int i=0;i<len;++i)
                    if(s[i]=='b')
                            ans += (ll)a[i]*c[i];
            printf("%lld\n",ans);
            return 0;
    }

# [B - 子串查询][B -] #

主要是学习了一下string 中 find 的用法  
字符串，暴力

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 1e5+7;
    
    
    int main() {
        
            int n,q;
            string s;
            cin>>n>>q>>s;
            while(q--) {
        
                    string a;
                    cin>>a;
                    int pos = 0, flag = 1;
                    for(int i=0;i<a.length();++i) {
        
                            int it = s.find(a[i],pos);//从串s的pos位置开始往后找
                            if(it == s.npos) {
        //没找到就返回npos
                                    flag = 0;
                                    break;
                            }
                            else    pos = it + 1;
                    }
                    if(flag)        cout<<"YES"<<endl;
                    else            cout<<"NO"<<endl;
            }
            return 0;
    }

# [C - 勾股定理][C -] #

数学题

根据[维基百科][Link 1]我们可以知道  
找寻勾股数的小技巧：  
若需要一组最小数为奇数的勾股数，可任意选取一个 3 或以上的奇数，将该数自乘为平方数，除以 2，答案加减 0.5 可得到两个新的数字，这两个数字连同一开始选取的奇数，三者必定形成一组勾股数。但却不一定是以这个选取数字为起首勾股数的唯一可能，例如 ( 27 , 364 , 365 ) \{\\displaystyle (27,364,365)\} (27,364,365)并非是以 27 为起首的唯一勾股数，因为存在另一个勾股数是 ( 27 , 36 , 45 ) \{\\displaystyle (27,36,45)\} (27,36,45)，同样也以 27 为首  
对于任何大于1的整数 x , x 2 + 1 、 x 2 − 1 与 2 x x,x^2+1、x^2-1与2x x,x2\+1、x2−1与2x，三个数必为勾股数

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    
    int main() {
        
            ll n;
            cin>>n;
            if(n<=2)        cout<<-1<<endl;
            else if(n&1) {
        
                    n>>=1;
                    cout<<2*n*n+2*n<<" "<<2*n*n+2*n+1<<endl;
            }
            else {
        
                    n>>=1;
                    cout<<n*n-1<<" "<<n*n+1<<endl;
            }
            return 0;
    }

# [D - 羊吃草][D -] #

这个是贪心写出来的(因为数据范围比较小)

正解应该是二分图匹配

//贪心
    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 1e3+7;
    struct line{
        
            int l,r;
    }L[MAXN];
    bool cmp(line x,line y){
        
            if(x.r==y.r)    return x.l<y.l;
            return x.r<y.r;
    }
    bool vis[MAXN];
    
    int main() {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ios::sync_with_stdio(0);
            int n,q;
            cin>>n>>q;
            for(int i=0;i<n;++i)    cin>>L[i].l;
            for(int i=0;i<n;++i)    cin>>L[i].r;
    
            sort(L,L+n,cmp);
    
            while(q--) {
        
                    memset(vis,0,sizeof(vis));
                    int ans = 0;
                    int l,r;
                    cin>>l>>r;
                    for(int i=0;i<n;++i) {
        
                            for(int j=L[i].l;j<=L[i].r;++j) {
        
                                    if(!vis[j] && j>=l && j<=r) {
        
                                            vis[j] = 1;
                                            ans ++;
                                            break;
                                    }
                            }
                    }
                    cout<<ans<<endl;
            }
            return 0;
    }

# [E - 数列][E -] #

[这里][Link 2]

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int MAXN = 1e5+7;
    
    
    int main() {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            ios::sync_with_stdio(0);
            int n,m;
            cin>>n>>m;
            m -= n;//每一位都填1
            for(int i=1;i<=n;++i) {
        
                    int T = (n-i)/i; //最大的元素
                    int P = (n-i)%i; //
                    int S = P*(T+1)*(T+2)/2 + (i-P)*(T+1)*T/2;
                    if(S <= m) {
        
                            for(int j=1;j<=P;++j)
                                    for(int k=1;k<=T+2;++k)
                                            cout<<k<<" ";
                            for(int j=1;j<=i-P;++j)
                                    for(int k=1;k<=T+1;++k)
                                            cout<<k<<" ";
                            cout<<endl;
                            break;
                    }
            }
            return 0;
    }

[A - abc]: https://ac.nowcoder.com/acm/contest/1083/A
[B -]: https://ac.nowcoder.com/acm/contest/1083/B
[C -]: https://ac.nowcoder.com/acm/contest/1083/C
[Link 1]: https://zh.wikipedia.org/wiki/%E5%8B%BE%E8%82%A1%E6%95%B0
[D -]: https://ac.nowcoder.com/acm/contest/1083/D
[E -]: https://ac.nowcoder.com/acm/contest/1083/E
[Link 2]: https://blog.csdn.net/ssl_zyc/article/details/100589586