Codeforces ラウンド #280 (ディビジョン 2)_html/css_WEB-ITnose

この質問は意外と簡単です

ABCはほぼサインインの質問です

Dの言葉

2人の撮影時間を整数に変換してください

gcdを取得して割ります。

二人の射撃頻度をそれぞれ1秒x、1秒yとする

xとyのgcdはg

換算すると

と同等

一人目の人は1秒間に1発撃つ y/g , そして、2人目は1秒間に1発撃つ y/g x/g秒で1発撃つ

その後、2人はx/g*y/g秒で同時に撃つことになります

その後、それぞれx/g*y /g 秒がサイクルです

モンスターの血液に があるとすると、a%(x+y) は最後のサイクルで撃たれる血液の量です

この時点では、考えるのが面倒なので、ただ割り算するだけです。誰かが二つに発砲した回数、それでOKです

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <cmath>#include <algorithm>#include <map>#define MAXN 55555#define MAXM 222222#define INF 1000000001using namespace std;int n, x, y, a;int main() {    scanf("%d%d%d", &n, &x, &y);    int g = __gcd(x, y);    x /= g;    y /= g;    for(int i = 0; i < n; i++) {        scanf("%d", &a);        a %= (x + y);        if(a == 0 || (a + 1) % (x + y) == 0) puts("Both");        else {            int flag = 0;            int low = 1, high = x;            while(low <= high) {                int mid = (low + high) >> 1;                long long tmp = (long long)mid * (long long)y;                long long z = tmp / (long long)x;                if(z + mid > a) {                    high = mid - 1;                } else if(z + mid == a) {                    flag = 1;                    break;                } else {                    low = mid + 1;                }            }            if(flag) {                puts("Vanya");            } else {                puts("Vova");            }        }    }    return 0;}

E

この質問は非常に良い制限を与えています

つまり、x方向またはy方向から、 0から歩き始めてn歩歩くと、0~n-1まですべて横断できるようになります

その後、0からx方向にn歩シミュレートしてx座標列を取得します

同様のことが言えますy 座標

2 つのシーケンス。それらはすべて周期的です

次に、特定の点 (x0, y0) から開始することを選択します

それは 2 つのシーケンスをペアにするだけです。x シーケンスは x0 から始まり、y シーケンスは y0 から始まり、それぞれに n がかかりますどの点が質問の要件を満たすか確認する手順

もう一度見てみると、それは 2 つのシーケンスの相対的な位置を調べているだけであることがわかりました。

与えられたすべての点について、2 つの対応するシーケンスの相対位置を計算し、最後にそれらを数えます

#include <iostream>#include <cstdio>#include <cstring>#include <queue>#include <cmath>#include <algorithm>#include <map>#define MAXN 55555#define MAXM 222222#define INF 1000000001using namespace std;int posx[1111111], posy[1111111];int n, m, dx, dy;int x[111111], y[111111];int num[1111111];int main() {    scanf("%d%d%d%d", &n, &m, &dx, &dy);    int now = 0;    int ind = 0;    while(posx[now] == 0) {        posx[now] = ++ind;        now = (now + dx) % n;    }    now = 0, ind = 0;    while(posy[now] == 0) {        posy[now] = ++ind;        now = (now + dy) % n;    }    int mx = 0, p = 0;    for(int i = 0; i < m; i++) {        scanf("%d%d", &x[i], &y[i]);        int px = posx[x[i]];        int py = posy[y[i]];        int t = (py - px + n) % n;        num[t]++;        if(num[t] > mx) {            mx = num[t];            p = t;        }    }    for(int i = 0; i < m; i++) {        int px = posx[x[i]];        int py = posy[y[i]];        int t = (py - px + n) % n;        if(t == p) {            printf("%d %d\n", x[i], y[i]);            break;        }    }    return 0;}