T1 Cow Poetry
Description
不为Farmer John所知的是，Bessie还热衷于资助艺术创作！最近，她开始研究许多伟大的诗人们，而现在，她想要尝试创作一些属于自己的诗歌了。
Bessie认识N（1≤N≤5000）个单词，她想要将她们写进她的诗。Bessie已经计算了她认识的每个单词的长度，以音节为单位，并且她将这些单词划分成了不同的“韵部”。每个单词仅与属于同一韵部的其他单词押韵。
Bessie的每首诗由M行组成（1≤M≤10^5），每一行必须由K（1≤K≤5000）个音节构成。此外，Bessie的诗必须遵循某个指定的押韵模式。
Bessie想要知道她可以写出多少首符合限制条件的不同的诗。Input
输入的第一行包含N、M和K。
以下N行，每行包含两个整数si（1≤si≤K）和ci（1≤ci≤N）。这表示Bessie认识一个长度（以音节为单位）为si、属于韵部ci的单词。
最后M行描述了Bessie想要的押韵模式，每行包含一个大写字母ei。所有押韵模式等于ei的行必须以同一韵部的单词结尾。不同ei值的行并非必须以不同的韵部的单词结尾。Output
输出Bessie可以写出的满足这些限制的不同的诗的数量。由于这个数字可能非常大，请计算这个数对1,000,000,007取余的结果。
Sample Input
输入样例： 3 3 10 3 1 4 1 3 2 A B ASample Output
输出样例： 960Data Constraint
Hint
在这个例子中，Bessie认识三个单词。前两个单词押韵，长度分别为三个音节和四个音节，最后一个单词长度为三个音节，不与其他单词押韵。她想要写一首三行的诗，每行包含十个音节，并且第一行和最后一行押韵。共有960首这样的诗。以下是一首满足要求的诗（其中1，2、3分别代表第一个、第二个、第三个单词）：121 123 321。
看错题了，这告诉我们读题要仔细，比赛时看成必须不同，想到两个 dp 杂交去了，结果后程在打暴力（当时看到暴力结果和我的代码一模一样但和题目输出不一样内心十分沸腾）：
不同 \(e_i\) 值的行并非必须以不同的韵部的单词结尾。
我以为要必须不同……
如果可以相同那么就很简单了，就是一个完全背包方案数。很容易可得到：
\[f[i][j] \text{为背包容量为 i 且结束韵部为 j 的最大容量} \]\[f[i][j]+=f[i-w][1]+f[i-w][2]+f[i-w][3]+\cdots+f[i-w][n]=\sum_{k = 1}^n f[i-w][k] \]如果这么打铁超时。
所以我们干脆：
\[f[i] \text{为背包容量为 i 的最大容量} \]\[f[i]+=f[i-w] \]但是这又不能很好的储存最后的结束韵部，怎么办呢？
可以发现我们只需要 \(f[n]\) 的结束韵部（前面的可以乱玩），我们开一个新的 dp：
\[g[i] \text{为背包容量为 n 且结束韵部为 i 的最大容量} \]更新时判断一下如果 i == n 就更新 \(g[i]\)。
结果为（以下用 \(p\) 表示某个韵部结尾的情况数）：
\[(p_1)^2 \times((p_1)^1+(p_2)^1)+(p_2)^2 \times((p_1)^1+(p_2)^1)=((p_1)^2+(p_2)^2)\times((p_1)^1+(p_2)^1) \]当然如果我们这么看感觉会很枯燥，我解释一下：我们把相同的韵部看作一组，即一组有多个相同的韵部。
那么韵部 \(A\) 因为有两个，它的结果有 \(((p_1)^2+(p_2)^2)\)。
韵部 \(B\) 因为有一个，它的结果有 \(((p_1)^1+(p_2)^1)\)。
使用乘法原理相乘。
把韵部的所有情况计算出来（加法原理），再用乘法原理相乘，即可。
#include <cstdio>
#define P 1000000007
#define ll long long
ll n, m, k, res = 1;
ll s[5010], c[5010];
char e[100010];
ll f[5010];
ll g[5010];
ll num['z'];
ll qpow(ll x, ll y) {
if(y == 0) return 1;
if(y % 2 == 0) {
ll res = qpow(x, y / 2);
return res * res % P;
}
return qpow(x, y - 1) * x % P;
}
int main() {
freopen("poetry.in", "r", stdin);
freopen("poetry.out", "w", stdout);
scanf("%lld %lld %lld", &n, &m, &k);
for(ll i = 1; i <= n; i++) {
scanf("%lld %lld", &s[i], &c[i]);
}
for(ll i = 1; i <= m; i++) {
char s[10];
scanf("%s", s);
e[i] = s[0];
num[e[i]]++;
}
f[0] = 1;
for(ll i = 0; i <= k; i++) {
for(ll j = 1; j <= n; j++) {
if(i < s[j]) continue;
(f[i] += f[i - s[j]]) %= P;
if(i == k) {
(g[c[j]] += f[i - s[j]]) %= P;
}
}
}
for(ll i = 'A'; i <= 'Z'; i++) if(num[i]) {
ll ans = 0;
for(ll j = 1; j <= n; j++) {
if(g[j]) {
(ans += qpow(g[j], num[i])) %= P;
}
}
(res *= ans) %= P;
}
printf("%lld", res);
}
T2 Sleepy Cow Sorting
Description
Farmer John正在尝试将他的N头奶牛（1≤N≤10^5），方便起见编号为1…N，在她们前往牧草地吃早餐之前排好顺序。
当前，这些奶牛以p1,p2,p3,…,pN的顺序排成一行，Farmer John站在奶牛p1前面。他想要重新排列这些奶牛，使得她们的顺序变为1,2,3,…,N，奶牛1在Farmer John旁边。
今天奶牛们有些困倦，所以任何时刻都只有直接面向Farmer John的奶牛会注意听Farmer John的指令。每一次他可以命令这头奶牛沿着队伍向后移动k步，k可以是1到N−1之间的任意数。她经过的k头奶牛会向前移动，腾出空间使得她能够插入到队伍中这些奶牛之后的位置。
例如，假设N=4，奶牛们开始时是这样的顺序：
FJ: 4, 3, 2, 1
唯一注意FJ指令的奶牛是奶牛4。当他命令她向队伍后移动2步之后，队伍的顺序会变成：
FJ: 3, 2, 4, 1
现在唯一注意FJ指令的奶牛是奶牛3，所以第二次他可以给奶牛3下命令，如此进行直到奶牛们排好了顺序。
Farmer John急欲完成排序，这样他就可以回到他的农舍里享用他自己的早餐了。请帮助他求出一个操作序列，使得能够用最少的操作次数将奶牛们排好顺序。Input
输入的第一行包含N。第二行包含N个空格分隔的整数：p1,p2,p3,…,pN，表示奶牛们的起始顺序。
Output
输出的第一行包含一个整数， K，为将奶牛们排好顺序所需的最小操作次数。
第二行包含K个空格分隔的整数， c1,c2,…,cK，每个数均在1…N−1之间。如果第i次操作FJ命令面向他的奶牛向队伍后移动ci步，那么K次操作过后奶牛们应该排好了顺序。
如果存在多种最优的操作序列，你的程序可以输出其中任何一种。Sample Input
输入样例： 4 1 2 4 3Sample Output
输出样例： 3 2 2 3Data Constraint
赛时想到的题目。
首先我列出了很多假设，再我人工验证后，有一个假设成功活了下来。例如 1 5 4 3 2 6首先就是：
- 找到最后的最长升序，例如这里的
2 6 - 然后划分区间，前面是乱序，后面是有序：
1 5 4 3|2 6 - 取出第一个放入有序的相应位置：
5 4 3|1 2 6 - 以此类推：
4 3|1 2 5 6 3|1 2 4 5 61 2 3 4 5 6
我们肯定不能一个一个模拟，其实我们发现，移动到最后一个只会影响比当前值大的，所以用树状数组维护区间加减即可。
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll n;
ll p[100010];
ll a[100010];
ll s[100010];
ll l = 1, r;
ll lowbit(ll x) {
return x & (-x);
}
void update(ll pos, ll x) {
while(pos <= n) {
s[pos] += x;
pos += lowbit(pos);
}
}
ll query(ll pos) {
ll res = 0;
while(pos >= 1) {
res += s[pos];
pos -= lowbit(pos);
}
return res;
}
int main() {
freopen("sleepy.in", "r", stdin);
freopen("sleepy.out", "w", stdout);
scanf("%lld", &n);
r = n;
for(ll i = 1; i <= n; i++) {
scanf("%lld", &p[i]);
if(p[i - 1] > p[i]) l = i; // 不用更新区间左端点
}
for(ll i = 1; i < l; i++) {
ll nl = l, nr = r, ans = l - 1;
while(nl <= nr) {
ll mid = (nl + nr) >> 1;
if(p[mid] <= p[i]) {
ans = mid;
nl = mid + 1;
} else {
nr = mid - 1;
}
}
a[p[i]] = ans - i; // 还要向后移动多少位
}
for(ll i = 1; i <= n; i++) {
update(i, a[i]);
update(i + 1, -a[i]); // 放入树状数组
}
printf("%lld\n", l - 1); // 前面的肯定要移动
for(ll i = 1; i < l; i++) {
printf("%lld ", query(p[i]));
update(p[i] + 1, 1);
update(n + 1, -1);
}
}
T3 Shortcut
Description
每天晚上，Farmer John都会敲响一个巨大的铃铛，召唤他的奶牛们前来牛棚享用晚餐。奶牛们都急切地想要前往牛棚，所以她们都会沿着最短的路径行走。
农场可以描述为N块草地（1≤N≤10,000），方便起见编号为1…N，牛棚位于草地1。草地之间由M条双向的小路连接（N−1≤M≤50,000）。每条小路有其通过时间，从每块草地出发都存在一条由一些小路组成的路径可以到达牛棚。
草地i中有ci头奶牛。当她们听到晚餐铃时，这些奶牛都沿着一条消耗最少时间的路径前往牛棚。如果有多条路径并列消耗时间最少，奶牛们会选择其中“字典序”最小的路径（也就是说，她们通过在两条路径第一次出现分支的位置优先选择经过编号较小的草地的方式来打破并列关系，所以经过草地7、3、6、1的路径会优先于经过7、5、1的路径，如果它们所消耗的时间相同）。
Farmer John担心牛棚距离某些草地太远。他计算了每头奶牛路上的时间，将所有奶牛消耗的时间相加，称这个和为总移动时间。他想要通过额外添加一条从牛棚（草地1）连接到某块他选择的其他草地的、通过时间为T（1≤T≤10,0001≤T≤10,000）的“近道”来尽可能地减少总移动时间。当一头奶牛在她平时前往牛棚的路上偶然看见这条近道时，如果这条近道能够使她更快地到达牛棚，她就会走这条路。否则，一头奶牛会仍然沿着原来的路径行走，即使使用这条近道可能会减少她的移动时间。
请帮助Farmer John求出通过添加一条近道能够达到的总移动时间减少量的最大值。Input
输入的第一行包含N、M和T。以下N行包含c1…cN，均为0…10,000范围内的整数。以下M行，每行由三个整数a， b和t描述了一条小路，这条小路连接了草地a和b，通过时间为t。所有的通过时间在1…25,000范围内。
Output
输出Farmer John可以达到的总移动时间的最大减少量。
Sample Input
输入样例： 5 6 2 1 2 3 4 5 1 2 5 1 3 3 2 4 3 3 4 5 4 5 2 3 5 7Sample Output
输出样例： 40Data Constraint
比赛时想到正解的思路，但不知道：最短路树
然后在牛经过最多的地方建路即可。
#include <cstdio>
#include <queue>
#include <cstring>
#define ll long long
using namespace std;
struct node {
ll u, w;
friend bool operator >(const node &x, const node &y) {
return x.w < y.w;
}
friend bool operator <(const node &x, const node &y) {
return x.w > y.w;
}
};
ll n, m, t;
ll c[10010];
ll ans;
ll cnt;
ll dis[10010];
bool vis[10010];
ll head[100010];
ll nxt[100010];
ll to[100010];
ll cost[100010];
void addEdge(ll u, ll v, ll co) {
++cnt;
to[cnt] = v;
cost[cnt] = co;
nxt[cnt] = head[u];
head[u] = cnt;
}
ll Head[100010];
ll Nxt[100010];
ll To[100010];
ll Cost[100010];
ll cnt2;
void addEdge2(ll u, ll v, ll co) {
++cnt2;
To[cnt2] = v;
Cost[cnt2] = co;
Nxt[cnt2] = Head[u];
Head[u] = cnt2;
}
void dij() {
for(ll i = 1; i <= n; i++) {
dis[i] = 1e15;
vis[i] = false;
}
dis[1] = 0;
priority_queue <node> q;
q.push((node){1, 0});
while(!q.empty()) {
ll u = q.top().u;
q.pop();
if(vis[u]) continue;
vis[u] = true;
for(ll i = head[u]; i; i = nxt[i]) {
ll v = to[i];
if(!vis[v]) if(dis[v] > dis[u] + cost[i]) {
dis[v] = dis[u] + cost[i];
q.push((node){v, dis[v]});
}
}
}
}
ll dfs(ll u) {
vis[u] = 1;
ll child = c[u];
for(ll i = Head[u]; i; i = Nxt[i]) {
ll v = To[i];
if(!vis[v]) {
child += dfs(v);
}
}
ans = max(ans, (dis[u] - t) * child);
return child;
}
int main() {
freopen("shortcut.in", "r", stdin);
freopen("shortcut.out", "w", stdout);
scanf("%lld %lld %lld", &n, &m, &t);
for(ll i = 1; i <= n; i++) {
scanf("%lld", &c[i]);
}
for(ll i = 1; i <= m; i++) {
ll u, v, co;
scanf("%lld %lld %lld", &u, &v, &co);
addEdge(u, v, co);
addEdge(v, u, co);
}
dij();
memset(vis, 0, sizeof(vis));
for(ll u = 1; u <= n; u++) {
for(ll i = head[u]; i; i = nxt[i]) {
ll v = to[i];
if(dis[v] == dis[u] + cost[i] && !vis[v]) {
addEdge2(u, v, cost[i]);
addEdge2(v, u, cost[i]);
vis[v] = 1;
}
}
}
memset(vis, 0, sizeof(vis));
dfs(1);
printf("%lld", ans);
}