十月總結
10.11 廣二23
T1：計數、容斥原理
有一個計數的做法，大致做法是在最后面的開頭統計，然后要求后面不能出現，這樣貢獻就是唯一的，需要fail樹上跑下來dfn這樣
容斥原理就比較直接，加上序列中有一個開頭的，減去有兩個開頭的，加上有三個開頭的...
我們假定一個位置集合S,我們只需要保證相臨的位置的貢獻即可，若它們兩個沒交，那貢獻為它們兩個中間沒有被欽定的，若有交判斷合不合法即可。
當然這個還需要考慮開頭結尾因為是循環數組，發現這個貢獻只與mx-mn有關，這啟發我們去根據長度DP轉移，而且每個位置能填的數都一樣，所以我們用這個長度在好多種位置開始。
商安澤寫法：就是前面說的計數。我們考慮暴力枚舉最后一個開始位置，我們DP當前是一個什么狀態，枚舉下一個填什么字符，暴力跳nxt數組更新狀態。
現在我們把fail樹建出來。
現在我們考慮枚舉下一位的狀態，現在這個狀態可能由對應節點的子樹轉移過來，那我們子樹求和，再把不合法的剪掉即可
點擊查看代碼
int Fm(int a,int b){int s=1;while(b){if(b&1)s=s*a%P;a=a*a%P;b>>=1;}return s;}
int n,m,K,b[N],pw[N];
int xs[N],f[N],g[N];
bool ok[N];
bool MB_2;
signed main() {
cin>>n>>m>>K;
pw[0]=1;
for(int i=1;i<=n;i++) pw[i]=pw[i-1]*K%P;
for(int i=1;i<=m;i++) b[i]=read();
for(int i=1;i<m;i++) {
ok[i]=1;
for(int j=1;j<=m-i;j++) if(b[j]^b[i+j]) ok[i]=0;
}
for(int i=1;i<=n;i++) xs[i]=(i<m?ok[i]:pw[i-m]);
f[0]=1;
for(int i=1;i<n;i++) {
for(int j=0;j<i;j++)
f[i]=(f[i]+f[j]*xs[i-j])%P;
f[i]=(-f[i]+P)%P;
}
for(int i=1;i<n;i++) f[i]=(f[i]*xs[n-i])%P;
int ans=n*pw[n-m]%P;
for(int i=1;i<n;i++) ans=(ans+f[i]*(n-i))%P;
cout<<ans;
return 0;
}
10.13 夏增銳
T1 簡單計數
之前貌似有個類似的題，只能說掌握的及其不牢固。
考慮盡可能靠后的匹配子序列S，枚舉起點，起點前面當然隨便填，后面相當于我們要選出n-1個位置，為了保證這個匹配是最靠后的，s中相鄰兩個字符在T中的間隔中不能出現靠前的那一個字符
即
T2 線段樹 容斥原理
首先如果k=1，那么變成了一個區間加減，統計全局不為0的位置就行。這個具體來講就是維護最小值和最小值個數，如果最小值為0就減去最小值個數，否則就是區間長度。掃描線一下。
k多了的情況，就考慮容斥，因為我們相當于求交集，就用一堆并集容斥就行，具體的，若并集大小為奇數，就加上，不然就減去。
T3 貪心 動態規劃
隨便貪一下就行，注意考場切莫急躁，注意細節，選擇合適的方法
T4 Ad-hoc 構造
觀察原始式子發現一定大于d。設 \(a \oplus b \oplus c \oplus d=d+x\) ,為了方便我們令d的后幾位為0，x為1
開始構造，以下構造正確性顯然不證:
設p為a二進制下最高位
\(a \equiv 0 \pmod 2\) : \(b=a+2^p,c=2^{p+1}+2^p+1\)
\(a \equiv 1 \pmod 2\) : \(b=a+2^p-1,c=2^{p+1}+2^p\)
10.17
- P12865 trick：冒泡排序結論
經歷c輪冒泡排序后，\([1,l]\) 內的數是 \([1,l+c]\) 的前 l 小值，證明顯然，每輪，小的數最多往前走1，大的數會出去
-
返祖邊找環，無向圖找環可以找返祖邊。
-
ht P10702
首先每個正整數都有斐波那契分解（每次減去比他小且最大的斐波那契數），且其他所有分解都能由這個轉移過來,發現如果有兩個連續的1，高位的就不能下放，具體的看代碼
點擊查看代碼
//^ v ^ "Surpassing never ends!"
//"Beyond Limits: The Journey Never Ends"
//超越極限 ， 征途永續
#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
const int N=5e5+500,M=1e15,V=5762005;
const ll P=998244353,inf=3e9;
int read() {
int x=0;short f=1;char s=getchar();
while(s<48||s>57){f=s=='-'?-1:1;s=getchar();}
while(s>=48&&s<=57){x=x*10+s-48;s=getchar();}
return x*f;
}
mt19937 rnd(time(0));
bool MB_1;
string s;
struct GJ {
int a[1010];
void init() { memset(a,0,sizeof(a)); }
friend bool operator <= (const GJ&a,const GJ&b) {
for(int i=1000;i>=0;i--) if(a.a[i]<b.a[i]) return 1;else if(a.a[i]>b.a[i]) return 0;
return 1;
}
friend GJ operator +(const GJ&a,const GJ&b) {
GJ c;c.init();
for(int i=0;i<=1000;i++) {
c.a[i]+=a.a[i]+b.a[i];
c.a[i+1]+=c.a[i]/M;
c.a[i]%=M;
}
return c;
}
}sum,n,b[50100];
int Lim,a[N];
int f[N][3];
int get(int p,int num) {
if(p<=2) {
if(num<=1) return 1;
return 0;
}
if(f[p][num]!=-1) return f[p][num];
if(num==2) {
if(a[p-1]) return f[p][num]=0;
else return f[p][num]=get(p-2,a[p-2]+1);
}
else if(num==1) {
if(a[p-1]) return f[p][num]=get(p-1,a[p-1]);
else return f[p][num]=(get(p-1,a[p-1])+get(p-2,a[p-2]+1))%P;
}
else return f[p][num]=get(p-1,a[p-1]);
}
bool MB_2;
signed main() {
cerr<<fabs(&MB_2-&MB_1)*1.0/(1024*1024)<<'\n';
freopen("winter.in","r",stdin);
freopen("winter.out","w",stdout);
cin>>s;
int nw=0;
for(int i=s.size()-1;i>=0;i-=15) {
int l=i,r=max(i-15+1,0ll);
for(int j=r;j<=l;j++) {
n.a[nw]=n.a[nw]*10+s[j]-'0';
}
nw++;
}
// for(int i=0;i<=nw;i++) cout<<n.a[i]<<" ";
b[0].a[0]=1,b[1].a[0]=1;
for(int i=2;b[i-1]<=n;i++) {
Lim=i;
b[i]=b[i-1]+b[i-2];
// for(int j=0;j<=1;j++) cout<<b[i].a[j]<<" ";cout<<'\n';
}
for(int i=Lim;i>=1;i--) {
f[i][0]=f[i][1]=f[i][2]=-1;
GJ j=sum+b[i];
if(j<=n) a[i]=1,sum=j;
// cout<<a[i]<<" ";
}
for(int i=Lim;i>=1;i--) {
if(a[i]) { cout<<get(i,a[i]); return 0; }
}
return 0;
}
- MX星航九月份ST1 ：
我們先把這個平方拆成二次函數
\(F_{[L,R]}(x) = \sum_{i=L}^{R} (A_i - B_ix)^2 = Q_{[L,R]} x^2 - 2 P_{[L,R]} x + C_{[L,R]}\)
這個式子在 \(t_{[L,R]} = \dfrac{P_{[L,R]}}{Q_{[L,R]}}\) 取到最小值。
我們能夠說明最終答案一定滿足 \(B_i\) 相等的一段是取到 \(t_{[L,R]}\) 的。因為如果不是這個值。那么它一定能在左邊或右邊的B值取到比當前更優的值，這樣他又會和前面或后面的區間合并成一個新區間，成為一個新的同質化問題，一直這樣下去就好了。
這樣還不夠。我們補充一個結論。
設某個區間最優點為 \(v\)
若 $v_i < v_{i+1} $ ,則它們最后的取值 \(x_i=x_{i+1}\)
微調法即可，不管哪種情況都會有一個x往對應的v挪移
廣二24
T1：計數
有點簡單吧，就把質因子分配即可，場切
T2：詐騙，性質
等價類的劃分耐人尋味，以后考試可以多注意這點（即會有很多無用或等價狀態）
T3：計數，連續段DP
顯然正負可以分開討論
先考慮部分分，就是都為正，把大數（ \(x > \sqrt C\) ）和小數分開考慮，顯然大數兩邊只能是某些小數，我們把大數從大到小，小數從小到大處理出來，讓大數兩邊只能是他之前加入的小數，而小數沒有其他限制。
那么大數能干的顯然只有合并兩個小數段，DP小數段數即可。注意這個需要左右端點
點擊查看代碼
void Solve(int n,int a[],int f[][N]) {
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) w[i]=0;
int pos=0;
for(int i=1;i<=n;i++) {
if(a[i]*a[i-1]<=K) pos=i;
}
int o=0;f[0][0]=1;
int p=pos+1;
for(int i=pos;i>=1;i--) {
while(a[p]*a[i]<=K&&p<=n) {
o^=1;
for(int j=0;j<=n;j++) f[o][j]=0;
for(int j=0;j<=n;j++) if(f[o^1][j]) {
add(f[o][j+1],f[o^1][j]*(j+1));
}
p++;
}
o^=1;
for(int j=0;j<=n;j++) f[o][j]=0;
for(int j=0;j<=n;j++) if(f[o^1][j]) {
add(f[o][j+1],f[o^1][j]*(j+1));
if(j) add(f[o][j-1],f[o^1][j]*(j-1));
add(f[o][j],f[o^1][j]*(2*j));
}
}
if(!o) for(int j=0;j<=n;j++) f[1][j]=f[0][j];
}
發現有正負之后可以存在不合法的段。那我們換一種DP方式，DP不合法的段數。改變加入順序：從小往大加入大數，從大往小加入小數，這時大數與前邊的數的乘積都不合法，只能新開一段，最后把正負拼起來即可。
點擊查看代碼
void Solve(int n,int a[],int f[][N]) {
sort(a+1,a+1+n);
for(int i=1;i<=n;i++) w[i]=0;
int pos=0;
for(int i=1;i<=n;i++) {
if(a[i]*a[i-1]<=K) pos=i;
}
int o=0;f[0][0]=1;
int p=pos+1;
for(int i=pos;i>=0;i--) {
while(a[p]*a[i]<=K&&p<=n) {
o^=1;
for(int j=0;j<=n;j++) f[o][j]=0;
for(int j=0;j<=n;j++) if(f[o^1][j]) {
add(f[o][j+1],f[o^1][j]*(j+1));
}
p++;
}
if(!i) continue;
o^=1;
for(int j=0;j<=n;j++) f[o][j]=0;
for(int j=0;j<=n;j++) if(f[o^1][j]) {
add(f[o][j+1],f[o^1][j]*(j+1));
if(j) add(f[o][j-1],f[o^1][j]*(j-1));
add(f[o][j],f[o^1][j]*(2*j));
}
}
if(!o) for(int j=0;j<=n;j++) f[1][j]=f[0][j];
}
bool MB_2;
signed main() {
cerr<<fabs(&MB_2-&MB_1)*1.0/(1024*1024)<<'\n';
// freopen("1.in","r",stdin);
// freopen("1.out","w",stdout);
cin>>n>>K;
for(int i=1;i<=n;i++) {
int x=read();
if(x>0) a[++le1]=x;
else x=-x,b[++le2]=x;
}
Solve(le1,a,f),Solve(le2,b,g);
int ans=0;
for(int i=1;i<=le1;i++) {
add(ans,f[1][i]*g[1][i]*2);
add(ans,f[1][i]*g[1][i-1]);
add(ans,f[1][i]*g[1][i+1]);
}
cout<<ans;
return 0;
}
浙公網安備 33010602011771號