Sep 28
只整理 T1, T2.
原題是 「ROI 2012 Day 1」密碼 和 「ROI 2012 Day 2」劇院始于演員，可以與 LOJ 提交。
T1
考試的時候忘記 return 0, 導致一口氣把所有答案都輸出出來了，100->30，再次警示使用 break 的時候一定一定要看清楚能不能達到你想要的目的。
經過觀察，對應區(qū)間處于第二個串中的長度絕對不會超過 6，我們從這里下手，枚舉開始的位置，兩個二分確定區(qū)間的左右位置，之后通過去掉區(qū)間的左右必須相等約束算出位置，hash判斷就行了。
代碼↓
點擊查看代碼
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MN=1e6+116;
const int P=1145141;
int sum[MN], n, m;
string a, b;
ull hasha[MN], hashb[MN], p[MN];
int query(int l, int r){
return sum[r]-sum[l-1];
}
ull gethasha(int l, int r){
return hasha[r]-hasha[l-1]*p[r-l+1];
}
ull gethashb(int l, int r){
return hashb[r]-hashb[l-1]*p[r-l+1];
}
unordered_map <int,int> trans;
vector <pair<int,int>> ans;
int main(){
//freopen("password.in","r",stdin);
//freopen("password.out","w",stdout);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>a>>b; n=a.size(), m=b.size(); a=' '+a, b=' '+b;
p[0]=1; for(int i=1; i<=n; ++i) p[i]=p[i-1]*P;
for(int i=0; i<=9; ++i) trans[i]=rand();
for(int i=1; i<=n; ++i){
hasha[i]=hasha[i-1]*P+trans[(a[i]-'0')];
}
for(int i=1; i<=m; ++i){
hashb[i]=hashb[i-1]*P+trans[(b[i]-'0')];
}
if(a==b){cout<<1<<" "<<1<<'\n'; return 0;}
for(int i=1; i<=n; ++i){sum[i]=sum[i-1]+(a[i]-'0');}
for(int i=1; i<=m; ++i){
if(a[i-1]!=b[i-1]) break;//前邊必須相等
for(int len=1; len<=6&&i+len-1<=m; ++len){//枚舉長度
int val=0;
for(int j=i; j<=i+len-1; ++j){
val=val*10+(b[j]-'0');
}
int l=i, r=n, resr=n;
while(l<=r){//盡量大
int mid=(l+r)>>1;
if(query(i,mid)<=val){
resr=mid; l=mid+1;
}else{
r=mid-1;
}
}
l=i, r=n; int resl=n;//盡量小
while(l<=r){
int mid=(l+r)>>1;
if(query(i,mid)>=val){
resl=mid; r=mid-1;
}else{
l=mid+1;
}
}
if(query(i,resr)!=val) continue;
if(m-len>=n-(resr-i+1)&&m-len<=n-(resl-i+1)){//合法
int res=n+i-1-m+len;
if(gethasha(res+1,n)==gethashb(i+len,m)){
ans.push_back({i,res});
}
}
}
}
sort(ans.begin(),ans.end());
cout<<ans[ans.size()-1].first<<" "<<ans[ans.size()-1].second;
return 0;
}
T2
考場上想的思路，現(xiàn)在實現(xiàn)對了。
我們考慮異或哈希，每個人初始為 0, 對于每次操作，我們隨機一個權值，將所有涉及的異或上這個值，明顯的，當一個值唯一對應一個人，那么我們就可以確定這個人了。
代碼↓
#include <bits/stdc++.h>
#define ull unsigned long long
using namespace std;
const int MN=1e6+116;
int n, m, ans[MN], at[MN];
ull hashed[MN];
map <ull,set<int>> man;
vector <ull> eraser;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0' && ch<='9')
x=x*10+ch-'0',ch=getchar();
return x*f;
}
int main(){
mt19937_64 rnd(time(0));
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
n=read(), m=read(); for(int i=1; i<=n; ++i) man[0].insert(i);
for(int i=1,K; i<=m; ++i){
K=read(); ull now=rnd();
vector <ull> tmp; tmp.clear();
for(int j=1,v; j<=K; ++j){
at[j]=v=read();
man[hashed[v]].erase(v);
tmp.push_back(hashed[v]);
hashed[v]^=now; man[hashed[v]].insert(v);
}
for(auto h:tmp){
if(man[h].size()==1){
if(!ans[*man[h].begin()]) ans[*man[h].begin()]=i;
}
}
for(int j=1; j<=K; ++j){
int x=at[j];
if(!ans[x]&&man[hashed[x]].size()==1) ans[x]=i;
}
}
for(int i=1; i<=n; ++i) cout<<ans[i]<<" ";
return 0;
}
浙公網安備 33010602011771號