[ HDU 5878 ] I Count Two Three
考虑极端，1e9就是2的30次方，3的17次方，5的12次方，7的10次方。
而且，不超过1e9的乘积不过5000多个，于是预处理出来，然后每次二分找就可以了。
代码语言：javascript复制 1 /*
2 TASK:I Count Two Three 2^a*3^b*5^c*7^d的最小的大于等于n的数是多少
3 LANG:C
4 URL:http://acm.hdu.edu.cn/showproblem.php?pid=5878
5 */
6 #include <iostream>
7 #include <algorithm>
8 #include <cstdio>
9 #include <cstring>
10 #define ll long long
11 using namespace std;
12 const int N=32;
13 const ll M=1e9 1;
14 int tw,th,fi,se,t,n;
15 ll two[N]={1},three[N]={1},five[N]={1},seven[N]={1};
16 ll ans[7000],cnt;
17 int main() {
18 for(int i=1;two[i-1]<M;i ,tw )
19 two[i]=two[i-1]*2;
20 for(int i=1;three[i-1]<M;i ,th )
21 three[i]=three[i-1]*3;
22 for(int i=1;five[i-1]<M;i ,fi )
23 five[i]=five[i-1]*5;
24 for(int i=1;seven[i-1]<M;i ,se )
25 seven[i]=seven[i-1]*7;
26
27 for(int i=0;i<tw;i )
28 for(int j=0;three[j]*two[i]<M&&j<th;j )
29 for(int k=0;five[k]*three[j]*two[i]<M&&k<fi;k )
30 for(int g=0;seven[g]*five[k]*three[j]*two[i]<M&&g<se;g )
31 ans[cnt ]=two[i]*three[j]*five[k]*seven[g];
32
33 sort(ans,ans cnt);
34
35 scanf("%d",&t);
36 while(t--){
37 scanf("%d",&n);
38 printf("%lldn",ans[lower_bound(ans,ans cnt,n)-ans]);
39 }
40 }[ HDU 5879 ] Cure
当n很大时，答案趋于1.64493，于是n小时输出预处理的，大时答案就是1.64493。
代码语言：javascript复制 1 /*
2 TASK:求∑1/k^2 k=1到n
3 LANG:C
4 URL:http://acm.hdu.edu.cn/showproblem.php?pid=5879
5 */
6 #include <iostream>
7 #include <algorithm>
8 #include <cstdio>
9 #include <cstring>
10 #define ll long long
11 #define N 115000
12 using namespace std;
13 char n[1000000];
14 double ans[N];
15 void init(){
16 for(ll i=1;i<N;i )
17 ans[i]=ans[i-1] 1.0/(i*i);
18 }
19 double get(){
20 int a=0,len=0;
21 for(int i=0;n[i]&&len<7;i ,len )
22 a=a*10 n[i]-'0';
23 if(len==7||a>=N)return 1.64493;
24 return ans[a];
25 }
26 int main() {
27 init();
28 while(~scanf("%s",n)){
29 printf("%.5fn",get());
30 memset(n,0,sizeof n);
31 }
32 }[ HDU 5881 ] Tea
注意最后可以留1升水，所以2升2升地倒向上取整是((r-1) 1)/2 就是r/2，l==0时，先倒了1次1，所以r还要-1；
代码语言：javascript复制 1 /*
2 TASK:壶里有L到R区间的水，倒俩杯里，倒完时相差不超过1，壶里最多可以余1，求最少多少次一定能倒完。
3 LANG:C
4 URL:http://acm.hdu.edu.cn/showproblem.php?pid=5881
5 */
6 #include <iostream>
7 #include <algorithm>
8 #include <cstdio>
9 #include <cstring>
10 #define ll long long
11 using namespace std;
12 ll l,r,ans;
13 int main() {
14 while(~scanf("%lld%lld",&l,&r)){
15 if(r<=1)
16 ans=0;
17 else if(r<=2)
18 ans=1;
19 else if(l==r)
20 ans=2;
21 else if(l==0)//第一次倒l/2 0.5，第二次倒l/2 1.5，然后2、2、2、如果l==0，不如第一次就倒1，然后2、2、2
22 ans=1 (r-1)/2;
23 else{
24 r-=l 2;//前两次倒的
25 ans=2 r/2;
26 }
27 printf("%lldn",ans);
28 }
29 return 0;
30 }[ HDU 5882 ] Balanced Game
n为奇数就是有n-1个度，只要保证n-1为偶数就存在，所以n为奇数就存在。
[ HDU 5883 ] The Best Path
如果点的度为奇数的有2个或0个，那么存在路，2个则从一个度为奇数的点出发，另一个点结束，起点和终点异或了(du[i] 1)/2次，其它点异或了du[i]/2次。都是偶数的点则以一个点为起点，最后回到它，那么这个点多异或一次。因为du为偶数时，(du[i] 1)/2和du[i]/2相等，所以循环里不用判断了。
代码语言：javascript复制 1 /*
2 TASK:The Best Path 求经过连通图的所有边一次且经过点异或起来值最大的路的异或值
3 LANG:C
4 URL:http://acm.hdu.edu.cn/showproblem.php?pid=5883
5 */
6 #include <iostream>
7 #include <algorithm>
8 #include <cstdio>
9 #include <cstring>
10 #define ll long long
11 #define N 100005
12 using namespace std;
13 int t,n,m,a[N];
14 int du[N];
15 void solve(){
16 int num=0;
17 for(int i=1;i<=n;i )
18 if(du[i]%2)
19 num ;
20 if(num!=2&&num){
21 puts("Impossible");
22 return;
23 }
24 int ans=0;
25 for(int i=1;i<=n;i )
26 for(int j=1;j<=(du[i] 1)/2;j )
27 ans^=a[i];
28 if(!num){
29 int tans=ans;
30 for(int i=1;i<=n;i )
31 ans=max(ans,tans^a[i]);
32 }
33 printf("%dn",ans);
34 }
35 int main() {
36 scanf("%d",&t);
37 while(t--){
38 memset(du,0,sizeof du);
39 scanf("%d%d",&n,&m);
40 for(int i=1;i<=n;i )
41 scanf("%d",&a[i]);
42 for(int i=1;i<=m;i ){
43 int u,v;
44 scanf("%d%d",&u,&v);
45 du[u] ;
46 du[v] ;
47 }
48 solve();
49 }
50 return 0;
51 }[ HDU 5884 ] Sort
做过类似的，主要要注意的是不能刚好每次k个时，要第一次来合并不足k个的，两个单调队列，一个是合并后的，一个是未合并的，每次合并时选两个队列里小的那个。
二分判断的时候，如果答案已经超过cost，就一定不行了。
代码语言：javascript复制 1 /*
2 TASK:Sort 合并数列，每次合并花费数列大小之和，求总代价不超过T的最小的每次最多合并个数k。
3 LANG:C
4 URL:http://acm.hdu.edu.cn/showproblem.php?pid=5884
5 */
6 #include<cstdio>
7 #include<algorithm>
8 #include<cstring>
9 #define N 100005
10 #define ll long long
11 using namespace std;
12 ll n,t,p;
13 ll a[N],h[N],cost;//h是合并后的优先队列
14 ll solve(int k)
15 {
16 memset(h,0,sizeof h);
17 t=(n-1)/(k-1);//需要减少n-1堆，每次减少k-1堆能合并几次。
18 p=(n-1)%(k-1);//还要减少p堆（p<k-1）
19 for(int i=0; i<=p; i )//那就合并前p 1堆
20 h[0] =a[i];
21 int top=p 1,htop=0;
22 ll ans=p?h[0]:0;//第一次有合并则加上合并的代价。
23 for(int i=1; i<=t; i )//k个k个合并t次
24 {
25 for(int j=0; j<k; j )//合并k个
26 if(htop>=i||a[top]<h[htop]&&top<n)//如果合并队列里没有了可选的了，或者未合并队列的更小，则取未合并队列的。
27 h[i] =a[top ];
28 else
29 h[i] =h[htop ];
30 ans =h[i];//累加答案
31 if(ans>cost)
32 return 0;
33 }
34 if(ans>cost)
35 return 0;
36 return 1;
37 }
38 int main()
39 {
40 int t;
41 scanf("%d",&t);
42 while(t--){
43 scanf("%lld%lld",&n,&cost);
44 for(int i=0; i<n; i )
45 scanf("%lld",&a[i]);
46 sort(a,a n);
47 int l=2,r=n;
48 while (l<r) {
49 int m=(l r)/2;
50 if(solve(m))
51 r=m;
52 else
53 l=m 1;
54 }
55 printf("%dn",l);
56 }
57 return 0;
58 }[ HDU 5887 ] Herbs Gathering
用map来存状态转移，还要优化一下，去掉体积更大且价值更小的状态。
代码语言：javascript复制 1 /*
2 TASK:Herbs Gathering 容量很大，价值也很大，数量少的01背包问题。
3 LANG:C
4 URL:http://acm.hdu.edu.cn/showproblem.php?pid=5887
5 */
6 #include <iostream>
7 #include <algorithm>
8 #include <cstdio>
9 #include <cstring>
10 #include <map>
11 #define ll long long
12 using namespace std;
13 const int N=108;
14 map<ll,ll>mm[N];
15 map<ll,ll>::iterator it,ij;
16 int n,t;
17 ll a[N],b[N];
18 int main() {
19 while(~scanf("%d%d",&n,&t)){
20 for(int i=0;i<=n;i )
21 mm[i].clear();
22 mm[0][0]=0;
23 for(int i=1;i<=n;i ){
24 scanf("%lld%lld",&a[i],&b[i]);
25 mm[i][0]=0;
26 }
27
28 for(int i=1;i<=n;i ){
29 for(it=mm[i-1].begin();it!=mm[i-1].end();it ){
30 if(it->first a[i]<=t)
31 {
32 if(mm[i].count((it->first) a[i]))
33 mm[i][(it->first) a[i]]=max(it->second b[i],mm[i][(it->first) a[i]]);
34 else mm[i][(it->first) a[i]]=it->second b[i];
35 }
36 if(mm[i].count((it->first)))
37 mm[i][(it->first)]=max(it->second,mm[i][it->first]);
38 else
39 mm[i][it->first]=it->second;
40
41 ll rm=0;
42 for(ij=mm[i].begin();ij!=mm[i].end();ij ){
43 //printf("%d [%lld %lld]:[%lld %lld]n",i,ij->first,ij->second,it->first,it->second);
44 if(ij->first>it->first &&ij->second<it->second)
45 rm=ij->first;
46 else if(ij->first<it->first && ij->second>it->second)
47 rm=it->first;
48 }
49 if(rm)
50 mm[i].erase(rm);
51 }
52 }
53 ll ans=0;
54 for(it=mm[n].begin();it!=mm[n].end();it )
55 ans=max(ans,(it->second));
56
57 printf("%lldn",ans);
58 }
59
60 }[ HDU 5889 ] Barricade
先用bfs求出最短路（经过最少点到达），之后把最短路的边加到网络流的边里，注意这里的权值是给的w，用isap跑网络流比较保险，不容易超时。
代码语言：javascript复制/*
TASK:Barricade 求最短路的最小割
LANG:C
URL:http://acm.hdu.edu.cn/showproblem.php?pid=5889
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define ll long long
#define N 1005
#define M 40010
#define inf 0x3f3f3f3f
using namespace std;
struct edge{
int to,next,cap,flow;
}e[M];
int head[N],cnt;
int gap[N],dep[N],cur[N];
void init(){
cnt=0;
memset(head, -1, sizeof head);
}
void add(int u,int v,int w,int rw=0){
e[cnt]=(edge){v,head[u],w,0};
head[u]=cnt ;
e[cnt]=(edge){u,head[v],rw,0};
head[v]=cnt ;
}
int q[N];
void bfs(int st,int ed){
memset(dep,-1,sizeof dep);
memset(gap,0,sizeof gap);
gap[0]=1;
int front=0,rear=0;
dep[ed]=0;
q[rear ]=ed;
while(front!=rear){
int u=q[front ];
for(int i=head[u];~i;i=e[i].next){
int v=e[i].to;
if(dep[v]!=-1)continue;
q[rear ]=v;
dep[v]=dep[u] 1;
gap[dep[v]] ;
}
}
}
int s[N];
int sap(int st,int ed,int n){
bfs(st,ed);
memcpy(cur,head,sizeof head);
int top=0;
int u=st;
int ans=0;
while(dep[st]<n){
if(u==ed){
int Min=inf;
int inser;
for(int i=0;i<top;i )
if(Min>e[s[i]].cap-e[s[i]].flow){
Min=e[s[i]].cap-e[s[i]].flow;
inser=i;
}
for(int i=0;i<top;i ){
e[s[i]].flow =Min;
e[s[i]^1].flow-=Min;
}
ans =Min;
top=inser;
u=e[s[top]^1].to;
continue;
}
bool flag=false;
int v;
for(int i=cur[u];~i;i=e[i].next){
v=e[i].to;
if(e[i].cap-e[i].flow&&dep[v] 1==dep[u]){
flag=true;
cur[u]=i;
break;
}
}
if(flag){
s[top ]=cur[u];
u=v;
continue;
}
int Min=n;
for(int i=head[u];~i;i=e[i].next)
if(e[i].cap-e[i].flow &&dep[e[i].to]<Min){
Min=dep[e[i].to];
cur[u]=i;
}
gap[dep[u]]--;
if(!gap[dep[u]])return ans;
gap[dep[u]=Min 1] ;
if(u!=st)u=e[s[--top]^1].to;
}
return ans;
}
int n,m;
int g[N][N],vis[N],d[N];
void solve(){
int l=0,r=0;
q[0]=1;
d[1]=0;
memset(vis,0,sizeof vis);
while(l<=r){
int k=q[l ];
for(int i=2;i<=n;i )if(g[k][i]!=-1){
if(vis[i])continue;
q[ r]=i;
vis[i]=1;
d[i]=d[k] 1;
}
}
init();
for(int i=1;i<=n;i )
for(int j=1;j<=n;j )
if(g[i][j]!=-1&&d[j]==d[i] 1)
add(i,j,g[i][j]);
printf("%dn",sap(1,n,n));
}
int main() {
int t;
scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
memset(g,-1,sizeof g);
for(int i=1;i<=m;i ){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
g[v][u]=g[u][v]=w;
}
solve();
}
return 0;
}小结：这次比赛既没带草稿纸又没带笔，还迟到，我们的态度太不认真了，不过睡得那么晚我真是起不来啊。我觉得我们还要多练多做，我发现很多基本的知识都不熟悉。
