不等式是否满足约束并输出最大差/单词接龙(E卷-hw_od)

1. 不等式是否满足约束并输出最大差

题目描述

给定一组不等式，判断是否成立并输出不等式的最大差(输出浮点数的整数部分)

要求:

1. 不等式系数为 double类型，是一个二维数组

2. 不等式的变量为 int类型，是一维数组;

3. 不等式的目标值为 double类型，是一维数组

不等式约束为字符串数组，只能是:“>”,“>=”,“<”,“<=”,“=”，

例如，不等式组:

 a11x1 + a12x2 + a13x3 + a14x4 + a15x5 <= b1; 
 a21x1 + a22x2 + a23x3 + a24x4 + a25x5 <= b2; 
 a31x1 + a32x2 + a33x3 + a34x4 + a35x5 <= b3; 

最大差 = max{(a11x1+a12x2+a13x3+a14x4+a15x5-b1),(a21x1+a22x2+a23x3+a24x4+ a25x5-b2),(a31x1+a32x2+a33x3+a34x4+a35x5-b3)},

类型为整数(输出浮点数的整数部分)

输入描述

a11,a12,a13,a14,a15,a21,a22,a23,a24,a25, a31,a32,a33,a34,a35,x1,x2,x3,x4,x5,b1,b2,b3,<=,<=,<=

• 不等式组系数(double类型):

a11,a12,a13,a14,a15

a21,a22,a23,a24,a25

a31,a32,a33,a34,a35

• 不等式变量(int类型):x1,x2,x3,x4,x5

• 不等式目标值(double类型):b1,b2,b3

• 不等式约束(字符串类型):<=,<=,<=

输出描述

true或者 false，最大差

示例1

输入:

2.3,3,5.6,7,6;11,3,8.6,25,1;0.3,9,5.3,66,7.8;1,3,2,7,5;340,670,80.6;<=,<=,<=

 输出:

false 458

示例2

输入:

2.36,3,6,7.1,6;1,30,8.6,2.5,21;0.3,69,5.3,6.6,7.8;1,13,2,17,5;340,67,300.6;<=,>=,<=

输出:

false 758 

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
int main() {
    string str;
    getline(cin,str);
    replace(str.begin(),str.end(),',',' ');
    replace(str.begin(),str.end(),';',' ');
    stringstream ss(str);
    vector<vector<double>> a; vector<int> x; vector<double> b;
    vector<string> symbol(3);
    a.resize(3,vector<double>(5,0));
    x.resize(5,0); b.resize(3,0); 
    for(int i=0;i<3;i++){
        for(int j=0;j<5;j++){
            ss>>a[i][j];
        } 
    } 
    for(int i=0;i<5;i++){
        ss>>x[i];
    }
    for(int i=0;i<3;i++){
        ss>>b[i];
    }
    for(int i=0;i<3;i++){
        ss>>symbol[i];
    }
    double maxDiff=-1e9;
    bool flag=true;
    for(int i=0;i<3;i++){
        double leftVal=0;
        for(int j=0;j<5;j++){
            leftVal+=a[i][j]*x[j];
        }
        double diff=leftVal-b[i];
        if(symbol[i]=="<="&&leftVal>b[i]) flag=false;
        if(symbol[i]=="<"&&leftVal>=b[i]) flag=false;
        if(symbol[i]==">="&&leftVal<b[i]) flag=false;
        if(symbol[i]==">"&&leftVal<=b[i]) flag=false;
        if(symbol[i]=="="&&abs(leftVal-b[i])>1e-9) flag=false;
        maxDiff=max(maxDiff,diff);
    }
    if(flag){
        cout<<"true"<<" "<<(int)maxDiff<<endl;
    }else{
        cout<<"false"<<" "<<(int)maxDiff<<endl;
    }
    return 0;
}

思路：根据题意进行模拟(自我感觉,这种题难的地方是输入输出,也可能是我力扣刷多了) 

2. 单词接龙

题目描述

单词接龙的规则是：

• 可用于接龙的单词首字母必须要前一个单词的尾字母相同；

• 当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词；已经参与接龙的单词不能重复使用。

现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，

请输出最长的单词串，单词串是单词拼接而成，中间没有空格。

输入描述

输入的第一行为一个非负整数，表示起始单词在数组中的索引K，0 <= K < N ；

输入的第二行为一个非负整数，表示单词的个数N；

接下来的N行，分别表示单词数组中的单词。

备注：

• 单词个数N的取值范围为[1, 20]；
• 单个单词的长度的取值范围为[1, 30]；

输出描述

输出一个字符串，表示最终拼接的单词串。

示例1

输入:

0
6
word
dd
da
dc
dword
d

 输入:

worddwordda

说明:

先确定起始单词word，再接以d开头的且长度最长的单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出worddwordda。

示例2

输入：

4
6
word
dd
da
dc
dword
d

输出:

dwordda

说明: 

先确定起始单词dword，剩余以d开头且长度最长的有dd、da、dc，则取字典序最小的da，所以最后输出dwordda。

#include<bits/stdc++.h>
using namespace std;
string maxLenStr;
vector<bool> visited;
void solve(string& curStr,vector<string>& words,int N){
    char lastStr=curStr.back(); string bestNext=""; int bestIndex=-1;
    for(int i=0;i<N;i++){
        if(!visited[i]&&words[i][0]==lastStr){
            if(words[i].size()>bestNext.size()||(words[i].size()==bestNext.size()&&(words[i]<bestNext))){
                bestNext=words[i];
                bestIndex=i;
            }
        }
    }
    if(bestIndex!=-1){
        visited[bestIndex]=true;
        curStr+=bestNext;
        solve(curStr,words,N);
        visited[bestIndex]=false;
    }else{
        maxLenStr=max(maxLenStr,curStr);
    }
}
int main() {
    int K; cin>>K;
    int N; cin>>N;
    vector<string> words(N);
    for(auto& it:words){
        cin>>it;
    }
    maxLenStr="";
    visited.resize(N,false);
    maxLenStr+=words[K];
    visited[K]=true;
    solve(words[K],words,N);
    cout<<maxLenStr<<endl;
    return 0;
}

思路：回溯同时去维护一个maxLenStr