社区讨论
求助Hash,WA on #4
P10467[CCC 2007] Snowflake Snow Snowflakes参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mih4gjx3
- 此快照首次捕获于
- 2025/11/27 15:38 3 个月前
- 此快照最后确认于
- 2025/11/28 19:15 3 个月前
rt,思路都在代码里了,能否讲讲错哪了,或者给个hack。
CPP#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define V vector
#define FOR(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define pb push_back
const int INF=1e9+10;
const ull mod=0xccf54188 - 1;//自己找的大质数
mt19937_64 rnd(time(0));
const ull mask=rnd();
ull gethash(ull x){
x^=mask;
x^=x<<13;
x^=x>>7;
x^=x<<17;
x^=mask;
return x;
}
ull calc(V<ull>&a){
//策略是:先将最小值放到前面,后面考虑把相邻两个数中差值更小的作为下一项
int id=min_element(a.begin(),a.end())-a.begin();
V<ull>b;
FOR(i,id,5) b.pb(a[i]);
FOR(i,0,id-1) b.pb(a[i]);
a=b;ull ans=0;
while(!b.empty()) b.pop_back();
if(a[1]-a[0]<a.back()-a[0]){
ull times=1;
for(auto i:a) ans+=gethash(i*times),times*=mod;
}else{
ans+=gethash(a[0]);ull times=mod;
for(int i=5;i;i--) ans+=gethash(a[i]*times),times*=mod;
}
return ans;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n;cin>>n;
V<ull>a(6);
V<ull>val;
FOR(i,1,n){
for(auto &i:a)cin>>i;
val.pb(calc(a));
}//两个相同的应该会被去重
sort(val.begin(),val.end());
val.erase(unique(val.begin(),val.end()),val.end());
if((int)val.size()!=n) cout<<"Twin snowflakes found.";
else cout<<"No two snowflakes are alike.";
return 0;
}
/*
3
1 2 3 4 6 5
1 2 3 4 5 6
4 6 5 1 2 3
*/
回复
共 0 条回复,欢迎继续交流。
正在加载回复...