Solution1103

一:繁繁的数字

题目描述

$n$的二进制数划分方案数

数据范围

$n \le 1000000$

思路

OEISA018819

$f(i)=\begin{cases}f(i-1) & x \text{为奇数}\\f(i -1)+f(i/2) & x \text{为偶数}\end{cases}$

奇数时很好想。

偶数时分类讨论:

  • 有1:去掉这个1,就是$f(i-1)$
  • 没有1:全是$\ge 2$的,那么将$f(i/2)$所有方案的每一个数$\times 2$。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define PER(i,a,b) for(int i = (a);i >= (b);i--)
#define SF scanf
#define PF printf
#define DB(...) fprintf(stderr,__VA_ARGS__)
#define N 51
#define INF 0x3f3f3f3f
using namespace std;
int T,n,d;
char mp[N][N];
int dis[N][N];
int solve(){
    memset(dis,0x3f,sizeof dis);
    REP(i,1,n) REP(j,1,n) if(mp[i][j] == 'Y') dis[i][j] = 1;
    REP(i,1,n) dis[i][i] = 0;
    REP(i,1,n)
        REP(j,1,n)
            REP(k,1,n)
                dis[j][k] = min(dis[j][k],dis[j][i]+dis[i][k]);
    int res = 0;
    REP(i,1,n)
        REP(j,1,n)
            res	= max(res,dis[i][j]);
    return res;
}
int main()
{
//	freopen("bridge.in","r",stdin);
//	freopen("bridge.out","w",stdout);
    cin>>T;
    while(T--){
        SF("%d %d",&n,&d);
        REP(i,1,n) SF("%s",mp[i] + 1);
        int res = solve();
        if(res >= INF) PF("-1\n");
        else PF("%d\n",res * d);
    }
    return 0;
}

二:繁繁的游戏

题目描述

给定$n,\; d$和一个邻接矩阵。

有一条边表示这两个点的高度差$\le d$。

问任意两个点高度差可能的最大值。

数据范围

$n \le 50$

思路

图不连通则答案-1。

若高度差最大的点a,b那么答案就是$dis(a,b)\times d$(dis时最短路)。

所以就是求最大的最短路。Floyd。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define PER(i,a,b) for(int i = (a);i >= (b);i--)
#define SF scanf
#define PF printf
#define DB(...) fprintf(stderr,__VA_ARGS__)
#define N 51
#define INF 0x3f3f3f3f
using namespace std;
int T,n,d;
char mp[N][N];
int dis[N][N];
int solve(){
    memset(dis,0x3f,sizeof dis);
    REP(i,1,n) REP(j,1,n) if(mp[i][j] == 'Y') dis[i][j] = 1;
    REP(i,1,n) dis[i][i] = 0;
    REP(i,1,n)
        REP(j,1,n)
            REP(k,1,n)
                dis[j][k] = min(dis[j][k],dis[j][i]+dis[i][k]);
    int res = 0;
    REP(i,1,n)
        REP(j,1,n)
            res	= max(res,dis[i][j]);
    return res;
}
int main()
{
//	freopen("bridge.in","r",stdin);
//	freopen("bridge.out","w",stdout);
    cin>>T;
    while(T--){
        SF("%d %d",&n,&d);
        REP(i,1,n) SF("%s",mp[i] + 1);
        int res = solve();
        if(res >= INF) PF("-1\n");
        else PF("%d\n",res * d);
    }
    return 0;
}

三:繁繁的队列

题目描述

有一个队列,是$1\cdots n$的排列,每次可以将任意数取出,放在队首或队尾。

问最少操作几次可以将队列变成递增。

数据范围

$n \le 500000$

思路

考虑不被操作的数,它们最后一定会是连续的一段。问题就是最大化这一段的长度。记录每个数的位置$pos_i$,扫描一遍。

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define REP(i,a,b) for(int i = (a);i <= (b);i++)
#define PER(i,a,b) for(int i = (a);i >= (b);i--)
#define SF scanf
#define PF printf
#define DB(...) fprintf(stderr,__VA_ARGS__)
#define N 50010
using namespace std;
int n,a[N],pos[N];
int main()
{
    cin>>n;
    REP(i,1,n){
        SF("%d",&a[i]);
        pos[a[i]] = i;
    }
    int tmp = 0, ans = 0;
    pos[0] = 0;
    REP(i,1,n){
        if(pos[i] > pos[i - 1])
            tmp++;
        else tmp = 1;
        ans = max(ans,tmp);
    }
    cout<<n - ans<<endl;
    return 0;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注