牛牛选物
链接：
https://ac.nowcoder.com/acm/contest/9887/A
牛牛有现在有n个物品，每个物品有一个体积v[i]和重量g[i],他想选择其中总体积恰好为V的若干个物品，想使这若干个物品的总重量最大，他想知道最大总重量为多少。（如果不存在合法方案，返回-1）
01背包，不过容量太大了，而物品数量却很小，所以用二进制枚举即可
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 返回总体积为V若干物品的最大总重量，如果g存在选择若干物品总体积为V的情况，返回-1
* @param v int整型一维数组
* @param g int整型一维数组
* @param V int整型
* @return int整型
*/
public int Maximumweight (int[] v, int[] g, int V) {
// write code here
int n=v.length;
int ans=-1;
for(int i=0; i<(1<<n); i++){/// 利用二进制法枚举子集，集合个数应当为 2^n
long SumW, SumV;
SumW = SumV = 0;
for(int j=0; j<n; j++){
if((i >> j & 1)!=0){
SumW += g[j];
SumV += v[j];
}
}
if(SumV==V&&SumW>ans)
ans=(int)SumW;
}
return ans;
}
}牛牛与字符串2
链接：
https://ac.nowcoder.com/acm/contest/9887/B
牛牛拿到了一个字符串。他想知道除去字符串本身以外，这个字符串最大的公共前后缀的长度是多少？
例如，对于字符串ABABA而言，“ABA”即是它的前缀，也是它的后缀，且是最长的公共前后缀，因此最大的长度是3。
牛牛无法解决该问题，所以他只好向你求助，给定一个只包含大写字母的字符串s，返回除去字符串本身以外公共前后缀最大长度，如果没有任何一个公共前后缀满足要求，返回-1即可。
很明显的最长前缀后缀长度，KMP next数组问题，这里是简化版：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 给定一个字符串s，返回具有相同前缀后缀的子串的第二大长度，反之，返回-1即可。
* @param s string字符串 代表题意中的字符串s
* @return int整型
*/
public int solve (String s) {
// write code here
int t=0;
for(int i=1;i<s.length();++i){
if(s.charAt(i)==s.charAt(t)){
t++;
}else{
if(s.charAt(i)==s.charAt(0)) t=1;
else t=0;
}
}
if(t==0)
return -1;
return t;
}
}当然也可以用字符串hash来做
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 给定一个字符串s，返回具有相同前缀后缀的子串的第二大长度，反之，返回-1即可。
* @param s string字符串 代表题意中的字符串s
* @return int整型
*/
public int solve (String s) {
// write code here
int n = s.length();
int base = 131, mod = 1000000007,mul = 1;
int left = 0, right = 0;
int ans = -1;
for (int i = 0; i < n; ++i) {
left = (int) (((long) left * base + s.charAt(i)) % mod);
right = (int) ((right + (long) mul * s.charAt(n-1-i)) % mod);
if (i!=n-1&&left == right) {
ans = i+1;
}
mul = (int) ((long) mul * base % mod);
}
return ans;
}
}牛牛送快递
链接：
https://ac.nowcoder.com/acm/contest/9887/C
牛牛为了向牛妹表达爱意，决定亲自给牛妹送上礼物。牛牛住在城市s\mathit ss，而牛妹住在城市t\mathit tt（牛牛和牛妹并不在同一座城市）。牛客国一共有n\mathit nn座城市，这n\mathit nn城市之间有m\mathit mm条城际高速可以让连接的城市相互通行。在牛客国，人们喜欢用组合数CabC_a^bCab来计数，所以通过某一条城际高速所需要的过路费也是用CabC_a^bCab来表示的。并且牛客国比起加法，更偏爱乘法，所以从城市s\mathit ss到达城市t\mathit tt所需要的总花费为路径上经历过的城际高速过路费之积，即∏i∈s→tCaibi\prod _{i\in s\rightarrow t}C_{a_i}^{b_i}∏i∈s→tCaibi。牛牛了省钱想让你帮助他规划一条花费最少的路线，并把总花费告诉牛牛。由于答案可能很大请对109+710^9+7109+7取模。
题目要求无向图中乘积的最小值路径，这里可以把乘法转化位对数运算的加法loga+logb=logab，然后直接用Dijkstra求即可,最后还原可能会有精度问题，不过这里数据比较友好，不用担心这个问题：
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param n int整型 有n个城市
* @param m int整型 有m条路径
* @param s int整型 起始城市坐标
* @param t int整型 终点城市坐标
* @param edge int整型vector<vector<>> 边的格式如下:[[u1,v1,a1,b1],[u2,v2,a2,b2],...]
* @return int整型
*/
typedef pair<double,int>pi;
typedef pair<int,int>Pi;
typedef pair<int,double>P;
typedef long long ll;
ll INF = 0x3f3f3f3f3f3f3f3f;
static const int N = 100010;
ll mod = 1000000007;
double cc[1010][1010];
ll C[1010][1010];
int vis[N];
double dis[N];
ll ans[N];
vector<P>G[N];
map<Pi,Pi>mp;
void Dijkstra(int s,int t,int n,int m){
priority_queue<pi,vector<pi>,greater<pi>>que;
que.push(pi(0,s));
for(int i = 1;i <= n;i++)dis[i] = INF,vis[i] = 0;
dis[s] = 0;
ans[s] = 1;
while(!que.empty()){
pi p = que.top();
que.pop();
int u = p.second;
if(vis[u])continue;
vis[u] = 1;
for(auto it : G[u]){
int v = it.first;double w = it.second;
if(!vis[v] && dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
Pi pp = mp[Pi(u,v)];
ans[v] = ans[u] * C[pp.first][pp.second] % mod;
que.push(pi(dis[v],v));
}
}
}
}
int minDist(int n, int m, int s, int t, vector<vector<int> >& edge) {
// write code here
for(int i = 0;i <= 1000;i++)cc[i][0] = C[i][0] = 1;
for(int i = 1;i <= 1000;i++){
for(int j = 1;j <= i;j++){
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % mod;
cc[i][j] = cc[i-1][j-1] + cc[i-1][j];
}
}
for(int i = 0;i < edge.size();i++){
int u,v,a,b;u = edge[i][0],v = edge[i][1],a = edge[i][2],b = edge[i][3];
double w = log2(cc[a][b]);
mp[Pi(u,v)] = mp[Pi(v,u)] = Pi(a,b);
G[u].push_back(P(v,w));
G[v].push_back(P(u,w));
}
Dijkstra(s,t,n,m);
return ans[t];
}
};