社区讨论

求助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 条回复,欢迎继续交流。

正在加载回复...