AcWing 第69场周赛
本文最后更新于 509 天前,其中的信息可能已经有所发展或是发生改变。

4615. 相遇问题


原题链接

题目大意

  • 求一维数轴上 $x$ 和 $y$ 分别以速度 $a,b$ 相向而行时,相遇所需时间是否为整数。

思想

  • 签到题。
  • 输出判断 $a + b$ 是否可以整除 $y - x$ 即可。

代码

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

typedef long long LL;

void sovle(){

    LL x, y, a, b; cin >> x >> y >> a >> b;
    if((y - x) % (a + b) == 0) cout << (y - x) / (a + b) << endl;
    else cout << - 1 << endl;

}

int main(){

    int _ = 1; cin >> _;

    while(_ --) sovle();

    return 0;

}

4616. 击中战舰


原题链接

题目大意

  • 存在长度为 $n$ 的格子,共 $a$ 个船,每个船占据连续的 $b$ 个格子。
  • 给定一个只包含 $0,1$ 的字符串 $S$,包含 $k$ 个 $1$,表示该格子受到打击,保证初始的打击不会击中船。
  • 求最少再打击几个格子可以保证下一次打击绝对命中船。
  • 输出任意方案即可。

思想

  • 思维题。
  • 由于船的位置不确定,那么对于每个包含连续的 $b$ 个格子的区间一定可以放下一条船。
  • 则我们最终打击的对象在于这些区间中的任意一个格子,因此我们记录所有的这些连续的 $b$ 个格子中任意一个格子的坐标。
  • 最后,由于无效打击的次数最少,假设所有可打击的区间数量为 $x$,则最少打击 $x - a + 1$ 次后,下一次的打击区间必定命中船。

代码

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

const int N = 1e6 + 10;

int num[N];

int idx;

void solve(){

    int n, a, b, k;
    cin >> n >> a >> b >> k;
    string s; cin >> s;
    int cnt = 0;
    for(int i = 0; i < s.size(); i ++){
        if(s[i] == '0'){
            cnt ++;
            if(cnt == b){
                num[idx ++] = i + 1;
                cnt = 0;
            }
        }
        else cnt = 0;
    }

    cout << idx - a + 1 << endl;
    for(int i = 0; i < idx - a + 1; i ++) cout << num[i] << ' ';

    return ;

}

int main(){

    solve();

    return 0;

}

4617. 解方程

原题链接

题目大意

  • 给定一个非负整数 $a$,请你计算方程 $a−(a \oplus x)−x= 0$ 的非负整数解的数量。

思想

  • 数学思维题。
  • 化简该方程为: $a - x = a \oplus x$。
  • 当 $a$ 二进制上的某一位是 $1$ 时:
    • $1-0= 1,1\oplus0=1,1-1=0,1 \oplus1 = 0$
    • 故此时 $a$ 与 $x$ 无论是做减法还是异或运算,结果都相同。
  • 当 $a$ 二进制上的某一位是 $0$ 时:
    • $0 - 0 = 0,0\oplus 0 = 0$
    • 故此时只有 $x$ 的二进制位也是 $0$ 才可使得等式成立。
  • 综上,设 $a$ 的二进制位上共有 $m$ 个位的值为 $1$ ,则 $x$ 的可选方案数为 $2^m$ 种。

代码

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

typedef long long LL;

void solve(){

    LL n; cin >> n;
    int cnt = 0;
    while(n){
        cnt += n & 1;
        n >>= 1;
    }

    cout << (1 << cnt) << endl;

}

int main(){

    int _ = 1; cin >> _;

    while(_ --) solve();

    return 0;

}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇