NOIP模拟 6.30

Problem 1 护花(flower.cpp/c/pas)

【题目描述】

约翰留下他的N(N<=100000)只奶牛上山采木．他离开的时候，她们像往常一样悠闲地在草场里吃草．可是，当他回来的时候，他看到了一幕惨剧：牛们正躲在他的花园里，啃食着他心爱的美丽花朵！为了使接下来花朵的损失最小，约翰赶紧采取行动，把牛们送回牛棚．牛们从1到N编号．第i只牛所在的位置距离牛棚Ti(1≤Ti≤2000000)分钟的路程，而在约翰开始送她回牛棚之前，她每分钟会啃食Di(1≤Di≤100)朵鲜花．无论多么努力，约翰一次只能送一只牛回棚．而运送第第i只牛事实上需要2Ti分钟，因为来回都需要时间．写一个程序来决定约翰运送奶牛的顺序，使最终被吞食的花朵数量最小．

【输入格式】

第1行输入N，之后N行每行输入两个整数Ti和Di

【输出格式】

一个整数，表示最小数量的花朵被吞食

【样例输入】

3 1

2 5

2 3

3 2

4 1

1 6

【样例输出】

【样例解释】

约翰用6，2，3，4，1，5的顺序来运送他的奶牛

按D/T排序，证明相邻的交换过来不会比原来更优即可。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <queue>
 8 inline void read(long long &x)
 9 {
10     x = 0;char ch = getchar();char c = ch;
11     while(ch > '9' || ch < '0')c = ch, ch = getchar();
12     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0',ch = getchar();
13     if(c == '-')x = -x; 
14 }
15 const long long MAXN = 1000000 + 10;
16 const int INF = 0x3f3f3f3f;
17 
18 long long n,T[MAXN],D[MAXN],cnt[MAXN];
19 
20 bool cmp(long long a, long long b)
21 {
22     return D[a] * T[b] > D[b] * T[a];
23 }
24 
25 long long ans;
26 long long sum;
27 
28 int main()
29 {
30     read(n);
31     for(register long long i = 1;i <= n;++ i)
32     {
33         read(T[i]);read(D[i]);
34         cnt[i] = i;
35         sum += D[i];
36     }
37     std::sort(cnt + 1, cnt + 1 + n, cmp);
38     for(register long long i = 1;i <= n;++ i)
39     {
40         sum -= D[cnt[i]];
41         ans += ((long long)(sum * T[cnt[i]]) << 1);
42     }
43     printf("%lld", ans);
44     return 0;
45 }

View Code

Problem 2 修剪草坪(mowlawn.cpp/c/pas)

【题目描述】

在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，
新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。
然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N(1 <= N <= 100,000)只排成一排的奶牛，编号为1...N。每只奶牛的效率是不同的，奶牛i的效率为E_i(0 <= E_i <= 1,000,000,000)。靠近的奶牛们很熟悉，因此，如果FJ安排超过K（1<=K<=N）只连续的奶牛，那么，这些奶牛就会罢工去开派对:)。因此，现在FJ需要你的帮助，计算FJ可以得到的最大效率，并且该方案中没有连续的超过K只奶牛。

【输入格式】
* 第一行：空格隔开的两个整数N和K
* 第二到N+1行：第i+1行有一个整数E_i

【输出格式】
* 第一行：一个值，表示FJ可以得到的最大的效率值。

【样例输入】

5 2

输入解释：

FJ有5只奶牛，他们的效率为1，2，3，4，5。他们希望选取效率总和最大的奶牛，但是

他不能选取超过2只连续的奶牛

【样例输出】

FJ可以选择出了第三只以外的其他奶牛，总的效率为1+2+4+5=12。

神奇的dp。

f[i]表示1..i只奶牛不选第i只的最小损耗

初始状态f[0] = 0

转移f[i] = min{f[j]} + e[i],其中（i - j - 1 <= k）

维护一个单调递增队列，从队首取最小元素，新元素加到队尾并维持单调性，每次取队首元素时检查是否合法(即i - j - 1 <= k)

此题开longlong，注意INF的取值，所以以后尽量手写一层，不要用INF

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <algorithm>
 6 #include <vector>
 7 #include <queue>
 8 inline void read(long long &x)
 9 {
10     x = 0;char ch = getchar();char c = ch;
11     while(ch > '9' || ch < '0')c = ch, ch = getchar();
12     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0',ch = getchar();
13     if(c == '-')x = -x; 
14 } 
15 const long long INF = 0x3f3f3f3f3f3f3f3f;
16 const int MAXN = 1000000 + 10;
17 inline long long max(long a, long b){return a > b ? a : b;}
18 inline long long min(long a, long b){return a < b ? a : b;}
19 
20 long long n,k,e[MAXN];
21 long long ans;
22 
23 long long q1[MAXN << 1], q2[MAXN << 1],head, tail;
24 long long f[MAXN]; 
25 
26 int main()
27 {
28     read(n);read(k);
29     for(register long long i = 1;i <= n;++ i)
30         read(e[i]),ans += e[i];
31     
32     head = tail = 1;//队列表示的范围：[head,tail] 
33     q1[1] = q2[1] = 0;
34     for(register int i = 1;i <= n;++ i)
35     {
36         while(i - q2[head] - 1 > k)head ++;
37         f[i] = e[i] + q1[head];
38         while(q1[tail] >= f[i] && head <= tail)tail--;
39         q1[++ tail] = f[i];
40         q2[tail] = i;
41     }
42     long long tmp = INF;
43 //最好改为tmp = f[n - k];
44     for(register int i = n - k;i <= n;++ i)
45     {
46         tmp = min(tmp, f[i]);
47     }
48     printf("%lld", ans - tmp);
49     return 0;
50 }

View Code

Problem 3 虫洞(wormhole.cpp/c/pas)

【题目描述】

John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边）连接着N （从1..N标号）块地，并有W个虫洞（有向边）。其中1<=N<=500,1<=M<=2500,1<=W<=200。现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。

【输入格式】

* Line 1: 一个整数 F, 表示农场个数。

* Line 1 of each farm: 三个整数 N, M, W。

* Lines 2..M+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条用时T秒的小路。

* Lines M+2..M+W+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地中间有一条可以使John到达T秒前的虫洞。

【输出格式】

* Lines 1..F: 如果John能在这个农场实现他的目标，输出"YES",否则输出"NO"。

【样例输入】

3 3 1

1 2 2

1 3 4

2 3 1

3 1 3

3 2 1

1 2 3

2 3 4

3 1 8

【样例输出】

YES

此虫洞非彼虫洞，明显简单一大截。

SPFA找负环即可，题意描述不够明确。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cstring>
  5 #include <algorithm>
  6 #include <vector>
  7 #include <queue>
  8 inline void read(int &x)
  9 {
 10     x = 0;char ch = getchar();char c = ch;
 11     while(ch > '9' || ch < '0')c = ch, ch = getchar();
 12     while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0',ch = getchar();
 13     if(c == '-')x = -x; 
 14 } 
 15 inline int max(int a, int b){return a > b ? a : b;}
 16 inline int min(int a, int b){return a < b ? a : b;}
 17 inline void swap(int &a, int &b){int tmp = a;a = b;b = tmp;} 
 18 
 19 const int INF = 0x3f3f3f3f;
 20 const int MAXN = 5000 + 10;
 21 const int MAXE = 25000 + 10;
 22 const int MAXW = 2000 + 10;
 23 
 24 int t; 
 25 int n,m,w;
 26 
 27 struct Edge
 28 {
 29     int u,v,w,next;
 30 }edge[(MAXE << 1) + MAXW];
 31 int head[MAXN],cnt;
 32 
 33 inline void insert(int a, int b, int c)
 34 {
 35     edge[++cnt] = Edge{a,b,c,head[a]};
 36     head[a] = cnt;
 37 }
 38 
 39 std::queue<int> q;
 40 int b[MAXN], d[MAXN], cot[MAXN];
 41 
 42 inline int SPFA(int s)
 43 {
 44     memset(b, 0, sizeof(b));
 45     memset(d, 0x3f, sizeof(d));
 46     memset(cot, 0, sizeof(cot));
 47     q.push(s);
 48     d[s] = 0;
 49     b[s] = true;
 50     cot[s] ++;
 51     register int u,v;
 52     while(!q.empty())
 53     {
 54         u = q.front();
 55         q.pop();
 56         b[u] = false;
 57         for(register int pos = head[u];pos;pos = edge[pos].next)
 58         {
 59             v = edge[pos].v;
 60             if(d[v] > d[u] + edge[pos].w)
 61             {
 62                 d[v] = d[u] + edge[pos].w;
 63                 if(!b[v])
 64                 {
 65                     b[v] = true;
 66                     q.push(v);
 67                     cot[v] ++;
 68                     if(cot[v] >= n)return 0;
 69                 }
 70             }
 71         }
 72     }
 73     return 1;
 74 } 
 75 
 76 int main()
 77 {
 78     read(t);
 79     register int tmp1,tmp2,tmp3;
 80     for(;t;--t)
 81     {
 82         read(n);read(m);read(w);
 83         memset(edge, 0, sizeof(edge));
 84         memset(head, 0, sizeof(head));
 85         cnt = 0;
 86         for(register int i = 1;i <= m;++ i)
 87         {
 88             read(tmp1);read(tmp2);read(tmp3);
 89             insert(tmp1, tmp2, tmp3);
 90             insert(tmp2, tmp1, tmp3);
 91         }
 92         for(register int i = 1;i <= w;i ++)
 93         {
 94             read(tmp1);read(tmp2);read(tmp3);
 95             insert(tmp1, tmp2, -1 * tmp3);
 96         }
 97         if(!SPFA(1))
 98         {
 99             printf("YES
");
100         }
101         else
102         {
103             printf("NO
");
104         }
105     }
106     return 0;
107 }

View Code

T4暴力模拟没意思。。。不上了