牛客練習試合51 A-E

目次

[A - abc](https://ac.nowcoder.com/acm/contest/1083/A)

[B-サブストリングクエリ](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
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
",ans);
        return 0;
}

B-サブストリングクエリ
主にstringのfindの使い方文字列、暴力を学びました

#include
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-勾股定理
数学の問題
ウィキペディアによると、最も小数が奇数の勾股数のセットが必要な場合は、3以上の奇数を任意に選択し、その数を平方数に乗算して2で割ると、答えを0.5加算すると2つの新しい数字が得られ、この2つの数字は最初に選択した奇数とともに、3つは必ず勾股数のセットを形成します.しかし、必ずしもこの選択された数字を先頭にした株数の唯一の可能性ではない.例えば、(27,364,365){displaystyle(27364365)}(27364365)は27を先頭にした唯一の株数ではない.もう一つの株数は(27,36,45){displaystyle(27,36,45)}(27,36,45)}(27,45)であり、同様に27を先頭に1より大きい整数xに対してx 2+1,x 2−1と2 x,x^2+1,x^2−1と2 x,x+2+1,x 2−1と2 xの3つの数は必ず勾配数である

#include
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-羊が草を食べる
これは欲張って書いたものです(データ範囲が小さいので)
正解は二分図マッチングであるべきである

//  
#include
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-数列
ここ

#include
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;
}