【NOIP2000普及组T1】计算器的改良
NCL是一家专门从事计算器改良与升级的实验室，最近该实验室收到了某公司所委托的一个任务：需要在该公司某型号的计算器上加上解一元一次方程的功能。实验室将这个任务交给了一个刚进入的新手ZL先生。为了很好的完成这个任务，ZL先生首先研究了一些
一元一次方程的实例：
4+3x=8
6a-5+1=2-2a
-5+12Y=0
ZL先生被主管告之，在计算器上键入的一个一元一次方程中，只包含整数、小写字母及十、一、＝这三个数学符号（当然，符号“一”既可作减号，也可作负号）。方程中并没有括号，也没有除号，方程中的字母表示未知数。
【问题求解】
编写程序，解输入的一元一次方程，将解方程的结果（精确至小数点后三位）输出至屏幕。你可假设对键入的方程的正确性的判断是由另一个程序员在做，或者说可认为键入的一元一次方程均为合法的，且有唯一实数解。
输入文件仅一行，为一个字符串，长度不超过100。
输出文件仅一行，为方程的结果。
感觉这道题算是模拟题，有很多细节需要注意，同时也有技巧，把数字分为常数和系数处理，用两个数来模拟符号和等式左右边
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
string s;
//这道模拟题我只过了两组数据。。。。
//看了题解发现大家的思路都好清晰
//哭哭
/*
int change(string x){
int op=0;
for(int i=0;i<x.length();i++) op=op*10+(x[i]-'0');
return op;
}
int vis[maxn]={0};
*/
int l,r;//l表示系数，r表示常数
char x;//表示字母
void solve(){
char c;
int f1=1,f2=1,temp=0;
//f1表示是不是负数（负数-1，正数1），f2表示在等号左边还是右边，左边1，右边-1
//最后的结果(常数） ：temp*（-f2)*f1，右边的负数时正的，左边的负数时负的，temp存储临时的数据
//系数：f1*f2,系数放在右边，所以右边是负就是负，左边正变负
while(scanf("%c",&c)!=EOF){ //根据输入一个个处理
if(c>='0'&&c<='9'){
temp=temp*10;
temp+=c-'0';
}
else{
if(c>='a'&&c<='z'){
if(temp==0) l+=f2*f1; //系数为1
else l+=temp*f2*f1;
x=c;
}
else r+=temp*(-f2)*f1; //不是系数，就是常数，常数是(-f1)*f2
temp=0;
}
if(c=='+'){
f1=1;continue;
}
else if(c=='-'){
f1=-1;continue; //表示系数的
}
else if(c=='='){
f2=-1;f1=1; //都变，因为=右边第一个如果是正数是不会有符号的，所以要人为地把f1变为1
continue;
}
}
if(temp!=0) r+=temp*(-f2)*f1; //系数最后处理一下
}
int main(){
solve();
printf("%c=%.3lf
",x,1.0*r/l==0? abs(1.0*r/l):1.0*r/l);
//因为会出现-0.0地情况，所以要排除这种情况，因为测评会过不了地
return 0;
/*
cin>>s;
char x;
int j,temp,sumx=0,sumy=0;
bool flag=0;
string op;
s=" "+s;
for(int i=1;i<=s.length();i++){
if(flag==0&&(s[i]>='a'&&s[i]<='z')){
x=s[i];
vis[i]=1;
j=i;
string stemp;
while(s[--j]>='0'&&s[j]<='9'){
stemp+=s[j];
vis[j]=1;
}
temp=change(stemp);vis[j]=1;
if(s[j]=='-') temp=-temp;
sumx+=temp;
}
else if(s[i]=='=') flag=1;
else if(flag==1&&(s[i]>='a'&&s[i]<='z')){
j=i;
vis[i]=1;
string stemp;
while(s[--j]>='0'&&s[j]<='9'){
stemp+=s[j];
vis[j]=1;
}
temp=change(stemp);vis[j]=1;
if(s[j]=='+') temp=-temp;
sumx+=temp;
}
}
flag=0;
for(int i=1;i<=s.length();i++){
if(s[i]=='=') flag=1;
else if(s[i]>='0'&&s[i]<='9'&&vis[i]==0){
j=i;
string stemp;
while(s[j]>='0'&&s[j]<='9'&&vis[j]==0) {
stemp+=s[j];
vis[j]=1;
j++;
}
//cout<<"stre "<<stemp<<endl;
temp=change(stemp);
//cout<<flag<<" "<<temp<<" "<<s[i-1]<<endl;
if(flag==0&&s[i-1]=='-') {
temp=-temp;
// cout<<"zuo"<<temp<<endl;
}
else if(flag==1&&s[i-1]!='-') {
temp=-temp;
//cout<<"you"<<temp<<endl;
}
sumy+=temp;
}
}
//for(int i=1;i<=s.length();i++) cout<<vis[i]<<" ";
//cout<<endl;
sumy=-sumy;
//cout<<"zuo"<<temp<<endl;
//cout<<sumx<<endl<<s<<endl<<-sumy<<endl;
double res=double(sumy)/double(sumx);
printf("%c=%.3lf
",x,res);
*/
return 0;
}
1215 -- 【NOIP2000普及组T2】税收与补贴问题
每样商品的价格越低，其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量（产品不会低于成本销售），并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后，销量以某固定数值递减。（我们假设价格及销售量都是整数）
对于某些特殊商品，不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。（所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币）
问题求解：你是某家咨询公司的项目经理，现在你已经知道政府对某种商品的预期价格，以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额（也为整数），才能使商家在这样一种政府预期的价格上，获取相对其他价位上的最大总利润。
总利润=单位商品利润*销量
单位商品利润=单位商品价格-单位商品成本（-税金 or +补贴）
输入的第一行为政府对某种商品的预期价
第二行有两个整数，第一个整数为商品成本，第二个整数为以成本价销售时的销售量
以下若干行每行都有两个整数，第一个为某价位时的单价，第二个为此时的销量，以一行-1，-1表示所有已知价位及对应的销量输入完毕
输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。
输出有两种情况：若在政府预期价上能得到最大总利润，则输出一个单独的整数，数的正负表示是补贴还是收税，数的大小表示补贴或收税的金额最小值。若有多解，取绝对值最小的输出。
如在政府预期价上不能得到最大总利润，则输出“NO SOLUTION” .
首先先把题目读懂（我好像完全不懂TAT
相当于求一系列不等式的解
要求给定价位的利润最高，显然利润ans=(单价+补贴)*销量，也就是说对于任意价位，它的利润都不能大于给定价位的利润。比如在样例中，对于价位29，
我们需要满足(x+3)*110>=(x+1)*125，对于价位32，需要满足(x+3)*110>=(x+4)*95。所有这样不等式的解集就是答案，取绝对值最小的就是答案。
首先是需要计算所有的能够取到的条件下的价格、销量，然后分别就补贴和收税进行处理，看哪种情况下得到的最大价值对应的价格是政府期待的价格就可以了
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
#include<map>
#include<vector>
#include<set>
using namespace std;
const int maxn=1010;
const int INF=0x3fffffff;
//这道题理解最难
//相当于求一系列不等式的解
//要求给定价位的利润最高，显然利润ans=(单价+补贴)*销量，也就是说对于任意价位，它的利润都不能大于给定价位的利润。比如在样例中，对于价位29，
//我们需要满足(x+3)*110>=(x+1)*125，对于价位32，需要满足(x+3)*110>=(x+4)*95。所有这样不等式的解集就是答案，取绝对值最小的就是答案。
int a[100000][2]; //存放价格对应的销量
int main(){
int expect;
cin>>expect;
int i=1;
while(cin>>a[i][0]>>a[i][1],a[i][0]!=-1&&a[i][1]!=-1){
i++;
if(i>2&&a[i-1][0]-a[i-2][0]>1){ //有中间数据需要处理
i--;
int more=(a[i-1][1]-a[i][1])/(a[i][0]-a[i-1][0]);
int temp=a[i][0]; //价格
for(int j=a[i-1][0]+1;j<=temp;j++){
a[i][0]=j; //价格
a[i][1]=a[i-1][1]-more; //对应的销量
i++;
}
}
}
i--; ///细节
int cha,nowsale=a[i][1],price;
cin>>cha;
//处理剩下的直到销量为0
while(nowsale>0){
if(nowsale-cha<0) break;
else{
nowsale-=cha;
i++;
a[i][0]=a[i-1][0]+1; //价格
a[i][1]=nowsale; //价格对应的销量
}
}
// for(int k=1;k<=i;k++) cout<<a[k][0]<<" "<<a[k][1]<<endl;
int maxx=-INF,p=1;
//对税收或者补贴分别进行遍历，看最大销量是不是预期的
for(int j=1;j<=10000;j++){
maxx=-INF;
for(int k=1;k<=i;k++){ //k是能够取得到的情况数
int num=(a[k][0]-a[1][0]+j)*a[k][1]; //这种价格，这样的补贴，得出的利润
if(num>=maxx){
p=1;
maxx=num;
price=a[k][0]; //记录价格
}
}
if(price==expect){
cout<<p*j<<endl;
return 0;
}
maxx=-INF;
for(int k=1;k<=i;k++){
int num=(a[k][0]-a[1][0]-j)*a[k][1]; //这里是税收
if(num>=maxx){
p=-1;
maxx=num;
price=a[k][0];
}
}
if(price==expect){
cout<<p*j<<endl;
return 0;
}
}
cout<<"NO SOLUTION"<<endl;
return 0;
}
1216 -- 【NOIP2000普及组T3】乘积最大
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友XZ也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目:
设有一个长度N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串: 312，当N=3，K=1时会有以下两种分法：
1）3*12=36
2）31*2=62
这时，符合题目要求的结果是： 31*2=62
现在，请你帮助你的好朋友XZ设计一个程序，求得正确的答案。
就是普通的dp，但是有细节需要注意，比如循环的下标，初始化的处理
首先需要初始化数组a[][]，表示i~j之间能够形成的数字，然后预处理f[i][0]，表示前i个没有乘号的
然后就是循环了，外层是乘号数，中间层是总数量，最里层是可以插入乘号的地方
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m;
long long s; //把字符串转化为数组存储。方便转化
long long f[11][7],a[11][11]; //注意这个也要用Longlong存储
int main(){
cin>>n>>m;
cin>>s;
for(int i=n;i>=1;i--){
a[i][i]=s%10;
s/=10;
}
for(int i=2;i<=n;i++){
for(int j=i-1;j>=1;j--){
a[j][i]=a[j][i-1]*10+a[i][i];
}
}
//以上为处理 a数组的含义
for(int i=1;i<=n;i++) f[i][0]=a[1][i]; //前i位没有乘号，就是本身
//预处理：不加乘号的情况
for(int i=1;i<=m;i++) //这里的循环是针对乘号个数的
for(int j=i+1;j<=n;j++) //可以插入的
for(int k=i;k<j;k++) { //寻找合适的插入位置 ，不能少于乘号数，也不能大于j
f[j][i]=max(f[j][i],f[k][i-1]*a[k+1][j]);
}
cout<<f[n][m]<<endl;
return 0;
}
1217 -- 【NOIP2000普及组T4】单词接龙
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们己知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙" 中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
输入的第一行为一个单独的整数n(n<=20）表示单词数
以下n行每行有一个单词，输入的最后一行为一个单个字符，表来“龙”开头的字母。你可以假定以此字母开头的“龙" 一定存在。
只需输出以此字母开头的最长的“龙”的长度
这道题又是字符串又是DP的，还比较难，主要是细节和思路有点难想
检查重叠部分的最大长度，然后搜索，如果当前遍历到的字符串可以和已有的串有重叠部分的话，那么就可以加入搜索，记得回溯
好题，值得再写
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<queue>
using namespace std;
string str[1000];
int n,vis[1001]={0},length=0;
//检查两个字符串的重叠部分
inline int check(string a,string b){
int p=min(a.length(),b.length());
for(int i=1;a.length()==1? i<=p:i<p;i++){
bool flag=1;//这个位置错了！！
//这个三目运算符看懂，要特判字符串是不是只有一个单词，是的话下面循环会直接退出
//如果不是为1那么为i<p因为从0开始
for(int j=0;j<i;j++){
if(a[a.length()-i+j]!=b[j]){//如果不匹配，注意这个是a.length()-i+j
flag=0;
break;
}
}
if(flag==1) return i; //i是重叠长度
}
return 0;
}
//接下来是搜索过程
void dfs(string s,int length_now){
length=max(length,length_now);//每次搜索都要特判
for(int i=1;i<=n;i++){ //对每个字符串都要判断（暴力搜索）
if(vis[i]>1) continue;//如果使用了两次就退出
else{
int add=check(s,str[i]);//不用纠结上面判断a.length()==0，因为这是个循环，每个字符串都会被判断
if(add!=0){
vis[i]++;
dfs(str[i],length_now+str[i].length()-add);//新的长度为现在长度加字符串长度-重叠长度
vis[i]--;//回溯
}
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>str[i];
cin>>str[n+1];
dfs(str[n+1],1);
cout<<length<<endl;
return 0;
}