错题集锦
ButterflyDew · · 个人记录
- P1854 花店橱窗布置
错误原因：dp数组初值没有赋值为-inf
- P1098 字符串的展开
错误原因：读题
以下具体分析一波
题目描述
如果在输入的字符串中，含有类似于“d-h”或者“4-8”的字串，我们就把它当作一种简写，输出时，用连续递增的字母或数字串替代其中的减号，即，将上面两个子串分别输出为“defgh”和“45678”。在本题中，具体约定如下：
(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，①出现了减号“-”，②减号两侧同为小写字母或同为数字，且按照ASCII码的顺序，③减号右边的字符严格大于左边的字符。
(2) 参数p1：展开方式。p1=1时，对于字母子串，填充小写字母；p1=2时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。p1=3时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号“*”来填充。
(3) 参数p2：填充字符的重复个数。p2=k表示同一个字符要连续填充k个。例如，当p2=3时，子串“d-h”应扩展为“deeefffgggh”。减号两边的字符不变。
(4) 参数p3：是否改为逆序：p3=1表示维持原来顺序，p3=2表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当p1=1、p2=2、p3=2时，子串“d-h”应扩展为“dggffeeh”。
(5) 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：“d-e”应输出为“de”，“3-4”应输出为“34”。如果减号右边的字符按照ASCII码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：“d-d”应输出为“d-d”，“3-1”应输出为“3-1”。
输入输出格式
输入格式：
第1行为用空格隔开的3个正整数，依次表示参数p1，p2，p3。
第2行为一行字符串，仅由数字、小写字母和减号“-”组成。行首和行末均无空格。
输出格式：
展开后的字符串。
具体错因：
- 条件1的第2小点没注意
- 条件2的数字不能转大写
结论：麻烦下次做模拟题划重点！！！
- P1064 金明的预算方案
错误原因：把背包拆开做了，也就是有依赖的背包思想错了
- P1065 作业调度方案
是模拟，kepi（copy）一下题面
题目描述
我们现在要利用m台机器加工n个工件，每个工件都有m道工序，每道工序都在不同的指定的机器上完成。每个工件的每道工序都有指定的加工时间。
每个工件的每个工序称为一个操作，我们用记号j-k表示一个操作，其中j为1到n中的某个数字，为工件号；k为1到m中的某个数字，为工序号，例如2-4表示第2个工件第4道工序的这个操作。在本题中，我们还给定对于各操作的一个安排顺序。
例如，当n=3，m=2时，“1-1，1-2，2-1，3-1，3-2，2-2”就是一个给定的安排顺序，即先安排第1个工件的第1个工序，再安排第1个工件的第2个工序，然后再安排第2个工件的第1个工序，等等。
一方面，每个操作的安排都要满足以下的两个约束条件。
(1) 对同一个工件，每道工序必须在它前面的工序完成后才能开始；
(2) 同一时刻每一台机器至多只能加工一个工件。
另一方面，在安排后面的操作时，不能改动前面已安排的操作的工作状态。
由于同一工件都是按工序的顺序安排的，因此，只按原顺序给出工件号，仍可得到同样的安排顺序，于是，在输入数据中，我们将这个安排顺序简写为“1 1 2 3 3 2”。
还要注意，“安排顺序”只要求按照给定的顺序安排每个操作。不一定是各机器上的实际操作顺序。在具体实施时，有可能排在后面的某个操作比前面的某个操作先完成。
例如，取n=3,m=2，已知数据如下：
工件号 机器号/加工时间
工序1 工序2
1 1/3 2/2
2 1/2 2/5
3 2/2 1/4
则对于安排顺序“1 1 2 3 3 2”，下图中的两个实施方案都是正确的。但所需要的总时间分别是10与12。
当一个操作插入到某台机器的某个空档时（机器上最后的尚未安排操作的部分也可以看作一个空档），可以靠前插入，也可以靠后或居中插入。为了使问题简单一些，我们约定：在保证约束条件（1）（2）的条件下，尽量靠前插入。并且，我们还约定，如果有多个空档可以插入，就在保证约束条件（1）（2）的条件下，插入到最前面的一个空档。于是，在这些约定下，上例中的方案一是正确的，而方案二是不正确的。
显然，在这些约定下，对于给定的安排顺序，符合该安排顺序的实施方案是唯一的，请你计算出该方案完成全部任务所需的总时间。
输入输出格式
输入格式：
输入的第1行为两个正整数，用一个空格隔开：
m n （其中m（<20）表示机器数，n（<20）表示工件数）
第2行：个用空格隔开的数，为给定的安排顺序。
接下来的2n行，每行都是用空格隔开的m个正整数，每个数不超过20。
其中前n行依次表示每个工件的每个工序所使用的机器号，第1个数为第1个工序的机器号，第2个数为第2个工序机器号，等等。
后n行依次表示每个工件的每个工序的加工时间。
可以保证，以上各数据都是正确的，不必检验。
输出格式：
输出只有一个正整数，为最少的加工时间。
具体错因： ①:在输入中第二行因为人家没写几个就先入为主的按照样例的两个机器读入了2*n个数
②:这点要很注意，拿出我的70分代码
code：
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N=23;
int n,m;
int ms[N][N*N];//第k个机器的时间i是否空余
int pas[N*N];//安排顺序
int item[N][N][2];//第i个工件第j个工序的所用机器号和用时
int i_now[N];//第i个工件处理到第几个了
int i_en[N];//第i个工件前一个工序的结束时间
int main()
{
int t=0;
cin>>m>>n;
memset(ms,0,sizeof(ms));
for(int i=1;i<=n;i++)
{
i_now[i]=1;
i_en[i]=1;
}
for(int i=1;i<=m*n;i++)
scanf("%d",&pas[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&item[i][j][0]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
scanf("%d",&item[i][j][1]);
t+=item[i][j][1];
}
for(int i=1;i<=m*n;i++)
{
int k=i_now[pas[i]]++;
int mm=item[pas[i]][k][0],tt=item[pas[i]][k][1];
int ii=i_en[pas[i]],s=0,tem;
while(s<tt)
{
s=0;
while(ms[mm][ii]) ii++;
s=ii;
tem=ii;
while(!ms[mm][ii]&&ii-s<=tt) ii++;
s=ii-s;
}
for(int j=tem;j<tem+tt;j++)
ms[mm][j]=1;
i_en[pas[i]]=tem+tt;
}
int ans=0;
for(int i=1;i<=m;i++)
for(int j=1;j<=t;j++)
if(ms[i][j])
ans=max(ans,j);
cout<<ans<<endl;
return 0;
}
注意到我的最后找答案的时候，时间枚举到了T，但这样是有可能爆掉ms数组的。
注意上界的选择合理性
- P2318 虚拟内存
卡了我很久，具体拿题目说吧
题目描述
操作系统中一种重要的存储管理技术就是虚拟内存技术。操作系统中允许进程同时运行，也就是并行。每个进程都有其相对独立的数据块（进程运行的过程中将对其进行读写操作）。理想的情况下，这些数据块都应该存放在内存中，这样才能实现高效的读写操作。但事实上，内存的容量有限，每个进程只能把一部分数据放在内存中，为了解决这个矛盾，提出了虚拟内存技术。
虚拟内存技术的基本原理是：对进程而言，内存空间是无限大的，进程可以随意地读写数据，而对操作系统内部而言，利用外存来模拟扩充的内存空间，进程要求访问某个内存单元时，交由操作系统处理，操作系统首先在内存中查找该单元是否存在，如果存在，查找成功，否则转入外存查找（一定存在于外存中）。
就存储介质的物理性质而言，内存的访问速度相对于外存要快得多，因此对于每个进程来说操作系统应该把那些访问次数较多的数据存放在内存中，而把那些访问次数很少的数据放在外存中。如何选择内存中暂留的数据是一个很值得研究的问题，下面介绍一个内存管理中比较常用的算法：
内存中的数据以页为基本存储单位，进程的读写操作都针对页来进行。实际内存空间被分割成n页，虚拟内存空间的页数往往要多得多。某一时刻，进程需要访问虚存编号为P的页，该算法的执行步骤如下：
a. 首先在内存中查找，如果该页位于内存中，查找成功，转d，否则继续下面的操作；
b. 寻找内存中是否存在空页（即没有装载任何数据页的页面），若有，则从外存中读入要查找页，并将该页送至内存中的空页进行存储，然后转d，否则继续下面的操作；
c. 在内存中寻找一个访问次数最少的页面（如果存在多个页面的访问次数同时为最少，则选取最早读入数据进入内存的那个页面），从外存中读入要查找页，替换该页。
d. 结束
所谓访问次数是指从当前页面进入内存到该时刻被访问的次数，如果该页面以前进入过内存并被其它页面替换，那么前面的访问次数不应计入这个时刻的访问次数中。
你的任务是设计一个程序实现上述算法。
测试数据将会提供m条读写内存的命令，每条命题提供要求访问的虚拟内存页的编号P。你的程序要求能够模拟整个m条命令的全部执行过程，所有的命令是按照输入的先后执行的，最开始的时候内存中的n页全为空。
输入输出格式
输入格式：
从文件input.txt中读入数据，文件第1行为n<10000和m<1000000，分别表示内存页数和读写内存命令条数。接下来有m行，其中第i+1行有一个正整数Pi<=10^9，表示第i条读写内存命令需要访问的虚拟内存页的编号。
输出格式：
输出文件output.txt中仅包含一个正整数，表示在整个模拟过程中，在内存中直接查找成功的次数（即上面的算法只执行步骤a的次数）。
分析一波题目。
- 很显然要hash一波，让内存和虚拟内存互指
- 查找最小值（这里找0和最小值是一样的）用数据结构维护一波
我用了map和线段树
来看看30分代码
#include <cstdio>
#include <map>
#define mid (l+r>>1)
#define mid0 (L+R>>1)
#define L t[id].l
#define R t[id].r
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=10010;
const int inf=0x3f3f3f3f;
int n,m;
int i[N];//实际内存
map <int,int > si;//虚拟内存对实际内存的映射
int a[N];//实际内存存的值
int read()
{
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x;
}
int min(int n1,int n2) {return n1<n2?n1:n2;}
struct node
{
int l,r,w,t;
node(){}
node(int l,int r)
{
this->l=l;
this->r=r;
this->w=0;
this->t=inf;
}
}t[N*4];
void build(int id,int l,int r)
{
node tt(l,r);
t[id]=tt;
if(l==r)
return;
build(ls,l,mid);
build(rs,mid+1,r);
}
void change(int id,int p)
{
if(L==R)
{
t[id].w++;
return;
}
if(p<=mid0)
change(ls,p);
else
change(rs,p);
t[id].w=min(t[ls].w,t[rs].w);
}
int query(int id,int tt)
{
if(L==R)
{
t[id].w=1;
t[id].t=tt;
si[a[L]]=0;
return L;
}
int kk;
if(t[ls].w<t[rs].w)
kk=query(ls,tt);
else if(t[ls].w>t[rs].w)
kk=query(rs,tt);
else
{
if(t[ls].t<t[rs].r)
kk=query(ls,tt);
else
kk=query(rs,tt);
}
t[id].w=min(t[ls].w,t[rs].w);
t[id].t=min(t[ls].t,t[rs].t);
return kk;
}
int ans=0;
void m_sear(int q,int tt)
{
if(si[q])
{
ans++;
change(1,si[q]);
return;
}
int p=query(1,tt);//最小节点位置顺带修改为1
si[q]=p;
a[p]=q;
}
int main()
{
n=read(),m=read();
build(1,1,n);
int p;
for(int i=1;i<=m;i++)
{
p=read();
m_sear(p,i);
}
printf("%d\n",ans);
return 0;
}
错在哪？
注意到访问次数和进入时间作为第一和第二关键字，是不能分开的
这里我们可以写键值对，然而我太蒻了，并不会
AC代码
#include <cstdio>
#include <map>
#define mid (l+r>>1)
#define mid0 (L+R>>1)
#define L t[id].l
#define R t[id].r
#define ls id<<1
#define rs id<<1|1
using namespace std;
const int N=10010;
const int inf=0x3f3f3f3f;
int n,m;
int i[N];//实际内存
map <int,int > si;//虚拟内存对实际内存的映射
int a[N];//实际内存存的值
int read()
{
int x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
return x;
}
struct node
{
int l,r,w,t;
node(){}
node(int l,int r)
{
this->l=l;
this->r=r;
this->w=0;
this->t=inf;
}
}t[N*4];
node min(node n1,node n2)
{
if(n1.w==n2.w)
return n1.t<n2.t?n1:n2;
return n1.w<n2.w?n1:n2;
}
void build(int id,int l,int r)
{
node tt(l,r);
t[id]=tt;
if(l==r)
return;
build(ls,l,mid);
build(rs,mid+1,r);
}
void change(int id,int p)
{
if(L==R)
{
t[id].w++;
return;
}
if(p<=mid0)
change(ls,p);
else
change(rs,p);
int ll=L,rr=R;
t[id]=min(t[ls],t[rs]);
t[id].l=ll,t[id].r=rr;
}
int query(int id,int tt)
{
if(L==R)
{
t[id].w=1;
t[id].t=tt;
si[a[L]]=0;
return L;
}
int kk;
if(t[ls].w<t[rs].w)
kk=query(ls,tt);
else if(t[ls].w>t[rs].w)
kk=query(rs,tt);
else
{
if(t[ls].t<t[rs].t)
kk=query(ls,tt);
else
kk=query(rs,tt);
}
int ll=L,rr=R;
t[id]=min(t[ls],t[rs]);
t[id].l=ll,t[id].r=rr;
return kk;
}
int ans=0;
void m_sear(int q,int tt)
{
if(si[q])
{
ans++;
change(1,si[q]);
return;
}
int p=query(1,tt);//最小节点位置顺带修改为1
si[q]=p;
a[p]=q;
}
int main()
{
n=read(),m=read();
build(1,1,n);
int p;
for(int i=1;i<=m;i++)
{
p=read();
m_sear(p,i);
}
printf("%d\n",ans);
return 0;
}
总结：关键字的不可分割性