丑话说在前头，T8我不会。（没错是指我会出丑……）
既然要玩尽可能多轮，那么每轮投入的钱就要最少，也就是 m m m 元，那么可以算出每轮游戏会亏损 ⌈ x × p % ⌉ \lceil x\times p\%\rceil ⌈x×p%⌉ 元，算一下可以玩几轮即可。
代码如下：
#include <cstdio>
#include <cmath>
int T,n,m,p;
int main()
{
scanf("%d",&T);while(T--)
{
scanf("%d %d %d",&n,&m,&p);
int cost=ceil(1.0*m*p/100.0);
printf("%d\n",(n-m)/cost+1);
}
}
显然将所有人排成一排距离和最小，对于每个间距，计算有多少个人计算距离时会算到这个间距，就可以知道这个间距对总和的贡献。
代码如下：
#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 100010
#define ll long long
int T,n,a[maxn];
int main()
{
scanf("%d",&T);while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+n+1);
ll ans=0;
for(int i=1;i<n;i++)ans+=1ll*i*(n-i)*(a[i+1]-a[i]);
printf("%lld\n",ans);
}
}
这题当时把我坑惨了……行末居然不能输出 0 0 0。
模拟一下即可，代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 20010
int T,n,len[maxn],pos[maxn][110],limit;
bool v[110],col[maxn];
int ans[maxn],anss;
int main()
{
scanf("%d",&T);while(T--)
{
scanf("%d",&n);limit=0;
memset(col,false,sizeof(col));
memset(pos,0,sizeof(pos));
for(int i=1;i<=n;i++){
scanf("%d",&len[i]);
for(int j=1,x,y;j<=len[i];j++){
scanf("%d %d",&x,&y),pos[i][x]=y;
limit=max(limit,x);
}
}
col[1]=true;
for(int i=1;i<=limit;i++){
memset(v,false,sizeof(v));
for(int j=1;j<=n;j++)if(pos[j][i]&&col[j])v[pos[j][i]]=true;
for(int j=1;j<=n;j++)if(pos[j][i]&&v[pos[j][i]])col[j]=true;
}
anss=0;
for(int i=1;i<=n;i++)if(col[i])ans[++anss]=i;
for(int i=1;i<anss;i++)printf("%d ",ans[i]);
printf("%d",ans[anss]);
printf("\n");
}
}
这题相当于要你将 10 10 10 个球放到 5 5 5 个盒子里，每个球有一个重量，令放完之后最轻的盒子重量为 k k k，要让 n − k n-k n−k 最小。
比赛时， 5 10 5^{10} 510 的暴力可以以 600 m s 600ms 600ms 的速度跑过去。
但是后来去 h d u hdu hdu 上交时就不行了，大概是赛时开了O2。
这种做法复杂度大概是 9 × 1 0 6 9\times 10^6 9×106 接近 1 × 1 0 7 1\times 10^7 1×107 级别的，而正解是个二分加dp的做法，复杂度大概是 log 2 ( 10000 ) × 10 × 3 10 ≈ 7 × 1 0 6 \log_2(10000)\times 10\times 3^{10}\approx 7\times 10^6 log2(10000)×10×310≈7×106。
但是考虑优化一下暴力，发现假如有盒子是空的那么答案一定不是最优的，于是枚举时不考虑有空盒子的情况，那么时间复杂度就是个第二类斯特林数，由于盒子是不同的再乘一个阶乘，就是 S ( 10 , 5 ) × 5 ! ≈ 5 × 1 0 6 S(10,5)\times 5!\approx 5\times 10^6 S(10,5)×5!≈5×106。
虽然说着很快，但实际上是压时过的……
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int T,n,tot[10],c[10],ans,kong=5;
void dfs(int x)
{
if(10-x<kong)return;
if(x==10)
{
int mi=999999999;
for(int i=0;i<5;i++)mi=min(mi,c[i]);
ans=min(ans,n-mi);
return;
}
for(int i=0;i<5;i++){
if(!c[i])kong--;c[i]+=tot[x];
dfs(x+1);
c[i]-=tot[x];if(!c[i])kong++;
}
}
int main()
{
scanf("%d",&T);while(T--)
{
scanf("%d",&n);
char s[10];
memset(tot,0,sizeof(tot));
for(int i=1;i<=n;i++)scanf("%s",s),tot[s[4]-'0']++;
ans=999999999;dfs(0);
printf("%d\n",ans);
}
}
考虑费用流，人的口味可以分为六种，分别统计出数量然后建图，二分图左边是三种饮料，右边是六种人，中间的边费用对应题中的欢乐值，那么答案就是最大费用最大流。
代码如下：
#include <cstdio>
#include <cstring>
#include <map>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 110
#define inf 999999999
int test,n,c[4],S,T;
struct edge{int x,y,z,cost,next;}e[maxn<<3];
int first[maxn],len;
void buildroad(int x,int y,int z,int cost){e[++len]=(edge){x,y,z,cost,first[x]};first[x]=len;}
void ins(int x,int y,int z,int cost){buildroad(x,y,z,cost);buildroad(y,x,0,-cost);}
map<string,int>mp;
map<int,string>MP;
int tot[maxn];
int q[maxn],st,ed,dis[maxn],fa[maxn];
bool v[maxn];
bool SPFA()
{
for(int i=1;i<=T;i++)fa[i]=0,dis[i]=-inf;
st=1;ed=2;q[st]=S;v[S]=true;dis[S]=0;
while(st!=ed){
int x=q[st++];st=st>maxn-10?1:st;v[x]=false;
for(int i=first[x];i;i=e[i].next){
int y=e[i].y;
if(e[i].z&&dis[y]<dis[x]+e[i].cost){
dis[y]=dis[x]+e[i].cost;fa[y]=i;
if(!v[y])v[q[ed++]=y]=true,ed=ed>maxn-10?1:ed;
}
}
}
return fa[T];
}
int main()
{
mp["012"]=1;mp["021"]=2;mp["102"]=3;mp["120"]=4;mp["201"]=5;mp["210"]=6;
MP[1]="012";MP[2]="021";MP[3]="102";MP[4]="120";MP[5]="201";MP[6]="210";
scanf("%d",&test);while(test--)
{
scanf("%d %d %d %d",&n,&c[1],&c[2],&c[3]);
memset(tot,0,sizeof(tot));string s;
for(int i=1;i<=n;i++)cin>>s,tot[mp[s]]++;
memset(first,0,sizeof(first));len=1;S=10;T=11;
for(int i=1;i<=3;i++)ins(S,i,c[i],0);
for(int i=1;i<=6;i++){
s=MP[i];
ins(s[0]-'0'+1,i+3,inf,3);
ins(s[1]-'0'+1,i+3,inf,2);
ins(s[2]-'0'+1,i+3,inf,1);
ins(i+3,T,tot[i],0);
}
int ans=0; while(SPFA())
{
int min_flow=inf;
for(int i=fa[T];i;i=fa[e[i].x])
min_flow=min(min_flow,e[i].z);
for(int i=fa[T];i;i=fa[e[i].x])
e[i].z-=min_flow,e[i^1].z+=min_flow,
ans+=e[i].cost*min_flow;
}
printf("%d\n",ans);
}
}
贪心思路是很容易看出来的，只是实现需要细致一些。
最优的方法肯定是两边的杆在最上面放，一路放下来，然后在下面的杆上放尽可能多。
但是也要考虑下面的杆长度比 x x x 小的情况，那么就是两边的杆交替放，具体细节可以看代码：
#include <bits/stdc++.h>
using namespace std;
int T;
double a,b,x;
int main()
{
scanf("%d",&T);while(T--)
{
scanf("%lf %lf %lf",&a,&b,&x);
if(x>b)
{
double c=sqrt(x*x-b*b);
if(2*c<x){
int k=floor(a/x);int ans=2*k+1;
double X=a-k*x,Y=X-(x-c);
if(X>=c)ans++,Y=X-c;
if(sqrt(x*x-X*X)+sqrt(x*x-Y*Y)<=b)ans++;
printf("%d\n",ans);
}
else printf("%d\n",(int)(a/c)+1);
}
else
{
int ans1,ans2;
ans1=(int)(a/x)+1;
double c=a-1.0*(ans1-1)*x;
c=sqrt((double)(x*x-c*c));
if(b-c*2>=x)ans2=(int)((b-c*2-x)/x)+2;
else if(b-c*2>=0)ans2=1;
else ans2=0;
printf("%d\n",ans1*2+ans2);
}
}
}
可以发现，Alice写完的题，肯定都是在Bob也写完后才交，这样Bob浪费最多时间，所以Bob做完第 i i i 题的时刻一定是 ∑ j = 1 i b [ j ] \sum_{j=1}^i b[j] ∑j=1ib[j]，假如Alice写完第i题后的时刻Bob已经写完了，那么Alice肯定不写这题，那么就是个简单的dp了。
代码如下：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxn 2010
#define ll long long
#define inf 999999999999999999ll
int T,n;
ll a[maxn],b[maxn],f[maxn][maxn];//f[i][j]表示前i题中Alice做完其中j题后的最小时刻
int main()
{
scanf("%d",&T);while(T--)
{
scanf("%d",&n);
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)f[i][j]=inf;
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
for(int i=1;i<=n;i++)scanf("%lld",&b[i]),b[i]+=b[i-1];
f[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=i;j>=0;j--){
f[i][j]=f[i-1][j];
if(j>0&&f[i-1][j-1]+a[i]<=b[i])//假如Alice做完这题后Bob还没做完
f[i][j]=min(f[i][j],f[i-1][j-1]+a[i]);
}
}
for(int i=n;i>=0;i--)if(f[n][i]<inf){printf("%d\n",i);break;}
}
}