A。Astonishing Combinatorial Number
题目大意：给你n, m, k,问你C（i， j）%k= 0的个数{1 <= i <=n, 1 <=j <= m }
题解：我们可以先预处理组合数，由组合数公式变形 A[i][j] = （A[i-1][j-1] + A[i-1][j]）%k
那么我们在n, m范围内，求出有多少个A[i][j] = 0就好了
我们可以把组合数预处理的三角形变成矩形，类似求矩形单位矩形内a[i][j]的和
变种公式 c[i][j] = c[i-1][j] + c[i][j-1] - c[i-1][j-1] + (a[i][j] == 0)
#include <iostream> #include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int MAXN = 2002; int T, n, m, k, t; int a[MAXN][MAXN]; long long int c[MAXN][MAXN]; int fun(int i, int j){ if(i < j) return 0; return a[i][j] == 0; } void slove() { memset(a, 0, sizeof(a)); memset(c, 0, sizeof(c)); for(int i = 0; i <= 2000; i++) { a[i][0] = 1; for(int j = 1; j <= i; j++) { a[i][j] = (a[i-1][j] + a[i-1][j-1])%k; } } for(int i = 0; i <= 2000; i++) { for(int j = 0; j <= 2000; j++) { if(i == 0 && j == 0) c[i][j] = fun(i, j); if(i == 0) c[i][j] = c[i][j-1] + fun(i, j); else if(j == 0) c[i][j] = c[i-1][j] + fun(i, j); else c[i][j] = c[i-1][j] + c[i][j-1] - c[i-1][j-1] + fun(i, j); } } } int main() { scanf("%d", &T); while(T--) { scanf("%d%d", &t, &k); slove(); while(t--) { scanf("%d%d", &n, &m); printf("%lld ", c[n][m]); } } return 0; }
B。Blind Father
题目大意：给你n条木板， 长度分别为a_i, 让你把它切成矩形， 可以纵向和横向切，问你能得到最大的矩形是多少
题解：本来想用RMQ和双指针去做，却卡了半小时。最后发现这是个可以用单调栈做的沙雕题。
以每个点为最短长度木板，分别向左向右跑一边，得到r[i], l[i]即为能延伸的最远位置，然后枚举最大值
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; const int MAXN = 10005; int l[MAXN], r[MAXN]; long long int a[MAXN]; int main() { int n; while(~scanf("%d", &n)) { for(int i = 1; i <= n; i++) { scanf("%lld", &a[i]); l[i] = i; r[i] = i; } for(int i = 2; i <= n; i++) { while(l[i] > 1 && a[l[i]-1] >= a[i]) l[i] = l[l[i]-1]; } for(int i = n-1; i >= 1; i--) { while(r[i] < n && a[r[i]+1] >= a[i]) r[i] = r[r[i]+1]; } long long int ans = 0; for(int i = 1; i <= n; i++) { ans = max(1LL*(r[i]-l[i]+1)*a[i], ans); } printf("%lld ", ans); } return 0; }
C。Collection Game
题目大意：一个人从1出发，每次能走1格，2格，或者3格，问能到达第n格的路径数是多少，其中有一些格子坏了不能走。
题解：简单dp，列出转移方程差不多就可以做出来了。
如果i的格子能走， 那么dp[i] = dp[i-1] + dp[i-2] +dp[i-3]。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int dp[100005], vis[100005]; const int mod = 10007; int main() { int n, m; while(~scanf("%d%d", &n, &m)) { memset(vis, 0, sizeof(vis)); memset(dp, 0, sizeof(dp)); for(int i = 0, x; i < m; i++) { scanf("%d", &x); if(x < n) vis[x] = 1; } dp[1] = 1; for(int i = 2; i <= n; i++) { if(!vis[i]) { dp[i] = (dp[i] + dp[i-1])%mod; if(i > 2) dp[i] = (dp[i] + dp[i-2])%mod; if(i > 3) dp[i] = (dp[i] + dp[i-3])%mod; } else dp[i] = 0; } printf("%d ", dp[n]); } return 0; }
D。Distinct Package Manager
题目大意：如果A依赖B，则install软件A需要install 软件B，同样uninstall B则需要uninstallA，给你一系列安装、卸载的软件，
问你每一步中软件改变的数量是多少。
题解：正向和反向分别建条边，然后可以用dfs来操作了。具体见代码
#include <iostream> #include <cstdio> #include <algorithm> #include <vector> #include <cstring> using namespace std; const int MAXN = 105; vector<int>G[105]; vector<int>R[105]; int vis[MAXN]; int uninstall(int u) { if(!vis[u]) return 0; else vis[u] = false; int ans = 1; for(int i = 0; i < (int)G[u].size(); i++) { int v = G[u][i]; if(vis[v]) { ans += uninstall(v); } } return ans; } int install(int u) { if(vis[u]) return 0; else vis[u] = true; int ans = 1; for(int i = 0; i < (int)R[u].size(); i++) { int v = R[u][i]; if(!vis[v]) ans += install(v); } return ans; } int main() { int T, n, q; scanf("%d", &T); while(T--) { memset(vis, false, sizeof(vis)); scanf("%d", &n); for(int i = 0; i < n; i++) { G[i].clear(); R[i].clear(); } for(int i = 1, m, v; i < n; i++) { scanf("%d", &m); while(m--) { scanf("%d", &v); R[i].push_back(v); G[v].push_back(i); } } scanf("%d", &q); char s[10]; int option; while(q--) { scanf("%s %d", s, &option); if(s[0] == 'u') printf("%d ", uninstall(option)); else printf("%d ", install(option)); } } return 0; }
E。Essential Element
题目大意：给你个由01组成的n,m矩阵，问你只包含1的子矩阵个数是多少个
题解：大佬说这是单调栈。待补
F。Final Ugly English
这个沙雕题我竟然因为不知道多组数据wa很多次
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; char s[10006]; int main() { while(gets(s) != NULL){ int len = strlen(s); string ss = ""; for(int i = 0; i < len; i++){ if(s[i] >= 'a' && s[i] <= 'z') ss += s[i]; else { reverse(ss.begin(), ss.end()); cout << ss; if(s[i] == ' ') printf(" "); ss = ""; } } if(ss.size() > 0) { reverse(ss.begin(), ss.end()); cout << ss; } printf(" "); } return 0; }
G。Great Atm
题目大意：给你一系列{xor, or, and} 操作问你选择一个在0~m内的x ，经过这些操作后得到的数最大
题解：按位枚举，设0~40位每个数为x, x可以是0，也可是1
发现 XXXXXX
OR 1111110
= 111111X
同样可以得到其他的几种状态，自己可以想想。
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; typedef long long int LL; int t; LL m, x; char s[10]; int a[51]; int main() { while(~scanf("%d%lld", &t, &m)) { for(int i = 0; i < 41; i++) { a[i] = 2; } while(t--) { scanf("%s %d", s, &x); if(s[0] == 'A') { for(int i = 0; i < 41; i++) if(((x>>i)&1) == 0) { a[i] = 0; } } else if(s[0] == 'O') { for(int i = 0; i < 41; i++) { if((x>>i)&1) a[i] = 1; } } else { for(int i = 0; i < 41; i++) { int y = (x>>i)&1; if(y) { if(a[i] == 2) a[i] = -2; else if(a[i] == -2) a[i] = 2; else a[i] ^= y; } } } } LL gg = 0, ans = 0; for(int i = 40; i >= 0; i--) { if(a[i] == 2 && gg + (1LL<<i) <= m) { gg += (1LL<<i); ans += (1LL<<i); } else if(a[i] == 1) ans += (1LL<<i); else if(a[i] == -2) { ans += (1LL<<i); } } printf("%lld ", ans); } return 0; }
H。还没看。