a.pigofzhou的巧克力棒
举一些例子，可以得出把长度为n的棒划分最多高兴值的方法是：设最大的不超过n的2的整数幂是k，则分为2^k和n-2^k两份。
2^k则是每次分为两半，而剩下的再递归以同样的方法划分。
f（n）=f（2^k）+f（n-2^k），f（2^k）=2*f（2^(k-1)）+1.
最开始时自己错误地认为每次减半就好了，结果n=6时先分为了两个长度3，不够优，正确的方法是分为4和2两份。
#include<cstdio>
using namespace std;
int t,n;
int f(int t)
{
if(t==1)return 0;
for(int i=30;;i--)
{
if(t==(1<<i))
{
return 2*f(t/2)+1;
}
else if(t>(1<<i))
{
return f(1<<i)+f(t-(1<<i));
}
}
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
printf("%d\n",f(n));
}
return 0;
} 后来看大佬的blog，了解到第一题可以和第二题用同样的代码ac，理解了一下，大概是自底向上的思路：假如n=9，则1~9中2存在2这个因子的有2，4，6，8四个数，记录下4个，然后每个数提出去一个因子2，结果是1，2，3，4，再找有2这个因子的数木，为2，相当于把这四个两两合并，再2/2，为1，共4+2+1=7种，就是这样自底向上，逐层合并。
#include<iostream>
using namespace std;
int main()
{
int t;
long long n,ans;
cin>>t;
while(t--)
{
cin>>n;
ans=0;
while(n)
{
ans+=n/2;
n/=2;
}
cout<<ans<<endl;
}
return 0;
}
b.Zhazhahe究竟有多二
统计n!中含有素数因子k的个数，数学推导如下：
设n!=1*2*3*......*n=(1*k)*(2*k)*(3*k)*......*(m*k)*a //其中m=n/k，a为不含因子k的数的乘积
=(k^m)*(m!)*a，接着以同样的方法递归求m!.
#include<iostream>
using namespace std;
int main()
{
int t;
long long n,ans;
cin>>t;
while(t--)
{
cin>>n;
ans=0;
while(n)
{
ans+=n/2;
n/=2;
}
cout<<ans<<endl;
}
return 0;
} c.剁手女生节
这道题要注意：不能想当然地认为买3本的价钱比买2本贵，买2本比买一本贵，必须详尽地考虑清楚所有的情况。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
long long t,n,a,b,c;
int main()
{
scanf("%lld",&t);
while(t--)
{
scanf("%lld%lld%lld%lld",&n,&a,&b,&c);
if(n%4==0)printf("0\n");
else if(n%4==3)printf("%lld\n",min(min(a,b+c),3*c));
else if(n%4==2)printf("%lld\n",min(min(2*a,b),2*c));
else printf("%lld\n",min(min(3*a,a+b),c));
}
return 0;
} d.勤奋的涟漪2
这题其实也不是很难，但是自己在第21行丢了d[i]=0，使得多组数据受到上一组残留数据的影响，结果死活找不出来这个bug，第二天才灵机一动在高数课上用手机ac了这道题。
#include<iostream>
using namespace std;
int t,n,a[105],ans,d[105];
void solve()
{
for(int i=1;i<=n;i++)
{
if(a[i]==3)
{
if(d[i-1])d[i]=3-d[i-1];
else
{
int j;
for(j=i+1;j<=n;j++)if(a[j]==1||a[j]==2)break;
if(j<=n)d[i]=((j-i)%2==0) ? a[j] : 3-a[j];
else d[i]=1;
}
}
else if(a[i]==0){ans++;d[i]=0;}
else if(a[i]==1)
{
if(d[i-1]==1)
{
ans++;
d[i]=0;
}
else d[i]=1;
}
else if(a[i]==2)
{
if(d[i-1]==2)
{
ans++;
d[i]=0;
}
else d[i]=2;
}
}
}
int main()
{
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
ans=0;
solve();
cout<<ans*-24<<endl;
}
return 0;
} e.穷游中国在统题
一个区间的元素可以形成一组的条件是这个区间以后的所有元素都大于或等于这个区间的所有元素，即区间后的最小值>=区间的最大值。于是从后往前预处理一下每个元素后面的所有元素的最小值，再从前往后扫一遍，维护当前最大值，就可以了。
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int t,n,a[100005];
int minn[100005],maxn,ans;
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;i++)cin>>a[i];
ans=0;
maxn=-1;
minn[n]=a[n];
for(int i=n-1;i>0;i--)minn[i]=min(a[i],minn[i+1]);
for(int i=1;i<n;i++)
{
maxn=max(maxn,a[i]);
if(maxn<=minn[i+1])ans++;
}
cout<<ans+1<<endl;
if(t)cout<<endl;
}
return 0;
} 看大佬的blog有一个思路是把原数组sort（）一下，对于每一个元素，它的原始位置和排序后的位置及其之间的所有元素必须在同一个组里，按照这个思路，我写了程序，结果runtime error，好像是因为sort（）崩溃，自己也不了解sort（）的内部实现，把数组换成结构体之后sort（）就可以了，sort（）崩溃的问题占坑以后解决。
下面是ac代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int t,n;
struct node{
int v,pre;
}a[100005];
bool cmp(node i,node j)
{
return i.v<j.v || (i.v==j.v && i.pre<j.pre);
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i].v);
for(int i=1;i<=n;i++)a[i].pre=i;
sort(a+1,a+1+n,cmp);
int pos=1,r=1,ans=0;
while(pos<=n)
{
while(pos<=r)
{
r=max(a[pos++].pre,r);
}
ans++;
r=a[pos].pre;
}
printf("%d\n",ans);
if(t)printf("\n");
}
return 0;
} 下面是自己的re代码：
#include<cstdio>
#include<algorithm>
using namespace std;
int t,n,a[100005],pre[100005];
bool cmp(int i,int j)
{
return a[i]<=a[j];
}
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++)pre[i]=i;
sort(pre+1,pre+1+n,cmp);
int pos=1,r=1,ans=0;
while(pos<=n)
{
while(pos<=r)
{
r=max(pre[pos++],r);
}
ans++;
r=pre[pos];
}
printf("%d\n",ans);
if(t)printf("\n");
}
return 0;
} f.神偷TMK
不说了。
g.神偷TMK后续
组合数。用杨辉三角或等式c(n,k)=c(n,k-1)*(n-k+1)/k都可以。紫书有详解。
h.《为什么会变成这样呢》
先排序，排好后相等的元素会相邻，然后就好找了。
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int t,n,a[1000005];
int b[2],num;
int main()
{
scanf("%d",&t);
while(t--)
{
num=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
sort(a+1,a+1+n);
for(int i=2;i<n;i++)if(a[i]!=a[i-1] && a[i]!=a[i+1])b[num++]=a[i];
if(a[1]!=a[2])b[num]=a[1];
else if(a[n-1]!=a[n])b[num]=a[n];
printf("%d %d\n",min(b[1],b[0]),max(b[1],b[0]));
}
return 0;
} i.只会做水题的jiakin
先记录下任意两种水管上下或者左右是否可以连接，然后从右下角搜索到左上角就可以了。
#include<cstdio>
#include<iostream>
using namespace std;
int t,n,m,a[1005][1005][2];
bool have[6][6][5];
void init()
{
have[2][0][3]=have[2][0][4]=1;
have[2][1][1]=have[2][1][2]=1;
have[2][2][2]=have[2][2][3]=1;
have[2][3][1]=have[2][3][4]=1;
have[2][4][1]=have[2][4][3]=1;
have[2][5][2]=have[2][5][4]=1;
have[3][0][2]=have[3][0][3]=have[3][0][4]=1;
for(int i=1;i<4;i++)have[3][1][i]=1;
for(int i=1;i<=4;i++)if(i!=2)have[3][2][i]=1;
for(int i=1;i<=4;i++)if(i!=3)have[3][2][i]=1;
for(int i=1;i<=4;i++)have[3][2][i]=1;
}
bool ok(int x,int y)
{
return x>=1&&x<=n&&y>=1&&y<=m;
}
bool f(int x,int y)
{
if(x==1&&y==1)return 1;
if(have[a[x][y][0]][a[x][y][1]][1]&&ok(x-1,y)&&have[a[x-1][y][0]][a[x-1][y][1]][2])if(f(x-1,y))return 1;
if(have[a[x][y][0]][a[x][y][1]][3]&&ok(x,y-1)&&have[a[x][y-1][0]][a[x][y-1][1]][4])if(f(x,y-1))return 1;
return 0;
}
int main()
{
init();
cin>>t;
for(int num=1;num<=t;num++)
{
cin>>n>>m;
getchar();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)scanf("(%d,%d)",&a[i][j][0],&a[i][j][1]);
getchar();
}
printf("Case %d\n",num);
printf(f(n,m)?"Well done!\n":"What a pity!\n");
}
return 0;
} j.质方数
先筛素数，筛到sqrt（n）即可，然后暴力从小到大枚举素数，对其平方，记录与n最近的质方数和对应的最小距离。这居然都能过！
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int t,n,v[20005],minn,ans;
int main()
{
for(int i=2;i<20000;i++)
if(!v[i])for(int j=i*i;j<20000;j+=i)v[j]=1;
scanf("%d",&t);
while(t--)
{
minn=(1<<30);
scanf("%d",&n);
for(int i=2;i<20000;i++)if(!v[i])
{
if(abs(i*i-n)<minn)
{
minn=abs(i*i-n);
ans=i*i;
}
}
printf("%d\n",ans);
}
return 0;
}
京公网安备 11010502036488号