#
hash.同余.不過(guò)這里的同余不是普通意義上的同余.
#include <iostream>
#include <fstream>
using namespace std;
//ifstream fin("1.txt");
const int MAXN=100001;
const int mod=99991;
int n,k;
int c[MAXN][30];
int d[MAXN][30];
int h[mod];
int p[MAXN],len=0;
int s[MAXN];
int result=0;
inline int hashcode(const int id)
{
int s = 0;
for(int i=0; i<k; i++)
s=((s<<2)+(d[id][i]>>4))^(d[id][i]<<10);
s = s % mod;
s = s < 0 ? s + mod : s;
return s;
}
void find_hash(int x,int id)
{
int f[30];
bool ok=true;
for (int i=0;i<k;i++)
{
if (i==0) f[i]=c[id][i]-c[p[x]][i];
else
{
f[i]=c[id][i]-c[p[x]][i];
if (f[i]!=f[i-1]||f[i]==0) {ok=false;break;}
}
}
if (ok)
{
if (result<id-p[x])
{
result=id-p[x];
}
}
if (s[x]==-1)
{
len++;
s[x]=len;
s[len]=-1;
p[len]=id;
return;
}
else
{
find_hash(s[x],id);
}
}
void hash(int u,int id)
{
if (h[u]==-1)
{
len++;
h[u]=len;
s[len]=-1;
p[len]=id;
return;
}
find_hash(h[u],id);
}
int main()
{
cin>>n>>k;
if (n==1) {cout<<1<<endl;exit(0);}
memset(h,-1,sizeof(h));
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++)
{
int x;
cin>>x;
int l=-1;
for (int j=0;j<k;j++)
{
int p=x%2;
l++;
c[i][l]=c[i-1][l]+p;
x/=2;
}
}
memcpy(d,c,sizeof(c));
for (int i=0;i<=n;i++)
{
int max=MAXN;
for (int j=0;j<k;j++)
{
if (max>d[i][j]) max=d[i][j];
}
for (int j=0;j<k;j++)
{
d[i][j]-=max;
}
int u=hashcode(i);
//cout<<u<<endl;
hash(u,i);
}
cout<<result<<endl;
// system("pause");
return 0;
}
這題做的很搞笑..
真得總結(jié)總結(jié)..
把方程分成兩半,然后計(jì)算其中一半,存入hash.
如果枚舉另一半,然后與hash表對(duì)照..并累加..
可笑的我一開(kāi)始用了兩個(gè)大數(shù)組來(lái)當(dāng)hash..直接1對(duì)1映射累加..然后內(nèi)存超了..
然后后來(lái)才想起來(lái)..只用一個(gè)hash..然后另一個(gè)來(lái)找就行了..
但是我用的大數(shù)組還是大了..
應(yīng)該寫(xiě)一個(gè)hash才好..
于是怒了..直接map扔上去..- -
#include <iostream>
#include <map>
using namespace std;
long long result=0;
map<int,int> m;
int main()
{
int a1,a2,a3,a4,a5;
cin>>a1>>a2>>a3>>a4>>a5;
for (int i=-50;i<=50;i++)
for (int j=-50;j<=50;j++)
{
if (i==0||j==0) continue;
int x=i*i*i*a4+j*j*j*a5;
map<int,int>::iterator iter=m.find(x);
if (iter==m.end())
{
m.insert(make_pair(x,1));
}
else
{
iter->second++;
}
}
for (int i=-50;i<=50;i++)
for (int j=-50;j<=50;j++)
for (int k=-50;k<=50;k++)
{
if (i==0||j==0||k==0) continue;
int x=i*i*i*a1+j*j*j*a2+k*k*k*a3;
map<int,int>::iterator iter=m.find(-x);
if (iter!=m.end())
{
result+=iter->second;
}
}
cout<<result<<endl;
system("pause");
return 0;
}
算上有道..第三次玩tc..
不知道是div1...看第一題挺簡(jiǎn)單的..就得意忘形了...也沒(méi)有仔細(xì)看看..想當(dāng)然了..最后終于被cha了..
不過(guò)有幸在room里發(fā)現(xiàn)了Petr..怎是orz啊..
大牛就是大牛..報(bào)了名..沒(méi)參加比賽..
哎.血一般的教訓(xùn)..下回努力
預(yù)賽66....orz..只能說(shuō)是個(gè)很吉利的數(shù)字...
長(zhǎng)期放置java..這個(gè)成績(jī)還在接受范圍呢..
進(jìn)復(fù)賽應(yīng)該沒(méi)問(wèn)題吧...
話說(shuō)當(dāng)初我就說(shuō)了..這樣的題60分就應(yīng)該能進(jìn)..除非專(zhuān)門(mén)天天去背來(lái)背去..
現(xiàn)在果然靈驗(yàn)了..
好了..吃點(diǎn)東西去..下午還有ural..晚上還有topcoder..forza
ural做了2個(gè)半小時(shí)..
做的很糟..只切了2道題...
除了能力,另一個(gè)就是英語(yǔ)問(wèn)題..
根據(jù)提交來(lái)看..應(yīng)該有4-5道水題...
題目大致能看懂...但幾個(gè)細(xì)節(jié)一直看不懂..
于是一個(gè)wa on 5..一個(gè)wa on 3...orz啊..orz..
B. Sandro's Book..
這題最水..枚舉字符串就完了..
不過(guò)我wa了一次..因?yàn)橛袀€(gè)細(xì)節(jié)沒(méi)看懂...- -我都快懷疑我在猜題目了..
J. Dill..
最最最最最簡(jiǎn)單的構(gòu)造..對(duì)于第一組箱子..可以把1-n給第一組..
那么第二組的m個(gè)可以構(gòu)造成n+1,n+1+n,n+1+2*n.....
因?yàn)榇a都很短..就不帖了..囧