xzm2019

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 现场赛 题解
Problem A. 日麻计算器当$x > 4$的时候，直接输出对应答案当$x \leq 4$时，按照题目公...
扫描右侧二维码阅读全文
18
2019/08

北京理工大学2019年计算机学院小学期程序设计方法与实践 - 现场赛 题解

  1.  Home
  2. Text  
    3. Share to：

Problem A. 日麻计算器

  • 当$x > 4$的时候，直接输出对应答案
  • 当$x \leq 4$时，按照题目公式去计算，和$12\,000$取max。注意$z$向上保留到整百的一个比较快的写法是$z' = (z / 100 + !!(z\ \%\ 100)) \times 100$。
#include <bits/stdc++.h> 
using namespace std;

int main()
{
    int T;
    scanf("%d", &T);
    int a,b;
    while (T--)
    {
        scanf("%d%d", &a, &b);
        if (a >= 13) printf("48000\n");
        else if (a >= 11) printf("36000\n");
        else if (a >= 8) printf("24000\n");
        else if (a >= 6) printf("18000\n");
        else if (a == 5) printf("12000\n");
        else
        {
            int t = (1 << (2 + a)) * 6 * b;
            t = (t / 100 + !!(t % 100)) * 100;
            printf("%d\n",min(t,12000));
        }
    }
    return 0;
}

Problem B. 麻将桌绘制

由于$w \times h$最大为$40\,000$，我们可以暴力的判断每一个点是否符合以下两个条件之一。

  • 对于圆形，直接带入圆的公式$(x - x_C)^2 + (y-y_C)^2 \leq r^2$即符合条件。
  • 对于矩形，我们先通过题目中的两个点判断出$x$和$y$的合法上下界，对于每个点直接判断。
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int w,h,xc,yc,r,x1,x2,y1,y2,xmin,xmax,ymin,ymax;
    cin >> w >> h >> xc >> yc >> r >> x1 >> y1 >> x2 >> y2;
    if (y1 < y2)
    {
        xmin = x1; xmax = x1 + y2 - y1;
        ymin = y1; ymax = y2;
    }
    if (y1 > y2)
    {
        xmin = x2 - y1 + y2; xmax = x2;
        ymin = y2; ymax = y1;
    }
    if (x1 < x2)
    {
        xmin = x1; xmax = x2;
        ymin = y2 - x2 + x1; ymax = y1;
    }
    if (x1 > x2)
    {
        xmin = x2; xmax = x1;
        ymin = y1; ymax = y1 + x1 - x2;
    }
    assert(xmax - xmin == ymax - ymin && xmax > xmin && ymax > ymin);
    for (int i = 0; i < w; i++)
    {
        for (int j = 0; j < h; j++)
        {
            bool flag = false;
            flag = flag || ((i - xc) * (i - xc) + (j - yc) * (j - yc) <= r * r);
            flag = flag || ((xmin <= i && i <= xmax) && (ymin <= j && j <= ymax));
            if (flag) printf("/"); else printf("\\");
        }
        printf("\n");
    }
    return 0;
}

Problem C. 雀士分麻将

Solution A: 贪心

本题可以直接贪心的来做，正着按照题目要求扫一遍，然后反着用上一次的数据扫一遍取max即可。注意最后答案可能会超出int的范围。

#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll

const int INF = 0x3f3f3f3f;
const int MAXN = 100000+10;
int n;
int a[MAXN];
int b[MAXN];
void solve()
{
    a[0] = a[n+1] = INF;
    for(int i = 1; i <= n; i++ ){
        b[i] = 1;
    }
    for(int i = 1; i <= n; i++ ){
        if( a[i] > a[i-1] ) b[i] = max( b[i], b[i-1]+1 );
    }
    for(int i = n; i >= 1; i-- ){
        if( a[i] > a[i+1] ) b[i] = max( b[i], b[i+1]+1 );
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++ ){
        // printf("%d\n", b[i]);
        ans += 1ll*b[i];
    }
    printf("%lld\n", ans);
}
int main(int argc, char * argv[]) 
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++ ){
        scanf("%d", &a[i]);
    }
    solve();
    return 0;
}

Solution B: 图论

我们可以根据相邻两个数的大小关系建立单向边，构成有向图。将所有入度为$0$的点设置为$1$个糖果，然后bfs向上递增。

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
struct edge{
    int to,next;
}e[100010];
int head[100010],cnt;
int I[100010];
inline void ins(int u,int v)
{
    e[++cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
    I[v]++;
}
int n,a[100010],tot[100010];
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)scanf("%d",a+i);
    for (int i=1;i<n;i++)
    {
        if (a[i]>a[i+1])ins(i+1,i);
        if (a[i]<a[i+1])ins(i,i+1);
    }
    ll ans=0;
    queue<int>q;while (!q.empty())q.pop();
    for (int i=1;i<=n;i++)if (!I[i])q.push(i),ans+=(tot[i]=1);
    while(!q.empty())
    {
        int now=q.front(),d=tot[now]+1;q.pop();
        for (int i=head[now];i;i=e[i].next)
        {
            tot[e[i].to]=max(tot[e[i].to],d);
            I[e[i].to]--;
            if (!I[e[i].to])q.push(e[i].to),ans+=tot[e[i].to];
        }
    }
    printf("%lld\n",ans);
    return 0;
}

Problem D. 牌河N对子

求给定的字符串有多少非空子序列，满足其是一个串加其本身。

由于$N \leq 200$，因此我们只需要$O(N^3)$的时间复杂度即可。

符合条件的子序列的第二部分可以从整个字符串的$s_1, s_2, \cdots, s_{|s| - 1}$开始，我们枚举这个起点$i$。

这样我们把字符串分割为两个部分$s[0:i]$和$s[i + 1: |s| - 1]$。

我们只需要求出其公共子序列的方案数即可，同时再减去$s[0:i]$和$s[i + 2: |s| - 1]$的公共子序列的方案数，就是该点的贡献。

求公共子序列的方案数可以在$O(n^2)$的时间复杂度内解决完毕，加上枚举分割点，整体时间复杂度为$O(n^3)$。

#include <bits/stdc++.h>
using namespace std;

const int maxn = 210;
const int mod = 1000000007;

int ans[maxn][maxn];
int res, n;
char ss[maxn];

int work(int l) {
    memset(ans, 0, sizeof(ans));
    int n1 = l, n2 = n - l - 1;
    for(int i=1; i<=n1; ++i)
        ans[i][0] = ans[i-1][0] + (ss[i-1] == ss[l] ? 1 : 0);
    for(int i=1; i<=n1; ++i)
        for(int j=1; j<=n2; ++j) {
            ans[i][j] = (ans[i][j-1] + ans[i-1][j])%mod;
            if(ss[i-1] != ss[l+j])
                ans[i][j] = (ans[i][j] - ans[i-1][j-1] + mod)%mod;
        }
    return ans[n1][n2];
}
void solve() {
    res = 0;
    n = strlen(ss);
    for(int i=1; i<n; ++i)
        res = (res + work(i))%mod;
    printf("%d\n", res);
}
int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        scanf("%s", ss);
        solve();
    }
}

Problem E. 牌墙的深坑

将矩阵周边的格子都放到堆里，这些格子上面是无法盛水的。

每次在堆里挑出一个高度最小的格子 cell，把周围的格子加入到堆里。

这些格子被加入堆的时候，计算他们上面的盛水量。

盛水量 = cell.height - 这个格子的高度

当然如果这个值是负数，盛水量就等于 0。

堆我们可以使用优先队列进行实现。

#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};
int h[MAXN][MAXN];
int vis[MAXN][MAXN];
int n, m;

struct node{
    int x, y;
    int height;
    node(){}
    node( int x, int y, int height): x(x), y(y), height(height) {}
};
struct cmp{
    bool operator()( node a, node b ){
        return a.height > b.height;
    }
};
priority_queue<node, vector<node>, cmp> q;
void solve()
{
    for(int i = 1; i <= n; i++ ){
        vis[i][1] = vis[i][m] = 1;
        q.push( node( i, 1, h[i][1]) );
        q.push( node( i, m, h[i][m]) );
    }
    for(int j = 2; j < m; j++ ){
        vis[1][j] = vis[n][j] = 1;
        q.push( node( 1, j, h[1][j]) );
        q.push( node( n, j, h[n][j]) );
    }
    ll ans = 0;
    while( !q.empty() ){
        node now = q.top();
        q.pop();
        int hh = now.height;
        for(int i = 0; i < 4; i++ ){
            int x = now.x+dx[i];
            int y = now.y+dy[i];
            if( x < 1 || x > n || y < 1 || y > m ) continue;
            if( vis[x][y] ) continue;
            vis[x][y] = 1;
            if( hh > h[x][y] ){
                ans += 1ll*(hh-h[x][y]);
                h[x][y] = hh;
            }
            q.push( node( x, y, h[x][y]) );
        }
    }
    printf("%lld\n", ans);
}
int main(int argc, char * argv[])
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++ ){
        for(int j = 1; j <= m; j++ ){
            scanf("%d", &h[i][j]);
        }
    }
    solve();
    return 0;
}

Problem F. 麻将大乱斗

如果$k$含有$2,3,5,7$之外的质因数，答案一定为$0$。

否则问题变成数位之积中恰好有若干个$2,3,5,7$质因子。

直接需要数位dp需要五维状态，如果处理不当，可能会MLE。

考虑到可能出现的乘积不会很多，使用map或unordered_map维护即可。

注意最后输出总积分数时不用取模！

bonus：如果这题改为$n \leq 10\,000$，应该怎么做？

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
int dp[105][66666];
ll k;
char A[105], B[105];
int a[105];
inline int get(ll x)
{
    static unordered_map<ll, int> dic;
    static int sz = 0;
    if (dic.count(x)) return dic[x];
    return dic[x] = sz++;
}
int dfs(int pos, ll mul, int lead, int flag)
{
    if (mul == 0) return 0;
    if (pos == -1) return mul == 1;
    int h = get(mul);
    if (!flag && !lead && ~dp[pos][h]) return dp[pos][h];
    int sum = 0;
    int up = flag ? a[pos] : 9;
    for (int i = 0; i <= up; i++)
    {
        if (i == 0 && !lead) continue;
        if (i == 0)
            sum += dfs(pos - 1, mul, lead && i == 0, flag && i == a[pos]);
        else if (mul % i == 0)
            sum += dfs(pos - 1, mul / i, lead && i == 0, flag && i == a[pos]);
        if (sum >= MOD) sum -= MOD;
    }
    if (!flag && !lead) dp[pos][h] = sum;
    return sum;
}
int solve(char* c)
{
    int len = strlen(c);
    int pos = 0;
    for (int i = 0; i < len; i++)
        a[pos++] = c[len - 1 - i] - '0';
    return dfs(pos - 1, k, 1, 1);
}
void _minus(char* c)
{
    int len = strlen(c);
    reverse(c, c + len);
    //    cout << c << endl;
    int flag = 1, len1 = 1;
    for (int i = 0; i < len; i++)
    {
        if (flag)
            if (c[i] == '0')
                c[i] = '9';
            else
                c[i]--, flag = 0;
        if (c[i] != '0') len1 = i + 1;
    }
    //    cout << "LEN: "<<len1 << endl;
    reverse(c, c + len1);
    c[len1] = '\0';
}
int fac[] = {2, 3, 5, 7};
int main()
{
    memset(dp, -1, sizeof(dp));
    int T;
    scanf("%d", &T);
    long long TT = 0;
    while (T--)
    {
        scanf("%s%s%lld", A, B, &k);
        ll K = k;
        for (int i = 0; i < 4; i++)
            while (K % fac[i] == 0) K /= fac[i];
        if (K != 1)
        {
            printf("0\n");
            continue;
        }
        _minus(A);
        int ans = solve(B) - solve(A);
        if (ans < 0) ans += MOD;
        printf("%d\n", ans);
        TT += ans;
    }
    cout << TT << endl;
}
Last modification：August 18th, 2019 at 01:26 pm
© The copyright belongs to the author
If you think my article is useful to you, please feel free to appreciate

Leave a Comment