A.Cow and Haybales
美国建设行动（USACO）最近命令农夫约翰在农场上布置n堆干草堆。第i堆包含ai haybales。
但是，农夫约翰刚刚去度假，贝西独自一人。每天，顽皮的贝西（Bessie）可以选择将任何干草堆中的任何干草捆移到相邻的干草堆中。形式上，她有一天可以选择两个索引i和j（1≤i，j≤n），使得| i | j | = 1且ai> 0并应用ai = ai-1，aj = aj + 1。她也可能因为懒惰而决定在某些日子不做任何事情。
贝西想使第1堆中的干草草数量最大化（即使a1最大化），而在农夫约翰回来之前，她只有d天的时间这样做。如果她的行为最佳，请帮助她找到最大的草捆数量！
输入值 输入包含多个测试用例。第一行包含一个整数t（1≤t≤100）-测试用例的数量。接下来的2t行包含测试用例的描述-每个测试用例两行。
每个测试用例的第一行包含整数n和d（1≤n，d≤100）-分别是干草堆的数量和天数。
每个测试用例的第二行包含n个整数a1，a2，…，an（0≤ai≤100）—每堆中的干草草数量。
输出量 对于每个测试用例，输出一个整数：如果Bessie表现最佳，则在d天后可能堆入1号草堆的最大草捆数量。
题解：
从头开始依次遍历每个草堆即可。
简单题。
#include<bits/stdc++.h> using namespace std; const int maxn=1014; int a[maxn]; int T; int N,K; int main () { scanf("%d",&T); while (T--) { scanf("%d%d",&N,&K); vector<int> vi; for (int i=1;i<=N;i++) scanf("%d",&a[i]); for (int i=2;i<=N;i++) { if (!a[i]) continue; while (K>=i-1&&a[i]) { a[1]++; a[i]--; K=K-(i-1); } } printf ("%d ",a[1]); } return 0; }
贝茜有太多的朋友，因为她是每个人最喜欢的母牛！她的新朋友Rabbit（Rabbit）试图越过以便他们玩！
更具体地说，他希望通过进行多跳来从（0,0）变为（x，0）。如果跳的端点之间的欧几里得距离是它的n个最喜欢的数字之一：a1，a2，…，an，他只愿意在2D平面上从一个点跳到另一个点。 Rabbit从（0,0）到（x，0）所需的最小跳数是多少？兔子可能会落在具有非整数坐标的点上。可以证明，兔子总是可以到达目的地。
回想点（xi，yi）和（xj，yj）之间的欧几里得距离为（xi-xj）2+（yi-yj）2 --------------------- √。
例如，如果Rabbit有喜欢的数字1和3，则他可以从两步跳中从（0,0）跳到（4,0），如下所示。请注意，还有其他有效的方法可以在2跳中跳到（4,0）（例如（0,0）→（2，−5–√）→（4,0））。
这是第一个示例的图形。这两跳的距离均为3，这是Rabbit最喜欢的数字之一。 换句话说，Rabbit每次选择一些数字ai，并在他想要的任何方向上选择距离等于ai的跃点。同一号码可以多次使用。
输入值 输入包含多个测试用例。第一行包含一个整数t（1≤t≤1000）-测试用例的数量。接下来的2t行包含测试用例-每个测试用例两行。
每个测试用例的第一行包含两个整数n和x（1≤n≤105，1≤x≤109），分别是喜欢的数字和Rabbit希望移动的距离。
每个测试用例的第二行包含n个整数a1，a2，…，an（1≤ai≤109）—兔子最喜欢的数字。可以保证最喜欢的数字是不同的。
保证所有测试用例的n之和不超过105。
输出量 对于每个测试用例，请打印一个整数-所需的最小跃点数。
题解：
依次遍历每个喜欢的数字，如果等于需要移动的距离输出1，如果只有大于的输出2，如果都小于就分类讨论。
#include<bits/stdc++.h> using namespace std; const int maxn=100014; int a[maxn]; bool cmp (int a,int b) { return a>b; } int N,d; int main () { int T; scanf("%d",&T); while (T--) { scanf("%d%d",&N,&d); for (int i=1;i<=N;i++) scanf("%d",&a[i]); sort(a+1,a+N+1,cmp); int ans=1e9; for (int i=1;i<=N;i++) { if (a[i]>d) ans=min(ans,2); if (a[i]==d) ans=1; if (a[i]<d) { ans=min(ans,(d+a[i]-1)/a[i]); } } printf ("%d ",ans); } return 0; }
C.Cow and Message
牛贝西（Bessie）刚刚截获了农夫约翰（John Farmer）发给汉堡皇后（Burger Queen）的短信！但是，Bessie确信内部隐藏了一条秘密消息。
文本是小写拉丁字母的字符串s。如果t作为s的子序列（其索引形成算术级数）存在，则她认为字符串t隐藏在字符串s中。例如，字符串aab被隐藏在字符串aaabb中，因为它出现在索引1、3和5上，它们形成了算术级数，并且相差2。贝西认为任何出现次数最多的隐藏字符串都是秘密信息。 。如果索引集不同，则S的子序列的两次出现是不同的。帮助她找到秘密信息的发生次数！
例如，在字符串aaabb中，a被隐藏3次，b被隐藏2次，ab被隐藏6次，aa被隐藏3次，bb被隐藏1次，aab被隐藏2次，aaa被隐藏1次， abb隐藏1次，aaab隐藏1次，aabb隐藏1次，aaabb隐藏1次。秘密消息的出现次数是6。
输入值 第一行包含小写拉丁字母（1≤| s |≤105）的字符串s，这是Bessie截获的文本。
输出量 输出一个整数-秘密消息的出现次数。
题解：
出现次数最多的子串只可能是长度1或2的子串，开两个数组DP处理。
#include<bits/stdc++.h> using namespace std; const int maxn=1014; typedef long long ll; ll a[maxn]; ll b[maxn][maxn]; string s; int main () { cin>>s; for (int i=0;i<s.length();i++) { int c=s[i]-'a'; for (int j=0;j<26;j++) b[j][c]+=a[j]; a[c]++; } ll ans=0; for (int i=0;i<26;i++) ans=max(ans,a[i]); for (int i=0;i<26;i++) for (int j=0;j<26;j++) ans=max(ans,b[i][j]); printf("%lld ",ans); return 0; }
贝西正在农场放牧，该农场由n条通过m条双向道路连接的田地组成。她目前在第1场，将在一天结束时返回她在第n场的家。
谷仓母牛联合会已命令农夫约翰额外安装一条双向道路。该农场有k个特殊领域，他决定在两个不同的特殊领域之间安装道路。他可以在已经有直接连接它们的道路的两个特殊领域之间添加道路。
添加道路后，贝西将沿着从字段1到字段n的最短路径返回家中。由于贝西需要更多的运动，因此农夫约翰必须最大限度地增加这条最短路径的长度。救救他！
输入值 第一行包含整数n，m和k（2≤n≤2⋅105，n-1≤m≤2⋅105，2≤k≤n）-农场的田地数量，道路数量，以及特殊字段的数量。
第二行包含k个整数a1，a2，…，ak（1≤ai≤n）-特殊字段。所有的ai都是不同的。
接下来的m条线中的第i条包含整数xi和yi（1≤xi，yi≤n，xi≠yi），表示字段xi和yi之间的双向道路。
保证一个人可以到达其他任何领域。还可以保证，对于任何一对田地，最多只有一条道路将它们连接起来。
输出量 在Farmer John最佳安装一条道路后，输出一个整数，即从字段1到n的最短路径的最大可能长度。
题解：找两个特殊的点a，b，1到a的最短路径长度是x，N到b的最短路径是y，要使得1到N的最短距离最长，就必须使得x+y+1的长度最大，但是a和b在路径上的先后顺序是个问题。
a1+bn+1<=an+b1+1
a1+bn<=an+b1
a1-an<=b1-bn
推导得到这个公式，把所有的特殊结点按照这个顺序排序，再依次从前往后遍历选出最大的路径即可。如果本来的最短路径就不用经过特殊结点，就直接输出本来的最短路径。
#include<bits/stdc++.h> using namespace std; const int maxn=1e6+14; int N,M,K,x,y; vector<int> g[maxn]; int d[2][maxn]; int a[maxn]; int visit[maxn]; void bfs (int x,int st) { memset(visit,0,sizeof(visit)); for (int i=1;i<=N;i++) d[x][i]=1e9; queue<int> q; d[x][st]=0; visit[st]=1; q.push(st); while (!q.empty()) { int u=q.front(); q.pop(); for (int i=0;i<g[u].size();i++) { int v=g[u][i]; if (visit[v]) continue; d[x][v]=d[x][u]+1; q.push(v); visit[v]=1; } } } int main () { scanf("%d%d%d",&N,&M,&K); for (int i=0;i<K;i++) { scanf("%d",&a[i]); } for (int i=0;i<M;i++) { scanf("%d%d",&x,&y); g[x].push_back(y); g[y].push_back(x); } bfs(0,1); bfs(1,N); int ans=0; vector<pair<int,int>> vi; for (int i=0;i<K;i++) { vi.push_back({d[0][a[i]]-d[1][a[i]],a[i]}); } sort (vi.begin(),vi.end()); int tmp=0; for (int i=0;i<vi.size();i++) { if (i!=0) ans=max(ans,tmp+d[1][vi[i].second]+1); tmp=max(tmp,d[0][vi[i].second]); } printf ("%d ",min(ans,d[0][N])); return 0; }