1.最近開始刷刷題，沒找到什麼好的方法，就把之前的比賽一場一場拿出來刷刷。
2.the Sum of Cube。三次方求和，很簡單，三次方求和就是pow(C(n+1,2),2).但是由于這個數比較大，高精度搞一下。我用JAVA 直接AC的。
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static BigInteger Get(BigInteger a){
return a.multiply(a.add(BigInteger.ONE)).divide(new BigInteger("2"));
}
public static BigInteger pow(BigInteger a){
return Get(a).multiply(Get(a));
}
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
int T=cin.nextInt();
for(int ca=1;ca<=T;ca++){
BigInteger a=cin.nextBigInteger();
BigInteger b=cin.nextBigInteger();
System.out.println("Case #"+ca+": "+pow(b).subtract(pow(a.subtract(BigInteger.ONE))));
}
}
} 3.Sawtooth。這題其實是一個很套路的題目了，n多種方法計算，其實核心就是歐拉公式，當然歐拉公司有好幾個，我說的是歐拉關于平面圖的公式。就是頂點數，邊數，面數的關系。這個題可以這樣算：
首先直線分平面是C(n+1,2)+1.現在M可以被看做四條直線，是以把n=4n帶入，但是發現其實它沒有達到4n的效果，因為還有損失。這個損失其實是和邊數成正比的，比例系數用n=1帶入算一下，就是n=4時其實應該有11個面，但是現在隻有2個，損失了九個，是以就是減掉9n。是以式子就是:C(4n+1,2)+1-9n.資料比較大，還是JAVA。
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static BigInteger pow(BigInteger a){
return a.multiply(a.multiply(new BigInteger("8")).subtract(new BigInteger("7"))).add(BigInteger.ONE);
}
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
int T=cin.nextInt();
for(int ca=1;ca<=T;ca++){
BigInteger a=cin.nextBigInteger();
System.out.println("Case #"+ca+": "+pow(a));
}
}
} 4.Contest。這個題做法有很多，其實最直覺就是狀壓DP。考慮dp[i][j]表示前i道題目，做題情況為j最大的收益。這個j表示了前i道題的做題情況的一個二進制表示。但是可以發現，如果考慮前n道題目，其實是每個人都需要做一道的，那麼從這個角度出發，就是可以把m道題目劃分為m/n取上整段，j儲存的最近n道題的情況，因為如果前n道題做完，就可以把這個j的資訊滾動掉了，不需要考慮。那麼到這裡其實就有兩種做法，對于每n題，其實就是一個dp。當然這裡也可以用費用流。dp的轉移式子:
這是一個人人為我的dp，最後的結果就是dp[m][i]取個最大值。p[k][i]表示第i個題目由k來做，st表示當第i個題目由k來做這i道題目做題情況達到的狀态，顯然st=j|(1<<k).然後就完事了。别問我代碼為啥還沒寫完，因為一旦我分析好了咋寫，就沒興趣了。畢竟我是著名的口胡大師。
---更新代碼，簡單的寫了一下，還是比較好寫的。主要是位運算的意義明白咋回事就好。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1500;
double p[15][maxn];
double dp[maxn][maxn];
int n, m;
void get() {
for (int i = 0; i <= m; i++)
for (int j = 0; j < (1 << n); j++)
dp[i][j] = -1.0;
dp[0][0] = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < (1 << n); j++) {
if (dp[i][j] < 0)continue;
for (int k = 0; k < n; k++) {
if (!((1 << k) & j)) {
int st = j | (1 << k);
if (st == ((1 << n) - 1))st = 0;
dp[i + 1][st] = max(dp[i + 1][st], dp[i][j] + p[k][i]);
}
}
}
}
}
int main() {
int T; scanf("%d", &T);
for (int ca = 1; ca <= T; ca++) {
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf("%lf", &p[i][j]);
}
}
get();
double ans = 0;
for (int i = 0; i < (1 << n); i++)
ans = max(ans, dp[m][i]);
printf("Case #%d: %.5lf\n", ca, ans);
}
} 5.Tree。這題有啥好說的，樹鍊剖分裸題。剖完+樹狀數組/線段樹，就是區間修改，單點查詢。别問我代碼為啥沒有，因為我手寫了一個樹剖，還沒調完。手寫書剖也是很簡單的嘛[狗頭]。
--- 更新：這個題我想簡單了，似乎沒那麼好過。。。。好像還卡讀入，以及記憶體。
// 代碼留坑 6.Airport。這個題開始沒仔細看，選取的K個是在N個點裡面選，要不然我以為是Kmeans聚類呢。。。。其實這個題就是抽象了一下，就是在這個格子裡面選k個點把所有的點覆寫掉，并且花費最小。覆寫問題？最小點覆寫呗。但是距離咋算?然後偷偷看了一眼題解，原來是DLX覆寫。。。好吧，這玩意其實我隻是知道，并沒有用過。DLX覆寫其實還是很常見的，學習了學習了。代碼？前兩個都沒有，這個肯定也沒呀。
// 代碼留坑 暫時是這五個題，後邊的還沒看，先把他們AC了。
--- 更新
7.Divided Land 這個題着實有點。。。。。，這場比賽可能應該叫做BigInteger知多少。。。簡單概括一下就是二進制狀态下的gcd，求完gcd輸出這個gcd的二進制。可以轉換為十進制求然後再轉回來。但是JAVA 中的BigInteger 裡面有這些操作。
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static BigInteger pow(BigInteger a){
return a.multiply(a.multiply(new BigInteger("8")).subtract(new BigInteger("7"))).add(BigInteger.ONE);
}
public static void main(String[] args) {
Scanner cin=new Scanner(System.in);
int T=cin.nextInt();
for(int ca=1;ca<=T;ca++){
BigInteger a=cin.nextBigInteger(2);
BigInteger b=cin.nextBigInteger(2);
System.out.println("Case #"+ca+": "+a.gcd(b).toString(2));
}
}
} 8.
沒怎麼看懂題目的意思，懶得看了。
9.gcd pair。一個數論題，比較有意思，可以寫一下。
// 代碼留坑 10.Yaoge’s maximum profit大家資料結構都這麼厲害嗎？？，這個題過的比gcd pair多了好幾倍。。。大概看了一下，應該是一個LCA問題。但是考慮道又是樹上路徑修改，是以大機率也得樹剖一下+線段樹維護。
基本上感覺看了這幾個題目，總的來說不是很好。碼農題居多。後邊應該還有一個計算幾何，等把這幾個AC了以後看看能不能做的動。
// 代碼留坑