- 上午
- 模拟考試
- Prob.1（AC）用用<cmath>裡的sin和cos就好
注意一個細節：因為double的精度問題，輸出0是可能會輸出-0。
要特判一下。
- Prob.2（WA）矩陣幂優化線性遞推，但我制杖地把遞推寫錯了一個地方。
考試時有多餘時間一定要寫暴力對拍啊，（可惡的萬能樣例竟然還過了）
- Prob.3（70）正解是線段樹優化dp，（用線段樹維護一個區間的最大值，log2n級别轉移）
我寫了一個差分限制（用的裸的spfa），過了70分。但之後把spfa用雙端隊列deque或者優先隊列優化以後，就快得飛起來，比正解（線段樹+dp，這個差分限制也算正解了吧）還快。
- 下午
- 改了改題，學了學上午考試第三題正解
- BOZJ 1072 半天沒搞出來，效率太低了。
- 、、、
- 晚上
- BOZJ 1072 [SCOI2007]排列perm
dp[s][j]:表示s這個集合中的數構成的對d取模後等于j的數有多少個。
然後有一個小結論：
若 j=A%d，令 x=(A*10+B)%d,則 (j*10+B)%d==x
這個也很顯然：
令 A=k*d+j,
則 x=((k*d+j)*10+B)%d
=(k*d*10+j*10+B)%d
=(j*10+B)%d
是以轉移如下：
dp[s|(1<<k)][(j*10+s[k]-'0')%d]+=dp[s][j];
最後處理一下出現多次的數字。因為不考慮相同數字的順序，是以除以其出現次數的階乘。
代碼：
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char s[15];
int dp[1<<10][1005],c[15],fac[15];
int T,d,n;
int idx(char ch){
return ch-'0';
}
int main(){
scanf("%d",&T); fac[0]=1;
for(int i=1;i<=10;i++) fac[i]=fac[i-1]*i;
while(T--){
scanf("%s",s);
scanf("%d",&d);
memset(dp,0,sizeof(dp));
dp[0][0]=1; n=strlen(s);
for(int i=0;i<(1<<n);i++)
for(int j=0;j<d;j++){
if(!dp[i][j]) continue;
for(int k=0;k<n;k++){
if(i&(1<<k)) continue;
dp[i|(1<<k)][(j*10+idx(s[k]))%d]+=dp[i][j];
}
}
memset(c,0,sizeof(c));
for(int i=0;i<n;i++) c[idx(s[i])]++;
for(int i=0;i<10;i++) dp[(1<<n)-1][0]/=fac[c[i]];
printf("%d
",dp[(1<<n)-1][0]);
}
return 0;
}
- BZOJ 1073 還沒打完……
- 今天效率是真的低啊！再這樣下次考試就要爆零了。