3-19网易有道C++笔试部分题解

第一题 n个数，均分给m个人，是否有方案可行

第二题表达式求职

第三题a * b = c * d 所有方案

第四题 矩阵乘法幂次加和

表达题汉子错误检索

第一题数据很小，直接暴力dfs就行。 n个数，均分给m个人，是否有方案可行

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;
const int maxx = 1e5 + 7;
ll a[maxx];
ll nowNum[20];
bool flag = 0;
ll ans = 0;
void dfs(int index){
    if(flag) return ;
    if(index == n + 1){
        for(int i = 1; i <=m ;i++){
            if(nowNum[i] != ans) return ;
        }
        flag = 1;
    }
    for(int i = 1; i <=m ;i++){
        if(nowNum[i] > ans) return ;
    }
    for(int i = 1; i <=m ;i++){
        nowNum[i] += a[index];
        dfs(index + 1);
        nowNum[i] -= a[index];
    }
}
int main(){
    cin >> n >> m;
    
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        ans += a[i];
    }
    
    if(ans % m != 0) 
        flag = 0;
    ans /= m;
    dfs(1);
    if(!flag)
        printf("False\n");
    else 
        printf("True\n");
    return 0;
}
表达式求职
有括号是真的烦，而且不知道他数据是怎样的，一只过75% ，改成long long 也是 ，这题也没注意啥规范编程，
自己模拟俩栈，总是就是写的很难受，而且咱也不知道他除0会怎么样，题目好像也没说


#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;
const int maxx = 1e5 + 7;
char a[maxx], b[maxx], c[maxx];
ll d[maxx];
stack<char>mid;
stack<char>ope;

int flag = 0;
ll getNum(ll a,ll b,char c){
    if(c=='+') return a+b;
    if(c=='-') return a-b;
    if(c=='*') return a*b;
    if(c=='/') {
        if(b == 0 ) {
            return 0;
            flag = 1;
        }
        
        
        return a/b;
        
    }
    return 0;
}
void solve(){
    int l=0,k=0,flag=0;
    for(int i = 0; a[i]; i++){
        if(a[i] >= '0' && a[i] <= '9'){
            b[k++] = a[i];
            if(a[i + 1] <'0' || a[i + 1] > '9'){
                b[k++] = '#';
            }
        }
        else if(a[i] == ')'){
            while(c[--l] != '('){
                b[k++] = c[l];
            }
        }
        else {
            if(l > 0){
                if(a[i] == '+' || a[i] == '-'){
                    while(c[l - 1] != '('  && l > 0   )
                        b[k++] = c[--l];
                }
                else {
                    if(c[i - 1] == '*' || c[i - 1] == '/'){
                        b[k++] = c[--l];
                    }
                }
            }
            c[l++] = a[i];
        }
    }
    while( l > 0){
        b[k++] = c[--l];
    }
    b[k] = '\0';
}

int f(){
    ll numc = 0,l = 0;
    for(int i=0;b[i];i++){
        if(b[i] >= '0' && b[i] <= '9'){
            numc = numc * 10 +(b[i]-'0');
        }
        else if(b[i]=='#'){
            d[l++] = numc;
            numc=0;
        }
        else {
            d[l-2] = getNum(d[l-2], d[l-1], b[i]);
            l--;
        }
    }
    return d[0];
}
int main(){
    
    cin >> a;
    if(a[0] == '-'){
        n = strlen(a);
        //a[n+1]='/0';
        for(int i = n;i>= 1;i--)
            a[i] = a[i-1];
        a[0]='0';
    }
    //cout<<a<<endl;
    solve();
    ll p =f();
    if(flag) {
        printf("0\n");
    }
    else 
    printf("%lld\n",p);
           
    return 0;
}
// 求a*b = c*d  11 <= a,b,c <=99 , 111 <= d <= 999
1 - 9出现一次，输出所有解  ，记录每个树出现的次数，直接暴力就完事了a^3 * 10
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;
const int maxx = 1e5 + 7;

#define rep(i, j, n) for(ll i = j; i<= n; i++)
ll vis[16];
void change(ll x){
    while(x){
        vis[x % 10]++;
        x /= 10;
    }
}
int main(){
    rep(i, 11, 99)
        rep(j, i, 99)
            rep(k, 11, 99){
        ll num = i * j;
        memset(vis, 0, sizeof(vis));
        
        if(num % k == 0){
            ll p = num / k;
            change(i) ; change(j) ; change(k) ; change(p);
            
            if(p >= 111){
                int flag = 0;
                if(vis[0] >= 1) flag = 1;
                rep(x,1,9){
                    if(vis[x] >= 2) flag = 1;
                    //printf("%lld ",vis[x]);
                }    
                if(!flag){
                    printf("%lld x %lld = %lld x %lld\n",i,j,k,p);
                }
            }
        }
    }
    return 0;
}

求矩阵1，2，3，到k的幂次和，我一看这不直接矩阵快速蜜吗，我一看是求和，而且 n = 10，k = 1e6 算下来复杂度到1e9了，可能又啥优化的？
算了先写了个暴力，然后就过了***网易就喜欢玩这个哈


#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m;
const int maxx = 1e5 + 7;

#define rep(i, j, n) for(ll i = j; i<= n; i++)
ll a[16][16];
ll ans[16][16];
ll b[11][11];
ll c[11][11];
ll k;
int main(){
    cin >> n >> k >> m;
    rep(i, 1, n)
        rep(j, 1, n){
        cin >> a[i][j];
        a[i][j] %= m;
        ans[i][j] = a[i][j] % m;
        b[i][j] = a[i][j] % m;
    }
    rep(x, 1, k-1){
        memset(c,0,sizeof(c));
        rep(i, 1, n){
            rep(j, 1, n){
                rep(k, 1, n){
                    c[i][j] += a[i][k] * b[k][j];
                }
            }
        }   
        rep(i, 1, n)
            rep(j, 1, n) {
            b[i][j] = c[i][j] % m;
            ans[i][j] = (ans[i][j] + b[i][j]) % m;
        }
        
    }
    rep(i, 1, n){
        rep(j, 1, n){
            printf("%lld ",ans[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}