暑期模拟赛九 解题报告

T1:瞬间移动

　　有一天，暮光闪闪突然对如何将一个整数序列a1,a2,...,an排序为一个不下降序列起了兴趣。身为一只年轻独角兽的她，只能进行一种叫做“单元转换”（unit shift）的操作。换句话说，她可以将序列的最后一个元素移动到它的起始位置：

$$a1,a2,...,an→an,a1,a2,...,an−1$$
　　请帮助暮光闪闪计算一下：她对这个序列进行排序所需的最小操作次数是多少？

测试数据：

算法分析:

• 这里提供两种算法当然还有更多
  

  • （大多数同学）：
    对于能够变成不下降序列的序列一定满足这样的特性：
    

    1. 有两段不下降序列组成（第二段可为空串）
       

    2. 第二段的末尾元素<=第一段的首元素

  
  　　　若都符合则答案为第二串长度。

  • (缺根筋的本人)：
    对于能够变成不下降序列的序列一定满足这样的特性：
    1 . 将这样的序列连成环，在最大的序列后一位开始遍历环，必是一段不下降序列。 答案就是$（总长度）n-（最大数的位置）max_id$

【AC代码】

#include<bits/stdc++.h>
using namespace std;
int a[100010],s[100010],n[100010];
int main() {
    int n,t=-1,mi=0;
    scanf("%d",&n);
    for(int i=0; i<n; i++) {
        scanf("%d",&a[i]);
        if(a[i]>=t) {
            t=a[i];
            mi=i;
        }
        s[i]=a[i];
    }
    int t1=1;
    sort(s,s+n);
    for(int i=1,j=mi+2; i<n; i++,j++) {
        if(j<n)
            if(s[i]!=a[j]) {
                t1=-1;
                break;
            } else if(s[i]!=a[j%n]) {
                t1=-1;
                break;
            }
    }
    if(t1==-1 ) cout<<-1;
    else cout<<n-mi-1;
    return 0;
}

T2:食物订购

　　新年快到了，乐乐开了一家著名的餐厅，名叫“巧克力餐厅。
这个餐厅可提供n种菜，其中第i种菜的单价为ci，共制作了ai份。从餐厅订单上显示，今天会有m个客户将一个接一个光临餐厅,第j个客户将购买第ti种食物dj份，并且第j+1个客户只有在第j个客户购买以后才会到来。如果餐厅无法满足这个人对第ti种菜的需求的话，那他就会买目前还有的价格最低的菜来满足他的需求，最低的菜买好后还不够他会继续买目前最低的菜，直到满足他的需求。（提示：如果所有菜都卖完了，但还是不能满足他的需求，那么就直接输出0，因为餐厅不能满足这个人的需要求，客户会愤怒地离开，无论之前提供多少菜肴，这个客户都不会买单，吃霸王餐）。如果餐厅能满足这个人的需求，就输出这个人的总消费数。
　　总之每个人必须先买他想要的那种菜，数量不够时再买价格最低的，直到买到他所需的数量为止，当然将所有菜都买完也不能满足他的需求，则输出0。你的任务是计算每个人的总消费数。

测试数据：

算法分析：
巨大的模拟题，注意每个变量所表示的含义，不要混乱。

【AC代码】

#include<bits/stdc++.h>
using namespace std;
long long n,m,cnt;//cnt 总共还有多少菜
struct forever {
    long long c,num,nxt,id;//c价格，num数量，nxt下一个最小的菜，id 序号
} a[100010];
bool cmp1(forever x,forever y) {
    return x.c<y.c;
}
bool cmp2(forever x,forever y) {
    return x.id<y.id;
}
int main() {
    scanf("%lld%lld",&n,&m);
    for(int i=1; i<=n; i++) {
        scanf("%lld",&a[i].num);
        a[i].id=i;
        a[i].nxt=1e9;
        cnt+=a[i].num;
    }
    for(int i=1; i<=n; i++) {
        scanf("%lld",&a[i].c);
    }
    sort(a+1,a+1+n,cmp1);
    for(int i=1; i<n; i++) {
        a[i].nxt=a[i+1].id;
    }
    int p=a[1].id;
    sort(a+1,a+1+n,cmp2);
    while(m--) {
        long long iid,inum,ans=0;
        scanf("%lld%lld",&iid,&inum);
        if(cnt<inum) {
            cnt=0;
            printf("0\n");
            continue;
        }
        cnt-=inum;
        if(a[iid].num>=inum) {
            a[iid].num-=inum;
            ans=a[iid].c*inum;
        } else {
            ans+=a[iid].num*a[iid].c;
            inum-=a[iid].num;
            a[iid].num=0;
            while(a[p].num<inum) {
                inum-=a[p].num;
                ans+=a[p].c*a[p].num;
                a[p].num=0;
                p=a[p].nxt;
            }
            ans+=inum*a[p].c;
            a[p].num-=inum;
        }
        printf("%lld\n",ans);
        while(p!=1e9 &&a[p].num==0)p=a[p].nxt;
    }
    return 0;
}

T3:马蹄印

　　 虽然当奶牛贝里斯找到平衡序列后很高兴了，但是他现在对序列提出了一个更高的要求，就是要求每个序列中必须是先一定数量的左括号然后是与左括号相同数量的右括号。例如：（（（（）））），就是一个完美的平衡序列。
　　当贝里斯某天在农场上走的时候，他在地上发现了马蹄印，这个农场是一个N*N的方格，每个小方格中都有一个马蹄印。贝里斯希望从方格的最左上角的地方开始出发，然后每次可以向上或者向下或者向左或者向右移动一步，使得他走过的每个小方格中的马蹄印能够组成一个完美的平衡序列。当然了，贝里斯不能重复经过任何小方格。
　　请帮助贝里斯在这个N*N的方格中找出长度最长的完美序列的长度。

测试数据:

【算法分析】
dfs，当然略显奇葩的本人也有不同的做法；

1.（一般做法）
dfs 参数中记录，前一个状态是左括号或右括号,跑完地图；
2.（本人奇葩做法）
跑两个dfs；第一个走通所有的与原点连通的左括号；第二个在所有的左括号节点向四面查找右括号的路径，当这条路径上的左扩号与右括号数相同时记录答案；

以上做法都注意要记录路径+回溯

【AC代码】

#include<bits/stdc++.h>
using namespace std;
int ans=0;
int n;
char c[6][6];
bool fg1[6][6],fg2[6][6];//fg1记录左，fg2记录右
void  fa(int l,int x,int y,int r) {
    if(r==l) {
        ans=max(ans,2*r);
        return ;
    }
    //蒟蒻本体，对于滚动数组来处理路径不是很熟练，于是复制粘贴贴4份解决。emm
    if(x+1<=n &&fg2[x+1][y]==0 &&c[x+1][y]==')') {
        fg2[x+1][y]=1;
        fa(l,x+1,y,r+1);
        fg2[x+1][y]=0;
    }
    if(y+1<=n &&fg2[x][y+1]==0 &&c[x][y+1]==')') {
        fg2[x][y+1]=1;
        fa(l,x,y+1,r+1);
        fg2[x][y+1]=0;
    }
    if(y-1>=1 &&fg2[x][y-1]==0 &&c[x][y-1]==')') {
        fg2[x][y-1]=1;
        fa(l,x,y-1,r+1);
        fg2[x][y-1]=0;
    }
    if(x-1>=1 &&fg2[x-1][y]==0 &&c[x-1][y]==')') {
        fg2[x-1][y]=1;
        fa(l,x-1,y,r+1);
        fg2[x-1][y]=0;
    }
    return;
}
void  dfs(int l,int x,int y) {
    if(x+1<=n &&fg1[x+1][y]==0) {
        if(c[x+1][y]=='(') {
            fg1[x+1][y]=1;
            dfs(l+1,x+1,y);
            fg1[x+1][y]=0;
        } else {
            fg2[x+1][y]=1;
            fa(l,x+1,y,1);
            fg2[x+1][y]=0;
        }
    }
    if(y+1<=n &&fg1[x][y+1]==0) {
        if(c[x][y+1]=='(') {
            fg1[x][y+1]=1;
            dfs(l+1,x,y+1);
            fg1[x][y+1]=0;
        } else {
            fg2[x][y+1]=1;
            fa(l,x,y+1,1);
            fg2[x][y+1]=0;
        }
    }
    if(y-1>=1 &&fg1[x][y-1]==0) {
        if(c[x][y-1]=='(') {
            fg1[x][y-1]=1;
            dfs(l+1,x,y-1);
            fg1[x][y-1]=0;
        } else {
            fg2[x][y-1]=1;
            fa(l,x,y-1,1);
            fg2[x][y-1]=0;
        }
    }
    if(x-1>=1 &&fg1[x-1][y]==0) {
        if(c[x-1][y]=='(') {
            fg1[x-1][y]=1;
            dfs(l+1,x-1,y);
            fg1[x-1][y]=0;
        } else {
            fg2[x-1][y]=1;
            fa(l,x-1,y,1);
            fg2[x-1][y]=0;
        }
    }
    return ;
}
int main() {
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            cin>>c[i][j];
    fg1[1][1]=true;
    if(c[1][1]==')') {//特判处理第一步就是右括号的情况，这样不能形成（平衡序列）
        cout<<0;
        return 0;
    }
    dfs(1,1,1);//(,),x,y;
    cout<<ans;
}

T4:景观美化

　　农夫约翰最近决定来美化他的花园，他需要运输很多的泥土。花园是由N块花圃组成的。第i块花圃初始的时候有Ai数量的泥土。为了达到美化的目的，必须使得第i块花圃的泥土数量Ai变成Bi。
　　约翰有三个选择：第一，他可以买一个单位的泥土放进任意花圃中，代价是X；第二，他可以将一个单位的泥土从某一个花圃中除去，代价是Y；第三，他可以将第i块花圃中的一个单位的泥土搬运到第j块花圃中，代价是Z*|i-j|。
　　请帮助约翰计算为了达到目的最小需要花费的代价。

测试数据:

算法分析:
对于这样的输入数据难以线性处理；
于是将各式进行转化：
原始（序列a）： 1 2 3 4 ----> 1 2 2 3 3 3 4 4 4 4
目标（序列b）： 4 3 2 0 ----> 1 1 1 1 2 2 2 3 3
这样这个题目就变成要求将 a变成b的最小代价；
也就能将它转化为多个子问题求最优解。
即 将a的第1~i位变为b的第1~j位的最小代价；
故本题为DP；
动态转移方程：

$$f[i][j]= \begin{Bmatrix} f[i][j-1]+x <--填土，现在填充一块后与目标相同\\ f[i-1][j]+y <--挖土，现在挖掉一块后与目标相同\\ f[i-1][j-1]+z*abs(a[i]-b[j])<---移土 \\ \end{Bmatrix}$$

【AC代码】

#include<bits/stdc++.h>
using namespace std;
int a[1010],b[1010],n,x,y,z;
int f[1010][1010];
int main() {
    scanf("%d %d %d %d",&n,&x,&y,&z);
    int t1,t2,tot1=0,tot2=0;
    for(int i=1; i<=n; i++) {
        scanf("%d %d",&t1,&t2);
        while(t1--) a[++tot1]=i;
        while(t2--) b[++tot2]=i; //格式转换
    }
    //预处理
    for(int i=0; i<=tot1; i++)
        f[i][0]=y*i;   //每一块都挖走
    for(int i=0; i<=tot2; i++)
        f[0][i]=x*i;    //每一块都买土
    //begin
    for(int i=1; i<=tot1; i++)
        for(int j=1; j<=tot2; j++)
            f[i][j]=min(f[i-1][j]+y,min(f[i][j-1]+x,f[i-1][j-1]+z*abs(a[i]-b[j])));
    cout<<f[tot1][tot2];
    return 0;
}

end