Loading... ## A. 欢迎参加北京理工大学程序设计新生赛 > 无聊的阅读理解题 答案：1940 2018 6 6 2 ## B.追赶矩阵行列式 > 给定矩阵，求它的行列式。 > $$ > \left[\begin{array}{cccccc} > {k x} & {0} & {0} & {} & {0} & {k x} \\ > {-x} & {k x} & {0} & {\cdots} & {0} & {k x} \\ > {0} & {-x} & {k x} & {} & {0} & {k x} \\ > {\vdots} & {\vdots} & {} & {\ddots} & {} & {\vdots} \\ > {0} & {0} & {0} & {\ldots} & {k x} & {k x} \\ > {0} & {0} & {0} & {} & {0} & {k x} > \end{array}\right] > $$ ### 做法一 定义原矩阵的 $n$ 阶行列式答案为 $D(n)$，按第一行展开，有 $D(n)=k x \cdot D(n-1)+(-1)^{1+n} \cdot k x \cdot(-x)^{n-1}$，手动画一下 $n=2$ 的样例 $\left[ \begin{array} { l l } { k x } & { k x } \\ { - x } & { k x } \end{array} \right]$ 是 $(k x)^{2}-k x \cdot(-x)$，然后线性递推。时间复杂度 $O(n\cdot \log(n))$ ### 做法二 按顺序第 $i-1$ 行乘以 $\frac{1}{k}$ 加到第 $i$ 行，可以化简成对角矩阵，接着用行列式性质计算。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 20191222; ll quickpow(ll a, ll b) { if (a >= mod) a %= mod; ll res = 1; while (b > 0) { if (b & 1) res = res * a % mod; b >>= 1; a = a * a % mod; } return res; } ll det(int n, int k, int x) { if (n == 2) return 1LL * (k * k % mod + k) % mod * x % mod * x % mod; int sgn = (n & 1) ? 1 : -1; return (1LL * k * x % mod * det(n-1, k, x) % mod + 1LL * sgn * quickpow(mod - x, n - 1) * k % mod * x % mod + mod) % mod; } int main() { int t, n, k, x; scanf("%d", &t); while (t--) { scanf("%d%d%d", &n, &k, &x); printf("%lld\n", det(n, k, x)); } return 0; } ``` ## C. 请给我扭曲你人生的权利 > 给定两个字符串。可以对第一个字符串进行操作，每次可以修改第一个字符串的一个字符，或者在第一个字符串后面添加或删除一个字符，问第一个字符串需要操作几次才能变成第二个字符串。 贪心地考虑问题。先考虑两个字符串相同的部分，显然，只要把原字符串和新字符串不同的字符修改就行了；对于两个字符串后面不同的部分，如果原字符串比较长，就全部删掉；如果原字符串比较短，就对照第二个字符串添加字符。所以，只要按照两个字符串较大的长度进行遍历，比较两个字符串不同的字符有几个就可以了。如果一个字符串比较短，那么它后面的部分可以看成`\0`，同样可以参与字符串比较。 ```cpp #include <cstdio> #include <algorithm> using namespace std; const int MAXN = 1e5 + 5; char str[2][MAXN]; int main() { int n, m; scanf("%d%d", &n, &m); scanf("%s%s", str[0], str[1]); int len = max(n, m); int cnt = 0; for (int i = 0; i < len; i++) { if (str[0][i] != str[1][i]) { cnt++; } } printf("%d\n", cnt); return 0; } ``` ## D. Dr.Bright And SCP-079 > 在一个最大 $2000 \times 2000$ 的方形区域内，每个位置一开始有一个初始值。然后存在单点修改的操作（次数很少，最多 $200$ 次）以及查询的操作（最多 $20\,0000$ 次），每次查询是给一个矩形范围，查询这个矩形范围内现有的所有值的和。 离线处理二维前缀和，也就是预处理 $(1,1)$ 这个点和 任意 $(x,y)$ 点构成的矩形范围内初始值的和。这个可以在 $O(n^2)$ 时间复杂度内离线处理出来，其中 $n$ 为方形区域的边长。考虑到单点修改的次数极其少，我们可以保存每次修改的位置及 $\Delta$ 。我们对于每个查询，首先可以使用容斥原理（鸽巢原理）获取这个区域内初始值的和，然后暴力判断前面修改过的值是否是在这个查询的区域范围内，如果是，增加相应的 $\Delta$ 即可。容易发现，这样操作的时间复杂度上界为 $O(q_1q_2)$，其中 $q_1$ 是单点修改的次数，$q_2$ 是查询的次数。故最终时间复杂度的上界为 $O(n^2+q_1q_2)$。 ```cpp #include <bits/stdc++.h> using namespace std; typedef long long ll; #define scan(x) scanf("%d",&x) const int maxn = 2005; ll val[maxn][maxn]; int n,q,op; const ll mod = 100000; ll sum[maxn][maxn] = {}; vector < pair<pair<int, int>, int> > output; ll GetDelta(int xl,int yl,int xr,int yr) { ll ret = 0; for (auto &tmp : output) { if (tmp.first.first >= xl && tmp.first.first <= xr && tmp.first.second >= yl &&tmp.first.second <= yr) ret += tmp.second; } return ret; } ll a0, a1, b; int main() { #ifdef _IRONHEAD_ assert(freopen("./InputData/10.in", "r", stdin)); assert(freopen("./Output/10.out", "w", stdout)); #endif // ios::sync_with_stdio(false); output.clear(); cin >> n >> q; cin >> a0 >> a1 >> b; for (int i = 1; i <= n; i++) for (int j = 1; j <= n;j++) { val[i][j] = ((((b * a0)>>23) + (a1 << 16)) % mod + mod) % mod; a0 = a1; a1 = val[i][j]; } for (int i = 1; i <= n;i++) for (int j = 1; j <= n;j++) sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + val[i][j]; while (q--) { cin >> op; if (op==1) { int x, y, num; cin >> x >> y >> num; output.push_back(make_pair(make_pair(x,y),num)); } else { int xl, yl, xr, yr; cin >> xl >> yl >> xr >> yr; cout << sum[xr][yr] - sum[xl - 1][yr] - sum[xr][yl - 1] + sum[xl - 1][yl - 1] + GetDelta(xl, yl, xr, yr) << endl; } } return 0; } ``` ## E. 奥术跃迁 > 你在$X=a$的位置，你每个单位时间可以移动$1$或者从$k$移动到$\sqrt[3]{k}$。求最短时间 ### 题解 贪心即可。当` (跃迁后的位置到目标位置的距离+1) < 直接走的距离`就一直跃迁；最后剩下的距离直接走过去即可。时间复杂度$O(kT)$，$k$是一个比较大的常数。 ### 坑点 - 直接用pow对负数开三次方可能得到nan(not a number)，考虑$\sqrt [ 3 ] { - a ^ { 3 } } = - \sqrt [ 3 ] { a ^ { 3 } }$，可以先对绝对值开三次方再决定符号 - float精度不够，请改用double ### 证明 请参看[证明][1] ```cpp #include<bits/stdc++.h> using namespace std; const double t=1/3.0; inline double sqrrrt(double x){return x>0?pow(x,t):-pow(-x,t);} int main() { int T;scanf("%d",&T); while (T--) { double x,y,tmp,ans=0;scanf("%lf%lf",&x,&y); while (tmp=sqrrrt(x),fabs(x-y)>fabs(tmp-y)+1)x=tmp,ans++; ans+=fabs(x-y); printf("%.9f\n",ans); } } ``` ## F. Shenyunhan and His Tiling Job 请参看[题解][2] ## G. 秀 > 求圆内接$n$边形第$i$个顶点到第$j$个顶点的较短边长。 先求一条边的边长。如图，$n$边形对应的$\theta=\frac{2 \pi}{2 n}=\frac{\pi}{n}$，边长就是$2 r \sin \theta=2 r \sin \frac{\pi}{n}$。 再求i到j最短经过几条边：$l=(i-j) \bmod n$ 最后答案就是$2 r \sin \frac{\pi}{n} \cdot(i-j) \bmod n$ <img src="https://image.mlwly.cn/2019/12/31/7cd333a97c828.png" alt="图片1.png" /> ```cpp #include <iostream> #include <vector> #include <cstdio> #include <algorithm> #include <cmath> #include <cstdlib> #include <string> #include <cstring> #include <queue> #include <stack> #include <functional> #include <map> #include <set> #include <bitset> #include <ctime> #include <cassert> #include <complex> using namespace std; const double PI = acos(-1); int main() { int n; double r; scanf("%d%lf", &n, &r); int i, j; scanf("%d%d", &i, &j); i--, j--; double dis = min((i - j + n) % n, (j - i + n) % n); double deg = PI / n; double len = r * sin(deg) * 2; printf("%lf\n", len * dis); return 0; } ``` ## H. 方块板 > 给一个方块板的部分点的颜色，求一个合法布局 ### 方法一 从左往右以列为单位遍历，如果分别两列存在字母则从中间分开成两部分。再从上往下依次遍历，当前情况每部分不存在两列都有字母，即所有字母都在同一列时，以行为单位遍历，可以区分不同行的字母。 ### 方法二 随机一种填充顺序，按顺序填充字母，对于每个字母维护它四侧的最远位置，贪心填充。 ```cpp #include <bits/stdc++.h> using namespace std; const int MAXN = 1005; int n, m; char g[MAXN][MAXN], h[MAXN][MAXN]; struct Node { char c; int x, y; Node() {} Node(char c, int x, int y) : c(c), x(x), y(y) {} }; vector<Node> v; int l[MAXN], r[MAXN]; bool solve() { for (int i = 1; i <= n; i ++) strcpy(h[i] + 1, g[i] + 1); shuffle(v.begin(), v.end(), mt19937(rand())); int x1, x2, y1, y2; for (auto& p : v) { char c = p.c; for (y1 = p.y; h[p.x][y1 - 1] == '.'; y1 --); for (y2 = p.y; h[p.x][y2 + 1] == '.'; y2 ++); for (x1 = p.x;; x1 --) { bool flag = true; for (int j = y1; j <= y2; j ++) if (h[x1 - 1][j] != '.') { flag = false; break; } if (!flag) break; } for (x2 = p.x;; x2 ++) { bool flag = true; for (int j = y1; j <= y2; j ++) if (h[x2 + 1][j] != '.') { flag = false; break; } if (!flag) break; } for (int i = x1; i <= x2; i ++) for (int j = y1; j <= y2; j ++) if (h[i][j] == '.') h[i][j] = c; } for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) if (h[i][j] == '.') return true; for (int i = 1; i <= n; i ++) printf("%s\n", h[i] + 1); return false; } int main() { srand(time(0)^19260817); scanf("%d%d", &n, &m); for (int i = 1; i <= n; i ++) { scanf("%s", g[i] + 1); for (int j = 1; j <= m; j ++) if (isupper(g[i][j])) { v.emplace_back(g[i][j], i, j); } } while (solve()); return 0; } ``` ## I. Dev-C++ 大法好 > 给出一个在 C99 标准下可以正常编译运行的 **C** **语言**代码，列出其所有的函数 出题人的本意就是匹配`){}`，所以把约束条件设置的非常的多，就是为了不断简化。其实这题的灵感来源是自己的大作业，当时我们要做一个C语言的IDE，我无聊的加一个这个功能，虽然不是很完善，但还是可以用的。 ```cpp #include <bits/stdc++.h> using namespace std; string source; void replaceAll(string &s, string oldstr, string newstr) { for (string::size_type pos = 0; pos != string::npos; pos += newstr.length()) if ((pos = s.find(oldstr, pos)) != string::npos) s.replace(pos, oldstr.length(), newstr); else break; } struct functions{ string inClass, name, outputType; vector<string> inputType; functions(string inClass = "", string name = "", string outputType = "void", vector<string> inputType = vector<string>(0)) :inClass(inClass), name(name), outputType(outputType), inputType(inputType) {} }; vector<functions> funs; void solve(string &s) { replaceAll(s, "/*", " /* "); replaceAll(s, "*/", " */ "); replaceAll(s, "//", " // "); replaceAll(s, "(", " ( "); replaceAll(s, ")", " ) "); replaceAll(s, "{", " { "); replaceAll(s, "}", " } "); replaceAll(s, "=", " = "); replaceAll(s, "\"", " \" "); replaceAll(s, "'", " ' "); replaceAll(s, ";", " ; "); replaceAll(s, ",", " , "); replaceAll(s, "+ = ", "+="); replaceAll(s, "- = ", "-="); replaceAll(s, "* = ", "*="); replaceAll(s, "/ = ", "/="); replaceAll(s, "^ = ", "^="); replaceAll(s, "| = ", "|="); replaceAll(s, "& = ", "&="); replaceAll(s, ":", " : "); replaceAll(s, " : : ", "::"); //ע���滻������ע�� vector<string> tokens; string now = ""; for (int i = 0; s[i]; i++) { if (s[i] == ' ' || s[i] == '\t' || s[i] == '\r' || s[i] == '\n' || s[i] == '\0') { if (now != "") { if (now == ":" && tokens.back() == ")") { string tmpnow = ""; for (int j = i + 1; s[j]; j++) { if (s[j] == ' ' || s[j] == '\t' || s[j] == '\r' || s[j] == '\n' || s[j] == '\0') { if (tmpnow == "{") { now = "{"; i = j - 1; break; } tmpnow = ""; } else tmpnow += s[j]; } continue; } if (now == "const") { now = ""; continue; } if (now == "//") { for (int j = i; s[j]; j++) { if (s[j] == '\n') { i = j - 1; break; } } now = ""; continue; } if (now == "/*") { int num = 1; string tmpnow = ""; for (int j = i + 1; s[j]; j++) { if (s[j] == ' ' || s[j] == '\t' || s[j] == '\r' || s[j] == '\n' || s[j] == '\0') { if (tmpnow == "/*") num++; if (tmpnow == "*/") { num--; if (num == 0) { i = j - 1; break; } } tmpnow = ""; } else tmpnow += s[j]; } now = ""; continue; } //cout << now << s[i]; tokens.push_back(now); now = ""; } //else cout << s[i]; } else now += s[i]; } int cnt = 0; string nowNamespace = ""; for (int i = 1; i < (int)tokens.size(); i++) { if ((tokens[i] == "struct" || tokens[i] == "class") && tokens[i + 2] == "{") { cnt = 0; nowNamespace = tokens[i + 1]; i += 2; } functions tmp(nowNamespace); if (tokens[i] == "{" && tokens[i - 1] == ")") { int num = 1; for (int j = i - 2; j >= 0; j--) { if (tokens[j] == ")") num++; if (tokens[j] == "(") { num--; if (num == 0) { tmp.name = tokens[j - 1]; tmp.outputType = ""; for (int k = j - 2; k >= 0; k--) if (tokens[k] != "}" && tokens[k] != "}" && tokens[k] != ";" && tokens[k].back() != ':' && tokens[k] != "inline" && tokens[k] != "static" && tokens[k][0] != '#' && tokens[k].back() != '\"' && tokens[k].back() != '>') tmp.outputType = tmp.outputType == "" ? tokens[k] : tokens[k] + " " + tmp.outputType; else break; int last = i - 2; for (int k = i - 2; k >= j; k--) { if (tokens[k] == "(" || tokens[k] == ",") { string tt = ""; for (int t = k + 1; t < last; t++) tt = tt == "" ? tokens[t] : tt + " " + tokens[t]; if (tt != "") tmp.inputType.push_back(tt); last = k - 1; } if (tokens[k] == "=" || tokens[k] == ")") last = k - 1; } reverse(tmp.inputType.begin(), tmp.inputType.end()); break; } } } funs.push_back(tmp); num = 1; for (int j = i + 1; j < (int)tokens.size(); j++) { if (tokens[j] == "{") num++; if (tokens[j] == "}") { num--; if (num == 0) { i = j; //cout << tmp.outputType << " " << tmp.name << " "; //cout << j << endl; break; } } } continue; } if (nowNamespace != "") { //cout << i << " " << nowNamespace << " " << cnt << endl; if (tokens[i] == "{") cnt++; if (tokens[i] == "}") { cnt--; if (!cnt) nowNamespace = ""; } } } } int main() { char ch; while ((ch = getchar()) != EOF) source += ch; solve(source); for (auto & i: funs) { if (i.outputType != "") cout << i.outputType << " "; if (i.inClass != "") cout << i.inClass << "::"; cout << i.name << "("; for (int j = 0; j < (int)i.inputType.size(); j++) cout << i.inputType[j] << (j == (int)i.inputType.size() - 1 ? ")" : ","); if ((int)i.inputType.size() == 0) cout << ")"; cout << endl; } return 0; } ``` ## J. shenyunhan的卡牌游戏 > 卡牌游戏，你是先手，你第一步最少要拿 1 张牌，最多拿 $n -1$张牌，接下来每一步，双方最少要拿 1 张牌，最多拿等同于上一步对方拿的牌数的牌。拿走最后一张牌的人将取得游戏的胜利。 当$n=2^k$的时候无解，不然每次取二进制下最后一个1的位置即可。因为对手的操作一定会时我们二进制的1增多。 ```cpp #include <bits/stdc++.h> using namespace std; int main() { int n; scanf("%d", &n); int x = n; if (bitset<31>(n).count() == 1) { printf("-1\n"); fflush(stdout); return 0; } while(1) { bitset<31> b(min(x, n)); for (int j = 0; j < 31; j++) if (b[j] == 1) { printf("%d\n", (1 << j)); fflush(stdout); n -= (1 << j); break; } if (n == 0) return 0; int x; scanf("%d", &x); n -= x; } return 0; } ``` ## K. 复读症候群 > 给定一些由01?构成的字符串，?可以换成0或1，问最多可以有多少连续相同的字符串。 $dp[1][i][j]$代表第j个位置，第i行之前，连续出现了多少次1 $dp[0][i][j]$代表第j个位置，第i行之前，连续出现了多少次0 转移方程： $\left\{\begin{matrix} a[i][j]=0 \qquad dp[0][i][j]=dp[0][i-1][j]+1 \qquad dp[1][i][j]=0\\ a[i][j]=1 \qquad dp[1][i][j]=dp[1][i-1][j]+1 \qquad dp[0][i][j]=0\\ a[i][j]=? \qquad dp[0][i][j]=dp[0][i-1][j]+1 \qquad dp[1][i][j]=dp[1][i-1][j]+1 \end{matrix}\right.$ 每次求完一行，更新答案 $ans=max(ans,min_{j=1}^m(max_{k=1}^{2}dp[k][i][j]))$ 滚动一维可以降低空间复杂度。 ```cpp #include<iostream> #include<cstring> #define INF 0x3f3f3f3f using namespace std; char a[10005][10005]; int last[2][10005]; int main(){ int n,m; scanf("%d %d",&n,&m); int ans=0; for(int i=1;i<=n;i++){ scanf("%s",a[i]+1); } memset(last,INF,sizeof last); for(int i=1;i<=n;i++){ int minn=1; for(int j=1;j<=m;j++){ if(a[i][j]=='0'){ last[0][j]=min(last[0][j],i); last[1][j]=INF; }else if(a[i][j]=='1'){ last[1][j]=min(last[1][j],i); last[0][j]=INF; }else{ last[0][j]=min(last[0][j],i); last[1][j]=min(last[1][j],i); } minn=max(minn,min(last[0][j],last[1][j])); } ans=max(ans,i-minn+1); } printf("%d\n",ans); return 0; } ``` ## L. 冬至的暖心礼物 > []代表盒子，J代表饺子，问找到饺子最少要开几个盒子。 找到`J`之前的`[`数量减去`]`数量即可。 ```cpp #include <bits/stdc++.h> using namespace std; char s[100005]; int main() { scanf("%s", s); int ans = 0; for (int i = 0; s[i]; i++) if (s[i] == '[') ans++; else if (s[i] == ']') ans--; else break; printf("%d\n", ans); return 0; } ``` [1]: http://xzm2001.cn/usr/uploads/2019/12/4285191662.pdf [2]: http://xzm2001.cn/usr/uploads/2019/12/526139929.pdf Last modification：December 31st, 2019 at 11:59 pm © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
