投稿
  1. 首页
  2. C

NewOJ Week 6题解

code • 2022-4-27 • C • 阅读 48

NewOJ Week 6题解,第1张

NewOJ周赛于2022年3月19日正式开始，比赛时间为每周六晚19:00-22:00。

比赛链接：http://oj.ecustacm.cn/contest.php?cid=1020

A 分数统计

题意： 在一场考试中，有 N N N位考生， K K K道题目。给定每道题目的分数，如果考生做出第 i i i题则得到 A i A_i Ai​分，否则得 0 0 0分，没有部分分。对于每一位考生，你知道他是否解答出了每道题，用 01 01 01字符串表示， 1 1 1表示解出， 0 0 0表示未解出。请求出每位考生的得分。

Tag： 模拟

难度： ☆

来源： C o d e C h e f   E a s y CodeChef\ Easy CodeChef Easy

思路： 直接根据题意模拟即可。注意答案需要用 l o n g   l o n g long\ long long long。

#include
using namespace std;
const int maxn = 1e5 + 10;
int score[maxn];
int main()
{
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < k; i++)
        cin >> score[i];
    while(n--)
    {
        string s;
        cin >> s;
        long long ans = 0;  //用long long
        for(int i = 0; i < k; i++)if(s[i] == '1')
            ans += score[i];
        cout<<ans<<endl;
    }
    return 0;
}
B 特殊数字

题意： 特殊数字定义： N = 2 x + 2 y , x ≠ y N=2^x+2^y,x\ne y N=2x+2y,x​=y。给定数字 x x x，每次可以加 1 1 1或者减 1 1 1，最少执行多少次 *** 作可以变成特殊数字。存在 T ≤ 10000 T\le 10000 T≤10000次询问。

Tag： 预处理、二分

难度： ☆☆

来源： C o d e C h e f   E a s y CodeChef\ Easy CodeChef Easy

思路： x x x是特殊数字相当于 x x x的二进制中仅包含 2 2 2个 1 1 1，这种数字十分特殊，在 1 0 9 10^9 109内,存在约为 30 ∗ 29 2 \frac{30*29}{2} 230∗29​个。因此最开始可以直接处理出所有的特殊数字，相当于两重循环枚举这两个 1 1 1的位置。

每次 *** 作加 1 1 1或者减 1 1 1，这说明整个变化中，要么全是加 1 1 1，要么全是减 1 1 1。因此两个都存在的话相当于没 *** 作。

在已经处理出特殊数字之后，对于数字 x x x要变成特殊数字，相当于找一下离哪个特殊数字最接近，直接使用二分查找即可。

#include
using namespace std;
int a[1010], tot;
int main()
{
    ///预先处理出所有特殊数字
    for(int i = 0; i <= 30; i++)
        for(int j = i + 1; j <= 30; j++)
            a[++tot] = (1 << i) + (1 << j);
    sort(a + 1, a + 1 + tot);
    int T;
    cin >> T;
    while(T--)
    {
        int n, ans;
        cin >> n;
        //对于每个输入，二分查找对应的数字
        int idx = lower_bound(a + 1, a + 1 + tot, n) - a;
        if(a[idx] == n)ans = 0;
        else
        {
            ans = a[idx] - n;
            if(idx - 1 > 0)ans = min(ans, n - a[idx - 1]);
        }
        cout<<ans<<endl;
    }
    return 0;
}
C 质数拼图游戏

题意： 拼图游戏由一个 3 × 3 3×3 3×3的棋盘和数字 1 − 9 1-9 1−9组成。目标是达到以下最终状态：

1 2 3
4 5 6
7 8 9

每次如果相邻两个数字之和为质数，则可以进行交换。 相邻：上下左右四联通。给定一个棋盘初始状态，求到达最终状态的最短步数。

Tag： B F S BFS BFS

难度： ☆☆☆

来源： C o d e C h e f   M i d CodeChef\ Mid CodeChef Mid

思路： 经典的八数码问题的变体。存在 T ≤ 50 T\le50 T≤50次询问。

由于题目的特殊性，只有相邻两个数字之后为质数才可以交换，这样可以猜想真正的合法解是不多的，同时存在 T T T组询问。

如果每次都是从当前状态去找终止状态，如果是一个非法解，那么 b f s bfs bfs需要遍历所有能到达的状态才能判断这是一个无解状态，这样时间代价过大。

但是由于终点都是一样的，我们可以反向从终点出发，在 b f s bfs bfs的过程中，一遍反向遍历所有状态，一遍记录答案。最终 T T T次询问直接输出答案即可。

而且可以快速判断出合法还是非法状态，只要 b f s bfs bfs过程中没有经过的状态，均为非法解。

#include
using namespace std;
bool ok[21] = {0,
        0,1,1,0,1,0,1,0,0,0,         //1-10
        1,0,1,0,0,0,1,0,1,0         //11-20
};

map<string, int>ans;
queue<string>q;
int dir[][2] = {1,0, 0,1};
void bfs(string s)
{
    q.push(s);
    ans[s] = 0;
    while(!q.empty())
    {
        string Now = q.front();
        q.pop();
        for(int i = 0; i <= 2; i++) for(int j = 0; j <= 2; j++)
        {
            ///(i,j) - (i,j+1)
            int first = i * 3 + j;
            for(int k = 0; k <= 1; k++)
            {
                int xx = i + dir[k][0];
                int yy = j + dir[k][1];
                if(xx == 3 || yy == 3)continue;
                int second = xx * 3 + yy;
                if(ok[Now[first]-'0' + Now[second]-'0'])
                {
                    string Next = Now;
                    swap(Next[first], Next[second]);
                    if(!ans.count(Next))
                    {
                        ans[Next] = ans[Now] + 1;
                        q.push(Next);
                    }
                }
            }
        }
    }
}

int main()
{
    string s = "123456789";
    bfs(s);
    int i = 0;
    int T;
    cin >> T;
    while(T--)
    {
        string now = "";
        for(int i = 1; i <= 3; i++)
            for(int j = 1; j <= 3; j++)
        {
            char c;
            cin >> c;
            now += c;
        }
        if(ans.count(now))
            cout<<ans[now]<<endl;
        else
            cout<<-1<<endl;
    }
    return 0;
}
D 推箱子

题意： 在一个高度为 H H H的箱子前方，有一个长和高为 N N N的障碍物。障碍物的每一列存在一个连续的缺口，第 i i i列的缺口从第 l l l各单位到第 h h h个单位（从底部由 0 0 0开始数）。现在请你清理出一条高度为 H H H的通道，使得箱子可以直接推出去。请输出最少需要清理的障碍物面积。

Tag： 差分、线段树、树状数组

难度： ☆☆☆

来源： C o d e C h e f   M i d CodeChef\ Mid CodeChef Mid

思路： 最简单的思想是暴力枚举每一个底部 l e f t left left，然后求出高度 [ l e f t , l e f t + H − 1 ] [left,left+H-1] [left,left+H−1]中存在多少个障碍物。

由于题目给的是缺口的位置，因此求高度为 [ l e f t , l e f t + H − 1 ] [left,left+H-1] [left,left+H−1]中存在的障碍物数量等于 N ∗ H − c n t N*H-cnt N∗H−cnt，其中 c n t cnt cnt为缺口的面积。

现在给出第 1 1 1列到第 N N N列的缺口底部 l i l_i li​和顶部 h i h_i hi​。相当于在数组 a a a上的区间 [ l i , h i ] [l_i,h_i] [li​,hi​]加上 1 1 1，其中 a [ i ] a[i] a[i]表示高度为 i i i存在的缺口面积。

题目转换成区间加法。可以使用线段树、树状数组来实现区间加法，最后枚举每一个高度，求区间和即可。

也可以用差分数组：原数组为 a a a，差分数组为 b b b，满足 a [ i ] = ∑ i = 0 i b [ i ] , a [ i ] − a [ i − 1 ] = b [ i ] a[i]=\sum_{i=0}^ib[i],a[i]-a[i-1]=b[i] a[i]=∑i=0i​b[i],a[i]−a[i−1]=b[i]。

在原数组 a a a的区间 [ l , r ] [l,r] [l,r]上加1，相当于差分数组 b [ l ] + + , b [ r + 1 ] − − b[l]++,b[r+1]-- b[l]++,b[r+1]−−。

最后求区间的时候，再对原数组 a a a求前缀和即可。

#include
using namespace std;
typedef long long ll;
const int INF = 1e9 + 7;
const int maxn = 1e6 + 10;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x = x * w;
}

ll sum[maxn];
int main()
{
    int n, h;
    read(n);read(h);
    for(int i = 0; i <= n + 1; i++)
        sum[i] = 0;
    for(int i = 1; i <= n; i++)
    {
        int l, r;
        read(l), read(r);
        sum[l]++;
        sum[r + 1]--;
    }
    //差分数组变成原数组
    for(int i = 1; i <= n; i++)
        sum[i] += sum[i - 1];
    //原数组变成前缀和数组
    for(int i = 1; i <= n; i++)
        sum[i] += sum[i - 1];
    ll ans = sum[h - 1];
    for(int left = 1; left + h - 1 <= n; left++)
    {
        ans = max(ans, sum[left + h - 1] - sum[left - 1]);
    }
    cout<<(ll)n * h - ans<<endl;
    return 0;
}
E 最小公倍数

题意： 给定一个数字 n n n，请问是否存在一个区间 [ l , r ] [l,r] [l,r]，使得 n n n等于整个区间所有数字的最小公倍数。

Tag： 预处理 数学

难度： ☆☆☆☆

来源： P O I   2019 POI\ 2019 POI 2019

思路： 区间长度等于 2 2 2的话，相当于判断 l ( l + 1 ) = = n l(l+1)==n l(l+1)==n。可以直接暴力求解。

区间长度大于等于 3 3 3，这说明 [ l , l + 1 , l + 2 , . . . ] [l,l+1,l+2,...] [l,l+1,l+2,...]，相邻 3 3 3个数字的最小公倍数存在两种情况：

  • l l l为奇数， l c m = l × ( l + 1 ) × ( l + 2 ) lcm=l\times (l+1)\times(l+2) lcm=l×(l+1)×(l+2)
  • l l l为偶数， l c m = l × ( l + 1 ) × ( l + 2 ) 2 lcm=\frac{l\times (l+1) \times(l+2)}{2} lcm=2l×(l+1)×(l+2)​

这相当于左端点上限为 2 × 1 0 6 2\times 10^6 2×106。

而区间长度越长，左端点上限越低。这种现象随着长度增加，左端点上限呈现指数级下降。因此可以直接暴力所有区间长度大于 3 3 3的情况即可。

只要保证区间的最小公倍数不超过 1 0 18 10^{18} 1018即可，不超过 1 0 18 10^{18} 1018的区间数量不会很多。

#include
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int maxn = 1e5 + 10;
template <typename T>
inline T read(T& x) {
  x = 0;
  T w = 1;
  char ch = 0;
  while (ch < '0' || ch > '9') {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + (ch - '0');
    ch = getchar();
  }
  return x = x * w;
}

//预处理所有情况，ans[n]表示n的答案。
map<ll, pair<int,int>>ans;
void init()
{
    for(ll left = 1; left <= 2000000; left++)
    {
        ll res = left * (left + 1);
        for(ll right = left + 2; ;right++)
        {
            ll g = __gcd(res, right);
            if(res / g > INF / right)
                break;
            res = res / g * right;
            if(!ans.count(res))
                ans[res] = make_pair(left, right);
        }
    }
}

int main()
{
    init();
    int T;
    read(T);
    while(T--)
    {
        ll n;
        read(n);
        //判断区间长度为2的情况
        ll sqrt_n = sqrt(n + 0.5);
        pair<int,int>res;
        if(sqrt_n * (sqrt_n + 1) == n)
        {
            res = make_pair(sqrt_n, sqrt_n + 1);
            if(ans.count(n))
            {
                if(res.first > ans[n].first)
                    res = ans[n];
            }
        }
        else if(ans.count(n))
            res = ans[n];
        else
        {
            puts("-1");
            continue;
        }
        printf("%d %d\n", res.first, res.second);
    }
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/735307.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-04-27
下一篇 2022-04-27

发表评论

登录后才能评论

评论列表（0条）

保存