【纪中受难记】——Day4：失去梦想的咸鱼

世界上没有什么困难能阻挡我前进，除非是调试一个水题调了半个小时……

0/40(60?)/0

---

3403. 数列变换 (Standard IO)

Time Limits: 1000 ms  Memory Limits: 524288 KB  Detailed Limits  

Goto ProblemSet

Description

小X 看到堆成山的数列作业十分头疼，希望聪明的你来帮帮他。考虑数列A=[A1,A2,...,An],定义变换f(A,k)=[A2,A3,,,,.Ak,A1,Ak+2,Ak+3,,,,A2k,Ak+1,...]，也就是把a 分段，每段k 个（最后如果不足k 个，全部分到新的一段里，见样例），然后将每段的第一个移动到该段的最后一个。

现在，小 X想知道 f (f (f (f ([1,2,3,⋯,n],2),3),⋯),n)的结果。

 

Input

输入一行包含一个整数n 。

Output

输出一行包含n 个整数，表示最终的数列。

 

Sample Input

4

Sample Output

4 2 3 1



【样例说明】

f ([1,2,3,4],2) = [2,1,4,3]

f ([2,1,4,3],3) = [1,4,2,3]（3单独被分在一组，移动到组的最后一位，仍然是3）

f ([1,4,2,3],4) = [4,2,3,1]

 

Data Constraint

对于60%的数据，1≤ n ≤10^3。

对于100%的数据，1≤ n ≤10^6。

这道题在听到一位神仙说出解法前，还以为正解是dp……

解法就是将数组不断右移，然后把跳到尾端的移到下一个即将跳到尾端的数字上去。

eg：1 2 3 4 

k=2:1  2  1 4 3

k=3:1  2 1 4 2  3

注意到最后一个区间跳跃的数，它应该预判一下n%k是否等于0，如果整除就不用管（我被坑了好久）。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1e6+10;
int n;
int b[N*2];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        b[i]=i;
    } 
    for(int k=2;k<=n;k++){
        int tail=n-n%k+k-1,re=b[tail];
        for(int i=tail;i>=k-1;i-=k){
            b[i]=b[i-k];
        }
        if(n%k!=0)
        b[n+k-1]=re;
    }
    for(int i=n;i<=2*n-1;i++)
    printf("%d ",b[i]);
    return 0;
}

---

3404. 卡牌游戏 (Standard IO)

Time Limits: 1000 ms  Memory Limits: 524288 KB  Detailed Limits  

Goto ProblemSet

Description

小X 为了展示自己高超的游戏技巧，在某一天兴致勃勃地找小Y 玩起了一种卡牌游戏。每张卡牌有类型（攻击或防御）和力量值两个信息。

小Y 有n 张卡牌，小X 有m 张卡牌。已知小X 的卡牌全是攻击型的。

游戏的每一轮都由小X 进行操作，首先从自己手上选择一张没有使用过的卡牌X。如果小Y 手上没有卡牌，受到的伤害为X 的力量值，否则小X 要从小Y 的手上选择一张卡牌Y。若Y 是攻击型（当X 的力量值不小于Y 的力量值时才可选择），此轮结束后Y 消失，小Y 受到的伤害为X 的力量值与Y 的力量值的差；若Y 是防御型（当X 的力量值大于Y 的力量值时才可选择），此轮结束后Y 消失，小Y 不受到伤害。

小X 可以随时结束自己的操作（卡牌不一定要用完）。希望聪明的你帮助他进行操作，使得小Y 受到的总伤害最大。

 

Input

输入的第一行包含两个整数n 和m 。

接下来n 行每行包含一个字符串和一个整数，分别表示小Y 的一张卡牌的类型（“ATK”表示攻击型，“DEF”表示防御型）和力量值。

接下来m 行每行包含一个整数，表示小X 的一张卡牌的力量值。

Output

输出一行包含一个整数，表示小Y 受到的最大总伤害。

 

Sample Input

输入1：

2 3

ATK 2000

DEF 1700

2500

2500

2500



输入2：

3 4

ATK 10

ATK 100

ATK 1000

1

11

101

1001

 

Sample Output

输出1：

3000

【样例说明1】

第一轮，小X 选择自己的第一张卡牌和小Y 的第二张卡牌，小Y 的第二张卡牌消失。

第二轮，小X 选择自己的第二张卡牌和小Y 的第一张卡牌，小Y 的第一张卡牌消失，同时受到500 点伤害。

第三轮，小X 选择自己的第三张卡牌，此时小Y 手上已经没有卡牌，受到2500 点伤害。

小X 结束游戏，小Y 共受到3000点伤害。



输出2：

992

【样例说明2】

第一轮，小X 选择自己的第三张卡牌和小Y 的第一张卡牌，小Y 的第一张卡牌消失，同时受到91点伤害。

第二轮，小X 选择自己的第四张卡牌和小Y 的第二张卡牌，小Y 的第二张卡牌消失，同时受到901点伤害。

小X 结束游戏，小Y 共受到992点伤害。

 

 

Data Constraint

各规模均有一半数据满足小Y 只有攻击型卡牌。

对于30%的数据，1≤ n,m ≤ 6。

对于60%的数据，1≤ n,m ≤10^3。

对于100%的数据，1≤ n,m ≤10^5，力量值均为不超过10^6的非负整数。

这道题是贪心。

考虑几种情况：

1.只消耗对方攻击牌：

　　我们用最大的攻击牌攻击对方最小的攻击牌，然后拿次大的攻击次小的，证明如下：

　　如果存在一个牌x<对方某一攻击牌y,我方共用牌点为X，对方为Y，则我方得分为X-Y，但是可知x-y<0 所以再攻击也不会得到更多优势，故不去攻击。

2.消耗对方所有牌再造成直接伤害：

    如果消耗所有牌的话，应当先攻击防御牌，用等大或者稍大的牌消掉防御牌再去攻击其他的，假设能消耗所有攻击牌，则得分为：sum[x]-def[x]-atk[y]（sum是我方牌总分数，def是用在攻击防御牌上的总分数，atk是敌方攻击牌总分数）

以上两种情况取最大即可。

不知道为啥只有80分。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N=1e5+10;
ll n,m,ans,maxans;
ll atk[N],dfn[N],ca,cb,vis[N],flag1,flag2;
ll x[N];
int main(){
    freopen("card17.in","r",stdin);
    scanf("%lld%lld",&n,&m);
    char a[10];
    ca=cb=0;
    for(ll i=1,k;i<=n;i++){
        cin>>a;
        scanf("%lld",&k);
        if(a[0]=='A') atk[++ca]=k;
        else dfn[++cb]=k;
    }    
    sort(atk+1,atk+ca+1);
    sort(dfn+1,dfn+cb+1);
    for(ll i=1;i<=m;i++) scanf("%lld",&x[i]);
    sort(x+1,x+m+1);
    ll ans=0;
    ll i,j;
    for(i=1,j=1;i<=ca&&j<=m;){
        while((x[j]<atk[i]&&j<=m)||vis[j]) j++;
        if(j>m) break;
        ans+=x[j]-atk[i];
        vis[j]=1;
        i++;
    }
    if(i>ca) flag1=1;
    for(i=1,j=1;i<=cb&&j<=m;){
        while((x[j]<dfn[i]&&j<=m)||vis[j]) j++;
        if(j>m) break;
        vis[j]=1,i++;
    }
    if(i>cb) flag2=1;
    if(flag1&flag2) for(i=1;i<=m;i++) if(!vis[i]) ans+=x[i];
    maxans=max(ans,maxans);
    memset(vis,0,sizeof(vis));
    flag1=flag2=ans=0;
    for(i=1,j=1;i<=cb&&j<=m;){
        while((x[j]<dfn[i]&&j<=m)||vis[j]) j++;
        if(j>m) break;
        vis[j]=1,i++;
    }
    if(i>cb) flag2=1;
    for(i=1,j=1;i<=ca&&j<=m;){
        while((x[j]<atk[i]&&j<=m)||vis[j]) j++;
        if(j>m) break;
        ans+=x[j]-atk[i];
        vis[j]=1;
        i++;
    }
    if(i>ca) flag1=1;
    if(flag1&flag2) for(i=1;i<=m;i++) if(!vis[i]) ans+=x[i];
    maxans=max(maxans,ans);
    memset(vis,0,sizeof(vis));
    flag1=flag2=ans=0;
    ll pt[N];
    for(ll i=m,j=1;i>=1&&j<=ca;){
        if(x[i]>atk[j]) ans+=x[i]-atk[j],vis[i]=1,i--,j++;
        else break;
    }
    ll t=0;
    for(ll i=1;i<=m;i++) if(vis[i]) t++; 
    if(t==ca) flag1=1;
    for(i=1,j=1;i<=cb&&j<=m;){
        while((x[j]<dfn[i]&&j<=m)||vis[j]) j++;
        if(j>m) break;
        vis[j]=1,i++;
    }
    if(i>cb) flag2=1;
    if(flag1&flag2) for(i=1;i<=m;i++) if(!vis[i]) ans+=x[i];
    maxans=max(maxans,ans);
    printf("%lld",maxans);
    return 0;
}

---

3405. 舞台表演 (Standard IO)

Time Limits: 1000 ms  Memory Limits: 524288 KB  Detailed Limits  

Goto ProblemSet

Description

小X 终于找到了自己的舞台，希望进行一次尽兴的表演。

不妨认为舞台是一个n 行m 列的矩阵，矩阵中的某些方格上堆放了一些装饰物，其他的则是空地。小X 可以在空地上滑动，但不能撞上装饰物或滑出舞台，否则表演就失败了。

小Y 为了让小X 表演得尽量顺畅，提前为小X 写好了每一段时间的移动方向。每个时刻，听话的小X 都会依据小Y 写好的所在时间段的方向（东、西、南、北）向相邻的方格滑动一格。由于小Y 之前没有探查过舞台的情况，如果

小X 直接按照小Y 写好的来移动，很容易表演失败。

不过，小Y 是个天使，拥有让小X 停在原地的魔法，也就是某一时刻，小X 以为自己移动了实际上没有移动。为了让小X 表演得尽量完美，小Y 想使小X 在舞台上滑行的路程尽量长（当然不能中途表演失败）。可惜小Y 的智商不足

以完成这么复杂的计算，希望你来帮助她决定哪些时刻该使用魔法。当然，她关心的首先是最长的路程是多少。

 

Input

输入的第一行包含五个整数n,m, x, y 和k 。(x, y )为小 X的初始位置，k 为时间的段数。

接下来n 行每行包含m 个字符，描述这个舞台（“.”表示该位置是空地，“x”表示该位置有装饰物）。

接下来k 行每行包含三个整数si ti di (1<= i<= k )，表示在时间段[si,ti ] 内，小 X的移动方向是di 。di 为1,2,3,4中的一个，依次表示北、南、西、东（分别对应矩阵中的上、下、左、右）

Output

输出一行包含一个整数，表示小X 滑行的最长路程。

 

Sample Input

4 5 4 1 3

..xx.

.....

...x.

.....

1 3 4

4 5 1

6 7 3

Sample Output

6

 

Data Constraint

保证输入的时间段是连续的，即 s1 =1 ，si=ti-1+1(1<i<=k) ,tk=t。

对于30%的数据，1≤ t ≤ 20。

对于60%的数据，1≤t ≤ 200。

对于100%的数据，1≤ n,m,k ≤ 200，1≤t ≤10^5。

这题调试要了我老命。

读题目，这道题并不难设状态，设f[k][i][j]表示在第k次转弯后停在（i,j）时走的最长步数，

f[k][i][j]=max(f[k-1][x][y]+step)，其中(x,y)表示上次停的位置，枚举这个位置，然后更新方向上的step就可以了。

注意一点，初始状态除了起点以外都为-1。

#include<bits/stdc++.h>
#pragma GCC optimize(3) 
using namespace std;
const int N=210;
const int T=1e5+10;
int n,m,xx,yy,k;
int a[N][N];
int f[N][N][N],ans;
struct Time{
    int s,t,d;
}r[N];
int main(){
    scanf("%d%d%d%d%d",&n,&m,&xx,&yy,&k);
    char q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>q;
            a[i][j]=(q=='.'?0:1);
        }
    }
    int s,t,d;
    int maxt=0;
    for(int i=1;i<=k;i++){
        scanf("%d%d%d",&s,&t,&d);
        r[i]=(Time){s,t,d};
    }
    memset(f,-1,sizeof(f));
    f[0][xx][yy]=0;
    for(int i=1;i<=k;i++){
        for(int x=1;x<=n;x++){
            for(int y=1;y<=m;y++){
                if(f[i-1][x][y]==-1) continue;
                f[i][x][y]=max(f[i][x][y],f[i-1][x][y]);
                if(r[i].d==1){
                    for(int step=1;step<=r[i].t-r[i].s+1;step++){
                        if(a[x-step][y]||x-step<=0) break;
                        f[i][x-step][y]=max(f[i][x-step][y],f[i-1][x][y]+step);
                        if(f[i][x-step][y]>ans) ans=f[i][x-step][y];
                    }
                }
                else if(r[i].d==2){
                    for(int step=1;step<=r[i].t-r[i].s+1;step++){
                        if(a[x+step][y]||x+step>n) break;
                        f[i][x+step][y]=max(f[i][x+step][y],f[i-1][x][y]+step);
                        if(f[i][x+step][y]>ans) ans=f[i][x+step][y];
                    }
                }
                else if(r[i].d==3){
                    for(int step=1;step<=r[i].t-r[i].s+1;step++){
                        if(a[x][y-step]||y-step<=0) break;
                        f[i][x][y-step]=max(f[i][x][y-step],f[i-1][x][y]+step);
                        if(f[i][x][y-step]>ans) ans=f[i][x][y-step];
                    }
                }
                else{
                    for(int step=1;step<=r[i].t-r[i].s+1;step++){
                        if(a[x][y+step]||y+step>m) break;
                        f[i][x][y+step]=max(f[i][x][y+step],f[i-1][x][y]+step);
                        if(f[i][x][y+step]>ans) ans=f[i][x][y+step];
                    }
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}

---

总结：下次要比今天多100分，否则就太菜了。