A题 ............太水就不说了，贴下代码
#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
int n,m;
int main()
{
int i,j;
scanf("%d",&n);
int nn=n;
int cnt=;
while(nn>=)
{
nn/=;
cnt*=;
}
printf("%d\n",cnt*(nn+)-n);
}
B题 开始没看懂题什么意思（英语渣），然后看着样例找到了规律，就AC了
题意是计算上升和下降的序列数之和，再除以n-k+1即可，相当于求其中每k个数的和的平均值！
#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
int n,m,k;
double arr[];
double sum[];
int main()
{
int i,j;
scanf("%d%d",&n,&k);
for(i=;i<=n;i++)scanf("%lf",&arr[i]);
sum[]=;
for(i=;i<=n;i++)sum[i]=sum[i-]+arr[i];
double ans=;
for(i=;i+k<=n;i++)
{
ans+=sum[i+k]-sum[i];
}
ans/=((n-k+));
printf("%.10f\n",ans);
}
C 题 题目的意思是主人有n个茶杯，每个茶杯有容量。现在给一壶茶，总量为w。希望倒茶满足条件：每杯茶要超过容量的一半，并且w被倒光，茶杯内的茶水为整数，容量大的杯子内的茶不允许比容量小的杯子内的茶水少。
先给每个茶杯倒一半的水，然后把剩下的水尽量倒到容量大的茶杯里，倒完为止
#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
using namespace std;
int n,m,w;
int arr[];
typedef struct node
{
int id,val,lim;
friend bool operator<(node a,node b){return a.lim<b.lim;}
}node;
node axx[];
int main()
{
int i,j;
scanf("%d%d",&n,&w);
int lim=;
for(i=;i<n;i++)
{
scanf("%d",&arr[i]);
lim+=(arr[i]+)/;
}
if(w<lim)printf("-1\n");
else
{
w-=lim;
for(i=;i<n;i++)axx[i].id=i,axx[i].val=(arr[i]+)/,axx[i].lim=arr[i];
sort(axx,axx+n);
for(i=n-;i>=&&w>;i--)while(axx[i].lim>axx[i].val&&w>)axx[i].val++,w--;
for(i=;i<n;i++)arr[axx[i].id]=axx[i].val;
for(i=;i<n;i++)
{
if(i)printf(" ");
printf("%d",arr[i]);
}
printf("\n");
}
}
D 题 给你一个序列ai，首先你可以让序列中的一个数移动到这个序列的任何一个位置，然后让你求是否存在一个前缀，使得前缀和等于序列中其余的数的和
解法:扫一遍求前缀和，扫x时有三种情况是yes，第一，1~x的前缀和恰好等于序列总和的一半；第二，存在前缀序列中某一个数跳到了后缀里，使得新的前缀和满足条件，
即(1~x+1前缀和-跳出去的数的值)=序列总和的一半；第三，存在后缀序列中某一个数跳到了前缀里，使得新的前缀和满足条件，即(1~x-1前缀和+跳进来的数的值)=序列总和的一半，
只要用map来维护前缀和后缀中存在的数即可
#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<map>
using namespace std;
typedef long long ll;
int n,m;
ll arr[];
ll sum[];
map<ll,int>dui1,dui2;
int main()
{
int i,j;
scanf("%d",&n);
for(i=;i<=n;i++)scanf("%I64d",&arr[i]);
dui1.clear();
dui2.clear();
sum[]=;
for(i=;i<=n;i++)sum[i]=sum[i-]+arr[i];
if(sum[n]&)
{
printf("NO\n");
}
else
{
for(i=;i<=n;i++)
{
if(!dui2.count(arr[i]))dui2[arr[i]]=;
else dui2[arr[i]]++;
}
for(i=;i<n;i++)
{
dui1[arr[i]]=;
dui2[arr[i]]--;
if(sum[i]==sum[n]/)
{
printf("YES\n");
return ;
}
else if(dui1.count(arr[i+]+sum[i]-sum[n]/))
{
printf("YES\n");
return ;
}
else if(dui2[-sum[i]+arr[i]+sum[n]/]>)
{
printf("YES\n");
return ;
}
}
printf("NO\n");
}
return ;
}
E题 题意是一个01背包，坏消息是n<=100000,m<=300000,好消息是w=1,2,3...这个题直接O(nm)去做肯定不行，模拟比赛的时候我心存侥幸大范围贪心，小范围dp，然后果断WA了....
正解是三分法，首先我们把物品以w=1,2,3分类，然后分别排序，并求出前缀和，然后枚举取用w=3的物品的个数，然后 三分2的个数， 1的个数也就知道了 。而2的个数和是一个单峰函数，
所以可以用三分法
#include<string>
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstdio>
#include<set>
using namespace std;
typedef long long ll;
vector<ll>arr[];
ll sum[][];
ll n,m;
bool cmp(ll a,ll b){return a>b;}
ll getans(ll tri,ll dob){return sum[][tri]+sum[][dob]+sum[][m-tri*-dob*];}
int main()
{
ll i,j;
scanf("%d%d",&n,&m);
for(i=;i<n;i++)
{
ll w;
ll val;
scanf("%I64d%I64d",&w,&val);
arr[w].push_back(val);
}
for(i=;i<=;i++)sort(arr[i].begin(),arr[i].end(),cmp);
for(i=;i<=;i++)
{
sum[i][]=;
for(j=;j<=arr[i].size();j++)sum[i][j]=sum[i][j-]+arr[i][j-];
for(j=arr[i].size()+;j<=m;j++)sum[i][j]=sum[i][j-];
}
ll maxn=;
for(i=;i<=arr[].size();i++)
{
if(*i>m)break;
ll l=,r=(m-*i)/;
while(r-l>)
{
ll rmid=(r*+l)/;
ll lmid=(l*+r)/;
ll ans1=getans(i,lmid);
ll ans2=getans(i,rmid);
if(ans1>ans2)r=rmid;
else l=lmid;
maxn=max(maxn,ans1);
maxn=max(maxn,ans2);
}
for(j=l;j<=r;j++)maxn=max(getans(i,j),maxn);
//printf("%I64d\n",maxn);
}
printf("%I64d\n",maxn);
return ;
}