(挂慘了 我晚上一定好好睡覺。
T1 求冒泡排列在第幾輪結束。\(n\leq 3e7\)
可以發現每次自己左邊最大的數字是向右移動的 是以答案為max{自己左邊有多少個數比自己大}
想要O(n)求出的話還要再考慮一下 如何求出max 由于是max 我們考慮自己右邊最多有多少比自己小的max等價于原答案。
是以我們可以發現 利用較小的數字來統計答案會比用較大的數字統計答案更優 換個說法 \(a_i<a_j\) \(a_i\)和\(a_j\)如果進行換位了 那麼我們隻統計\(a_i\)的對答案的
貢獻至少不會比\(a_j\)要小。一個很難得到最很好好證明的答案:max{i-\(a_i\)}即為答案。
考慮證明：一個數字前面包括本身最多有\(a_i\)個數對答案沒有貢獻。考慮如果不夠這\(a_i\)個數 那麼一定有比自己還要小的數字在自己後面 那麼這樣統計下去至少能夠找到答案。
bf：
const int MAXN=30000010;
int n;
ll S,B,C,D;
int a[MAXN],c[MAXN];
int cnt,ans;
int main()
{
freopen("bubble.in","r",stdin);
freopen("bubble.out","w",stdout);
get(n);get(S);get(B);get(C);get(D);
rep(1,n,i)
{
a[i]=i;
S=(S*B+C)%D;
swap(a[i],a[(S%i)+1]);
}
//rep(1,n,i)cout<<a[i]<<' '<<endl;
rep(1,n,i)
{
int w=a[i];cnt=0;
while(w)
{
cnt+=c[w];
w-=w&(-w);
}
ans=max(ans,i-1-cnt);
w=a[i];
while(w<=n)
{
++c[w];
w+=w&(-w);
}
}
put(ans);
return 0;
}
sol:
const int MAXN=30000010;
int n;
ll S,B,C,D;
int a[MAXN],c[MAXN];
int cnt,ans;
int main()
{
freopen("1.in","r",stdin);
get(n);get(S);get(B);get(C);get(D);
rep(1,n,i)
{
a[i]=i;
S=(S*B+C)%D;
swap(a[i],a[(S%i)+1]);
}
//rep(1,n,i)cout<<a[i]<<' '<<endl;
rep(1,n,i)ans=max(ans,i-a[i]);
put(ans);
return 0;
}
T2：
sb比對題...無語。(每次我都暴力 每次暴力還挂。我真是個菜雞。
容易推出性質 兩個比對的字元串a,b a種某種字元隻能對應b上的位置隻能對應一種字元 b種也同理 容易證明這樣是可以比對的充要條件。
可以簡單證明一下：如果滿足上述條件 那麼直接swap即可 可以發現這樣做就可以形成一模一樣的字元。考慮必要條件的證明：反證：如果不滿足上述情況 那麼必然某種字元對應了兩種字元 而swap每次隻能将一種字元變成另外一種字元 如果swap是那兩種字元 顯然無法比對還是原來的情況 如果不是 顯然還是原情況。證畢。
是以現在問題變成了 給出兩個字元串看 是否滿足上述條件。考慮暴力 n^2 比對。最尴尬的事實是優化不了 這個思路雖然沒錯 但是 必須一一得到位置資訊。
貼一發暴力代碼:
const int MAXN=1000010;
int T,C,n,m,top;
int ans[MAXN];
int a[MAXN],b[MAXN],c[MAXN],c1[MAXN],cnt,cnt1;
vector<int>w[MAXN];
int main()
{
freopen("1.in","r",stdin);
//freopen("match.out","w",stdout);
get(T);get(C);
while(T--)
{
get(n);get(m);top=0;
rep(1,C,i)w[i].clear();
rep(1,n,i)get(a[i]);
rep(1,m,i)get(b[i]),w[b[i]].pb(i);
rep(1,n-m+1,i)
{
int cnt=0;
rep(1,C,j)
{
if(w[j].size())
{
int last=0;
rep(0,w[j].size()-1,k)
{
int ww=w[j][k];
if(last&&last!=a[i+ww-1]){cnt=1;break;}
last=a[i+ww-1];
if(c[last]&&c[last]!=j){cnt=1;break;}
c[last]=j;
}
if(cnt)break;
}
}
rep(1,C,j)c[j]=0;
if(!cnt)ans[++top]=i;
}
put(top);
rep(1,top,i)printf("%d ",ans[i]);
puts("");
}
return 0;
}
可以發現這是一個sb比對題 我們可以考慮算法了 hash 或者 KMP(關于自己的子串和模式串的比對問題。
hash不太會 但是考慮KMP的話 我們可以通過性質定義一種比對 自己上次的字元的比對位置和目前位置的差 恰好等于自己比對到的字元的上次位置和這次位置的內插補點。如果完全符合的話顯然和我們的性質是剛好吻合的。
考慮KMP做這件事 接下來是魔改KMP...(這題的暴力分給的很不合理 推出性質之後暴力隻有10分 正解KMP想出來了才能拿100.果然算法要套到題目上 這個角度來思考這道題更容易出解 而不是得到性質之後套到暴力之上。
建立數組 la[i] 表示 a串的i的上一個位置和目前位置的內插補點 lb[i]同理 進行比對即可。
值得注意的是 存在斷層現象 可能目前比對的長度為 w w+1上一次出現的位置與w+1的差是大于w的 此時預設為w+1上的字元為第一次出現 那麼值為w+1即可。
剩下的就沒有了。複雜度O(n)
const int MAXN=1000010;
int T,C,n,m,top;
int ans[MAXN];
int a[MAXN],b[MAXN],c[MAXN],la[MAXN],lb[MAXN];
int nex[MAXN];
inline void KMP()
{
int j=0;top=0;
rep(2,m,i)
{
while(min(j+1,lb[i])!=lb[j+1]&&j)j=nex[j];
if(min(j+1,lb[i])==lb[j+1])++j;
nex[i]=j;
}
j=0;
rep(1,n,i)
{
while(min(j+1,la[i])!=lb[j+1])j=nex[j];
if(min(j+1,la[i])==lb[j+1])++j;
if(j==m)j=nex[j],ans[++top]=i;
}
}
int main()
{
freopen("1.in","r",stdin);
//freopen("match.out","w",stdout);
get(T);get(C);
while(T--)
{
get(n);get(m);
rep(1,C,i)c[i]=0;
rep(1,n,i)
{
get(a[i]);
la[i]=i-c[a[i]];
c[a[i]]=i;
}
rep(1,C,i)c[i]=0;
rep(1,m,i)
{
get(b[i]);
lb[i]=i-c[b[i]];
c[b[i]]=i;
}
KMP();
put(top);
rep(1,top,i)printf("%d ",ans[i]-m+1);
puts("");
}
return 0;
}
T3：
一道沒見過的dp優化題目。
看出來dp之後可以列狀态f[i]表示到達第i頁的最大價值。
頁數1e9當場gg 很容易發現和頁數無關 之和我們到達第i個關鍵點了沒有有關。
考慮最優政策 一定是從第K頁一路上經過若幹個關鍵點過來的。f[i]表示到達第i個點的最大價值。
容易得到轉移 \(f[i]=f[j]-\lceil\frac{(T_i-T_j)}{D}\rceil\cdot A+B_i\)
轉移是\(n^2\)的 暫時看不出來怎麼優化。
不過這個向上取整的式子我倒是可以拆成向下取整。
\(\lceil\frac{a}{b}\rceil=\frac{a-1}{b}+1\)
沒啥用。。。
不過這倒是可以進一步化簡這個式子。
\(\lfloor\frac{a-c}{b}\rfloor=\frac{a}{b}-\frac{c}{b}\)-(a%b<c%b)
到這裡可以發現 還是沒有任何用 我隻不過在玩這個式子罷了/cy 至少對寫暴力有很大的優化...
bf score:20
const ll MAXN=100010;
ll f[MAXN];
ll K,M,D,A,n,maxx=-INF;
ll a[MAXN],b[MAXN];
signed main()
{
freopen("1.in","r",stdin);
//freopen("reading.out","w",stdout);
f[0]=0;get(K);get(M);get(D);get(A);get(n);
rep(1,n,i)get(a[i]),get(b[i]),f[i]=-INF;a[0]=K;
//if(n<=1000)
{
rep(1,n,i)
{
rep(0,i-1,j)
{
ll w=(a[i]-a[j]-1)/D+1;
f[i]=max(f[i],f[j]+b[i]-w*A);
}
}
rep(0,n,i)
{
ll w=(M-a[i]-1)/D+1;
f[i]=f[i]-w*A;
maxx=max(maxx,f[i]);
}
putl(maxx);
}
return 0;
}
考慮題目中的子任務 D<=100
觀察我們的dp式如果存在 j<k 且j和k 模D同餘 我們從dp的角度分析從j轉移過來沒啥用 直接從k轉移即可。
這樣我們得到了一個非常好些的 nD的dp.
接下來就要讓這兩個方法結合 其實光我第一個dp就可以推出正解。
考慮dp式的化簡 \(f[i]=f[j]-\lceil\frac{(T_i-T_j)}{D}\rceil\cdot A+B_i\) 這個向上取整等價于 \(\frac{T_i}{D}-\frac{T_j}{D}\)+(\(T_i\)%D>\(T_j\)%D.
絕殺化簡 對于任意一條路徑來說 對于路徑上兩個相連的點 i j 他們對答案的貢獻的\(\frac{T_i}{D}-\frac{T_j}{D}\)的連續累加 恰好等于\(\frac{M}{D}-\frac{K}{D}\).
也就是說我們隻需要管 後面那個東西 就行了 這其實是是否多了一個A的關系 采用資料結構優化一下即可。
區間查詢最值 考慮線段樹 (zkw線段樹常數會很小很小。或者标記永久化 沒必要懶标記了。這裡推薦zkw.
const ll MAXN=100010;
ll f[MAXN];
ll K,M,D,A,n,maxx=-INF,top,num,base;
ll a[MAXN],b[MAXN],c[MAXN],val[MAXN<<2];
inline void discrete()
{
sort(c+1,c+1+num);
rep(1,num,i)if(i==1||c[i]!=c[i-1])c[++top]=c[i];
rep(0,n,i)a[i]=lower_bound(c+1,c+1+top,a[i])-c;
}
inline void build(ll len)
{
while(base<=len)base=base<<1;
rep(1,base*2,i)val[i]=-INF;
}
inline void modify(ll pos,ll x)
{
pos+=base;val[pos]=max(val[pos],x);pos=pos>>1;
while(pos)
{
val[pos]=max(val[pos<<1],val[pos<<1|1]);
pos=pos>>1;
}
}
inline ll ask(ll l,ll r)
{
ll res=-INF;
for(l=base+l-1,r=base+r+1;l^r^1;l=l>>1,r=r>>1)
{
if(~l&1)res=max(res,val[l^1]);//經過左兒子
if(r&1)res=max(res,val[r^1]);//經過右兒子
}
return res;
}
signed main()
{
freopen("1.in","r",stdin);
//freopen("reading.out","w",stdout);
get(K);get(M);get(D);get(A);get(n);
rep(1,n,i)get(a[i]),get(b[i]),a[i]%=D,c[i]=a[i];
num=++n;a[n]=M%D;c[n]=a[n];c[++num]=a[0]=K%D;discrete();
base=1;build(top);
modify(a[0],0);
rep(1,n,i)
{
ll w1=ask(1,a[i]-1)-A;
ll w2=ask(a[i],top);
f[i]=max(w1,w2)+b[i];
modify(a[i],f[i]);
}
putl(f[n]-(M/D-K/D)*A);
return 0;
}