10.27 CSP-S模擬40 改題記錄
寫在前面
沒想到離CSP還有4天然后創造了一次保齡的經歷。。。然后就是讀假題專場。其實感覺沒有太難但是。。。好吧，礙于時間不多，也不說廢話了。
A. 公約數神廟
我無言。我以為我敗在了空間，結果其實是敗給了糖錯和可惡的特判。難得想出正解嗚嗚嗚。題意是有一個數列，從編號小的到編號大的且公因數大于1的點對有有向邊。給出詢問一個點對是否能通達。
讀假題，還說終于來簽到題了。還好樣例善良。肯定不考慮暴力建邊，暴力轉移也不可取。觀察到\(i\) 可以通過中轉點走到\(j\)。由于保證了從編號小的點走到編號大的點，我們考慮倒著維護通達性。觀察到值域內每個數至多有4個質因數，共有168個質因數。由于從某個位置開始，就算一個數不含某個質因數也能通過中轉點走到含有該質因子的位置，我們考慮維護每個質因數的數從哪個位置開始能走到另一個質因數的倍數上，動態加入取min即可。然后每個詢問就枚舉終點的質因數看其是否在起點可通達范圍內即可。然后難點還沒來，難點在特判。全場因為特判的問題掛了inf分。
B. 棧法師
讀假題\(\times 2\)。甚至還寫了1h。
題意是給出一個起始棧，構造一系列操作，使得棧內元素在終止棧內升序排列，且要求過渡棧的量最小。
省略讀假題的內容。顯然過渡棧的數量最多是2。考慮是1的情況，直接做看看能否滿足要求即可。否則考慮先將所有元素放到一個過渡棧，這樣每次操作都是有規律的不用特判。然后我們肯定要從小到大彈進終止棧，如果其上方有比其大的數肯定需要到過渡棧里待避，我們預處理出這個值即可。然后要彈出一個元素我們就先將其上方元素彈入另一個過渡棧，再將該元素彈出，再將過渡棧元素彈回去，就能減少分討了。其實沒有任何技術含量可言。
C. 城堡考古
改了inf小時沒改完。先存下代碼和題解。
需要寫一個高精度的10->2進制轉換（可以每次暴力做高精度除22，復雜度是對的），位數大概\(\times3\) 題目要求的是一個差分形式，需要矩陣多開一維記錄前綴 sum直接實現的話大概能跑65分。
按照網格狀壓DP的套路，有很多狀態其實是到不了的，dfs 預處理合法且能夠從 s=0s=0 到達的狀態，發現只有20個（其實是一個組合數，mm 列恰有 \(\binom{m}{m/2}\) 個合法狀態）。
復雜度變為 \(O(20^3\times len)\)，這樣就能通過了。
#include<bits/stdc++.h>
using namespace std;
const int maxn=100,mod=998244353;
int dp[maxn][maxn];
string sl,sr;
bitset<10000> l,r;
int m;
struct matrix{
int a[30][30];
matrix(){
memset(a,0,sizeof(a));
}
inline matrix operator*(const matrix &b)const{
matrix c;
for(int i=1;i<=m;i++){
for(int k=1;k<=m;k++){
int p=a[i][k];
for(int j=1;j<=m;j++)
c.a[i][j]=(c.a[i][j]+1ll*p*b.a[k][j]%mod)%mod;
}
}
return c;
}
}ll,rr,aa;
inline void qpow(matrix &a,matrix b,bitset<10000> y){
for(int i=0;i<10000;i++){
if(y[i]) a=a*b;
b=b*b;
}
}
inline string div(string &s){
string ss="";
int now=0;
for(int i=0;i<s.size();i++){
now=now*10+s[i]-'0';
if(now==1&&i<s.size()-1) continue;
ss+=now/2+'0';
now%=2;
}
return ss;
}
inline void get2(string &s,bitset<10000> &c){
for(int i=0;;i++){
if((s[s.size()-1]-'0')&1){
c[i]=1;
}
s=div(s);
if(s[0]=='0') break;
}
}
bool vis[70];
inline void dfs(int las,int lv){
vis[las]=1;
if(lv>=5) return;
for(int i=0;i<(1<<m);i++){
bool flg=1;
int cnt=0;
for(int j=0;j<m;j++)
if(((i>>j)&1)&&((las>>j)&1)){
flg=0;
break;
}
else if(((i>>j)&1)||((las>>j)&1)){
if(cnt&1){
flg=0;
break;
}
cnt=0;
}
else ++cnt;
if(cnt&1) flg=0;
if(flg) dfs(i,lv+1);
}
}
vector<int> legal;
bool start[70];
inline bool check(int x,int y){
int cnt=0;
for(int i=0;i<m;i++)
if((((x>>i)&1)&&((y>>i)&1))) return 0;
else if(((x>>i)&1)||((y>>i)&1)){
if(cnt&1) return 0;
cnt=0;
}
else ++cnt;
if(cnt&1) return 0;
return 1;
}
int main(){
freopen("decoration.in","r",stdin);
freopen("decoration.out","w",stdout);
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>sl;
cin>>sr;
cin>>m;
for(int i=sl.size()-1;i>=0;i--){
sl[i]--;
if(sl[i]>='0') break;
sl[i]+=10;
}
if(sl[0]=='0'){
string ss=sl;
sl="";
for(int i=1;i<ss.size();i++) sl+=ss[i];
}
int cnt=0;
get2(sl,l);
get2(sr,r);
if(m==1) vis[0]=vis[1]=1,cnt=2;
else{
for(int i=0;i<(1<<m);i++){
vis[i]=1;
int cnt=0;
for(int j=0;j<m;j++)
if((i>>j)&1){
if(cnt&1){
vis[i]=0;
break;
}
cnt=0;
}
else ++cnt;
if(cnt&1) vis[i]=0;
if(vis[i]) start[i]=1,dfs(i,0);
}
for(int i=0;i<(1<<m);i++)
if(vis[i]){
legal.emplace_back(i),++cnt;
if(start[i]) ll.a[cnt][1]=rr.a[cnt][1]=1;
}
}
for(int i=0;i<legal.size();i++)
for(int j=0;j<legal.size();j++)
if(check(legal[i],legal[j])) aa.a[i+1][j+1]=1;//,cout<<legal[i]<<' '<<legal[j]<<'\n';
// ll=aa*ll;
// cout<<ll.a[1][1]<<' '<<ll.a[2][2]<<'\n';
qpow(ll,aa,l);
qpow(rr,aa,r);
int ans=0;
for(int i=1;i<=cnt;i++) ans=(ans+rr.a[i][1])%mod;
// cout<<ans<<'\n';
for(int i=1;i<=cnt;i++) ans=(ans-ll.a[i][1])%mod;
cout<<(ans%mod+mod)%mod;
return 0;
}
D. 生命之樹
感覺做過原題。然后咕了（其實是賀了題解式子然后自己懶得沒空詳寫）。哦哦對了，大概就是打了15min暴力還沒來得及交然后一腳把機箱電源踹了
浙公網安備 33010602011771號