思路

这题要求的是带负权边的最短路，显然不能直接用Dijkstra。然而Bellman-Ford或SPFA的时间复杂度最坏$O(NM)$，而且众所周知，USACO总是卡SPFA的。尽管这题数据比较老，因此SPFA+SLF可以水过，但是正解并不是如此。

顺便说一下，用优先队列优化SPFA并不有效(来自[模板]单源最短路-题解)，在这题比普通SPFA更慢。然而在某些边权为正的卡SPFA的图中，几乎和Dijkstra不相上下。

可以发现，图有一个很强的性质：对于无向边，边权总是正的，因此每个无向边联通块是强联通的。而可能的负权边保证不能反向联通，因此把无向边联通块缩点后，得到的就是DAG。这样就可以在块内使用Dijkstra，块间利用拓扑排序更新答案。时间复杂度$O(M\log N)$。

1.穿越马路

30%

$C,N\le10$

这么小的数据，应该随便怎么搜索都可以吧。我没有写过。

60%

$C,N\le500$

直接二分图最大匹配，用匈牙利算法，应该是提高组要求。输出方案只要输出match[]数组。时间复杂度近似是$N^3$的，应该很容易得到这个分。

题目来源或改编自USACO月赛，顺序与难度无关。

题目概述

注意事项

1. 请注意题目的数据大小，根据情况适当地使用输入/输出优化。
2. 数据范围中，如果没有说明，前面的数据满足后面的要求。
3. 对于有部分分的题目，如果你只做了其中一问，也要按照格式要求输出所有内容；否则无法保证得分。

题目来源于USACO月赛，数据范围有所加强

题目概述

注意事项

1. 所有题目中程序允许创建临时文件(仅供参考)。在C/C++中建议使用tmpfile函数创建临时文件，在关闭文件后将自动删除。

   1 2 3 4 5 6

   #include<stdio.h> FILE *tmpfile( void ); //C #include<cstdio> std::FILE* std::tmpfile(); //C++

2. 新挑战*为附加题，同时测试交互题的情况。

3. 对于#标的题，请注意常数因子对于程序效率的影响(标程最长运行时间超过时限的一半)。

题目描述

翻译都很乱，我自己翻译题目

给出一个COWBASIC程序，所有运算对$10^9+7$取模，求返回的结果。

COWBASIC语言

• 有三种语句：

1
2
3
4
5
6
7

<变量名> = <表达式>

<字面值> MOO {
<语句列表>
}

RETURN <变量名>

• 变量名为长度不超过10的小写字符串
• 字面值为不超过100000的正整数
• 语句列表为一个或多个语句
• 有三种表达式：

1
2
3
4
5

<字面值>

<变量名>

( <表达式> ) + ( <表达式> )

• 保证表达式中或返回的变量在使用前已经定义

• 保证返回在程序最后一行

  阅读全文 »

参考ZJOI2017 Day2讲课《动态传递闭包问题的探究》

题目：洛谷P2881 [USACO07MAR]排名的牛Ranking the Cows

总体思路

分析

给定n($n\le1000$)个数的m($m\le10000$)个大小关系，求出最少增加几个大小关系才可以给这些数排序。

很明显，如果没有任何已知关系，答案为$C_n^2=\frac{n*(n-1)}{2}$。要计算已知的关系能使答案减小的值，可以使用传递闭包，一般常用Floyd。

但是由于$n\le1000$，$O(n^3)$不能通过，那么怎么做呢？

改进Floyd

以下来自课件

$t_{i,j}^{(k)}$表示i和j经过前k个点是否连通。

定义集合$T_i^{(k)}=\{j\vert t_{i,j}^{(k)}=1\}$

对于$k\ge1$，有

用bitset或手动压位，可以在$O(\frac{n^3}{w})$求出传递闭包，其中w表示字长，为64或32。

来自WC的小技巧，Pascal不支持

适用范围

仅适用于计算$2^n$的精确值，且$\left\vert n\right\vert<2^{14}$

浮点数能精确表示$2^n$，因为大部分浮点数内部都以2为底数，n的范围与浮点数类型有关。常用浮点数最高精度的long double也只有15位阶码。

使用方法

直接使用pow函数即可计算。

C++

1
2
3
4
5
6
7
8
9
10

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	cout.precision(n>0?0:-n);
	cout<<fixed<<pow(2.0L,n)<<endl;
	return 0;
}

思路

整体

首先，我们可以知道，要满足题意，两个正方形的坐标$(x_i,y_i)(x_j,y_j)$必须满足$\vert x_i-x_j\vert<k$并且$\vert y_i-y_j\vert<k$。如果有且仅有一组正方形满足条件，那么重叠部分的面积$ans=\vert k-(x_i-x_j)\vert\times\vert k-(y_i-y_j)\vert$。

最简单的方法是直接暴力扫描，时间复杂度为$O(n^2)$。

我本来打算写一个二维线段树的，但好像有些大材小用了，难度才提高啊。

根据官方题解，先对所有点排序，然后维护与当前点横坐标差值小于k的所有点的集合，每次查找点集中纵坐标最接近当前点的点，更新答案即可。

如何维护所有满足条件的点呢？因为点是有序的，满足$x_i\le x_{i+1}$，每次只需将无效的点删除即可。

问题描述

这是最为人知的跨平台问题之一

平台

• 在Windows下，我们一般使用mingw-gcc，一般使用MSVC风格的I/O
• 在Linux下，我们使用原生的gcc，一般使用GNU/ISO风格的I/O

表现

• 64位整数的I/O问题(signed/unsigned long long)
  • Windows下只能使用%I64d，%I64u
  • Linux下使用%lld，%llu

• 扩展精度浮点数的I/O问题(long double)

  • Windows下无法输入/输出long double类型，因为在MSVC中，long double==double
  • Linux下使用%Lf，%Lg，%Le等
  阅读全文 »

使用C的随机数

实现

C中随机数函数非常简单，定义在<stdlib.h>中：

• 1	void srand(unsigned seed);

  将随机种子设为seed ；相同的种子将获得相同的随机数序列，只要在程序开始初始化即可。

• 1	int rand();

  返回[0,RAND_MAX]之间的伪随机数。