【纪中受难记】——C2Day3：坠入深渊

20/0/0/0

无话可说。

---

1207. 遥控车 (Standard IO)

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

Goto ProblemSet

Description

平平带着韵韵来到了游乐园，看到了n辆漂亮的遥控车，每辆车上都有一个唯一的名字name[i]。韵韵早就迫不及待地想玩名字是s的遥控车。可是韵韵毕竟还小，她想象的名字可能是一辆车名字的前缀（也就是说能确定一个i，使s是name[i]的前缀），这时她就能玩第i辆车；或者是一个无中生有的名字，即s不是任何一辆车名字的前缀，这时候她什么也不能玩。
你需要完成下面的任务：
1.韵韵想了m个她想要的名字，请告诉她能玩多少次。
2.由于管理员粗心的操作，导致每辆车的摆放位置都可能出现微小的差错，原来第i辆车现在的位置可能是i-1、i、i+1中的任意一个（第1辆车的位置不可能是0，第n辆车的位置不可能是n+1）。请你计算出共有多少种可能的排列。
注：数据保证当s是name[i]的前缀时，i是唯一确定的。一辆车可以玩多次。

 

Input

第一行是2个正整数n、m。
接下来n行，每行1个字符串name[i]，表示第i辆车的名字。
接下来m行，每行1个字符串s，表示韵韵想要的名字。

Output

第一行输出韵韵能玩的次数。
第二行输出共有多少种可能的排列。

 

Sample Input

4 4
Abcd
DeF
AAa
aBccc
Ab
AA
AbC
aBcc

Sample Output

3
5

 

Data Constraint

 

 

Hint

【数据规模和约定】
对于题目涉及到的字符串严格区分大小写，且长度小于255。
对于20％的数据 n≤10,m≤10；
对于40％的数据 n≤1000，m≤1000；
对于100％的数据 n≤10000，m≤10000。

企图使用trie+暴力匹配，炸了。

正解：直接对字符串排序，二分查找。

下面那个题就是求斐波那契数列，要用高精。

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n,m,ans;
string s[N];
string c;
struct bigint{
    char num[100000];
    int len;
    bigint operator =(const bigint &t){
        strcpy(num,t.num);
        len=t.len;
    }//也许这个没啥卵用……
    bigint operator +(const bigint &t){
        bigint tmp;
        tmp.len=0;
        for(int i=0,g=0;g||i<len||i<t.len;i++){
            int now=g;
            if(i<len) now+=num[i]-'0';
            if(i<t.len) now+=t.num[i]-'0';
            tmp.num[tmp.len++]=now%10+'0';
            g=now/10;
        }
        return tmp;
    }
}fib[4];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) cin>>s[i];
    sort(s+1,s+n+1);
    for(int i=1;i<=m;i++){
        cin>>c;
        int pos=lower_bound(s+1,s+n+1,c)-s;
        bool flag=1;
        for(int j=0;j<c.size();j++){
            if(c[j]!=s[pos][j]){
                flag=0;break;
            }
        }
        ans+=flag;
    }
    printf("%d
",ans);
    fib[0]=(bigint){"1",1};
    fib[1]=(bigint){"1",1};
    for(int i=2;i<=n;i++){
        fib[i%3]=fib[(i-1)%3]+fib[(i-2)%3];
    }
    for(int i=fib[n%3].len-1;i>=0;i--){
        cout<<fib[n%3].num[i];
    }
    return 0;
}

---

1208. 车展 (Standard IO)

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

Goto ProblemSet

Description

遥控车是在是太漂亮了，韵韵的好朋友都想来参观，所以游乐园决定举办m次车展。车库里共有n辆车，从左到右依次编号为1，2，…，n，每辆车都有一个展台。刚开始每个展台都有一个唯一的高度h[i]。主管已经列好一张单子：
L1 R1
L2 R2
…
Lm Rm
单子上的(Li,Ri)表示第i次车展将要展出编号从Li到Ri的车。
为了更加美观，展览时需要调整展台的高度，使参展所有展台的高度相等。展台的高度增加或减少1都需花费1秒时间。由于管理员只有一个人，所以只好对每个展台依次操作。每次展览结束后，展台高度自动恢复到初始高度。
请告诉管理员为了举办所有展览，他最少需要花多少时间将展台调整好。

 

Input

第一行为两个正整数n、m。
第二行共n个非负整数，表示第i辆车展台的高度h[i]。
接下来m行每行2个整数Li、Ri（Li≤Ri）。

Output

一个正整数，调整展台总用时的最小值。

 

Sample Input

6 4
4 1 2 13 0 9
1 5
2 6
3 4
2 2

Sample Output

48

 

Data Constraint

 

 

Hint

【数据规模和约定】
对于50％的数据 n≤500，m≤1000；
对于80％的数据 n≤1000，m≤100000；
对于100％的数据n≤1000，m≤200000;
答案小于2^64。

简单来说就是求区间中位数。

用一个大根堆和一个小根堆搞一下即可。

还是讲一下吧：

就是中位数可以看做从小到大排序好的序列拆成两半中间的那个数字，可以类似的模拟这个过程，前半部分是从小到大的一个大根堆，后半部分是一个从大到小的小根堆，堆顶是最接近中位数的数字。

也可以用主席树(忘了咋写，不写了)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
const ll N=1010;
ll n,m;
ll ans,bsum,ssum; 
ll a[N];
ll mid[N][N];
priority_queue<int,vector<int>,less<int> > big;
priority_queue<int,vector<int>,greater<int> > small;
int main(){
    n=read();m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++){
        while(!big.empty()) big.pop();
        while(!small.empty()) small.pop();
        bsum=ssum=0;
        for(int j=i;j<=n;j++){
            if(big.size()==small.size()){
                big.push(a[j]);
                bsum+=a[j];
            }
            else{
                small.push(a[j]);
                ssum+=a[j];
            }
            if(big.size()&&small.size()){
                int bx=big.top(),sx=small.top();
                if(sx<bx){
                    small.pop();
                    big.pop();
                    small.push(bx);
                    big.push(sx);
                    ssum=ssum-sx+bx;
                    bsum=bsum-bx+sx;
                }
            }
            mid[i][j]=bsum-big.top()*big.size()+big.top()*small.size()-ssum;
        }
    }
    for(int i=1,x,y;i<=m;i++){
        x=read();y=read();
        ans-=mid[x][y];
    }
    printf("%lld",ans);
    return 0;
}

不要问我为什么用负数更新答案。

---

1209. 拉力赛 (Standard IO)

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

Goto ProblemSet

Description

车展结束后，游乐园决定举办一次盛大的山道拉力赛，平平和韵韵自然也要来参加大赛。
赛场上共有n个连通的计时点，n-1条赛道（构成了一棵树）。每个计时点的高度都不相同（父结点的高度必然大于子结点），相邻计时点间由赛道相连。由于马力不够，所以韵韵的遥控车只能从高处驶向低处。而且韵韵的车跑完每条赛道都需花费一定的时间。
举办方共拟举办m个赛段的比赛，每次从第u个计时点到第v个计时点，当然其中有不少比赛韵韵的遥控车是不能参加的（因为要上坡）。平平想知道他能参加多少个赛段的比赛，并且想知道他完成这些赛段的总用时。

 

Input

第一行两个整数n，m。
接下来n-1行每行3个整数a、b、t。
表示韵韵的遥控车可以花t秒从第a个计时点到第b个计时点。
接下来m行每行2个整数u、v，意义如描述所示。

Output

第一行输出一个正整数，表示能参加的赛段数。
第二行输出一个正整数，表示总用时。

 

Sample Input

6 2
1 2 1
2 4 1
2 5 1
5 6 1
1 3 1
2 6
4 5

Sample Output

1
2

 

Data Constraint

 

 

Hint

【数据规模和约定】
第一个计时点的高度是最高的；
u≠v；
对于50％的数据 n≤1000 m≤1000；
对于100％的数据 n≤10000 m≤100000；
答案小于2^64。

倍增。

注意判一下深度啊。

#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=1e4+10;
const int M=1e5+10;
int n,m,cnt;
long long ans1,ans2;
int f[N][25],head[M<<1],dep[N],det[N];
struct edge{
    int to,next,w;
}e[M<<1];
void addedge(int from,int to,int w){
    e[++cnt]=(edge){to,head[from],w};
    head[from]=cnt;
}
void dfs(int u,int fa){
    f[u][0]=fa;
    det[u]=det[fa]+1;
    for(int i=head[u];i;i=e[i].next){
        int v=e[i].to,w=e[i].w;
        if(v==fa) continue;
        dep[v]=dep[u]+w;
        dfs(v,u);
    }
}
int main(){
//    freopen("data2.in","r",stdin);
    n=read();m=read();
    for(int i=1,x,y,z;i<n;i++){
        x=read();y=read();z=read();
        addedge(x,y,z);
        addedge(y,x,z);
    }
    dfs(1,0);
    for(int j=1;j<=20;j++){
        for(int i=1;i<=n;i++){
            f[i][j]=f[f[i][j-1]][j-1];
        }
    }
    for(register int i=1,x_,y_;i<=m;i++){
        x_=read();y_=read();
        int x=x_,y=y_;
        if(det[x]>det[y]) continue;
        int j=20;
        for(int j=20;j>=0;j--){
            if(det[f[y][j]]>=det[x]) y=f[y][j];
        }
        if(x==y){
            ans1++;
            ans2+=dep[y_]-dep[x_];
        }
    }
    printf("%lld
%lld",ans1,ans2);
    return 0;
}

---

1210. 舞台设置 (Standard IO)

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

Goto ProblemSet

Description

游乐园决定在一个n×m的广场上举办一次颁奖晚会，总管要你帮忙搭建一个舞台。
现在给你广场的布置图（规定地图的上方为正北），有些位置需要布置为观众席（记为1），另一些是空地（记为0）。舞台只能在空地上搭建。
为了使晚会更加吸引人，平平觉得舞台应该是朝北的h—金字塔形。h—金字塔形舞台是由h个矩形舞台相接而成的，其中后方的矩形舞台的两端必须超出在其前面的矩形舞台，且最小矩形面对的朝向为舞台的方向。下面给出几个实例:

舞台的面积应该尽量大，输出面积最大的朝北h—金字塔形舞台的面积。

 

Input

第一行3个整数 n、m、h。
接下来n行，每行m个0或1，中间用一个空格隔开。

Output

一个整数，表示最大的朝北的h—金字塔形舞台的面积。
如果没有符合题意的h—金字塔形舞台输出0。

 

Sample Input

4 6 2
0 0 1 0 0 1
0 0 0 0 0 0
0 0 1 0 0 0
0 1 1 0 0 0

Sample Output

10

 

Data Constraint

 

 

Hint

样例对应的最优方案如下图：

×表示观众席
【数据规模和约定】
对于10％的数据 h=1；
对于40％的数据 h≤5；
对于100％的数据 h≤20；
对于100％的数据 n、m≤100。

dp题。

设

f[i][j][l][r]表示第i行，此时放了j个矩形，在区间[l,r]放矩形的最大面积。

g[i][j][l][r]表示第i行，此时放了j个矩形，在区间(l,r)放矩形的最大面积。

转移：

g[i][j][l][r]=max(g[i][j][l+1][r],g[i][j][l][r-1],f[i][j][l+1][r-1])

f[i][j][l][r]=max(f[i-1][j][l][r],g[i-1][j-1][l][r])+r-l+1或0（看这一行l到r是否都为0）.

滚动一下即可AC。

注意枚举顺序。

#include<bits/stdc++.h>
using namespace std;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
const int N=110;
int n,m,h,ans;
bool a[N][N];
int s[N][N];
int f[2][25][N][N],g[2][25][N][N];
int main(){
    n=read();m=read();h=read();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            a[i][j]=read();
            s[i][j]=s[i][j-1]+a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        int p=i%2;
        for(int j=1;j<=h;j++){
            for(int l=m;l>=1;l--){
                for(int r=l;r<=m;r++){
                    if(r-l+1>=3) g[p][j][l][r]=max(g[p][j][l+1][r],max(g[p][j][l][r-1],f[p][j][l+1][r-1]));
                    
                    if((s[i][r]-s[i][l-1]==0)&&(j==1||g[p^1][j-1][l][r]>0)){
                        
                        f[p][j][l][r]=max(f[p^1][j][l][r],g[p^1][j-1][l][r])+r-l+1;
                        if(j==h) ans=max(ans,f[p][j][l][r]);
                        
                    }
                    else f[p][j][l][r]=0;

//                    if(i==1&&j==1&&l==5&&r==5){
//                        cout<<g[p][j][l][r]<<endl;
//                    }
                }
            }
        }
    }
    printf("%d",ans);
    return 0;
}