长乐Day5
T1、圆圈舞蹈
圆圈舞蹈
将环断开，变成一条2*n的链，只需求sum<=总长/2的最大sum。
可以采用二分求解。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int a[1000010],n,sum[1000010],cnt,Max;
bool check(int x,int y)
{
if(sum[y]-sum[x-1]<=cnt/2) return true;
else return false;
}
int main()
{
// freopen("circle.in","r",stdin);
// freopen("circle.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
cnt+=a[i];
}
for(int i=1;i<=2*n;i++)
{
sum[i]=sum[i-1]+a[i];
}
for(int i=1;i<=n;i++)
{
int l=i,r=i+n-1,last;
while(l<r)
{
int mid=(l+r)>>1;
if(check(i,mid))
{
last=mid;
l=mid+1;
}
else r=mid;
}
Max=max(Max,(sum[last]-sum[i-1]));
}
cout<<Max;
return 0;
}T2、小麦亩产一千八
小麦亩产一千八
不妨设第一个为x，依次递推
1 a==0
x a==1 f[1]x+f[0]
x+1 a==2 f[2]x+f[1]
2x+1 a==3 f[3]x+f[2]
3x+2 a==4 f[4]x+f[3]
5x+3 a==5 f[5]x+f[4]
7x+5 a==6 f[6]x+f[5]
…… …… ……
(f[i]表示斐波那契第i项)
注意：要开long long
#include<iostream>
#include<cstdio>
using namespace std;
long long f[100];
int main()
{
// freopen("kela.in","r",stdin);
// freopen("kela.out","w",stdout);
f[0]=0;
f[1]=1;
for(int i=2;i<=30;i++)
{
f[i]=f[i-1]+f[i-2];
}
long long a,x,b;
while(scanf("%lld",&a)!=EOF)
{
scanf("%lld%lld",&x,&b);
long long ans=(x-f[a-1])/f[a]*f[b]+f[b-1];
if((x-f[a-1])%f[a]!=0) printf("-1\n");
else printf("%lld\n",ans);
}
return 0;
}
/*
1 a==0
x a==1 f[1]x+f[0]
x+1 a==2 f[2]x+f[1]
2x+1 a==3
3x+2 a==4
5x+3 a==5
7x+5 a==6
*/*T3、好元素
好元素
将 a[m]+a[n]+a[p]=a[i] 转换成a[m]+a[n]=a[i]-a[p];
创建一个哈希表，将所有a[m]+a[n]储存进去,对于每个i，查询是否存在a[p]使得式子成立
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 5010, M = 4194303;
int n,a[N],head[M + 10],ver[12600001],Next[12600001],tot,ans;
inline void add(int y)//哈希表
{
int x=y&M;
ver[++tot]=y;
Next[tot]=head[x];
head[x]=tot;
}
int ask(int y)
{
int x=y&M;
for(int i=head[x];i;i=Next[i])
{
if(y==ver[i]) return 1;
}
return 0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(ask(a[i]-a[j]))
{
ans++;
break;//a[i]已被证明是好数，即可退出循环
}
}
for(int j=1;j<=i;j++)
{
add(a[i]+a[j]);
}
}
cout<<ans;
return 0;
}*T4、国际象棋
10分：N*N放入N个棋子，显然方案数为N！(第一行N种选择，第二行N-1种，以此类推)
N*M放入K个棋子(N>=M)，容易想到递推：F[i][j]表示放到第i行放j个棋子的方案数。
50分：F[i][j]=F[i-1][j-1]*(M-j+1)，若此行可以不放，则还要累加一个F[i-1][j]。
100分：现在考虑W和H：类似上面的做法，将棋盘拆成三个部分：
用F[i][x][y][z]表示到了第i层，在1部分放x个，2部分放y个，3部分放z个的方案数。
沿用上面的递推式，F[i][x][y][z]=F[i-1][x-1][y][z]+F[i-1][x][y-1][z]+F[i-1][x][y][z-1]，若此行可以不放再累加一个F[i-1][x][y][z]，而x+y+z=k才更新答案，这里枚举x,y,z时如果从大到小枚举可以省略去第一位的i(上面50分的二维递推亦是如此)，注意到方案数有可能很大，所以需要加个高精
#include<cstdio>
#include<iostream>
using namespace std;
int n,m,w,h,k,l1,l2,l3,H,W,n1,n2,n3;
struct node
{
int f[100];
void clear()
{
for(int i=0;i<=99;i++) f[i]=0;
}
friend bool operator > (node a,node b)
{
if(a.f[0]>b.f[0]) return 1;
if(a.f[0]<b.f[0]) return 0;
for(int i=a.f[0];i>=1;i--)
{
if(a.f[i]>b.f[i]) return 1;
if(a.f[i]<b.f[i]) return 0;
}
return 0;
}
friend node operator + (node a,node b)
{
node c;
if(a>b) c=a;
else c=b;
for(int i=1;i<=c.f[0];i++) c.f[i]=a.f[i]+b.f[i];
for(int i=1;i<=c.f[0];i++)
if(c.f[i]>9)
{
c.f[i+1]+=c.f[i]/10;
c.f[i]%=10;
if(i==c.f[0]) c.f[0]++;
}
return c;
}
friend node operator * (node a,int b)
{
node c=a;
for(int i=1;i<=c.f[0];i++) c.f[i]=a.f[i]*b;
for(int i=1;i<=c.f[0];i++)
if(c.f[i]>9)
{
c.f[i+1]+=c.f[i]/10;
c.f[i]%=10;
if(i==c.f[0]) c.f[0]++;
}
return c;
}
}f[50][25][25][25],ans;
bool check(int x,int y)
{
if(x<=n&&y<=n) return 1;
if(x>w&&x<=w+m&&y>h&&y<=m+h) return 1;
return 0;
}
int main()
{
scanf("%d%d%d%d%d",&n,&m,&w,&h,&k);
if(w>n) w=n;
if(h>n) h=n;
if(m+w<=n&&m+h<=n) w=h=0,m=n;
H=max(m+h,n);W=max(m+w,n);
n1=w;n2=min(m+w,n);n3=max(m+w,n);
l1=n1;l2=n2-n1;l3=n3-n2;
f[0][0][0][0].f[0]=f[0][0][0][0].f[1]=1;
for(int i=0;i<H;i++)
for(int x=0;x<=l1&&x<=k;x++)
for(int y=0;y<=l2&&y+x<=k;y++)
for(int z=0;z<=l3&&z+y+x<=k;z++)
{
if(check(n1,i+1)) f[i+1][x+1][y][z]=f[i+1][x+1][y][z]+f[i][x][y][z]*(l1-x);
if(check(n2,i+1)) f[i+1][x][y+1][z]=f[i+1][x][y+1][z]+f[i][x][y][z]*(l2-y);
if(check(n3,i+1)) f[i+1][x][y][z+1]=f[i+1][x][y][z+1]+f[i][x][y][z]*(l3-z);
f[i+1][x][y][z]=f[i+1][x][y][z]+f[i][x][y][z];
}
for(int x=0;x<=l1;x++)
for(int y=0;y<=l2;y++)
for(int z=0;z<=l3;z++)
if(x+y+z==k)
ans=ans+f[H][x][y][z];
for(int i=ans.f[0];i;i--) printf("%d",ans.f[i]);
return 0;
}