【2019-总结】初中毕业暑假集训No.3

目录

前言

考题解析

一、Imena

题目

分析

代码

二、Pohlepko

题目

         分析

错误的DP代码

AC代码

三、Kronican

题目

分析

代码

四、Kvalitetni

题目

题目大意

分析

代码

---

前言

新的一周，新一场考试...
考试的时候（自信满满）以为自己两百多分，测下来不到一百/果然自己太年轻
总之很伤心QAQ...
睡一觉，明天又是一条好汉（女汉子）

考题解析

一、Imena

题目

Sample Input 1
1
Spavas li Mirno del Potro Juan martine?
Sample Output 1
4

Sample Input 2
2
An4 voli Milovana. Ana nabra par Banana.
Sample Output 2
1
2

分析

1.扫描出每个句子
2.在每个句子中找到“名字”：
（1）首字母大写
（2）除首、尾字母外，其他字符为小写字母
（3）尾字母可以为小写字母或标点符号（’.’’,’’?’’!’）
Ps.考试的时候没有考虑“一个大写字母也为名字”，丢了40分

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=1000;
char a[MAXN+5];
int n,tot,len,ans;
int main()
{//freopen("imena.in","r",stdin);//freopen("imena.out","w",stdout);scanf("%d",&n);while(tot<n){scanf("%s",a+1);len=strlen(a+1);bool flag=true;if(!('A'<=a[1]&&a[1]<='Z'))//首字母非大写字母 flag=false;for(int i=2;i<=len-1;i++)if(!('a'<=a[i]&&a[i]<='z'))flag=false;if(len>1&&!(('a'<=a[len]&&a[len]<='z')||(a[len]=='.'||a[len]==','||a[len]=='!'||a[len]=='?')))flag=false;if(flag)ans++;if(a[len]=='.'||a[len]==','||a[len]=='!'||a[len]=='?'){tot++;printf("%d\n",ans);ans=0;}}return 0;
}

二、Pohlepko

题目

Sample Input 1

4 5

ponoc

ohoho

hlepo

mirko

Sample Output 1

pohlepko

Sample Input 2

4 5

bbbbb

bbbbb

bbabb

bbbbb

Sample Output 2

bbbbabbb

Sample Input 3

2 5

qwert

yuiop

Sample Output 3

qweiop

分析

考试时自己想的DP，dp[ i ][ j ]表示从（1,1）走到（i,j）字典序最小的字符串的各字符asc码之和

即dp[ i ][ j ]=min( dp[ i ][ j-1 ] , dp[ i-1 ][ j ] ) + a[ i ][ j ] - 'a'

测评的时候,,,因为代码开了long long ,暴空间了... ...

改成int后只对了两三个点（好多点都是答案错误+运行时错误，错得五颜六色233），才反应过来这个解法是错误的（真是一波三折OTZ）

在各大佬的“友好”帮助下，找到了反例

所以DP存asc码之和的方法是不可行的...

---

接下来说正解：略改良的BFS

在最原始的BFS的过程中，每次往右或往下走，若果两个方向的字符大小不同，就存下较小的那个字符，

如果两个方向的字符大小相同，则需两个都存下来继续走

而这个BFS有点不一样的就是，它在每一层的搜索中不是取出的一个点（q.front()）

而是取出所有该层的点，把这些点的下一步都遍历一边

就如图中一层层浅蓝色的直线，BFS是一层一层地向外扩展的，第i层中的点就是字符串第i位的字符

假如，已搜索到了图中紫色点的一层，那么前面保留下来的路径（或者说答案）（橙色的线）一定都是相同的（都是字典序最小）

取出所有紫色点，它们的下一步是红色的点，分别有'c''a''b''a'，其中'a'最小，于是字符串ans的新一位就是'a'

最后再遍历一遍红点，把两个点'a'( == ans[ 新一位 ] )加入队列，其他点不加（相当于删除某些不优的路径）继续搜索即可

错误的DP代码

（贴一下，这个思路万一以后用得到咧）

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=2000;
char a[MAXN+5][MAXN+5],ans[MAXN+5];
int n,m,cnt;
struct node
{int lx,ly,num;
}dp[MAXN+5][MAXN+5];
int main()
{//freopen("pohlepko.in","r",stdin);//freopen("pohlepko.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",a[i]+1);dp[1][1].lx=dp[1][1].ly=0;dp[1][1].num=a[1][1]-'a';//a:0~z:25for(int j=2;j<=m;j++){dp[1][j].num=dp[1][j-1].num+a[1][j]-'a';dp[1][j].lx=1;dp[1][j].ly=j-1;}for(int i=2;i<=n;i++){dp[i][1].num=dp[i-1][1].num+a[i][1]-'a';dp[i][1].lx=i-1;dp[i][1].ly=1;}for(int i=2;i<=n;i++){for(int j=2;j<=m;j++){if(dp[i-1][j].num<dp[i][j-1].num){dp[i][j].num=dp[i-1][j].num+a[i][j]-'a';dp[i][j].lx=i-1;dp[i][j].ly=j;}else{dp[i][j].num=dp[i][j-1].num+a[i][j]-'a';dp[i][j].lx=i;dp[i][j].ly=j-1;}}}int x=n,y=m,temp;cnt=n+m-1;while(x!=0&&y!=0){ans[cnt]=a[x][y];cnt--;temp=x;x=dp[temp][y].lx;y=dp[temp][y].ly;}for(int i=1;i<=n+m-1;i++)printf("%c",ans[i]);return 0;
}

AC代码

#include<cstdio>
#include<queue>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN=2000;
char a[MAXN+5][MAXN+5],ans[2*MAXN+5];
bool vis[MAXN+5][MAXN+5];
int n,m;
struct node
{int x,y;
}b[MAXN+5];
int dir[2][2]={{1,0},{0,1}};
queue<node> Q;
void BFS()
{Q.push((node){1,1});ans[1]=a[1][1];while(!Q.empty()){int len=0;while(!Q.empty())b[++len]=Q.front(),Q.pop();for(int i=1;i<=len;i++)for(int t=0;t<=1;t++){int x=b[i].x+dir[t][0],y=b[i].y+dir[t][1];if(x>n||y>m) continue;if(ans[x+y-1]=='\0')ans[x+y-1]=a[x][y];elseans[x+y-1]=min(ans[x+y-1],a[x][y]);			}for(int i=1;i<=len;i++)for(int t=0;t<=1;t++){int x=b[i].x+dir[t][0],y=b[i].y+dir[t][1];if(x>n||y>m) continue;if(ans[x+y-1]==a[x][y]&&!vis[x][y]){Q.push((node){x,y});vis[x][y]=1;}}}
}
int main()
{//freopen("pohlepko.in","r",stdin);//freopen("pohlepko.out","w",stdout);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)scanf("%s",a[i]+1);BFS();printf("%s\n",ans+1);return 0;
}

三、Kronican

题目

Sample Input 1

3 3

0 1 1

1 0 1

1 1 0

Sample Output 1

0

Sample Input 2

3 2

0 1 1

1 0 1

1 1 0

Sample Output 2

1

Sample Input 3

5 2

0 5 4 3 2

7 0 4 4 4

3 3 0 1 2

4 3 1 0 5

4 5 5 5 0

Sample Output 3

5

分析

考试时脑子还可以，反正想到了要用DP来做...

但是因为自己没系统学习，所以DP只知道“瞎搞”qwq...

以下是自己考试时的辛酸历程：

思路一：dp[ i ][ j ]表示前i个杯子倒 j 次水的最小花费 ×

pass原因：倒 j 次水不能保证倒完后有 j 个空杯——>有可能水倒进空杯里了

思路二：dp[ i ][ j ]表示前i个杯子有 j 个空杯的最小花费 ×

pass原因：不好转移啊...要记录之前每个杯子是否有水的状态...不好弄...

思路三：既然要记录之前每个杯子是否有水的状态，那我就搜索呗，还能回溯 ×

就这样码代码度过了大半个考试...最后运行不起...一看时间不够了，就交了个“printf("%d\n",n)”上去23333...

（本来每个过程都有代码的，不小心电脑重启了，全没了，唉╮(╯▽╰)╭）

---

正解时间到！同志们，当你看到：

会有什么想法？（“哇怎么会有这么小的数据范围~好~良~心~”）——>不要高兴太早啦，想不到正解就别想拿分吧（本人的惨痛经历）2333...

厉害的大佬脑海中会立马出现四个字：状压DP

其实想到DP应该是很容易的（自己这种小菜都能想到），结合数据范围（1<=k<=n<=20）和题目的特性（有水没水两种状态）就能想到状压DP（想不到就多刷题感受感受吧）

状压DP确定后的思路：

（1）用二进制表示n杯水的有无水状态（0：没水，1：有水），再保存成一个十进制整数S

（2）DP定义式：dp[ S ]表示把水倒成S这个状态的最小花费

（3）DP转移方程式：dp[ S ]=min( dp[ S ] , dp[ S+(1<<(i-1)) ] + c[ i ][ j ] )

（4）边界：dp[ (1<<n) - 1 ]=0 ——>所有杯子都有水，不用倒水，不产生花费

Ps.(1)同桌说这道题要用读入优化...不然会卡常，很迷...

      (2)同桌还说要用“register”...不然不能AC，非常迷...

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 20
#define ll long long
#define INF 0x3f3f3f3f
int n,k,c[MAXN+5][MAXN+5];
int f[(1<<MAXN)+5];
int read()
{int f=1,x=0;char c=getchar();while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=x*10+c-'0',c=getchar();return f*x;
}
int Cnt(int s)
{int ret=0;while(s)ret++,s-=(s&-s);return ret;
}
int main()
{//freopen("kronican.in","r",stdin);//freopen("kronican.out","w",stdout);scanf("%d%d",&n,&k);for(register int i=1;i<=n;i++)for(register int j=1;j<=n;j++)c[i][j]=read();memset(f,0x3f,sizeof(f));f[(1<<n)-1]=0;for(register int S=(1<<n)-1;S>=1;S--)for(register int i=1;i<=n;i++)if(!((1<<(i-1))&S))//若第i位没有水 for(register int j=1;j<=n;j++)if((1<<(j-1))&S)//若第j位有水f[S]=min(f[S],f[S+(1<<(i-1))]+c[i][j]);int ans=INF;for(register int S=(1<<n)-1;S>=1;S--)if(Cnt(S)==k)ans=min(ans,f[S]);cout<<ans;					return 0;
}

四、Kvalitetni

题目

Sample Input 1

2

10 6

((?)+(?))

Sample Output 1

6.00000

Sample Input 2

3

2 5 3

(((?)+(?))*(?))

Sample Output 2

6.00000

Sample Input 3

3

2 10 6

((?)*(?)*(?))

Sample Output 3

8.000000000

题目大意

（这道题的题意太难懂了...好多大佬的博客又没写解释，自己东问西问才搞懂QAQ...所以这里必须解释清楚题意）

1.所有形似"(?)"的表达式的最大值为Z1（暴眼们要看清是Z1不是Zi...）

2.若在表达式(()+()+()+......)或者(()*()*()*()*......)中有k项,

则这个表达式里所有数的总和的最大值为Zk

3.表达式只有全是'+'或者全是'*'（不用处理加和乘计算的先后问题了）

再拿样例二来说吧

（1）Z1=2，于是三个单独的“(?)”的最大值为2

（2）k=2时，先看"(?)+(?)"，把它看作整体，两个？的和的最大为Z2=5；再看((?)+(?))*(?)，"(?)+(?)"与(?)分别是两个式子，三个？的和的最大值也为Z2=5

（3）当"(?)+(?)"=3，“(?)”=2时，ans最大值为2*3=6

分析

首先，特别鸣谢：https://blog.csdn.net/CQBZLYTina/article/details/94486145

类似的“括号题”以前自己也做过，运用“栈”加入和弹出括号，这道题也类似

其实这样的方式类似于“函数递归”（基础不好的我特地去研究了一下递归、递推和迭代的区别...）

（1）有三类表达式：

(A)——>单独的一个
(A1+A2+…+Ak) ——>连加
(A1∗A2∗…∗Ak) ——>连乘

（2）A.第一种表达式的值直接等于Z1（最大值）

第二种和第三种表达式在递归时，先让每个数等于它的最大值，在考虑限制问题

B.第二种、连加的表达式

表达式中的k个数之和不超过Zk，所以这一表达式的和的最大值为min(Zk,A1+A2+...+Ak)

C.第三种、连乘的表达式

表达式中k个数的和的最大值仍为min(Zk,A1+A2+...+Ak)

现在要解决——已知k个数的和，且为定值，求k个数乘积最大值

通过“均值不等式”可得：当k个数相等（=sum/k 平均值）时，乘积最大（这个证明emm...单独研究吧...）

所以每个数的目标值为它们的平均值：sum/k

接下来分两种情况：

a.Ai<sum/k：小于目标值就尽可能地接近目标值--->取自身的最大值(就是它自己，因为递归时已找到了其最大值) 

b.Ai>=sum/k：令其直接等于目标值

但是要注意：

Ai确定之后，剩下没确定的数要再取一次目标值（平均值）

（呼，这题终于讲完了）

代码

#include<cstdio>
#include<vector>
#include<stack>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN=1000000,N=50;
double z[N+5];
char s[MAXN+5];
int k,len,p=1;
double Cal()
{if(s[p++]!='(')//不再有质量表达式了 return 0;vector<double> v;//当前这个区间包含的数 bool f;//f=0:+,f=1:*char now;while(now=s[p++]){if(now=='(')p--,v.push_back(Cal());//递归到下一个区间 if(now=='?')//只此一个数，先让它最大，后面再考虑限制 v.push_back(z[1]);if(now=='+')f=0;if(now=='*')f=1;if(now==')')//走过一个完整的区间 {if(!f)//加法：取区间限制的最大值与区间总和的min值 {double tot1=0,tot2=0;tot1=z[v.size()];for(int i=v.size()-1;i>=0;i--)tot2+=v[i];return min(tot1,tot2);}else//乘法： {int ret=1;sort(v.begin(),v.end());double sum=z[v.size()];//限制的最大的和for(int i=0;i<v.size();i++)//遍历区间中每个数 {double tmp=sum/(v.size()-i);if(z[i]<tmp)//小于目标值就尽可能地接近目标值--->取自身的最大值(就是它自己，因为递归时已找到了其最大值) sum-=z[i],ret*=z[i];elsesum-=z[i],ret*=tmp;}return 	ret;}}}
}
int main()
{//freopen("kvalitetni.in","r",stdin);//freopen("kvalitetni.out","w",stdout);scanf("%d",&k);for(int i=1;i<=k;i++)scanf("%lf",&z[i]);scanf("%s",s+1);len=strlen(s+1);double ans=Cal();printf("%.6f\n",ans);return 0;
}