定制手机app价格,网站链接优化,北京个人制作网站有哪些内容,建网站软件CF
1391D - 505#xff08;思维状压dp#xff09;
首先简化问题#xff0c;发现一个矩阵如果要满足条件#xff0c;那它其中的每一个 2 2 2\times 2 22 的小矩阵都要满足条件#xff0c;于是很容易发现 4 4 4\times4 44 的矩阵是一定不满足条件的#xff08;因为是…CF
1391D - 505思维状压dp
首先简化问题发现一个矩阵如果要满足条件那它其中的每一个 2 × 2 2\times 2 2×2 的小矩阵都要满足条件于是很容易发现 4 × 4 4\times4 4×4 的矩阵是一定不满足条件的因为是由四个 2 × 2 2\times2 2×2 的矩阵拼起来的所以里面的 1 1 1 一定是偶数个既然如此更大的矩阵就更不行了因为里面肯定会包含 4 × 4 4\times4 4×4 的矩阵所以就把问题简化到 n ≤ 3 n\le3 n≤3 的情况了 n 1 n1 n1 时没有边长为偶数的子矩阵所以一定是好矩阵 n 2 n2 n2 时枚举一下第一列有 0 / 1 / 2 0/1/2 0/1/2 个 1 1 1 的情况取最小操作数 n 3 n3 n3 时状压dp用二进制表示每一列的情况 d p [ i ] [ j ] dp[i][j] dp[i][j] 表示第 i i i 列变成状态 j j j 的最小操作数转移方程 d p [ i ] [ j ] min ( d p [ i ] [ j ] , d p [ i − 1 ] [ k ] c h a n g e ( i , j ) ) dp[i][j]\min(dp[i][j],\ dp[i-1][k]change(i, j)) dp[i][j]min(dp[i][j], dp[i−1][k]change(i,j)) 如果 k k k 和 j j j 状态合法
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 1e6 10;
const int maxn 1e6 10;
const int mod 1e9 7;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n, m;cin n m;vectorvectorchar g(n 1, vectorchar(m 1));for (int i 1; i n; i )for (int j 1; j m; j )cin g[i][j];if (n 4) cout -1 \n;else if (n 1) cout 0 \n;else if (n 2){vectorint cnt(m 1);for (int i 1; i m; i ){int tmp 0;for (int j 1; j n; j ){if (g[j][i] 1) tmp ;}cnt[i] tmp;}vectorint ans(3);for (int k 0; k 3; k ){ans[k] abs(cnt[1] - k);int lst k;for (int i 2; i m; i ){if (lst 1){if (cnt[i] 1) ans[k] ;lst 0;}else{if (cnt[i] % 2 0) ans[k] ;lst 1;}}}cout min({ans[0], ans[1], ans[2]}) \n;}else if (n 3){// 将每一列转化成二进制vectorint mp(m 1);for (int i 1; i m; i ){int tmp 0;for (int j 1; j n; j ){if (g[j][i] 1) tmp (1ll (j - 1));}mp[i] tmp;}// 转化步数auto change [](int a, int b){int state (a ^ b);int ans 0;for (int i 0; i 3; i ){if ((state i) 1) ans ;}return ans;};// 判断相邻状态合法性auto check [](int a, int b){int a1 ((a 0) 1), a2 ((a 1) 1), a3 ((a 2) 1);int b1 ((b 0) 1), b2 ((b 1) 1), b3 ((b 2) 1);if ((a1 a2 b1 b2) % 2 0) return false;if ((a2 a3 b2 b3) % 2 0) return false;return true; };// 初始化vectorvectorint dp(m 1, vectorint(8, INF));for (int i 0; i 8; i ) dp[1][i] change(mp[1], i);for (int i 2; i m; i ){for (int j 0; j 8; j ) // i-1列的状态{for (int k 0; k 8; k ) // i列的状态{if (!check(j, k)) continue; // jk作为相邻状态不合法dp[i][k] min(dp[i][k], dp[i - 1][j] change(mp[i], k));}}}int ans INF;for (int i 0; i 8; i ) ans min(ans, dp[m][i]);if (ans INF) cout -1 \n;else cout ans \n;}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t--){solve();}
}1296E2 - String Coloring (hard version)思维dp
首先想一想什么情况下需要交换呢即一个字母在另一个字母前面但是前面的字母比后面的字母大的时候也就是说涂同一种颜色的位置必须是单调不减的我们把涂同一种颜色的位置放在一个集合里可以证明所有集合的最后一个位置上的字符一定是单调递减的感性理解一下如果有递增的那直接放到前一个集合就好了没必要放在下一个集合所以问题就转化成了求最长下降子序列应该是一个经典的trick可以积累一下 d p [ i ] dp[i] dp[i] 表示从 [ i , n ] [i,\ n] [i, n] 的最长下降子序列长度 m a x x [ i ] maxx[i] maxx[i] 表示从字母 i ′ a ′ ia i′a′ 到 ′ z ′ z ′z′ 开头的最长下降子序列长度
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 1e6 10;
const int maxn 1e6 10;
const int mod 1e9 7;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n; cin n;string s; cin s;s s;vectorint dp(n 1);vectorint maxx(26);int ans 0;for (int i n; i 1; i -- ){int c s[i] - a;dp[i] maxx[c] 1;for (int j c 1; j 26; j ) maxx[j] max(maxx[j], dp[i]);ans max(ans, dp[i]);}cout ans \n;for (int i 1; i n; i ) cout dp[i] ;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;// cin t;while (t--){solve();}
}1616D - Keep the Average High思维
好聪明的做法先把所有数都减去 x x x这样需要满足的条件就是 a l a r 0 a_la_r0 alar0 了然后只需要看连续的长度为 2 2 2 的串和长度为 3 3 3 的串是否满足条件就好了为什么只需要看这两种呢因为其他长度的串都可以用这两种拼起来啊这种想法在今天的第一道 dp 中已经出现过了
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 1e6 10;
const int maxn 1e6 10;
const int mod 1e9 7;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n; cin n;vectorint a(n 1);for (int i 1; i n; i ) cin a[i];int x; cin x;for (int i 1; i n; i ) a[i] - x;int ans n;for (int i 2; i n; i ){if (a[i] a[i - 1] a[i - 2] 0 || a[i] a[i - 1] 0){ans -- ;a[i] INF;}}cout ans \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;cin t;while (t--){solve();}
}1978D - Elections思维前缀后缀
贪心一下想赢的话先删前面的人前面的人删了还赢不了就删掉后面最大的
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 1e6 10;
const int maxn 1e6 10;
const int mod 1e9 7;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n, c;cin n c;vectorint a(n 1);vectorint pre(n 1), maxx_pre(n 1), maxx_suff(n 2);for (int i 1; i n; i ) cin a[i];for (int i 1; i n; i ) pre[i] pre[i - 1] a[i];for (int i 1; i n; i ) maxx_pre[i] max(maxx_pre[i - 1], a[i]);for (int i n; i 1; i -- ) maxx_suff[i] max(maxx_suff[i 1], a[i]);for (int i 1; i n; i ){if (i 1){if (a[i] c maxx_suff[i 1]) cout 0 ;else cout 1 ;}else if (i n){if (a[i] max(maxx_pre[i - 1], a[1] c)) cout 0 ;else cout n - 1 ;}else{if (a[i] max(a[1] c, maxx_pre[i - 1])){if (a[i] maxx_suff[i 1]) cout 0 ;else{if (a[i] pre[i - 1] c maxx_suff[i 1]) cout i - 1 ;else cout i ;}}else{if (a[i] pre[i - 1] c maxx_suff[i 1]) cout i - 1 ;else cout i ;}}}cout \n;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;cin t;while (t--){solve();}
}1979D - Fixing a Binary String思维
#include bits/stdc.husing namespace std;#define int long long
using i64 long long;typedef pairint, int PII;
typedef pairint, char PIC;
typedef pairdouble, double PDD;
typedef pairint, PII PIII;
typedef pairint, pairint, bool PIIB;const int N 1e6 10;
const int maxn 1e6 10;
const int mod 1e9 7;
const int mod1 954169327;
const int mod2 906097321;
const int INF 0x3f3f3f3f3f3f3f3f;void solve()
{int n, k;cin n k;string s;cin s;vectorint a(1);int tmp 1;for (int i 1; i n; i ){if (s[i] ! s[i - 1]){a.push_back(tmp);tmp 1;}else tmp ;}if (tmp ! 0) a.push_back(tmp);int pos -1;int m a.size() - 1;vectorint pre(m 1);for (int i 1; i m; i ) pre[i] pre[i - 1] a[i];for (int i 1; i m - 1; i ){if (a[i] ! k){if (pos -1) pos i;else{cout -1 \n;return;}}}if (pos -1){if (a[m] k) cout n \n;else cout -1 \n;}else{if (a[m] k){if ((m % 2 0 pos % 2 0) || (m % 2 ! 0 pos % 2 ! 0)){cout -1 \n;}else{if (a[pos] 2 * k) cout pre[pos - 1] k \n;else cout -1 \n;}}else{if (a[m] k) cout -1 \n;else{int tmp k - a[m];if ((m % 2 0 pos % 2 0) || (m % 2 ! 0 pos % 2 ! 0)){if (a[pos] tmp ((a[pos] - tmp) k || (a[pos] - tmp) 0)) cout pre[pos - 1] tmp \n;else cout -1 \n;}else cout -1 \n;}}}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t 1;cin t;while (t--){solve();}
}
