这次SRM题型比较老而且想对容易，就不花大功夫写解题报告了。不过从赛后900pt的AC率来看，tc对网络流模板卡的是相当严的
250pt:
Problem Statement
   
Fox Jiro likes dice. He wants to make his own dice. Each die he wants to make is a cube. Each of the 6 faces has an integer between 1 and N, inclusive. No two faces have same number. Also the following condition must be satisfied: for all faces, the sum of the numbers on opposite faces must be equal and the sum must be greater than or equal to K.
He realized that there are many ways to make such dice. He wants to know how many ways there are. Please help Jiro to make a program that is given two integers N and K and returns the number of different dice satisfying the condition mentioned above.
Two dice are considered the same if you can rotate one to form the other.
Definition
   
Class: FoxMakingDice
Method: theCount
Parameters: int, int
Returns: long
Method signature: long theCount(int N, int K)
(be sure your method is public)
==========================================
这题很简单，枚举筛子相对的两个面上的点数i,j,1<=i<j<=N,统计i+j=K,K+1..2N-1的(i,j)对数cnt[K],cnr[K+1]...cnt[2N-1],答案就是 ∑(i>=K,cnt[i]>=3)C(cnt[i],3)*2
算法复杂度O(N^2)
   
Notes
-
The answer will always fit in a signed 64-bit integer.
Constraints
-
N will be between 1 and 1,000, inclusive.
-
K will be between 1 and 2,000, inclusive.

Problem Statement
   
Fox Jiro and Haruko play a game with two piles of cards: pile A and pile B. Pile A and pile B contain same number of cards. Each card contains a real number between 1.0 and 100.0. Initially, the two players have 0 points. Then they repeat following operations exactly k times:
They choose two cards from the piles (one from pile A and another from pile B).
The choosen cards are removed from the piles.
Jiro earns max{a+b, a*b} points and Haruko earns min{a+b, a*b} points (where a and b are the numbers written on the two cards that were removed).
You are given a double[] pileA, a double[] pileB, and an int k. Return the maximal possible value of (Jiro's points) / (Haruko's points).
Definition
   
Class: FoxCardGame
Method: theMaxProportion
Parameters: double[], double[], int
Returns:double
Method signature: double theMaxProportion(double[] pileA, double[] pileB, int k)
(be sure your method is public)
   
Notes
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
pileA and pileB will contain between 1 and 50 elements, inclusive.
-
pileA and pileB will contain the same number of elements.
-
Each element of pileA and pileB will be between 1.0 and 100.0, inclusive.
-
k will be between 1 and the number of elements in pileA, inclusive.
===========================================
二分枚举答案ans,设选出的K对数是{ai,bi},设si=max{ai*bi,ai+bi},ti=min{ai*bi,ai+bi},有 f(ans)=∑si-ans*∑ti= ∑(si-ans*ti),若f(ans)>=0调整上界否则调整下界。计算f(ans)的方法就很直接,构建2N+4个顶点的图G,边{0->1},{2N+2,2N
+3
}容量K,费用0,{2+i,N+2+j}(0<=i,j<N)容量1,费用max{pileAi*pileBj,pileAi+pileBj}-ans*min{pileAi*pileBj,pileAi+pileBj}.计算最大流下的最小费用即可
算法复杂度很难估计，但数据很小不会TLE。关键是要有好的最小费用流模板，否则答案精度达不到要求

有个人发了个900pt的O(N^3)的解法没来的及细看,马克之

另外说句，这次我跟tomek一个房间，但他发挥失常了

居然忘记比赛了，悲剧。。。

回复：6楼
比赛是最不重要的事情了，你懂的