上文有提到noip2014还有没A的嘛。。就先把这个坑给填了
flappy bird好sad啊 还是先做解方程
八中的数据好强了,然而我最后凑了四个质数就A了,感谢shy!
作为联赛最后一题,学习它的思考方式比较关键.
前30分,人人都能得吧,不多说.
我一开始做,居然没有看到高精度,搞什么啊...看到1010000居然没有自动次方,晕.
看到了超长的a[i]后,可能很多人都会跟我一样,啊啊啊高精度,啊啊啊不想写,然后就能自然地诞生出取模的想法啦!
而且,五次方以上的方程没有求根公式,要么枚举要么hash!
当f(x)==0,f(x)%p==0.再进一步考虑，f(x+p)%p==f(x)%p,Po姐的blog没有写为啥,相信这个连我都能懂,所有人都可以自己脑补了.
对于每个ans,将它mod p,预处理出对于每一个质数,x取0~p-1时f(x)是否为0.
接下来是考虑冲突的问题,每一篇题解上都说冲突概率很小...个人觉得..如果出题人要卡你的话,3w以内的质数是全都可以被卡掉的吧..
不过思考也不成熟,哈希嘛尽管用就行了.
#include<cstdio>
#include<cstdio>
#define ll long long
using namespace std;
,,,,};
ll n,m,tot=;ll f[][];ll b[];
ll a[][];
inline void input(int x)
{
];);
;s[i];i++)
{
if(s[i]=='-')flag=true;
;j<=;j++)a[x][j]=(a[x][j]*+s[i]-')%pri[j];
}
;j<;j++)a[x][j]=pri[j]-a[x][j];
}
inline ll F(int x,int j)
{
ll re=;
;i--)
re=(re*x+a[i][j])%pri[j];return re;
}
int main()
{
//freopen("my.out","w",stdout);
scanf("%lld%lld",&n,&m);
;i<=n;i++)input(i);
;j<=;j++);i<pri[j];i++)
f[i][j]=F(i,j);
;ans<=m;ans++)
{
;
;i<=;i++)
{
int p=pri[i],x=ans%p;
)s++;
}
)++tot,b[tot]=ans;
}
printf("%lld\n",tot);
;i<=tot;i++)printf("%lld\n",b[i]);
}
【飞扬的小鸟】
终于开坑了。。。其实好久之前就开坑了。。。。
之前有一个很搞笑的trick,在罗oj上交了一发,等待&pending.....等了好几个月...
时隔半年之后再做,做到了大概七十分的样子...然后还是有wa的..不管它65分了
又过了有三个月吧 就是今天
因为学校迎检各种没课没作业 有充足的时间来搞这道题 就写了完全背包...
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define inf 2000000000
#define M 10010
using namespace std;
int n,m,k,p,sum,cnt;
int lo[M],ans[M],hi[M],up[M],down[M],d[M];
int f[M][1010];
int main()
{
//freopen("219.in","r",stdin);
//freopen("219.out","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<=n-1;i++)scanf("%d%d",&up[i],&down[i]);
for(int i=0;i<=n;i++)lo[i]=0,hi[i]=m+1;
for(int i=1;i<=k;i++)
{
scanf("%d",&p);
d[p]=1;scanf("%d%d",&lo[p],&hi[p]);
}
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)f[i][j]=inf;
for(int j=1;j<=m;j++)f[0][j]=0;
for(int j=0;j<=n;j++)ans[j]=inf;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j>=up[i-1]){
f[i][j]=min(f[i][j],f[i-1][j-up[i-1]]+1);
f[i][j]=min(f[i][j],f[i][j-up[i-1]]+1);
} //完全背包很好理解吧..希望自己比赛的时候能想到
if(j==m){
for(int k=j-up[i-1];k<=m;k++){
f[i][j]=min(f[i][j],f[i-1][k]+1);
f[i][j]=min(f[i][j],f[i][k]+1);//个人觉得这句话可以del，然而wa了，然后顿悟！这也是我为什么一开始70分中有wa的原因，前一个可以一直跳一直跳跳到m！！！
}
}
}
for(int j=lo[i]+1;j<=hi[i]-1;++j)
if(j+down[i-1]<=m)f[i][j]=min(f[i][j],f[i-1][j+down[i-1]]);
for(int j=1;j<=lo[i];++j)f[i][j]=inf;
for(int j=hi[i];j<=m;j++)f[i][j]=inf;
for(int j=1;j<=m;j++)ans[i]=min(ans[i],f[i][j]);
}
int sum=0;
for(int i=0;i<=n;i++)if(d[i]==1&&ans[i]<inf)sum++;
if(ans[n]==inf)printf("0\n"),printf("%d",sum);
else printf("1\n"),printf("%d",ans[n]);
}