#include
     
      #include
      
       #include
       
        #define N 1001using namespace std;string s[N];int ans[N];inline int read(){    int x=0,f=1;char c=getchar();    while(c>'9'||c<'0'){
   if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int main(){    freopen("curse.in","r",stdin);    freopen("curse.out","w",stdout);    int x,y,n,l;    n=read();    for(int i=1;i<=n;i++)    {        cin>>s[i];        l=s[i].length();    }    for(int i=0;i
        
         y) ans[i]=1;        else ans[i]=0;    }    for(int i=0;i
        
       
      
     

 

/*当R 和 G 的大小超过了 N 时，L 的最小值就是 1，R,G 的规模就降到了 2000 以内。显然要采用二分答案的方法。法坛的位置按照从小到大进行排序。令 dp[i][j]表示，在用了 i次红光，j 次绿光的情况下，最多从第一座法坛开始，一直摧毁到第几座法坛。dp[i][j] = max ( P[dp[i-1][j] + 1], Q[dp[i][j-1] + 1] )。其中 P[k]表示使用一次红光，能从第 k 座法坛向右（正向为右）连续摧毁到第几座，Q[k]表示使用一次绿光，能从第 k 座法坛向右连续摧毁到第几座。 P 和 Q 数组可以通过预处理得到。判断 dp[R][G]的值是否为 N 即可。*/#include 
     
      #include 
      
       #include 
       
        #define N 2007using namespace std;int n,p,q,a[N],l=1,r,ans;int dp[N][N],P[N],Q[N];bool check(int L){    memset(dp,0,sizeof(dp));    memset(P,0,sizeof(P));    memset(Q,0,sizeof(Q));    for (int i=1;i<=n;i++)        for (int j=i;j<=n;j++)        {            if (a[j]-a[i]+1<=L) P[i]=j;            if (a[j]-a[i]+1<=2*L) Q[i]=j;        }    P[n+1]=Q[n+1]=n;    for (int i=0;i<=p;i++)        for (int j=0;j<=q;j++)        {            if (i>0) dp[i][j]=max(dp[i][j],P[dp[i-1][j]+1]);            if (j>0) dp[i][j]=max(dp[i][j],Q[dp[i][j-1]+1]);        }    return dp[p][q]==n;}int main(){    freopen("light.in", "r", stdin);    freopen("light.out", "w", stdout);    scanf("%d%d%d", &n,&p,&q);    for (int i=1;i<=n;i++)        scanf("%d",&a[i]);    sort(a+1,a+1+n);    a[0]=0;    r=a[n]-a[1]+1;    if (p+q>=n) {printf("1\n"); return 0;}    while (l<=r)    {        int mid=(l+r)/2;        if (check(mid)) ans=mid,r=mid-1; else l=mid+1;    }    printf("%d\n",ans);    return 0;}
       
      
     

 

 

 

/*1到n的次短路长度必然产生于：从1走到x的最短路 + edge[x][y] +  y到n的最短路首先预处理好1到每一个节点的最短路，和n到每一个节点的最短路然后枚举每一条边作为中间边（x，y）或者（y，x），如果加起来长度等于最短路长度则跳过，否则更新。到x的最短路 + edge[x][y] +  y到n的最短路  给dist[n] 比较 找大于dist[n] 且是最小的那一个 */#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define R 100007#define INF 0x3f3f3f3fusing namespace std;int num,n,m;int dist1[R],dist2[R],head[R];bool vis[R];struct Node{    int v;int w;int next;} edge[R*2];void init(){    num=0;    memset(head,-1,sizeof(head));    memset(dist1,0x3f,sizeof(dist1));    memset(dist2,0x3f,sizeof(dist2));}void add(int u,int v,int w){    edge[num].v=v;edge[num].w=w;    edge[num].next=head[u];head[u]=num++;}void SPFA(int u,int *dist){    int i,v,w;    queue
         
           Q;    memset(vis,false,sizeof(vis));    dist[u]=0;vis[u]=true;Q.push(u);    while(!Q.empty())    {        u=Q.front();Q.pop();        vis[u]=false;        for(i=head[u]; i!=-1; i=edge[i].next)        {            v=edge[i].v;            w=edge[i].w;            if(dist[v]>dist[u]+w)            {                dist[v]=dist[u]+w;                if(!vis[v])                {                    vis[v]=true;                    Q.push(v);                }            }        }    }}int main(){    freopen("maze.in","r",stdin);    freopen("maze.out","w",stdout);    scanf("%d%d",&n,&m);    int u,v,w;;    init();    for(int i=1;i<=m;i++)    {        scanf("%d%d%d",&u,&v,&w);        add(u,v,w);add(v,u,w);    }    SPFA(1,dist1);    SPFA(n,dist2);    int ans=INF;    for(int i=1;i<=n;i++)    {        for(int j=head[i]; j!=-1; j=edge[j].next)        {            v=edge[j].v;w=edge[j].w;            int tem=dist1[i]+dist2[v]+w;            if(tem>dist1[n] && tem
         
        
       
      
     

 

 

 

 

NOIP2018  模拟试题（二） 提高组更多咨询：北京信息学窦老师QQ3377089232NOIP2018提高组模拟题（二）（请选手务必仔细阅读本页内容）一．题目概况中文题目名称 咒语 神光 迷宫英文题目与子目录名curse light maze可执行文件名curse light maze输入文件名curse.in light.in maze.in输出文件名curse.out light.out maze.out每个测试点时限 1 秒 2 秒 2 秒测试点数目10 10 10每个测试点分值10 10 10结果比较方式 全文比较（过滤行末空格及文末回车）题目类型 传统 传统 传统二．提交源程序文件名对于 pascal 语言curse.pas light.pas maze.pas对于 C 语言curse.c light.c maze.c对于 C++语言curse.cpp light.cpp maze.cpp三．运行内存限制内存上限512M 512M 512MNOIP2018  模拟试题（二） 提高组更多咨询：北京信息学窦老师QQ33770892321、咒语(curse.pas/c/cpp)【题目描述】亮亮梦到自己来到了魔法城堡， 但一扇巨大的石门阻拦了他通向城堡内的路。正当他沮丧之际，突然发现门上有一处机关，机关上有一张很长的纸条。亮亮拿起纸条的一端，只见上面写着打开机关的方法： “打开机关需要念动符咒，咒语是一串长为 L 的由 0 和 1 组成的字符串。在这张长纸条上列了 n 个长为 L 的字符串，正确的咒语即是在纷繁的 2^L 种字符串中，与这些纸条上的字符串相异度之和最小，并且在满足这一条件下，0 的个数最多的字符串。两个字符串的相异度定义为对应位置不相等的字符对的个数。如‘011’和‘001’的相异度为 1，因为它们有且只有第二个位置上的字符不相等。”亮亮拉起纸条，只觉得纸条似乎永远也拉不完。这上面有着数以万计的字符串，而每一个字符串的长度也或百或千，以人力看来是无法得到正确的咒语。你能帮帮他，让他得以进入魔法城堡，一窥其中的奥秘吗？【输入格式】第一行为一个数字 N 。接下来的 N 行， 每行为一个长为 L 的 01 字符串。 数据保证 N 个字符串等长。【输出格式】只有一行，是一个长为 L 的字符串 S，即为正确的咒语。【样例输入】401011010010110110111【样例输出】01001【数据规模】对于 20%的数据，N<=5；对于 60%的数据，N<=100；对于 100%的数据，1<=N<=1000，1<=L<=1000。NOIP2018  模拟试题（二） 提高组更多咨询：北京信息学窦老师QQ33770892322、神光(light.pas/c/cpp)【题目描述】亮亮成功地念出了咒语，石门缓缓地自动移开，一道道绚丽的神光从城堡内激射而出。亮亮好奇而又兴奋地走入了城堡中，迎面有一座极长的魔法阵。魔法阵可以看作一条直线，它被均匀地分成了 1 000 000 000 个位置，一个位置可以看成是一个格子。有些位置上筑有法坛，一共 N座。亮亮只有破了眼前的魔法阵，才能继续前进，而欲破法阵，必须毁掉所有的法坛。亮亮身前有两根法杖：一根颜色血红，能发红色神光，光芒可以笼罩连续 L个位置，并摧毁这 L 个位置上所有的法坛，最多使用 R 次；另一根颜色碧绿，能发绿色神光，光芒可以笼罩连续 2L 个位置，并摧毁这 2L 个位置上所有的法坛，最多使用 G 次。法杖的神奇之处在于，L 的值必须由亮亮事先设定好，并且一经设定，便无法更改。亮亮需要在规定的次数下摧毁所有法坛，并且使得 L 最小。【输入格式】第一行三个整数 N, R, G。第 i (2<=i<=n+1) 行一个整数iA ，表示第 i 座法坛的位置。【输出格式】只有一个整数，表示L 的最小值。【样例输入】3 1 12217【样例输出】4【样例解释】亮亮将 L 设为 4，并用红色神光笼罩 21-24 位置，用绿色神光笼罩 1-8 位置。【数据规模】对于50%的数据，N <= 100；对于100%的数据，1 <= N <= 2000，1 <= R, G,iA <= 1,000,000,000。NOIP2018  模拟试题（二） 提高组更多咨询：北京信息学窦老师QQ33770892323、迷宫(maze.pas/c/cpp)【题目描述】破了魔法阵后，亮亮进入了一座迷宫。这座迷宫叫做“梦境迷宫” ，亮亮只有走出这座迷宫，才能从睡梦中醒来。梦境迷宫可以用无向图来表示。它共有 n 个点和 m 条双向道路，每条道路都有边权，表示通过这条道路所需的时间，且每条道路可以多次经过。亮亮位于一号点，而出口则是 n 号点。原本，亮亮该找到一条最短路，快速冲出迷宫，然而，梦境迷宫的特殊之处在于，如果沿着最短路到达出口，亮亮就会永远陷入梦境。因此，亮亮必须寻找一条次短路。次短路的长度须严格大于最短路（可以有多条）的长度，同时又不大于所有除最短路外的道路的长度。你的任务，就是编写一个程序，帮助亮亮找到通向出口的次短路。【输入格式】第一行有两个整数 n、m，表示迷宫内共有 n 个点，m 条边。接下来 m 行，每行三个整数 x、y、z，表示结点 x 和 y 之间连有一条边权为z 的无向边。【输出格式】一个整数，表示次短路的长度。【样例输入】4 41 2 22 4 42 3 33 4 4【样例输出】9【样例解释】最短路：1 -> 2 -> 4 (长度为 2+4=6)次短路：1 -> 2 -> 3 -> 4 (长度为 2+3+4=9)【数据规模】对于 100%的数据，1 <= n <= 5000，1 <= m <= 100,000。对于 100%的数据，1 <= z <= 5000，z 表示无向边的边长。