好未來2018筆試研發卷

1.拆分字元串

#include<iostream>
#include<string>
using namespace std;
int count(string str){
int size = 0;
int count = 0;
for (int i = 0; i < str.size(); i++){
if (int(str[i]) % 3 == 0 || size >= 2){
count++; size = 0;
}
else{
if (size == 0)
size++;
else{
if ((int(str[i]) + int(str[i - 1])) % 3 == 0){
count++;
size = 0;
}
else
size++;
}
}
}
return count;
}
int main(){
string str;
cin >> str;
cout << count(str);
cin.get();
cin.get();
return 0;
}
           

2.x+y=x|y

作者：雨_
連結：https://www.nowcoder.com/discuss/100235
來源：牛客網

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
pair<int, int> get_zero(int num)
{
    int count = 0;
    int count_1 = 0;
    while(num)
    {
        if( (num & 1) == 0)
        {
            ++ count;
        }
        num >>= 1;
        ++count_1;
    }
    return {count, count_1};
}
 
 
int main() {
    // input
    int t;
    cin >> t;
    cin.get();
 
    vector<vector<int> > data(t, vector<int>(2));
     
    // 
    int x = 0;
    int k = 0;
    int y = 1;
     
    for (int i = 0; i < t; ++i)
    {
        cin >> x >> k;
        cin.get();
        data[i] = {x, k};
    }
 
 
    for (int _t = 0; _t < t; ++_t)
    {
        x = data[_t][0];
        k = data[_t][1];
        auto counts = get_zero(x);
        int zeros   = counts.first;
        int ones    = counts.second;
 
        int temp   = pow(2, zeros);
        int cycle  = k / temp;
        int offset = k % temp;
 
        int _k = 0;
        y = 0;
        while(_k != offset)
        {
            ++y;
            if((x + y) == (x | y))
            {
                ++_k;
            }
        }
 
        y = y + cycle * pow(2, ones);
        cout << y << endl;
 
    }
 
    return 0;
}
           

作者：泫
連結：https://www.nowcoder.com/discuss/100031?type=2&order=0&pos=7&page=1
來源：牛客網

#include <bits/stdc++.h>
 
using namespace std;
#define ll long long
 
int main() {
    //freopen("../in.txt", "r", stdin);
    ll t,x,k,ans,i,j,a,lenX,lenK,lenA;
    int posX[160],posK[160],posA[160];
    cin>>t;
    while (t--){
        memset(posX,0, sizeof(posX));
        cin>>x>>k;
        i=0,ans=0;
        while (x>0){
            posX[i++]=x&1;
            x=x>>1;
        }
        lenX=i;
 
        i=0;
        while (k>0){
            posK[i++]=k&1;
            k=k>>1;
        }
        lenK=i;
 
        for(i=0,j=0,a=0;j<lenK;i++){
            if(posX[i]==0)
                posA[a++]=posK[j++];
            else
                posA[a++]=0;
        }
        lenA=a;
        for(i=lenA-1;i>=0;i--){
            ans=ans<<1;
            ans=ans|posA[i];
        }
        cout<<ans<<endl;
    }
}
           

3.排列組合

作者：雨_
連結：https://www.nowcoder.com/discuss/100235
來源：牛客網

#include <vector>
#include <algorithm>
#include <iostream>
 
using namespace std;
 
void dfs(vector<int>& b, int idx, vector<int> temp, vector<string>& res)
{
    if (idx == b.size())
    {
        string r;
        for (auto e : temp) r += to_string(e);
        res.push_back(r);
        return;
    }
 
    if (b[idx] == 0)
    {
        dfs(b, idx + 1, temp, res);
    }
 
    temp.push_back(idx);
    dfs(b, idx+1, temp, res);
}
 
int main()
{
    int temp;
    vector<int> v;
    while (cin >> temp) v.push_back(temp);
    vector<string> res;
 
    dfs(v, 0, vector<int>(), res);
    sort(res.begin(), res.end());
    for (const auto &e : res) cout << e << endl;
}
           

4.擲骰子

#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
    int n,m;
    cin>>n>>m;
    int sum=0;
    int num=0;
    for(int i=0;i<n;i++)
    {
        cin>>num;
        sum+=num;
    }
    if(sum==0)
        cout<<0.00<<endl;
    else
    {
        double res=sum*1.0/(n-m);
        printf("%.2f\n",res);
    }
    return 0;
}
           

5.求最大的升序子列和，動态規劃！

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int Sum(vector<int>&number)
{
    int n=number.size();
    vector<int>dp(n,-1);
    dp[0]=number[0];
    for(int i=1;i<n;i++)
    {
        dp[i]=number[i];
        for(int j=i-1;j>=0;j--)
        {
            if(number[i]>number[j])
                dp[i]=max(dp[j]+number[i],dp[i]);
        }
    }
    auto it=max_element(dp.begin(),dp.end());
    return *it;
}
int main()
{
    int a;
    vector<int>num;
    while(cin>>a)
    {
        num.push_back(a);
    }
    int res=Sum(num);
    cout<<res<<endl;
    system("pause");
    return 0;
}
           

6.字元串替換

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
int main()
{
    string str,global,local;
    while(getline(cin,str))
    {
        cin>>global;
        cin>>local;
        string out;
        while(str.find(global)!=string::npos)
        {
            out+=str.substr(0,str.find(global));
            out+=local;
            str=str.substr(str.find(global)+global.length());
        }
        out+=str;
        cout<<out;
    }
    return 0;
}