xzm2019

北京理工大学第八届程序设计新生赛 题解
A. 欢迎参加北京理工大学程序设计新生赛无聊的阅读理解题答案:1940 2018 6 6 2B.追赶矩阵行列式给定...
扫描右侧二维码阅读全文
01
2020/01

北京理工大学第八届程序设计新生赛 题解

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$ 行,可以化简成对角矩阵,接着用行列式性质计算。

#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,同样可以参与字符串比较。

#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)$。

#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

证明

请参看证明

#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

请参看题解

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$

图片1.png

#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. 方块板

给一个方块板的部分点的颜色,求一个合法布局

方法一

从左往右以列为单位遍历,如果分别两列存在字母则从中间分开成两部分。再从上往下依次遍历,当前情况每部分不存在两列都有字母,即所有字母都在同一列时,以行为单位遍历,可以区分不同行的字母。

方法二

随机一种填充顺序,按顺序填充字母,对于每个字母维护它四侧的最远位置,贪心填充。

#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,我无聊的加一个这个功能,虽然不是很完善,但还是可以用的。

#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增多。

#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]))$
滚动一维可以降低空间复杂度。

#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之前的[数量减去]数量即可。

#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;
}
Last modification:December 31st, 2019 at 11:59 pm
If you think my article is useful to you, please feel free to appreciate

Comment here is closed