apio2013游记【= =】

day0
  下午1点的飞机 导致在起飞前被各种问房号= =
  飞机还晚点了T_T 
  最后好像4点多了才到吧。。
  到了燕山大酒店 众犇已经准备去玩了 我们把行李扔在宾馆大堂就走了= =
  另外 今年的apio真是奇葩 非常奇葩。。。
  总共只有3天 第一天和第三天上课 第二天考试
  上课是从10点 上到12点  <什么心态= =
  然后12:30才能吃饭 早去就会被赶出来=。=
  下午从1:30就开始上课 上到快6:00。。
  考试那天 从8:00先试一个小时的机 然后直接开始考- – 考到2:00….
  即9:00~14:00= =
day1
  上午钱桥讲提交答案题 教我们如何写comparer
  顺便讲了一些随机化算法(盾神说的可以解决 非多项式题目的算法 用在提交答案题貌似极其合适。。)
  下午先是ural试题选讲
  “这题一定没人听懂 我们来分析下为什么没听懂“——冯齐纬
  然后李超的ural冠军赛题目讲解
day2
  被乱虐的时候终于到了0v0
  第一题是一堆机器人跑啊跑 一开始什么都没看出来 去看第二题
  乍看之下 不是动态树就是神结论 (orz hhs神犇
  想了半天没想出有什么神结论。。 动态树在提交答案题的威压下好像不是很可写。。
  于是决定写k=2的暴力
  第三题叫我们cha人 cha人啊。。 我这种好孩纸从来不cha人的啊 如何cha。。。
  看完题就直接123的写 第一题papapa暴力写完交国际 incorrect 
  想了想 可能国际是像oj一起算的。。 于是交国内 过了3个点
  不信服 加了一个-1 多过了一个点。。。 于是就心满意足的去写第二题。。
   写这个暴力我写了200行我会乱说? 交国际 OK 交国内 过了4个点 喜闻乐见 去玩第三题了。。
  还是有几个水的点的 但是那个chaDJ的真心不会 又看了下后面的那个神秘题目的第二个点有25分 一定不可做!(hehe
  神秘题我连程序都没看 第一个点我直接随机数据直接过了。。 第二个点 也没太多时间了 就无视之= =,  (我是傻b= =
  于是hehe的apio考试就这么过去了= =
  下午看成绩 112分 虽然是有gold 但是感觉好弱= = 第一题dp都木有想出来。。 还有第三题的最后一个点 如果略看下程序应该是可以构造出来的。。
  就这样吧=、=
day3
  木有听课去考acm了 被各种乱虐 我们队做出了5题 很悲剧的C没有做出来 然后就没有然后了。。
  晚上听说集训队名额缩减为50人 但是可能不算去年进过队的
  thu夏令营政策出来 最多加100分
day4
  BACK

  

APIO——11·题解

fange

Time Limit: 20 Sec  Memory Limit: 256 MB
Description
Sam和他的妹妹Sara有一个包含n × m个方格的
表格。她们想要将其的每个方格都染成红色或蓝色。
出于个人喜好,他们想要表格中每个2 ×   2的方形区
域都包含奇数个(1 个或 3 个)红色方格。例如,右
图是一个合法的表格染色方案(在打印稿中,深色代
表蓝色,浅色代表红色) 。
可是昨天晚上,有人已经给表格中的一些方格染上了颜色!现在Sam和Sara
非常生气。不过,他们想要知道是否可能给剩下的方格染上颜色,使得整个表格
仍然满足她们的要求。如果可能的话,满足他们要求的染色方案数有多少呢?
Input
输入的第一行包含三个整数n, m和k,分别代表表格的行数、列数和已被染
色的方格数目。
之后的k行描述已被染色的方格。其中第 i行包含三个整数xi, yi和ci,分别
代表第 i 个已被染色的方格的行编号、列编号和颜色。ci为 1 表示方格被染成红
色,ci为 0表示方格被染成蓝色。
Output
输出一个整数,表示可能的染色方案数目 W 模 10^9得到的值。(也就是说,如果 W大于等于10^9,则输出 W被10^9除所得的余数)。
对于所有的测试数据,2 ≤ n, m ≤ 106
,0 ≤ k ≤ 10^6
,1 ≤ xi ≤ n,1 ≤ yi ≤ m。
Sample Input
3 4 3
2 2 1
1 2 0
2 3 1
Sample Output
8
———————————————————————————————–
他们想要表格中每个2 ×   2的方形区域都包含奇数个(1 个或 3 个)红色方格
设红为1 蓝为0
则可以推推推推推推出 (1,1)xor(1,m)xor(n,1)xor(n,m)= 1
如果(1,1)固定的话 直接用这个 否则把1和0的方案加起来
对于每个确定的点 可以知道他的(1,m) 和(n,1)必然相同或必然不同
用并查集维护之 最后算算算算就行了
————————————————-code———————————-
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 300*10000;
struct point
{
  int x, y, c;
}a[maxn*2];
int fas[maxn*2], fad[maxn*2], k, m, n, b[maxn*2], bb[maxn*2], fa[maxn*2];
int getfad(int now)
{
  return fad[now] == 0 ? now : fad[now] = getfad(fad[now]);
}
int getfas(int now)
{
  return fas[now] == 0 ? now : fas[now] = getfas(fas[now]);
}
int getfa(int now)
{
  return fa[now] == 0 ? now : fa[now] = getfa(fa[now]);
}
int main()
{
freopen(“fange.in”, “r”, stdin);
freopen(“fange.out”, “w”, stdout);
  cin >> n >> m >> k;
  int br = -1;
  for (int i = 0; i < k; i++)
  {
    scanf(“%d%d%d”, &a[i].x, &a[i].y, &a[i].c);
    if (a[i].x == 1 && a[i].y == 1) br = a[i].c;
    a[i].x += maxn;
  }
  int ans = 0;
  if (br != 1)
  {
    for (int i = 0; i < k; i++)
    {
      if (a[i].c == 1)
      {
        int f1 = getfas(a[i].x);
        int f2 = getfas(a[i].y);
        if (f1 != f2) fas[f1] = f2;
      }
      int f1 = getfa(a[i].x);
      int f2 = getfa(a[i].y);
      if (f1 != f2) fa[f1] = f2;
    }
    for (int i = 0; i < k; i++)
    {
      if (a[i].c == 0)
      {
        int f1 = getfas(a[i].x);
        int f2 = getfas(a[i].y);
        if (f1 == f2)
        {
          cout << 0;
          fclose(stdin);fclose(stdout);
        }
      }
    }
    int now = 0;
    for (int i = 2; i <= n; i++)
    {
      int f = getfa(i+maxn);
      if (!b[f])
      {
        now++;
        b[f] = 1;
      }
    }
    for (int i = 2; i <= m; i++)
    {
      int f = getfa(i);
      if (!b[f])
      {
        now++;
        b[f] = 1;
      }
    }
    for (int i = 0; i < k; i++)
    {
      if (a[i].x-maxn == 1)
      {
        int f = getfa(a[i].x);
        if (!bb[f])
        {
          now–;
          bb[f] = 1;
        }
      }
      if (a[i].y == 1)
      {
        int f = getfa(a[i].y);
        if (!bb[f])
        {
          now–;
          bb[f] = 1;
        }
      }
    }
    int wh = 1;
    for (int i = 1; i <= now; i++) wh = (wh*2)%(10000*10000*10);
    ans = (ans+wh)%(10000*10000*10);
  }
  memset(fas, 0, sizeof(fas));
  memset(fa, 0, sizeof(fas));
  memset(fad, 0, sizeof(fad));
  memset(b, 0, sizeof(b));
  memset(bb, 0, sizeof(bb));
  if (br != 0)
  {
    for (int i = 0; i < k; i++)
    {
      if (a[i].c == 0)
      {
        int f1 = getfas(a[i].x);
        int f2 = getfas(a[i].y);
        if (f1 != f2) fas[f1] = f2;
      }
      int f1 = getfa(a[i].x);
      int f2 = getfa(a[i].y);
      if (f1 != f2) fa[f1] = f2;
    }
    for (int i = 0; i < k; i++)
    {
      if (a[i].c == 1)
      {
        int f1 = getfas(a[i].x);
        int f2 = getfas(a[i].y);
        if (f1 == f2)
        {
          cout << 0;
          fclose(stdin);fclose(stdout);
        }
      }
    }
    int now = 0;
    for (int i = 2; i <= n; i++)
    {
      int f = getfa(i+maxn);
      if (!b[f])
      {
        now++;
        b[f] = 1;
      }
    }
    for (int i = 2; i <= m; i++)
    {
      int f = getfa(i);
      if (!b[f])
      {
        now++;
        b[f] = 1;
      }
    }
    for (int i = 0; i < k; i++)
    {
      if (a[i].x-maxn == 1)
      {
        int f = getfa(a[i].x);
        if (!bb[f])
        {
          now–;
          bb[f] = 1;
        }
      }
      if (a[i].y == 1)
      {
        int f = getfa(a[i].y);
        if (!bb[f])
        {
          now–;
          bb[f] = 1;
        }
      }
    }
    int wh = 1;
    for (int i = 1; i <= now; i++) wh = (wh*2)%(10000*10000*10);
    ans = (ans+wh)%(10000*10000*10);
  }
  printf(“%d”, ans);
fclose(stdin);fclose(stdout);
}
222222222222222222222222222222222222222222222222222222222222
<!– A:以下试题我没做 so 只是顺便说说想法 不一定对、、

题目描述

TooDee是一块二维格子状的土地(就像著名的笛卡尔坐标系那样),在这里生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物,它们只在二维活动,而且它们非常的文明开化。TooDee的蜂窝和正常世界的蜂窝也是很不一样的,它们是矩形的且它们的边平行于TooDee的地理坐标系,就是说矩形的边或者是东西走向,或者是南北走向。
因为Dees是很高级的生物,它们有很多固定的飞行轨道,这些轨道由一些平行于坐标轴的线段组成,线段只会在经纬度都是整数的点相交。Dee在TooDee飞行时必须遵守以下规则(请记住TooDee中所有点的经纬度都是整数):
; 如果当前在点(XS, YS),则下步只能飞到四个邻点 (XS, YS – 1), (XS, YS + 1), (XS – 1, YS ), (XS + 1, YS );
; 不可以进入蜂巢;
; 只能在蜂巢的角或者边上改变飞行方向;
; 开始的时候可以向任何方向飞;
今晚是公共财政大臣Deeficer的女儿的生日,她想尽早回家,请帮她找到最快的回家路径。假设她每秒可以飞行一个单位的距离。

【数据规模】
对于20%的测试数据,n ≤ 10,所有的坐标都是小于100的非负整数;
对于60%的测试数据,n ≤ 100,所有坐标的绝对值都小于1000;
对于100%的测试数据,1 ≤ n ≤ 1000,所有坐标都是不超过10^9的整数;

【时限】2秒

输入格式

每个测试点包含多组数据。
输入的第一行包含一个整数T,表示测试数据的组数。接下来依次描述这T组数据,相邻的两组之间使用一个空行分隔。测试数据不多于20组。
对于每组数据,第一行包含4个整数xs, ys, xt, yt,表示Deeficer的办公室和家的坐标分别为(xs, ys)和(xt, yt)。第二行包含一个整数n,表示蜂巢的个数。接下来的n行描述所有的蜂巢,其中第i行包含4个整数xi1, yi1, xi2, yi2,表示第i个蜂巢两个对角的坐标分别为(xi1, yi1)和(xi2, yi2)。
任何两个蜂巢都不会相交,也不会接触(在角上也不会接触)。办公室和家处在不同的位置。每个蜂巢的面积为正。

输出格式

对于每一组数据,输出一个整数,表示Deeficer最快回家的时间(单位为秒),如果她无法按规则回家,则输出“No Path”。

样例输入

21 7 7 82

样例输出

9No Path

 
—————————————————————————————-
我的想法其实很简单
把他们离散化 再广搜
f[x][y][d]
X,Y是坐标 方向是d
然后就很随意了= =。
—————————————without code————————————
333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

题目描述

“猜单词”是一个双人游戏,在伊朗的青年学生中广为流行。假设有两个游戏者A和B,A作为先手,首先在一个双方都知道的语料库中选出一个单词,并记在脑海中。随后,他在一张小纸片上划下与单词字母数相等的小横线(不妨设为n条)。
接下来,B尝试猜出这个单词。每一轮,B选择一个字母并告诉A。A按如下规则回应:
; 若B所说的字母在单词中出现,A就把它写在对应的横线上。如果整个单词已经完整(所有的字母已经被猜出),B获胜。
;否则,如果字母没有在单词中出现,A就把它写在最左侧的下方仍为空白的横线下。如果所有横线下的空白处都已经有字母(也就是说,在这一轮前B已经猜了n个错误字母),那么B就输了,A获胜。
例如,A从语料库中选出了单词RED,且B已经依次猜了字母A, E, C, D, B和R。每一步的结果都在下图中展现。最终B获胜。但如果B在最后一步猜了S而不是R,他就输了。

Aidin是猜单词游戏迷。他相信,如果给定的语料库足够大,且其中的单词相对好,那么玩家A(先手)可以采取一种不公平的行动——修改选择的单词。也就是说,既然玩家A只将单词记在脑海中而不写下来,那他能够在游戏过程中随时变化这个单词,只要使得和当前已经给出的结果仍然一致即可。例如,在上面的游戏中,如果单词RED, BED, LED和TED都在语料库中,那么在第4步之后,A就可以确信他将胜利。他将总是把B给出的字母写在横线下(也就是认定其为错误的字母),那么每一次他将至多在集合 {RED, BED, LED, TED} 中失去一个备选单词。最终他将向B宣布:“这个单词是,嗯,……”,然后在他的集合中说出一个剩下的单词。
Aidin想,如果语料库足够好,那么A甚至可能在游戏一开始就确定获胜。例如,如果选择的单词长度为2,而集合{ME, MD, DE, ED, AS, IS, AI, SI}中的单词都在语料库中,那么A总能获胜。请自己找出A获胜的策略。
给定一个语料库,Aidin想知道是否无论B如何进行游戏,玩家A一定能获胜?
请注意在任何一次游戏结束时,如果A获胜,A需要能够给出一个语料库中的单词作为被选出的单词,这个单词应当与A所有给出的回答一致。

【数据规模】
对于20%的测试数据,k ≤ 100,每个单词的长度不超过3;
对于50%的测试数据,k ≤ 300,每个单词的长度不超过4;
对于所有测试数据中,k ≤ 1000。

输入格式

输入包含若干个语料库。每个语料库应该被独立地处理。
输入的第一行是一个整数C,代表语料库的数目。随后C个语料库以C个模块的形式出现在输入中。每两个模块之间以一个空行隔开。1 ≤ C ≤ 20。
对于每个输入模块,第一行包含一个正整数k,表示语料库中单词的个数。接下来的若干行中包含k个单词。相邻的单词以空格、制表符或换行符分隔。每个单词由小于7个大写英语字母组成。
每个单词都由不同的字母组成,也就是说,同一个字母在一个单词中出现的次数不会超过1次。

输出格式

对于每个语料库,如果玩家A有必胜策略(也就是说,不论B按什么方法猜,A总能获胜),输出一行“Yes”。否则输出一行“No”。输出不包含引号。

样例输入

212SI ME AND AI ARE MD AS WHEN ED IS DEHAPY5A B AB AC AD

样例输出

YesNo——————————————————————————————————————————————–

据说这题是搜索 = =。

我刚看这题的时候就想用他题解说的搜索骗分的。。居然是正解- –

———————————————without code and 题解——————————————————————-

!@#——)(*&……%¥#@!@(*&……%¥#@!@#——)(*&……%¥#@!@(*&……%¥#@

早知道rqnoj的复制效果那么好就不自己在pdf上2b般的copy了= =。

APIO——10·题解

特别行动队

【问题描述】
你有一支由 n 名预备役士兵组成的部队,士兵从 1到n编号,要将他们拆分
成若干特别行动队调入战场。出于默契的考虑,同一支特别行动队中队员的编号
应该连续,即为形如(i, i + 1, …, i + k)的序列。
编号为 i 的士兵的初始战斗力为 xi ,一支特别行动队的初始战斗力 x为队内
士兵初始战斗力之和,即 x = xi + xi+1 + … + xi+k。
通过长期的观察,你总结出一支特别行动队的初始战斗力 x将按如下经验公
式修正为x’:x’ = ax
2
+ bx + c,其中 a, b, c是已知的系数(a < 0)。
作为部队统帅,现在你要为这支部队进行编队,使得所有特别行动队修正后
战斗力之和最大。试求出这个最大和。
例如, 你有4名士兵, x1 = 2, x2 = 2, x3 = 3, x4 = 4。经验公式中的参数为 a = –1,
b = 10, c = –20。此时,最佳方案是将士兵组成 3个特别行动队:第一队包含士兵
1和士兵2,第二队包含士兵3,第三队包含士兵 4。特别行动队的初始战斗力分
别为4, 3, 4,修正后的战斗力分别为 4, 1, 4。修正后的战斗力和为 9,没有其它
方案能使修正后的战斗力和更大。
【输入格式】
输入由三行组成。第一行包含一个整数 n,表示士兵的总数。第二行包含三
个整数 a,  b,  c,经验公式中各项的系数。第三行包含 n 个用空格分隔的整数 x1,
x2, …, xn,分别表示编号为1, 2, …, n的士兵的初始战斗力。
【输出格式】
输出一个整数,表示所有特别行动队修正后战斗力之和的最大值。
【样例输入】
4
-1 10 -20
2 2 3 4
【样例输出】
9
【数据范围】
20%的数据中,n ≤ 1000;
50%的数据中,n ≤ 10,000;
100%的数据中,1  ≤  n  ≤  1,000,000,–5  ≤  a  ≤  –1,|b|  ≤  10,000,000,|c|  ≤
10,000,000,1 ≤ xi ≤ 100。
———————————————————————————————————-
斜率优化经典~
先写出方程:
f[i] = max(f[j]+(sum[i]-sum[j])^2*a+(sum[i]-sum[j])*b+c)
坐标表示:
  (sum[i], f[i]-sum[i]^2*a-b*sum[j])
斜率:
   2*sum[i]*a
that’s all~~
—————————————–code——————————————————————
#include <cstdio>
const int maxn=1000005;
long long f[maxn],c[maxn],team[maxn],y[maxn],a,b,cc;
bool work(int i,int j,int k)
{
  return a*2*c[i]*(c[j]-c[k])>y[j]-y[k];
}
bool del(int i,int j,int k)
{
  return (c[j]-c[k])*(y[i]-y[j])-(c[i]-c[j])*(y[j]-y[k])>0;
}
long long max(long long a,long long b)
{
  if (a>b) return a;else return b;
}
int main()
{
freopen(“bzoj1911.in”,”r”,stdin);
freopen(“bzoj1911.out”,”w”,stdout);
  long long n;
  scanf(“%I64d%I64d%I64d%I64d”,&n,&a,&b,&cc);
  for (int i=1;i<=n;i++)
  {
    scanf(“%I64d”,&c[i]);
    c[i]+=c[i-1];
  }
  int h=1;
  int t=1;
  for (int i=1;i<=n;i++)
  {
    while (h<t) if (work(i,team[h],team[h+1])) h++;else break;
    int j=team[h];
    f[i]=f[j]+a*(c[i]-c[j])*(c[i]-c[j])+b*(c[i]-c[j])+cc;
    y[i]=f[i]+a*c[i]*c[i]-b*c[i];
    while (h<t) if (del(i,team[t],team[t-1])) t–;else break;
    team[++t]=i;
  }
  printf(“%I64d”,f[n]);
fclose(stdin);fclose(stdout);
}
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
巡逻
【问题描述】
在一个地区中有 n个村庄,编号为1, 2, …, n。有n – 1条道路连接着这些村
庄,每条道路刚好连接两个村庄,从任何一个村庄,都可以通过这些道路到达其
他任一个村庄。每条道路的长度均为 1个单位。
为保证该地区的安全,巡警车每天要到所有的道路上巡逻。警察局设在编号
为1的村庄里,每天巡警车总是从警察局出发,最终又回到警察局。
下图表示一个有8个村庄的地区,其中村庄用圆表示(其中村庄 1用黑色的
圆表示),道路是连接这些圆的线段。为了遍历所有的道路,巡警车需要走的距
离为14 个单位,每条道路都需要经过两次。psb (21)

 

为了减少总的巡逻距离,该地区准备在这些村庄之间建立 K 条新的道路,

每条新道路可以连接任意两个村庄。两条新道路可以在同一个村庄会合或结束

(见下面的图例(c) )。一条新道路甚至可以是一个环,即,其两端连接到同一

个村庄。

由于资金有限,K 只能是 1或2。同时,为了不浪费资金,每天巡警车必须

经过新建的道路正好一次。

下图给出了一些建立新道路的例子:

psb (23)

在(a)中,新建了一条道路,总的距离是 11。在(b)中,新建了两条道路,总

的巡逻距离是 10。在(c)中,新建了两条道路,但由于巡警车要经过每条新道路

正好一次,总的距离变为了 15。

试编写一个程序,读取村庄间道路的信息和需要新建的道路数,计算出最佳

的新建道路的方案使得总的巡逻距离最小,并输出这个最小的巡逻距离。

 

【输入格式】

第一行包含两个整数 n, K(1 ≤ K ≤ 2)。接下来 n – 1行,每行两个整数 a, b,

表示村庄a与b之间有一条道路(1 ≤ a, b ≤ n)。

【输出格式】

输出一个整数,表示新建了K 条道路后能达到的最小巡逻距离。

【样例输入1】

8 1

1 2

3 1

3 4

5 3

7 5

8 5

5 6

【样例输出 1】

11

【样例输入2】

8 2

1 2

3 1

3 4

5 3

7 5

8 5

5 6

【样例输出 2】

10

【样例输入3】

5 2

1 2

2 3

3 4

4 5

【样例输出 3】

6

【数据范围】

10%的数据中,n ≤ 1000,    K = 1;

30%的数据中,K = 1;

80%的数据中,每个村庄相邻的村庄数不超过 25;

90%的数据中,每个村庄相邻的村庄数不超过 150;

100%的数据中,3 ≤ n ≤ 100,000, 1 ≤ K ≤ 2。

—————————————————————————————————————-

这题一条边的很好想 就直接找直径就行了

两条边:

先找第一条边 把直径上的权赋值为-1

再找一次直径

省的路为两次直径的权值和

————————————————–code———————————————————

 

#include <cstdio>

#include <iostream>

#include <cstring>

using namespace std;

const int maxn = 300000;

struct line

{

int to, next, opt, v;

}a[maxn];

int k, be[maxn], b[maxn], n, l, m, mx, f, to;

void makeline(int f, int t, int opt)

{

l++;

a[l].next = be[f];

be[f] = l;

a[l].to = t;

a[l].opt = opt;

a[l].v = 1;

}

void dfsf(int now, int t)

{

for (int i = be[now]; i != 0; i = a[i].next)

{

int to = a[i].to;

if (!b[to])

{

b[to] = 1;

dfsf(to, t+a[i].v);

b[to] = 0;

}

}

if (t > mx) mx = t, f = now;

}

void dfst(int now, int t)

{

for (int i = be[now]; i != 0; i = a[i].next)

{

int to = a[i].to;

if (!b[to])

{

b[to] = 1;

dfst(to, t+a[i].v);

b[to] = 0;

}

}

if (t > mx) mx = t, to = now;

}

bool change(int now, int t)

{

if (now == to) return mx = t, true;

for (int i = be[now]; i != 0; i = a[i].next)

{

int to = a[i].to;

if (!b[to])

{

b[to] = 1;

if (change(to, t+1))

{

a[i].v = -1;

a[a[i].opt].v = -1;

b[to] = 0;

return true;

}

b[to] = 0;

}

}

return false;

}

int dfsa(int now)

{

int max1 = 0;

int max2 = 0;

for (int i = be[now]; i != 0; i = a[i].next)

{

int to = a[i].to;

if (!b[to])

{

b[to] = 1;

int d = dfsa(to);

if (d+a[i].v > max1)

{

max2 = max1;

max1 = d+a[i].v;

}

else

if (d+a[i].v > max2) max2 = d+a[i].v;

}

}

if (max1+max2 > mx) mx = max1+max2;

return max1;

}

int main()

{

freopen(“patrol.in”, “r”, stdin);

freopen(“patrol.out”, “w”, stdout);

cin >> n >> k;

l = 0;

for (int i = 1; i < n; i++)

{

int f, t;

scanf(“%d%d”, &f, &t);

makeline(f, t, l+2);

makeline(t, f, l);

}

f = 0;

b[1] = 1;

dfsf(1, 0);

memset(b, 0, sizeof(b));

mx = -1000000;

b[f] = 1;

dfst(f, 0);

memset(b, 0, sizeof(b));

b[f] = 1;

int ans = n*2-mx-1;

if (k == 1) cout << ans;

else

{

change(f, 0);

memset(b, 0, sizeof(b));

mx = -1000000;

b[1] = 1;

dfsa(1);

ans = ans-mx+1;

cout << ans;

}

fclose(stdin);fclose(stdout);

}

###############################################################################
信号覆盖
【问题描述】
一家电信公司正在北京城搭建一个 GSM 网络。城市里共有 n 个房子需要被
信号覆盖。由于经费的限制,电信公司只能安装一个天线。
这里将每个房子用一个点坐标来表示。为了简化天线的放置,电信公司将会
选择其中的3个房子作一个外接圆,然后将天线放在圆的中心,所有位于这个圆
内或者圆的边界上的房子都将被天线的信号所覆盖。
电信公司将会随机选择城市中的3个房子来搭建天线,他们想知道在所有可
能放置天线的方案中平均会有多少个房子被信号覆盖。
例如,假设共有 4个房子A, B, C, D,它们的位置如下图:psb (24)

如果我们选择ABC或者BCD三个点搭建的外接圆,所有的房子都会被覆盖。

如果我们选择ACD 或者ABD,剩下的房子将不会在天线的信号覆盖范围内。因

此平均有(4 + 4 + 3 + 3) / 4 = 3.50 个房子被信号覆盖。

给定所有房子的位置,你的任务是计算平均有多少个房子被信号覆盖。假定

每一个房子都有一个二维的整数坐标,并且保证任何三个房子都不在同一条直线

上,任何四个房子都不在同一个圆上。

【输入格式】

输入第一行包含一个正整数 n, 表示房子的总数。接下来有 n 行,分别表示

每一个房子的位置。对于 i = 1, 2, .., n, 第i 个房子的坐标用一对整数 xi和yi来表

示,中间用空格隔开。

【输出格式】

输出文件包含一个实数,表示平均有多少个房子被信号所覆盖,需保证输出

结果与精确值的绝对误差不超过0.01。

 

【样例输入】

4

0 2

4 4

0 0

2 0

【样例输出】

3.500

【样例说明】

3.5,  3.50,  3.500,  …  中的任何一个输出均为正确。此外,3.49,  3.51,

3.499999,…等也都是可被接受的输出。

【数据范围】

100%的数据保证,对于 i  =  1,  2,  ..,  n, 第 i 个房子的坐标(xi,  yi)为整数且

–1,000,000 ≤ xi, yi ≤ 1,000,000. 任何三个房子不在同一条直线上,任何四个房子不

在同一个圆上;

40%的数据,n ≤ 100;

70%的数据,n ≤ 500;

100%的数据,3 ≤ n ≤ 1,500。

 

——————————————————————————————————-

这题很麻烦啊= =

一个凸多边形对答案贡献14(3+3+4+4)

一个凹多边形对答案贡献13(3+3+3+4)

so 要算出答案就要算出有几个凹多边形

就是算出所有点被几个三角形包含的和

对一个点可以算出它被几个三角形包含

用总三角形数减上面的个数就是一个的ans

所有的和就是凹多边形数

用总4边形减凹多边形数就是凸多边形数

然后再算啊算啊就ok了~

 

算一个点没被几个三角形包含:

把所有点对于这个点极角排序

用一个单调队列维护 保持队列中的夹角<180度

每次算有几个三角形  求和 就是ans了~

———————————————————code———————————————–

 

#include <cstdio>

#include <iostream>

#include <cstring>

#include <string>

#include <algorithm>

using namespace std;

const long long maxn = 2000;

long long ans;

struct point

{

long long x, y;

}a[maxn], b[maxn];

long long c(long long n, long long m)

{

if (n < m) return 0;

if (m == 1) return n;

if (m == 2) return n*(n-1)/2;

if (m == 3) return n*(n-1)*(n-2)/6;

if (m == 4) return n*(n-1)*(n-2)*(n-3)/24;

}

long long n;

long long operator^(point x, point y)

{

return x.x * y.y – x.y * y.x;

}

void sortb(long long l, long long r)

{

long long i = l;

long long j = r;

point mid = b[(l+r)/2];

while (true)

{

while ((mid^b[i]) > 0) ++i;

while ((mid^b[j]) < 0) –j;

if (i <= j)

{

swap(b[i], b[j]);

++i; –j;

}

if (i > j) break;

}

if (i < r) sortb(i, r);

if (l < j) sortb(l, j);

}

void solve(long long now)

{

for (long long i = 0; i < n; i++)

{

b[i].x = a[i].x-a[now].x;

b[i].y = a[i].y-a[now].y;

}

swap(b[now], b[0]);

sortb(1, n-1);

long long j = 2;

long long k = 0;

for (long long i = 1; i < n; i++)

{

while ((b[j]^b[i]) > 0)

j < n-1 ? j++ : (j = 1, k = n-1);

ans += c(j+k-i-1, 2);

}

}

int main()

{

freopen(“signaling.in”, “r”, stdin);

freopen(“signaling.out”, “w”, stdout);

cin >> n;

for (long long i = 0; i < n; i++)

scanf(“%I64d%I64d”, &a[i].x, &a[i].y);

ans = 0;

for (long long i = 0; i < n; i++)

solve(i);

printf(“%.6f”, (double)(c(n, 4)*2-c(n-1, 3)*n+ans)/c(n, 3)+3);

fclose(stdin);fclose(stdout);

}

APIO——09·题解

————————————————-ACE————————————————————-

采油区域
Siruseri 政府决定将石油资源丰富的 Navalur 省的土地拍卖给私人承包商以
建立油井。被拍卖的整块土地为一个矩形区域,被划分为M×N 个小块。
Siruseri地质调查局有关于Navalur土地石油储量的估测数据。这些数据表示
为M×N 个非负整数,即对每一小块土地石油储量的估计值。
为了避免出现垄断,政府规定每一个承包商只能承包一个由K×K 块相连的
土地构成的正方形区域。
AoE石油联合公司由三个承包商组成,他们想选择三块互不相交的 K×K 的
区域使得总的收益最大。
例如,假设石油储量的估计值如下:
1  1  1  1  1  1  1  1  1
1  1  1  1  1  1  1  1  1
1  8  8  8  8  8  1  1  1
1  8  8  8  8  8  1  1  1
1  8  8  8  8  8  1  1  1
1  1  1  1  8  8  8  1  1
1  1  1  1  1  1  8  8  8
1  1  1  1  1  1  9  9  9
1  1  1  1  1  1  9  9  9
如果 K  =  2,  AoE 公司可以承包的区域的石油储量总和为 100,  如果 K  =  3,
AoE公司可以承包的区域的石油储量总和为 208。
AoE公司雇佣你来写一个程序,帮助计算出他们可以承包的区域的石油储量
之和的最大值。
输入格式
输入第一行包含三个整数 M, N, K,其中 M和N 是矩形区域的行数和列数,
K 是每一个承包商承包的正方形的大小(边长的块数) 。接下来 M行,每行有 N
个非负整数表示这一行每一小块土地的石油储量的估计值。
输出格式
输出只包含一个整数,表示 AoE 公司可以承包的区域的石油储量之和的最
大值。
数据范围
数据保证 K≤M且K≤N并且至少有三个 K×K的互不相交的正方形区域。其
中30%的输入数据,M, N≤ 12。所有的输入数据, M, N≤ 1500。每一小块土地的
石油储量的估计值是非负整数且≤ 500。
输入样例
9 9 3
1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 8 8 8 8 8 1 1 1
1 1 1 1 8 8 8 1 1
1 1 1 1 1 1 8 8 8
1 1 1 1 1 1 9 9 9
1 1 1 1 1 1 9 9 9
输出样例
208
———————————————————————————-
这题就是求三个不相交矩阵的最大和
把一个矩形割出来3个有一下6中方法:
psb (18)枚举分割线 取max就行了~有一种比较好写的方法:可以for4次 每次把整个矩阵转90度 每次求值就只要求两种就行了。(我没用这个。。写完才听说的= = )

————————————————————-code————————————————————-

 

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int maxn = 2000;

int z[maxn][maxn], n, m, k, a[maxn][maxn], ma[4][maxn][maxn], hr[maxn], sr[maxn], h[maxn][maxn], s[maxn][maxn];

int main()

{

freopen(“oil.in”, “r”, stdin);

freopen(“oil.out”, “w”, stdout);

cin >> n >> m >> k;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= m; j++)

{

int t;

scanf(“%d”, &t);

z[i][j] = z[i-1][j]+z[i][j-1]-z[i-1][j-1]+t;

}

for (int i = 1; i+k-1 <= n; i++)

for (int j = 1; j+k-1 <= m; j++)

a[i][j] = z[i+k-1][j+k-1]-z[i+k-1][j-1]-z[i-1][j+k-1]+z[i-1][j-1];

for (int i = 1; i <= n-k+1; i++)

for (int j = 1; j <= m-k+1; j++)

hr[i] = max(hr[i], a[i][j]);

for (int j = 1; j <= m-k+1; j++)

for (int i = 1; i <= n-k+1; i++)

sr[j] = max(sr[j], a[i][j]);

for (int i = k; i <= n; i++)

for (int j = k; j <= m; j++)

ma[0][i][j] = max(a[i-k+1][j-k+1], max(ma[0][i-1][j], ma[0][i][j-1]));

for (int i = n-k+1; i >= 1; i–)

for (int j = k; j <= m; j++)

ma[1][i][j] = max(a[i][j-k+1], max(ma[1][i][j-1], ma[1][i+1][j]));

for (int i = n-k+1; i >= 1; i–)

for (int j = m-k+1; j >= 1; j–)

ma[2][i][j] = max(a[i][j], max(ma[2][i+1][j], ma[2][i][j+1]));

for (int i = k; i <= n; i++)

for (int j = m-k+1; j >= 1; j–)

ma[3][i][j] = max(a[i-k+1][j], max(ma[3][i-1][j], ma[3][i][j+1]));

for (int i = 1; i <= n; i++)

for (int j = i+k-1; j <= n; j++)

h[i][j] = max(hr[j-k+1], h[i][j-1]);

for (int i = 1; i <= m; i++)

for (int j = i+k-1; j <= m; j++)

s[i][j] = max(sr[j-k+1], s[i][j-1]);

int ans = 0;

for (int i = k; i <= n; i++)

for (int j = i+k; j <= n-k; j++)

ans = max(ans, h[1][i] + h[i+1][j] + h[j+1][n]);

for (int i = k; i <= m; i++)

for (int j = i+k; j <= m-k; j++)

ans = max(ans, s[1][i] + s[i+1][j] + s[j+1][n]);

for (int i = k; i <= n-k; i++)

for (int j = k; j <= m-k; j++)

{

ans = max(ans, h[1][i] + ma[1][i+1][j] + ma[2][i+1][j+1]);

ans = max(ans, s[1][j] + ma[3][i][j+1] + ma[2][i+1][j+1]);

}

for (int i = n-k+1; i >= k+1; i–)

for (int j = k; j <= m-k; j++)

{

ans = max(ans, h[i][n] + ma[0][i-1][j] + ma[3][i-1][j+1]);

ans = max(ans, s[j+1][m] + ma[0][i-1][j] + ma[1][i][j]);

}

cout << ans;

fclose(stdin);fclose(stdout);

}

//2b的写了n个for。。。。

——————————————————————–ACE—————————————————————————-

会议中心
Siruseri 政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很
感兴趣,他们希望能够在里面举行会议。
对于一个客户而言,仅当在开会时能够独自占用整个会堂,他才会租借会堂。
会议中心的销售主管认为:最好的策略应该是将会堂租借给尽可能多的客户。显
然,有可能存在不止一种满足要求的策略。
例如下面的例子。总共有 4个公司。他们对租借会堂发出了请求,并提出了
他们所需占用会堂的起止日期(如下表所示)。

psb (20)

 

上例中,最多将会堂租借给两家公司。 租借策略分别是租给公司 1和公司3,

或是公司 2 和公司 3,也可以是公司 1 和公司 4。注意会议中心一天最多租借给

一个公司,所以公司 1和公司2不能同时租借会议中心,因为他们在第九天重合

了。

销售主管为了公平起见,决定按照如下的程序来确定选择何种租借策略:首

先,将租借给客户数量最多的策略作为候选,将所有的公司按照他们发出请求的

顺序编号。对于候选策略,将策略中的每家公司的编号按升序排列。最后,选出

其中字典序最小1

的候选策略作为最终的策略。

例中,会堂最终将被租借给公司 1 和公司 3:3 个候选策略是

{(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。

你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

输入格式

输入的第一行有一个整数 N,表示发出租借会堂申请的公司的个数。第 2到

第N+1 行每行有2个整数。第 i+1 行的整数表示第 i 家公司申请租借的起始和终

止日期。对于每个公司的申请,起始日期为不小于 1的整数,终止日期为不大于

109

的整数。

输出格式

输出的第一行应有一个整数 M,表示最多可以租借给多少家公司。第二行应

1

字典序指在字典中排列的顺序,如果序列 l1是序列 l2的前缀,或者对于 l1和 l2的第一个不同位置 j,

l1[j]<l2[j],则 l1比 l2小。

 

列出M个数,表示最终将会堂租借给哪些公司。

数据范围

对于 50%的输入,N≤3000。在所有输入中,N≤200000。

输入样例

4

4 9

9 11

13 19

10 17

输出样例

2

1 3

——————————————————————————————————————

这题看似so easy有木有?

顺便动归一下第一行就over了

至于第二行 肯定是动归完随便处理一下就行了~

<!–以上是我写这题前想的。。

 

第一行的确很easy 10min就搞定了

开始很happy的准备写第二行的时候发现。。。。。

how.to.do ?IDK.IDK.IDK.IDK.IDK.IDK.IDK.IDK…..

难点其实是字典序。。。。。。

坑啊 啊啊啊

果断看了题解还是不知道在说什么。。。

==再看看吧..

code先不写了

题解==补吧。。

————————————————-3.rd——————————————————-

 

抢掠计划

Siruseri城中的道路都是单向的。不同的道路由路口连接。按照法律的规定,

在每个路口都设立了一个 Siruseri 银行的 ATM 取款机。令人奇怪的是,Siruseri

的酒吧也都设在路口,虽然并不是每个路口都设有酒吧。

Banditji 计划实施 Siruseri有史以来最惊天动地的 ATM 抢劫。他将从市中心

出发,沿着单向道路行驶,抢劫所有他途径的ATM 机,最终他将在一个酒吧庆

祝他的胜利。

使用高超的黑客技术,他获知了每个ATM 机中可以掠取的现金数额。他希

望你帮助他计算从市中心出发最后到达某个酒吧时最多能抢劫的现金总数。他可

以经过同一路口或道路任意多次。但只要他抢劫过某个 ATM 机后,该 ATM 机

里面就不会再有钱了。

例如,假设该城中有6个路口,道路的连接情况如下图所示:

psb (22)

市中心在路口 1,由一个入口符号→来标识,那些有酒吧的路口用双圈来表

示。每个ATM机中可取的钱数标在了路口的上方。在这个例子中,Banditji 能抢

劫的现金总数为47,实施的抢劫路线是:1-2-4-1-2-3-5。

输入格式

第一行包含两个整数 N、M。N 表示路口的个数,M表示道路条数。接下来

M行,每行两个整数,这两个整数都在 1到 N 之间,第i+1 行的两个整数表示第

i 条道路的起点和终点的路口编号。接下来 N 行,每行一个整数,按顺序表示每

个路口处的ATM机中的钱数。接下来一行包含两个整数 S、P,S表示市中心的

编号,也就是出发的路口。P表示酒吧数目。接下来的一行中有 P个整数,表示

P个有酒吧的路口的编号。

输出格式

输出一个整数,表示 Banditji 从市中心开始到某个酒吧结束所能抢劫的最多

的现金总数。

 

数据范围

50%的输入保证 N,  M<=3000。所有的输入保证 N,  M<=500000。每个 ATM

机中可取的钱数为一个非负整数且不超过 4000。输入数据保证你可以从市中心

沿着Siruseri的单向的道路到达其中的至少一个酒吧。

输入样例

6 7

1 2

2 3

3 5

2 4

4 1

2 6

6 5

10

12

8

16

1

5

1 4

4 3 5 6

 

输出样例

47

—————————————————————————————————————-

这题就真的easy了、只不过略显麻烦一点.一点.点.d…

先一个强连通分量 把它变成无环 再一个记忆化就行了~

坑爹点:(不是难点 是坑点..)

强连通分量本来要开的数组就多

又要用链表

用链表就罢了

居然还要非递归。。。。。

let‘s数一下开了几个数组

 

struct line

{

long long to, next, f;

}a[maxn], ap[maxn];

struct point

{

long long v;

bool b;

}p[maxn];

long long be[maxn], bep[maxn], b[maxn], tot, v[maxn], l, k, h[maxn], lp, n, s, m;

bool t[maxn], br;

struct pt

{

long long i, n, ans;

}z[maxn];

如果结构体分开算 一共。。17个数组 = =

主要问题是处理的真心晕。。。

250行 还算挺长的。。。

——————————————————-code——————————————–

 

 

#include <cstdio>

#include <iostream>

#include <string>

#include <cstring>

#include <cstring>

using namespace std;

const long long maxn = 1000000;

struct line

{

long long to, next, f;

}a[maxn], ap[maxn];

struct point

{

long long v;

bool b;

}p[maxn];

long long be[maxn], bep[maxn], b[maxn], tot, v[maxn], l, k, h[maxn], lp, n, s, m;

bool t[maxn], br;

struct pt

{

long long i, n, ans;

}z[maxn];

void makeline(long long f, long long t)

{

l++;

a[l].next = be[f];

be[f] = l;

a[l].f = f;

a[l].to = t;

}

void makelinep(long long f, long long t)

{

lp++;

ap[lp].next = bep[f];

bep[f] = lp;

ap[lp].f = f;

ap[lp].to = t;

}

void dfs(long long now)

{

z[0].i = be[now];

z[0].n = now;

tot = 0;

while (tot >= 0)

{

if (z[tot].i == 0)

{

h[k++] = z[tot].n;

tot–;

continue;

}

long long to = a[z[tot].i].to;

z[tot].i = a[z[tot].i].next;

if (!b[to])

{

b[to] = 1;

z[++tot].i = be[to];

z[tot].n = to;

}

}

/*for (long long i = be[now]; i != 0; i = a[i].next)

{

long long to = a[i].to;

if (!b[to])

{

b[to] = 1;

dfs(to);

}

}

h[k++] = now;*/

}

void dfsp(long long now)

{

tot = 0;

z[tot].i = bep[now];

z[tot].n = now;

b[now] = k;

p[k].v += v[now];

p[k].b = p[k].b | t[now];

if (now == s && br)

s = k, br = false;

while (tot >= 0)

{

if (z[tot].i == 0)

{

–tot;

continue;

}

long long to = ap[z[tot].i].to;

z[tot].i = ap[z[tot].i].next;

if (!b[to])

{

z[++tot].i = bep[to];

z[tot].n = to;

b[to] = k;

p[k].v += v[to];

p[k].b = p[k].b | t[to];

if (to == s && br)

s = k, br = false;

}

}

/*b[now] = k;

p[k].v += v[now];

p[k].b = p[k].b | t[now];

if (now == s && br)

s = k, br = false;

for (long long i = bep[now]; i != 0; i = ap[i].next)

{

long long to = ap[i].to;

if (!b[to]) dfsp(to);

}     */

}

long long dfsr(long long now)

{

if (b[now] != -1) return b[now];

tot = 0;

z[tot].n = now;

z[tot].i = bep[now];

z[tot].ans = -1;

while (tot >= 0)

{

if (z[tot].i == 0)

{

long long ans = z[tot].ans;

long long no = z[tot].n;

if (ans == -1)

{

if (p[no].b)

{

ans = p[no].v;

b[no] = ans;

if (tot) –tot, z[tot].ans = max(z[tot].ans, ans);

else tot–;

}

else tot–;

}

else

{

ans += p[no].v;

b[no] = ans;

if (tot) –tot, z[tot].ans = max(z[tot].ans, ans);

else tot–;

}

continue;

}

long long to = ap[z[tot].i].to;

z[tot].i = ap[z[tot].i].next;

if (b[to] != -1) z[tot].ans = max(z[tot].ans, b[to]);

else

{

z[++tot].i = bep[to];

z[tot].n = to;

z[tot].ans = -1;

}

}

/*if (b[now] != -1) return b[now];

long long ans = -1;

for (long long i = bep[now]; i != 0; i = ap[i].next)

{

long long to = ap[i].to;

long long d = dfsr(to);

if (d > ans) ans = d;

}

if (ans == -1)

{

if (p[now].b)

{

ans = p[now].v;

b[now] = ans;

return ans;

}

return -1;

}

else

{

ans += p[now].v;

b[now] = ans;

return ans;

}  */

}

int main()

{

freopen(“large-tree-1.in”, “r”, stdin);

freopen(“atm.out”, “w”, stdout);

cin >> n >> m;

l = lp = 0;

for (long long i = 0; i < m; i++)

{

long long f, t;

scanf(“%I64d%I64d”, &f, &t);

makeline(f, t);

makelinep(t, f);

}

for (long long i = 1; i <= n; i++) scanf(“%I64d”, &v[i]);

cin >> s;

long long te;

cin >> te;

for (long long i = 1; i <= te; i++)

{

long long now;

scanf(“%I64d”, &now);

t[now] = true;

}

k = 0;

for (long long i = 1; i <= n; i++)

if (!b[i])

{

b[i] = 1;

dfs(i);

h[k++] = i;

}

memset(b, 0, sizeof(b));

k = 1;

br = true;

for (long long i = n-1; i >= 0; i–)

if (!b[h[i]])

{

if (b[h[i]] == s && br)

s = k, br = false;

dfsp(h[i]);

k++;

}

–k;

memset(ap, 0, sizeof(ap));

memset(bep, 0, sizeof(bep));

lp = 0;

for (long long i = 1; i <= l; i++)

{

long long f = b[a[i].f];

long long t = b[a[i].to];

if (f != t) makelinep(f, t);

}

for (long long i = 1; i <= k; i++)

b[i] = -1;

for (long long i = 1; i <= k; i++)

if (b[i] == -1) dfsr(i);

cout << b[s];

fclose(stdin); fclose(stdout);

}

 

 

 

 

 

 

!@#¥%¥@……%¥&#&*(…………&&#%……#@¥!@#¥%¥@……%¥&#&*(…………&&#%……#@¥

 

这届apio考出来估计全部晕

第一题什么几十个for

第二题什么看似easy 其实= =

第三题什么一坨数组。。。

 

正版坑的一届 啊。。。

APIO——08·题解

珠链交换器
beads
X 教授展示了他的最新发明:珠链交换器(UBS)。顾名思义,就是一个能通
过交换一些珠子使珠链更有趣的工具。
UBS 有 N 条平行于南北方向的传送带,已按照从左到右的顺序 1 至 N 编号。
每条传送带的速度相同,且都是由北向南传送。有 M 个交换器,每个交换器都
安放在某两个相邻的传送带上,任意两个交换器与传送带最北端的距离都是不同
的(也就是说,所有的交换器可以按照它们与传送带最北端的距离严格排序)。所
有的交换器按从北到南的顺序 1 到 M编号。图 1 为一个 UBS 的俯视图: psb (13)

在使用 UBS 的时候,将 N 个珠子分别放在每条传送带的最北端,这样在传

送带向南传送时,所有的珠子一直保持在同一条水平横线上。当两颗珠子同时到

达一个交换器时,在右边传送带上的珠子被移动到左边的传送带上,同时左边传

送带上的珠子被移动到右边的传送带上。经交换后,这两个珠子仍保持与其他珠

子在一条水平线上。图 2 所示为一次交换的过程:

psb (14)

任务 任务 任务 任务

编写一个程序,对于给定的传送带条数 N,交换器个数 M,以及每个交换器

的位置,回答以下形式的问题:

给出 K(传送带的编号)和 J(交换器的编号),当所有的珠子都刚好完全经

过交换器 J(又称 J号交换器)时,最开始时放在第 K 条传送带(又称 K 号传送

带)最北端的珠子现在位于哪一条传送带上。

输入格式 输入格式 输入格式 输入格式

从标准输入读入数据。第一行包含传送带的条数 N( )和交换器

的个数 M( )。

接下来的 M 行,按照从北向南的顺序描述所有的交换器,每行包含一个整

数 P(1 1 P M ≤ ≤ ?6?1 ),表示在传送带 P 和 P+1 之间有一个交换器。

交互方法 交互方法 交互方法 交互方法

在读入上述数据之后,你的程序需要和表格 1 中所描述的库进行交互。库中

的函数必须按下面的顺序调用:

1.  调用 getNumQuestions 以获取 Q( ),表示有多少个问

题。

2.  以后 Q 次,每次

(a) 调用函数 getQuestion 来获取一个问题。

(b) 调用函数 answer回答对应的问题。

特别注意,getNumQuestions 必须首先调用,且只能调用 1 次。getQuestion

和 answer必须交替调用:当调用完 getQuestion 之后,你的程序不能马上再次调

用 getQuestion,而必须先调用 answer,反之亦然。如果你的程序在某个测试点

违反了这一约定,则该测试点你的得分为 0。

 

图片psb (15)

 

程序指令 程序指令 程序指令 程序指令

如果你提交 Pascal 的程序,在你的代码中必须有如下的声明:

uses beadslib;

如果你提交 C 或 C++的程序,在你的代码中必须有如下的声明:

#include “beadslib.h”

 

伪函数库与样例程序

将为你提供一个包含样例库的源文件和样例的调用。这些文件在一个压缩包

中,包含三个目录——pascal,  c和 cpp,分别是 Pascal,C 和 C++的源文件,每个

目录中包含一个伪交互库的源文件和一个按正确顺序调用交互库的程序。

如果你使用 Pascal,伪交互库在一个名字为 beadslib 的单元中,其源文件为

beadslib.pas。文件 sample.pas 是使用这个库的样例。

如果你使用 C 语言,伪交互库的函数包含在 beadslib.h 中,函数在 beadslib.c

中,文件 sample.c是使用这个库的样例。

如果你使用 C++语言,伪交互库的函数也包含在 beadslib.h 中(但这个文件和

C 语言对应的文件不一样),函数实现在 beadslib.cpp 中,文件 sample.cpp 是使用

这个库的样例。

伪交互库的执行方式如下:

 

 

当伪交互库的 getNumQuestions 被调用时,它打开文件 questions.txt,读

出有多少个问题,并返回读到的问题个数。

当 getQuestion 被调用时,函数库文件中读出两个整数 K 和 J。

当 answer被调用时,将参数 x 输出到标准输出中。

当调用函数的顺序不正确时,函数库输出一行错误信息到标准输出。

questions.txt 的格式如下:第一行包含问题的个数 Q,接下来 Q 行,每行两

个整数 K 和 J,K 表示传送带的编号,J表示交换器的编号。

样例输入 样例输入 样例输入 样例输入

5 5

2

4

1

3

3

questions.txt 样例 样例 样例 样例

2

3 4

5 5

(此输入对应图 1)

样例交互 样例交互 样例交互 样例交互

图片

 

时间和空间限制 时间和空间限制 时间和空间限制 时间和空间限制

你的程序必须在 2 秒钟内运行结束,至多使用 256M 内存。

评分 评分 评分 评分

对于每个测试点,如果你的程序遵守调用约定且正确的回答了每一个问题,

那么你将得到满分,否则得 0 分。

至少有 20 分的测试点中,M和 Q都不超过 10,000。

——————————————————————————————————————–

传说中的互交题。。。。。

互交的目的就是逼你用在线算法= =。

so

how.it.can.be.done?

其实灰常简单啊。。。

对于每个珠子开一数组 记录这个珠子有经过哪些交换器 询问的时候二分查就行了= =。

// 其实这个空间不怎么够。。 我用了vector动态分配空间- -、

——————————————————————————————————————–

#include <cstdio>

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstring>

#include <vector>

#include “beadslib.h”

using namespace std;

 

const int maxn = 300005;

struct point

{

int num, v;

};

vector<point> q[maxn];

int a[maxn], n, m;/*

int getNumQuestions()

{

return 1;

}

void getQuestion(int &num, int &now)

{

num = 50;

now = 10;

}

void answer(int ans)

{

cout << ans << endl;

}*/

int main()

{

freopen(“beads.in”, “r”, stdin);

freopen(“beads.out”, “w”, stdout);

cin >> n >> m;

for (int i = 1; i <= n; i++)

{

a[i] = i;

point p;

p.num = 0;

p.v = i;

q[i].push_back(p);

}

for (int i = 1; i <= m; i++)

{

int t;

scanf(“%d”, &t);

point p;

p.num = i;

p.v = t+1;

q[a[t]].push_back(p);

p.v = t;

q[a[t+1]].push_back(p);

swap(a[t], a[t+1]);

}

int k = getNumQuestions();

for (int i = 0; i < k; i++)

{

int num, now;

getQuestion(num, now);

int l = 0;

int r = q[num].size();

while (l+1 < r)

{

int mid = (l + r) / 2;

if (now < q[num][mid].num) r = mid;

else l = mid;

}

answer(q[num][l].v);

}

fclose(stdin);fclose(stdout);

}

 

 

——————————————————————————————————————–
免费道路 

                                                                      roads
新亚(New  Asia)王国有 N 个村庄,由 M 条道路连接。其中一些道路是鹅
卵石路,而其它道路是水泥路。保持道路免费运行需要一大笔费用,并且看上去
王国不可能保持所有道路免费。为此亟待制定一个新的道路维护计划。
国王已经决定保持尽可能少的道路免费,但是每两个不同的村庄之间都应该
由 由由 由一条 一条 一条 一条且仅由一条 且仅由一条 且仅由一条 且仅由一条免费道路的路径连接。同时,虽然水泥路更适合现代交通的需
要,但国王也认为走在鹅卵石路上是一件有趣的事情。所以,国王决定保持刚好
K 条鹅卵石路免费。
举例来说,假定新亚王国的村庄和道路如图 3(a)所示。如果国王希望保持两
条鹅卵石路免费,那么可以如图 3(b)中那样保持道路(1, 2)、(2, 3)、(3, 4)和(3, 5)
免费。该方案满足了国王的要求,因为:(1)每两个村庄之间都有一条由免费道
路组成的路径;(2)免费的道路已经尽可能少;(3)方案中刚好有两条鹅卵石道路
(2, 3)和(3, 4)。
psb (17)
图 3: (a)新亚王国中村庄和道路的一个示例。实线标注的是水泥路,虚线标注
的是鹅卵石路。(b)一个保持两条鹅卵石路免费的维护方案。图中仅标出了免
费道路。
任务 任务 任务 任务
给定一个关于新亚王国村庄和道路的描述以及国王决定保持免费的鹅卵石
道路数目,写一个程序确定是否存在一个道路维护计划以满足国王的要求,如果
存在则任意输出一个方案。
输入格式
  输入第一行包含三个由空格隔开的整数:
 N,村庄的数目(1≤N≤20,000);
 M,道路的数目(1≤M≤100,000);
 K,国王希望保持免费的鹅卵石道路数目(0≤K≤N – 1)。
此后 M 行描述了新亚王国的道路,编号分别为 1 到 M。第(i+1)行描述了第 i 条
道路的情况。用 3 个由空格隔开的整数描述:
 ui和 vi,为第 i 条道路连接的两个村庄的编号,村庄编号为 1 到 N;
 ci,表示第 i 条道路的类型。ci = 0 表示第 i 条道路是鹅卵石路,ci = 1 表
示第 i 条道路是水泥路。
输入数据保证一对村庄之间至多有一条道路连接。
输出格式
  如果满足国王要求的道路维护方案不存在,你的程序应该在输出第一行打印
no solution。
否则,你的程序应该输出一个符合要求的道路维护方案,也就是保持免费的
道路列表。按照输入中给定的那样输出免费的道路。如果有多种合法方案,你可
以任意输出一种。
输入样例 输入样例 输入样例 输入样例( (( (见图 见图 见图 见图 3(a)) )) )
5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1
输出样例 输出样例 输出样例 输出样例( (( (见图 见图 见图 见图 3(b)) )) )
3 2 0
4 3 0
5 3 1
1 2 1
时间和空间限制
你的程序必须在 1 秒钟内结束运行并且使用不超过 128MB内存。
评分 评分 评分 评分
  对于每组输入数据,如果你的程序输出正确便能得到 100%的分数,否则得 0
分。
  在 20 分的测试数据中,K 的值最多为 10。
———————————————————————————————————–
这题N年前做过了= =。找不到code就不贴了
这题用并查集 开始只连水泥的边
看下会有几个集
如果>k+1个集 就无解<!–显然。 因为这几个集都是要用鹅卵石连起来的。。
然后顺便搞一搞输出就行了= =、
——————————————————————————————————————–
DNA
                                                                        dna
分析如 DNA 序列这样的生命科学数据是计算机的一个有趣应用。从生物学
的角度上说,DNA 是一种由腺嘌呤、胞嘧啶、鸟嘌呤和胸腺嘧啶这四种核苷酸
组成的链式结构。这四种核苷酸分别用大写字母 A、C、G、T 表示。这样,一
条 DNA单链可以被表示为一个只含以上四种字符的字符串。我们将这样的字符
串称作一个 DNA序列。
有时生物学家可能无法确定一条 DNA单链中的某些核苷酸。在这种情况下,
字符 N将被用来表示一个不确定的核苷酸。换句话说,N可以用来表示 A、C、
G、T 中的任何一个字符。我们称包含一个或者多个 N 的 DNA序列为未完成序
列;反之,就称作完成序列。如果一个完成序列可以通过将一个未完成序列中的
每个 N任意替换成 A、C、G、T 得到的话,就称完成序列适合这个未完成序列。
举例来说,ACCCT 适合 ACNNT,但是 AGGAT 不适合。
  研究者们经常按照如下方式排序四种核苷酸:A 优先于 C,C 优先于 G,G
优先于 T。如果一个 DNA 序列中的每个核苷酸都与其右边的相同或者优先,就
将其归类为范式-1。举例来说,AACCGT 是范式-1,但是 AACGTC不是。
  一般来说,一个 DNA 序列属于范式-j ( j > 1),只要它属于范式-( j-1)或者是
一个范式-( j-1)和一个范式-1 的连接。举例来说,AACCC、ACACC和 ACACA
都是范式-3,但 GCACAC和 ACACACA不是。
  同样,研究者们按照字典序对 DNA 序列进行排序。按照这个定义,最小的
属于范式-3 的 DNA序列是 AAAAA,最大的是 TTTTT。这里是另外一个例子,
考虑未完成序列 ACANNCNNG。那么前 7 个适合这个未完成序列的 DNA 序列
是:
ACAAACAAG
ACAAACACG
ACAAACAGG
ACAAACCAG
ACAAACCCG
ACAAACCGG
ACAAACCTG
任务 任务 任务 任务
写一个程序,找到按字典序的第 R 个适合给定的长度为 M 的未完成序列的
范式-K。
输入格式 输入格式 输入格式 输入格式
  输入第一行包含三个由空格隔开的整数:M(1≤M≤50,000),K(1≤K≤10)和
R(1≤R≤2×1012
)。第二行包含一个长度为 M 的字符串,表示未完成序列。保证适
合该未完成序列的范式-K 的总数不超过 4×1018
,因此该数可以用 C 和 C++中的
long long类型或者 Pascal 中的 Int64 类型表示。同时,R不会超过适合给定未完
成序列的范式-K 的总数。
输出格式 输出格式 输出格式 输出格式
  在第一行中输出第 R个适合输入中的未完成序列的范式-K。
输入样例 输入样例 输入样例 输入样例 1
9 3 5
ACANNCNNG
输出样例 输出样例 输出样例 输出样例 1
ACAAACCCG
输入样例 输入样例 输入样例 输入样例 2
5 4 10
ACANN
输出样例 输出样例 输出样例 输出样例 2
ACAGC
编程提示 编程提示 编程提示 编程提示
在 C 和 C++中,你应该使用 long  long 数据类型。下面的程序片断给出了如
何从标准输入中读写 long long:
long long a;
scanf(“%lld”,&a);
printf(“%lld\n”,a);
 在 Pascal 中,你应该使用 Int64 类型。
时间和空间限制 时间和空间限制 时间和空间限制 时间和空间限制
你的程序必须在 1 秒钟内运行结束并且使用不超过 128MB内存。
评分 评分 评分 评分
  对于每组输入数据,如果你的程序输出正确便得到 100%的分数,否则得 0
分。
  在 20 分(20%)的测试数据中,M的值最多为 10。
 ———————————————————————————————
动归。or叫递推?。。
f[i][j][k]表示前i个 刚好有j个下降(即为最少范式j) 且第i个字符为k 有几种情况
最后就是可以求第某个是什么了~
——————————————————————————————————————–
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;
long long f[60000][20][10], n, m, r;
string s;
long long a[60000], b[60000][20][10];
string ans;
inline long long rtn(char c)
{
       if (c == ‘N’) return 0;
  else if (c == ‘A’) return 1;
  else if (c == ‘C’) return 2;
  else if (c == ‘G’) return 3;
  else if (c == ‘T’) return 4;
}
inline char ret(long long a)
{
       if (a == 1) return ‘A’;
  else if (a == 2) return ‘C’;
  else if (a == 3) return ‘G’;
  else if (a == 4) return ‘T’;
}
void doit()
{
  long long rank = r;
  long long no = m;
  for (long long i = 0; i < n; i++)
  {
    if (a[i] != 0)
    {
      ans += ret(a[i]);
      if (ret(a[i]) < ans[ans.size()-2]) –no;
      continue;
    }
    long long now = 0;
    for (long long j = 1; j <= 4; j++)
    {
      long long nowno = ret(j) < ans[ans.size()-1]? no-1 : no;
      now += b[i][nowno][j];
      if (now >= r)
      {
        ans += ret(j);
        no = nowno;
        r -= now – b[i][nowno][j];
        break;
      }
    }
  }
}
int main()
{
freopen(“dna.in”, “r”, stdin);
freopen(“dna.out”, “w”, stdout);
  cin >> n >> m >> r;
  cin >> s;
  for (long long i = 0; i < s.size(); i++) a[i] = rtn(s[i]);
  if (a[n-1] == 0) for (long long k = 1; k <= 4; k++) f[n-1][1][k] = 1;
  else f[n-1][1][a[n-1]] = 1;
  for (long long i = n-2; i >= 0; i–)
    for (long long j = 1; j <= m; j++)
      for (long long k = 1; k <= 4; k++)
      if (a[i] != 0 && a[i] != k) continue;
      else
      {
        for (long long l = 1; l < k; l++) f[i][j][k] += f[i+1][j-1][l];
        for (long long l = k; l <= 4; l++) f[i][j][k] += f[i+1][j][l];
      }
  for (long long i = 0; i < n; i++)
    for (long long j = 1; j <= 4; j++)
      for (long long k = 1; k <= m; k++) b[i][k][j] = b[i][k-1][j]+f[i][k][j];
  doit();
  cout << ans << endl;
fclose(stdin);fclose(stdout);
}

APOI——07·题解

第 1题

风铃(Mobiles)
输入文件:mobiles.in
输出文件:mobiles.out
时间限制:1 秒   内存限制:32M
你准备给弟弟 Ike 买一件礼物,但是,Ike 挑选礼物的方式很特别:他只喜
欢那些能按照他的特有方式排成有序的东西。
你准备给Ike 买一个风铃。风铃是一种多层的装饰品,一般挂在天花板上。
每个风铃都包含一些由竖直的线连起来的水平杆。每根杆的两端都有线连接,下
面或者挂着另一根水平杆,或者挂着一个玩具。下面是一个风铃的例子:

psb (5)

 

为使你的弟弟满意,你需要选一个满足下面两个条件的风铃:
(1) 所有的玩具都在同一层(也就是说, 每个玩具到天花板之间的杆的个数是
一样的)或至多相差一层。
(2) 对于两个相差一层的玩具,左边的玩具比右边的玩具要更靠下一点。
风铃可以按照下面的规则重新排列:任选一根杆,将杆两端的线“交换” 。
也就是解开一根杆左右两端的线,然后将它们分别绑到杆的另一端。注意这个操
作不会改变下面的杆上线的排列顺序。
由于你正在参加信息学奥林匹克的训练,所以你决定设计一个算法,判断能
否通过重新排列,将一个给定的风铃变为 Ike喜欢的样子。
考虑上面的例子,上图中的风铃满足条件(1),却不满足条件(2)——最左边
的那个玩具比它右边的要高。
但是,我们可以通过下面的步骤把这个风铃变成一个 Ike喜欢的形式:
1.  第一步,将杆 1 的左右两端交换,这使得杆 2 和杆 3 的位置互换,交换
的结果如下图所示:

psb (6)

 

2.  第二步,也是最后一步,将杆 2 的左右两端交换,这使得杆 4 到了左边,
原来在左边的玩具到了右边,交换的结果如下图所示:

psb (7)

 

现在这个风铃就满足 Ike 的条件了。
你的任务是:给定一个风铃的描述,求出最少需要多少次交换才能使这个风
铃满足 Ike的条件(如果可能的话)。
输入
输入的第一行包含一个整数 n (1≤ n ≤ 1 00 000),表示风铃中有多少根杆。
接下来的 n 行描述杆的连接信息。这部分的第 i 行包含两个由空格分隔的整
数 li和 ri,描述杆 i 的左右两端悬挂的东西。如果挂的是一个玩具,则对应的值
为-1,否则为挂在下面的杆的编号。
如果杆 i 下面挂有其它杆,则这些杆的编号将严格大于 i。杆 1 位于风铃的
顶部。
输出
输出仅包含一个整数。表示最少需要多少次交换能使风铃满足Ike 的条件。
如果不可能满足,输出-1。
样例输入  样例输出
6                 2
2 3
-1 4
5 6
-1 -1
-1 -1
-1 -1
说明
上面的样例输入给出了前面描述的示例情形。
评分
对于每一个测试点,如果你得到了正确的结果,得到该测试点100%的分数,
否则得 0 分。
——————————————————————————————————————–
  这题略水啊。。
设较深的叶子的深度为h
  他是棵2X树 不妨设每个节点有个属性:
0:以这个节点为根的子树的叶子有高度为h和h-1的
1:以这个节点为根的子树的每个叶子高度都是h-1
2:以这个节点为根的子树的每个叶子高度都是h
对于一个节点 如果
l=0 r=0   ->                  return -1;            //无解
l=1 r=0   ->     ans++;  return 0;             //交换左右儿子
l=1 r=1   ->                  return 1;
l=1 r=2   ->     ans++;  return 0;            //交换左右儿子
l=2 r=0   ->                  return 0;
l=2 r=1   ->                  return 0;
l=2 r=2   ->                  return 2;
最后ans就是ans~~~
——————————————————————————————————————–
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int maxn = 200005;
struct point
{
  int l, r;
}a[maxn];
int abs(int a)
{
  return a < 0 ? -a : a;
}
int n, t1, ans, t2;
int dfs(int now, int t)
{
  int r1;
  if (a[now].l == -1)
  {
    if (t+1 == t1) r1 = 1;
    else r1 = 2;
  } else r1 = dfs(a[now].l, t+1);
  if (ans == -1) return 0;
  int r2;
  if (a[now].r == -1)
  {
    if (t+1 == t1) r2 = 1;
    else r2 = 2;
  } else r2 = dfs(a[now].r, t+1);
  if (ans == -1) return 0;
  if (r1 == 0 && r2 == 0)
  {
    ans = -1;
    return 0;
  }
  if (r1 == 0)
  {
    if (r2 == 2) ans++;
    return 0;
  }
  if (r2 == 0)
  {
    if (r1 == 1) ans++;
    return 0;
  }
  if (r1 == 1 && r2 == 1) return 1;
  else if (r1 == 2 && r2 == 2) return 2;
  else
  {
    if (r1 == 1) ans++;
    return 0;
  }
}
void get(int now, int t)
{
  if ((a[now].l == -1 || a[now].r == -1) && t+1 != t1 && t+1 != t2)
  {
    if (t1 == 0)
    {
      t1 = t+1;
    }
    else if (t2 == 0 && abs(t+1-t1) <= 1)
    {
      t2 = t+1;
      if (t1 > t2)
      {
        int k = t1;
        t1 = t2;
        t2 = k;
      }
    }
    else
    {
      ans = -1;
      return;
    }
  }
  if (a[now].l != -1) get(a[now].l, t+1);
  if (a[now].r != -1) get(a[now].r, t+1);
}
int main()
{
freopen(“mobiles.in”, “r”, stdin);
freopen(“mobiles.out”, “w”, stdout);
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) scanf(“%d%d”, &a[i].l, &a[i].r);
  t1 = 0;
  t2 = 0;
  ans = 0;
  get(1, 1);
  if (ans == -1)
  {
    cout << -1;
    fclose(stdin);fclose(stdout);
    return 0;
  }
  dfs(1, 1);
  cout << ans;
fclose(stdin);fclose(stdout);
}
——————————————————————————————————————–
第 2题
数据备份(Backup)
输入文件:backup.in
输出文件:backup.out
时间限制:1 秒   内存限制:32M
你在一家 IT 公司为大型写字楼或办公楼(offices)的计算机数据做备份。
然而数据备份的工作是枯燥乏味的, 因此你想设计一个系统让不同的办公楼彼此
之间互相备份,而你则坐在家中尽享计算机游戏的乐趣。
已知办公楼都位于同一条街上。你决定给这些办公楼配对(两个一组) 。每
一对办公楼可以通过在这两个建筑物之间铺设网络电缆使得它们可以互相备份。
然而,网络电缆的费用很高。当地电信公司仅能为你提供 K 条网络电缆,
这意味着你仅能为K对办公楼(或总计 2K个办公楼)安排备份。任一个办公楼
都属于唯一的配对组(换句话说,这2K个办公楼一定是相异的) 。
此外,电信公司需按网络电缆的长度(公里数)收费。因而,你需要选择这
K对办公楼使得电缆的总长度尽可能短。换句话说,你需要选择这K对办公楼,
使得每一对办公楼之间的距离之和(总距离)尽可能小。
下面给出一个示例,假定你有 5 个客户,其办公楼都在一条街上,如下图所
示。这 5 个办公楼分别位于距离大街起点 1km, 3km, 4km, 6km和 12km处。电信
公司仅为你提供 K=2 条电缆。

 psb (8)

上例中最好的配对方案是将第1 个和第 2 个办公楼相连, 第3个和第4个办

公楼相连。这样可按要求使用 K=2 条电缆。第 1 条电缆的长度是 3km―1km =

2km,第 2 条电缆的长度是 6km―4km = 2 km。这种配对方案需要总长4km的网

络电缆,满足距离之和最小的要求。

输入

输入的第一行包含整数n 和 k,其中n(2 ≤ n ≤100 000)表示办公楼的数目,

k(1≤ k≤ n/2)表示可利用的网络电缆的数目。

接下来的n 行每行仅包含一个整数(0≤ s ≤1000 000 000), 表示每个办公楼

 

到大街起点处的距离。这些整数将按照从小到大的顺序依次出现。

 

输出

输出应由一个正整数组成,给出将2K个相异的办公楼连成k 对所需的网络

电缆的最小总长度。

 

样例输入  样例输出

5 2               4

1

3

4

6

12

 

说明

上面的样例输入给出了前面描述的示例情形。

 

评分

对于每一个测试点, 如果写到输出文件中的答案正确, 则得到该测试点100%

的分数, 否则得零分。 30%的输入数据满足 n≤20。 60%的输入数据满足n≤10 000。

——————————————————————————————————————–

这题就不是那么好A了。。。

显然易证可知可得:

每条电线必然连接的是相邻的两栋楼 用反证法慢慢证去吧…

so 问题就变成 给一串数 取k个数 且不能相邻 求最小和 n<=10w

然后这题居然用的是费用流。。。。。。。。。。。。。。。。。

 

建图如下:

s连接所有单数点 费用为值 容量1

所有单数点连接相邻的双数点 费用0 容量1

所有双数点连接t  费用为值 容量1

 

求一个最小费用流

but but but but but but but but but but but

it’s too slow

– -。。

so 还要优化。。
用堆优化费用流听说过不?、
其实是这题独有的= =。
怎么优化就不说了。。 自己看年鉴去吧。。。
——————————————————————————————————————–
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const long long maxn = 200000;
const long long inf = 20*10000*10000+2;
struct point
{
  long long v, n;
}h[maxn];
struct pt
{
  long long l, r, v;
}p[maxn];
bool small(point a, point b){ return a.v > b.v; }
long long b[maxn], n, m, l[maxn];
int main()
{
freopen(“backup.in”, “r”, stdin);
freopen(“backup.out”, “w”, stdout);
  cin >> n >> m;
  long long k = 0;
  long long rr = 0;
  for (long long i = 0; i < n; i++)
  {
    scanf(“%d”, &l[i]);
    if (i != 0)
    {
      h[k].v = l[i]-l[i-1];
      h[k].n = k;
      if (k != 0)
      {
        p[k].l = k-1;
        p[k-1].r = k;
      }else p[k].l = -1;
      p[k].v = l[i]-l[i-1];
      k++;
    }
  }
  p[k-1].r = -1;
  make_heap(h, h+k, small);
  long long nb = k;
  long long ans = 0;
  for (long long i = 0; i < m; i++)
  {
    while (b[h[0].n]) { pop_heap(h, h+k, small); –k;}
    pop_heap(h, h+k, small);
    –k;
    long long num = h[k].n;
    ans += h[k].v;
    b[num] = 1;
    if (p[num].l == -1)
    {
      if (p[num].r != -1)
      {
        b[p[num].r] = 1;
        p[p[p[num].r].r].l = -1;
      }
      continue;
    }
    if (p[num].r == -1)
    {
      if (p[num].l != -1)
      {
        b[p[num].l] = 1;
        p[p[p[num].l].l].r = -1;
      }
      continue;
    }
    b[p[num].l] = 1;
    b[p[num].r] = 1;
    h[k].v = p[p[num].l].v+p[p[num].r].v-p[num].v;
    nb++;
    p[nb].l = p[p[num].l].l;
    p[nb].r = p[p[num].r].r;
    p[nb].v = h[k].v;
    p[p[p[num].l].l].r = nb;
    p[p[p[num].r].r].l = nb;
    h[k].n = nb;
    k++;
    push_heap(h, h+k, small);
  }
  cout << ans;
  fclose(stdin);fclose(stdout);
}
——————————————————————————————————————–
ps: 这里用到了C++ STL的heap 就是堆。。。
——————————————————————————————————————–
第 3题
动物园(Zoo)
输入文件:zoo.in
输出文件:zoo.out
时间限制:2 秒   内存限制:16M
新建的圆形动物园是亚太地区的骄傲。 圆形动物园坐落于太平洋的一个小岛
上,它包含一大圈围栏,每个围栏里有一种富有异国风情的动物。如下图所示:
 psb (9)
你是动物园的公关主管。你要做的是,让每个参观动物园的游客都尽可能高
兴。今天有一群小朋友来到动物园参观,你希望能让他们在动物园度过一段美好
的时光。但这并不是一件容易的事——有些小朋友喜欢某些动物,而有些小朋友
则害怕某些动物。例如,Alex喜欢可爱的猴子和考拉,而害怕张牙舞爪的狮子。
而 Polly会因狮子有美丽的鬃毛而喜欢它,但害怕有臭味的考拉。
你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。 但你移走的动
物也不能太多,否则留给小朋友们观赏的动物就所剩无几了。
每个小朋友站在大围栏圈的外面,可以看到连续的5 个围栏。你得到了所有
小朋友喜欢和害怕的动物信息。当出现下面两种情形之一时,小朋友就会高兴: z  至少有一个他害怕的动物(从视线可见的范围内)被移走,或z  至少有一个他喜欢的动物没有被(从视线可见的范围内)移走。 

例如,考虑下图中的小朋友和动物:

 

psb (11)

假如你将围栏 4 和 12 的动物移走。Alex 和 Ka-Shu 将很高兴,因为至少有

一个他们害怕的动物被移走了。这也会使 Chaitanya 高兴,因为他喜欢的围栏 6

和 8 中的动物都保留了。但是,Polly 和 Hwan 将不高兴,因为他们看不到任何

他们喜欢的动物, 而他们害怕的动物都还在。 这种安排方式使得三个小朋友高兴。

现在换一种方法,如果你将围栏 4 和 6 中的动物移走,Alex和 Polly将很高

兴,因为他们害怕的动物被移走了。Chaitanya 也会高兴,因为虽然他喜欢的动

物 6 被移走了,他仍可以看到围栏8 里面他喜欢的动物。同样的 Hwan 也会因可

以看到自己喜欢的围栏 12 里的动物而高兴。唯一不高兴的只有 Ka-Shu。

如果你只移走围栏 13 中的动物,Ka-Shu 将高兴,因为有一个他害怕的动物

被移走。Alex, Polly, Chaitanya和Hwan 也会高兴,因为他们都可以看到至少一

个他们喜欢的动物。 所以有 5 个小朋友会高兴。 这种方法使得最多的小朋友高兴。

 

输入

输入的第一行包含两个整数 N, C,用空格分隔。N是围栏数(10≤N≤10 000),

C是小朋友的个数(1≤C≤50 000)。围栏按照顺时针的方向编号为 1,2,3,…,N。

接下来的 C行,每行描述一个小朋友的信息,以下面的形式给出:

 

E F L X1 X2  … XF Y1 Y2  … YL

其中:

E 表示这个小朋友可以看到的第一个围栏的编号(1≤E≤N),换句话说,该小

朋友可以看到的围栏为 E, E+1, E+2, E+3, E+4。注意,如果编号超过 N将继续从

1 开始算。如:当 N=14, E=13 时,这个小朋友可以看到的围栏为 13,14,1, 2 和 3

F表示该小朋友害怕的动物数。L表示该小朋友喜欢的动物数。

围栏X1, X2,  …, XF 中包含该小朋友害怕的动物。

围栏 Y1, Y2,  …, YL  中包含该小朋友喜欢的动物。

X1, X2,  …, XF, Y1, Y2,  …, YL是两两不同的整数,而且所表示的围栏都是该小

朋友可以看到的。

小朋友已经按照他们可以看到的第一个围栏的编号从小到大的顺序排好了

(这样最小的E对应的小朋友排在第一个, 最大的E对应的小朋友排在最后一个)

注意可能有多于一个小朋友对应的 E是相同的。

 

输出

仅输出一个数,表示最多可以让多少个小朋友高兴。

 

说明

上面的样例 1 给出了前面描述的示例情形。它使得所有小朋友(C=5)高兴。

样例 2 给出了这样的情形,要使得所有小朋友(C=7)都高兴是不可能的。

评分

对于每一个测试点,如果你的答案正确,则该测试点得满分,否则得 0 分。

 

——————————————————————————————————-

经典状压。。。<其实我没压 = =。。>

f[i][state]表示以i结尾  状态为state的max小盆友数

随便7推8推一下··

but

它是一个圈 这略坑啊

我用一个很sb的枚举前5个点解决 -慢死。。。

——————————————————————————————————————–

 

#include <cstdio>

#include <iostream>

#include <queue>

#include <cstring>

#include <vector>

struct point

{

int e, u, l;

int un[10], li[10];

}p[50005];

using namespace std;

int n, m, a[2][2][2][2][2][2], now, last;

inline int ad(int a, int b)

{

return a+b > n ? a+b-n : a+b;

}

inline int de(int a, int b)

{

return a-b <= 0 ? a-b+n : a-b;

}

inline bool init(int a, int b)

{

if (b <= a) return b >= a-4;

else return n-(5-a) < b;

}

inline int get(int a, int b)

{

if (b <= a) return 4-(a-b);

else return b-(n-(5-a))-1;

}

inline bool check(int now, int s1, int s2, int s3, int s4, int s5, point a)

{

int k[5] = {s1, s2, s3, s4, s5};

for (int i = 0; i < a.u; i++)

if (init(now, a.un[i])) if (k[get(now, a.un[i])] == 0) return true;

for (int i = 0; i < a.l; i++)

if (init(now, a.li[i])) if (k[get(now, a.li[i])] == 1) return true;

return false;

}

int main()

{

freopen(“zoo.in”, “r”, stdin);

freopen(“zoo.out”, “w”, stdout);

cin >> n >> m;

int i;

int no = 0;

int la = 1;

for (i = 0; i < m; i++)

{

scanf(“%d%d%d”, &p[i].e, &p[i].u, &p[i].l);

for (int j = 0; j < p[i].u; j++) scanf(“%d”, &p[i].un[j]);

for (int j = 0; j < p[i].l; j++) scanf(“%d”, &p[i].li[j]);

}

int j = 0;

int ans = 0;

bool br = true;

int ss[10];

for (int ss1 = 0; ss1 < 2; ss1++)

for (int ss2 = 0; ss2 < 2; ss2++)

for (int ss3 = 0; ss3 < 2; ss3++)

for (int ss4 = 0; ss4 < 2; ss4++)

for (int ss5 = 0; ss5 < 2; ss5++)

{

ss[0] = ss1;

ss[1] = ss2;

ss[2] = ss3;

ss[3] = ss4;

ss[4] = ss5;

int j = 0;

memset(a, 0, sizeof(a));

bool br = true;

int bbb = true;

for (i = 5; bbb || i <= 4; i < n ? i++ : (i = 1, bbb = false))

{

int k = j-1;

int bb = false;

while (k < m-1 && ad(p[k+1].e, 4) == i) k++;

for (int s1 = de(i, 4) <= 5 ? ss[de(i, 4)-1] : 0; s1 <= (de(i, 4) <= 5 ? ss[de(i, 4)-1] : 1); s1++)

for (int s2 = de(i, 3) <= 5 ? ss[de(i, 3)-1] : 0; s2 <= (de(i, 3) <= 5 ? ss[de(i, 3)-1] : 1); s2++)

for (int s3 = de(i, 2) <= 5 ? ss[de(i, 2)-1] : 0; s3 <= (de(i, 2) <= 5 ? ss[de(i, 2)-1] : 1); s3++)

for (int s4 = de(i, 1) <= 5 ? ss[de(i, 1)-1] : 0; s4 <= (de(i, 1) <= 5 ? ss[de(i, 1)-1] : 1); s4++)

for (int s5 = de(i, 0) <= 5 ? ss[de(i, 0)-1] : 0; s5 <= (de(i, 0) <= 5 ? ss[de(i, 0)-1] : 1); s5++)

{

a[no][s5][s4][s3][s2][s1] = max(a[la][s4][s3][s2][s1][1], a[la][s4][s3][s2][s1][0]);

if (br)

for (int l = j; l <= k; l++)                //很壮观的12重for有木有~~~~~~

if (check(i, s1, s2, s3, s4, s5, p[l]))

++a[no][s5][s4][s3][s2][s1];

if (ans < a[no][s5][s4][s3][s2][s1]) ans = a[no][s5][s4][s3][s2][s1];

}

j = k+1;

no = no ^ 1;

la = la ^ 1;

}

}

cout << ans;

fclose(stdin);fclose(stdout);

}

——————————————————————————————————————–