考慮DP，定義狀態\(F_{i,0}\)為第\(i\)張卡片正面朝上的方案數，\(F_{i,1}\)為第\(i\)張卡片背面朝上的方案數，每次check是否相同然後轉移即可
int f[N][2];
int a[N];
int b[N];
void solve(){
int n;
cin >> n;
for (int i = 1;i <= n;i ++) {
cin >> a[i] >> b[i];
}
f[1][0] = 1;
f[1][1] = 1;
for (int i = 2;i <= n;i ++) {
f[i][0] = (f[i - 1][0] * (a[i - 1] != a[i]) + f[i - 1][1] * (b[i - 1] != a[i])) % mod;
f[i][1] = (f[i - 1][0] * (a[i - 1] != b[i]) + f[i - 1][1] * (b[i - 1] != b[i])) % mod;
}
cout << (f[n][0] + f[n][1]) % mod << endl;
}
考慮到題目所說的大小關係，可以聯絡到是一個有向圖的形式，如果\(a\)和\(b\)有一條有向邊，則含義為\(a\leqslant b\)，所以我們可以發現，其實題目只是求一個拓撲序，觀察第二個樣例，我們還可以發現不能同時有多個點在拓撲序的同一時刻入隊，所以就構造完了。
vector<int> G[N];
queue<int> qq;
int c[N];
int d[N];
int n, m;
vector <int > ans;
int f[N];
bool topsort(){
int z=0;
for (int i=1;i<=n;i++){
if (!d[i])qq.push(i),z++,ans.push_back(i);
}
while (!qq.empty()){
if(qq.size() != 1) {
return false;
}
int t = qq.front();
qq.pop();
for (int i : G[t]){
d[i]--;
if (!d[i]){
qq.push(i);
ans.push_back(i);
z++;
}
}
}
return z==n;
}
void solve(){
cin >> n >> m;
map<PII,bool> mp;
for (int i = 1;i <= m;i ++) {
int x,y;
cin >> x >> y;
d[y]++;
G[x].push_back(y);
}
if(topsort()) {
cout << "Yes" << endl;
int now = 1;
vector<int> last(n + 1);
for (int i : ans) {last[i] = now++;}
for (int i = 1;i <= n;i ++) cout << last[i] << ' '; cout << endl;
}
else cout << "No" << endl;
}
觀察到\(m \leqslant 10\)，且題目要求的是不經過一個點的時候的最短路，所以對於不經過的點，我們只需要列舉其前面最多\(10\)個位置，他們是需要"跨過"當前不能經過的點的，所以DP先處理出來兩個最短路，一個從\(1\)到後面的點的，一個從後面的點到\(n\)的最短路，列舉完點就可以很快的算出答案了。
int f[N][2];
void solve(){
int n , m;
cin >> n >> m;
vector<string> s(n + 1);
for (int i = 2;i <= n;i ++) f[i][1] = 1e18;
for (int i = 1;i <= n - 1;i ++) f[i][0] = 1e18;
for (int i = 1;i <= n;i ++) {
cin >> s[i];
s[i] = " " + s[i];
for (int j = 1;j <= m && i + j <= n;j ++) {
if(s[i][j] == '1') f[i + j][1] = min(f[i + j][1], f[i][1] + 1);
}
}
for (int i = n;i >= 1;i --) {
for (int j = 1;j <= m && i + j <= n;j ++) {
if(s[i][j] == '1') {
f[i][0] = min(f[i][0],f[i + j][0] + 1);
}
}
}
for (int i = 2;i <= n - 1;i ++) {
int ans = 1e18;
for (int j = max(1ll,i + 1 - m);j <= i - 1;j ++) {
for (int k = i + 1 - j;k <= min(m , n);k ++) {
if(s[j][k] == '1') {
ans = min(ans , f[j][1] + f[j + k][0] + 1);
}
}
}
if(ans != 1e18)
cout << ans << ' ';
else
cout << -1 << ' ';
}
}
暴力的複雜度是\(O(N^{2})\)，所以考慮優化。複雜度來自兩個地方，一個是列舉迴圈的情況，\(O(N)\)，還有是掃描一遍算或的值，\(O(N)\)，前一個迴圈不好優化，因為每個數都很小，所以考慮優化後面這一個運算的複雜度。首先我們可以對每位進行分析，\(A|B = A + B - A \& B\)，這樣子拆開式子後，我們就可以發現，前兩項會是一個定值，就是所有元素的和，將\(B\)倒序之後，後面一項，對於每一位的情況就是\(\sum_{i = 1}^{n}A_{i + k} \& B_{n - i}\)，顯然是個折積的形式，二進位制最多五位，做五次折積分別算貢獻就做出來了。
void solve(){
int n;
cin >> n;
int s = 0;
for (int i = 1;i <= n;i ++) cin >> A[i], s += A[i];
for (int i = 1;i <= n;i ++) cin >> B[i], s += B[i];
for (int c = 0;c < 5;c ++) {
memset(f,0,sizeof(f));memset(g,0,sizeof(g));
for (int i = 0;i < n;i ++) {
f[i] = f[i + n] = (A[i + 1] >> c) & 1;
g[i] = (B[n - i] >> c) & 1;
}
poly_mul(f,g,2 * n);
for (int i = 0;i < n;i ++) {
ans[i] += f[n + i] * (1ll << c);
}
}
int now = -1;
for (int i = 0;i < n;i ++) {
now = max(now , s - ans[i]);
}
cout << now << endl;
}