7.4总结

得分情况

估分：

100+100+10=210

实际：

100+100+62.5=262.5

Rank9

海星…

怎么T3被切穿了呀，还以为没人会做呢

还好暴力水了62.5分

T1

题目大意

当一个数字不包含长度大于1的子回文数字时称为非回文数字。例如，16276是非回文数字，但17276不是，因为它包含回文数字727。你的任务是在一个给定的范围内计算非回文数字的总数。

100%的数据：0<=a<=b<=10^18

正解

显然是数位dp嘛。但是有18位，回文串最长有18位，难道要开18维的数组？

想了想不会做，打暴力。

打暴力的时候忽然发现，判断一个串包不包含回文串只用判断一个a[i]是否与a[i-1]或a[i-2]相等就好了。

这样就只用记录两位了呀

设f[i][0/1][x1][x2][0/1]表示放到第i位，是否已有回文串，第i位数，第i-1位数，是否达到上限。

还要考虑前导零的问题，要不然010这种串会被认为是回文串

赋初值的时候枚举数字开始的那一位i设，枚举前两位，就可以完美避免前导零的干扰了

话说T1的题解挺妙的

进行数位 DP 的一般方法
设 x 表示除了数位 i 以外的状态，本题是 p,q。若求区间[l,r]之间的答案，我
们用[0,r]的答案减去[0,l-1]的答案。下文“原串”表示这里的 r 或者 l-1。我们就
是要保证 DP 到的状态都小于等于原串。
方法 1
顺推，设状态 f(i,x,k)，k=0（表示 1~i-1 位都和原串一样）或 1（有至少一位
小于原串）。枚举第 i 位数字 c，若 k=0，则 c≤原串第 i 位，否则 c≤9，若 i 为
数字的开头则保证 c>0。按情况转移即可。
方法 2
先逆推，设状态 f(i,x)，表示 i 位数符合情况的所有答案，不必考虑和原串
的关系。注意逆推时 x 的定义可能稍有变化，比如本题 p,q 不再表示最右侧数字
而表示最左侧。然后顺序扫描一遍，同理枚举 c<原串第 i 位，然后对于所有 1~i-1
位与原串相同，第 i 位为 c 的答案都包含在 f(n-i,x)中。统计求和即可。

By

我一直都是用方法1…

原来还有方法二…

长见识了

T2

题目大意

Hotham的淡水存储在N个水库，由M个管道连接。
任意2个水库之间至少有一条路径，该路径可能包含多个管道。每个管道连接两个不同的水库，任何两个水库之间最多只有一个管道。Jester破坏了一些管道进行排水。管道的排水量为偶数立方米/秒。如果连接水库u和水库v的管道排水量为2D立方米/秒，那么水库u和水库v排水量分别为D立方米/秒。Jester可以也破坏一些管道进行注水。同样，连接水库u和v的管道注入水量为2P立方米/秒，则水库u和水库v注水量分别为P立方米/秒。
每个水库供水量的净变化是由连接到它的管道的排水量和注水量的总和。如果连接该水库的管道排水量分别为2D1, 2D2,…,2Da立方米/秒, 注水量分别为2P1, 2P2 ,…,2Pb 立方米/秒。该水库水量的净变化为P1 + P2 + ... + Pb -D1 - D2 –Da。
Hotham市长已在水库安装了传感器，但不是在管道中。因此，他可以观察到在每个水库水的净变化，但并知道有多少水被排出或注入各个管道。
给出水管连接图和每个水库供水量的净变化，编写程序决定这些信息是否能确定一个唯一的计划。如果各个水管排出或注入的水量是唯一的，那么该计划可以被唯一确定。请注意，并不是每一个水管中的注水量和排水量都相等。如果恰好有一个可能性，你的程序应该打印出来。

每个点的权值等于与它相连的边的权值之和除以二。这不就是高斯消元嘛。看看数据范围（往下翻往下翻…）

1<=N<=100 000

1<=M<=500 000

打扰了（往上翻往上翻…）

正解

有M个未知数，N条方程，若M<N则一定没有唯一解。

所以分M=N-1和M=N两种情况来讨论。

1.M=N-1时

一颗树嘛…

叶子节点到父亲的边很容易求，求完之后叶子的父亲往上的边也好求…

于是从叶子往上推一下就好了

2.M=N时

一个环套树嘛…

首先把环拎出来，把环上的边删掉，剩下很多棵树可以像上面一样搞。

如果是偶环则无解，推一下式子可以发现。

如果是奇环，就列方程解一下就好了。（废话）

花絮:

打完第一题很激动，交到第二题去了，过一会xzb问我第二题怎么拿的18分（汗）

T3

题目大意

Farmer John的N(1<=N<=1000)头奶牛分别居住在农场所拥有的B(1<=B<=20)个牛棚的某一个里。有些奶牛很喜欢她们当前住的牛棚，而另一些则讨厌再在它们现在所在的牛棚呆下去。
FJ在忍受了若干次奶牛的抱怨后，决定为所有奶牛重新安排牛棚，使最不满的那头奶牛与最高兴的奶牛的心情差异最小，即使这会让所有奶牛都更加郁闷。
每头奶牛都把她对各个牛棚的好感度从高到低排序后告诉了FJ。当然，如果一头奶牛被安排到的牛棚在她给出的列表中越靠后，她就会越郁闷。你可以认为奶牛的郁闷指数是她被分配到的牛棚在列表中的位置。奶牛们是斤斤计较的，她们无法容忍别的奶牛在自己喜欢的牛棚里快乐地生活，而自己却呆在一个自己不喜欢的牛棚里。每个牛棚都只能容纳一定数量的奶牛。FJ希望在每个牛棚都没有超出容量限制的前提下，使最郁闷和最高兴的奶牛的郁闷指数的跨度最小。
FJ请你帮他写个程序，来计算这个最小的郁闷指数跨度到底是多少。

最多人切的题目。

我考场上没想到，只打了个暴力水62.5分