T1 簡單的二分法
有一個果園，有 n 棵果樹依次排成一排，其中已知第 i 棵果樹上結(jié)了 a 個果子『踩現(xiàn)在要按照果樹編號順序依次收果
子，對于一個能裝 v 個果樹的果籃糕殉，收果子從第 1 棵果樹開始亩鬼，如果果籃的剩余容積大于等于當(dāng)前果樹所結(jié)的果子，那么就可以將此樹上的果子全收下來阿蝶，否則就要拿一個新的籃子來裝果子雳锋。特別地，如果果籃容積小于某果樹的結(jié)果數(shù)羡洁，那么我們認(rèn)為這樣將永遠(yuǎn)不能收完果子玷过。
現(xiàn)在假若只能用 k 個果籃，問按照以上方法能使用不超過 k 個果籃并收完所有果子的果籃最小容積筑煮。
輸入格式：
從文件 fruit.in 輸入數(shù)據(jù)辛蚊。
輸入有兩行，第一行兩個正整數(shù)真仲，代表 n袋马、k，意義如題秸应。
第二行 n 個正整數(shù)ai 虑凛，代表每棵果樹的結(jié)果數(shù)。
輸出格式：
輸出到文件 fruit.out 中软啼。
輸出僅一行桑谍，一個正整數(shù)，即滿足條件的果籃最小容積焰宣。
樣例 1：
輸入
9 3
1 2 3 4 5 6 7 8 9
輸出
17
限制與約定：
對于 30% 的數(shù)據(jù)霉囚，滿足 n, k ? 100、ai? 100匕积。
對于 60% 的數(shù)據(jù)盈罐，滿足 n, k ? 1000、ai? 105闪唆。
對于 80% 的數(shù)據(jù)盅粪，滿足 n, k ? 10000、ai ? 105悄蕾。
對于 100% 的數(shù)據(jù)票顾，滿足 n, k ? 105、ai ? 109帆调。
一個顯然的二分法奠骄，大佬們肯定都會
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e5+5;
ll n,k,l=1,r,ans,s;
ll a[N];
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool check(ll v)
{
ll sum=0,now=0;
for(ll i=1;i<=n;i++)
{
if(now+a[i]<=v) now+=a[i];
else if(a[i]>v||sum==k-1) return 0;
else sum++,now=a[i];
}
return 1;
}
int main()
{
freopen("in.txt","r",stdin);
n=read();k=read();
for(ll i=1;i<=n;i++) a[i]=read(),s+=a[i];
r=s;
while(l<r)
{
ll mid=(l+r)>>1;
if(check(mid)) ans=r=mid;
else l=mid+1;
}
cout<<ans<<endl;
}
T2 哈密頓回路
題目描述：長者國馬上要舉行一次盛大的馬拉松賽跑了！全國各地的記者在首都?xì)g聚一堂番刊，參加這一意義重大的比賽含鳞。有一位長者在首都畫了一個圈，作為比賽的賽道芹务。同時蝉绷，為了增加趣味性，這條賽道還添加了一些“捷徑”枣抱。當(dāng)然熔吗，這些捷徑并不意味著具體來講，賽道上一共有 n 個地點佳晶，編號為 1..n桅狠。某些地點之間可能存在相連的跑道。記者們將在 1 號地點起跑轿秧，經(jīng)過每個地點一次之后回到 1 號地點中跌。例如，在下面的賽道中：
路徑 1 ? 2 ? 3 ? 4 ? 1 是允許的淤刃，而 1 ? 2 ? 4 ? 1 和 1 ? 2 ? 3 ? 4 ? 2 ? 1 是不允許的晒他。
作為來自全世界記者跑的最快的地區(qū)的你博烂，早已經(jīng)打聽到賽道的具體情況亮蛔。于是你想知道這一次賽跑你最少要花多少時間。
輸入格式：
從文件 run.in 輸入數(shù)據(jù)寓调。
第一行輸入兩個正整數(shù) n 和 m铝侵，表示地點的數(shù)量和跑道的數(shù)量灼伤。
接下來 m 行，每行三個正整數(shù) u咪鲜、v 和 t狐赡，表示 u 號地點和 v 號地點之間的一條跑道，并且通過這條跑道你需要花費 t分鐘疟丙。我們認(rèn)為經(jīng)過每個地點是不需要花費時間的颖侄。
輸出格式：
輸出到文件 run.out 中鸟雏。
輸出一行一個整數(shù)，表示最少需要多少分鐘览祖，你才可以完成賽跑孝鹊。
樣例 1
輸入
4 5
1 2 1
2 3 1
3 4 1
4 1 1
2 4 1
輸出
4
樣例2：
輸入
15 19
4 11 3
2 3 3
3 12 5
12 15 1
3 4 9
4 15 8
2 6 4
6 14 8
9 13 7
2 13 8
1 10 1
7 10 6
6 8 10
5 7 9
8 11 3
12 14 10
1 15 2
3 9 7
5 14 8
輸出
91
限制與約定
對于 100% 的數(shù)據(jù)，滿足 n ? 105展蒂，n ? m ? n + 20又活，1 ? u, v ? n，1 ? t ? 100锰悼。并且數(shù)據(jù)保證你可以找到一組合法的
方案柳骄。
對于每個測試點限制如下：
20170919102824_86125[1].jpg
T3 二項式定理
輸入格式
從文件 problem.in 輸入數(shù)據(jù)。
輸入一共一行三個正整數(shù) n箕般、s 和 d耐薯，這些參數(shù)的意義均在上文給出。
輸出格式
輸出到文件 problem.out 中隘世。
輸出共一行一個整型可柿，表示答案對 998244353 取模后的值。
樣例 1
輸入
9999999 1 0
輸出
951935696
解釋
機智的鷗蛤菌發(fā)現(xiàn)這個數(shù)字就是 29999999mod 998244353丙者。
樣例 2
輸入
9999999 1000000000000000000 899999999999777777
輸出
348456814
限制與約定
對于 100% 的數(shù)據(jù)复斥，滿足 n, s, d ? 1018。
對于每個測試點的限制如下：
顯然的二項式定理
所以很簡單械媒，
