Educational Codeforces Round 41 A B C D E

A. Tetris
に言及
ロシアのブロックは、何点取れるかを聞いた.
構想
つまり最小値を求める
Code

#include 
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
typedef long long LL;
#define maxn 1010
int cnt[maxn];
int main() {
    int n,m,x;
    scanf("%d%d", &n, &m);
    F(i, 0, m) {
        scanf("%d", &x);
        ++cnt[x];
    }
    int ans = m;
    F2(i ,1, n) ans = min(ans, cnt[i]);
    printf("%d
", ans);
    return 0;
}

B. Lecture Sleep
に言及
授業は全部で(n)秒、(t_i=1)では、明ちゃんが(i)秒目に居眠りをするときだけ、明ちゃんは(a_i)個の知識点を学ぶことができ、彼が(i)秒目に居眠りをしないときだけです.
今では明ちゃんに連続(k)秒居眠りをさせない魔法がありますが、一度しか使えないので、明ちゃんが学べる知識点の数を最大化するように要求されています.
構想
2つの接頭辞和を計算し、魔法を用いた開始時刻を列挙して接頭辞と(O(1))を用いて対応する収益を計算する.
時間複雑度:(O(n)).
//料理私は条件式の実力に穴をあけられて、その優先度がかなり低くて、算術演算より低くて、ビット演算より低くて、論理演算より低くて、括弧を括弧を括弧で括弧を括ることを覚えています.
Code

#include 
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 100010
using namespace std;
typedef long long LL;
LL a[maxn], pre[maxn], pre2[maxn];
int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    F2(i, 1, n) {
        scanf("%I64d", &a[i]);
        pre[i] = pre[i-1] + a[i];
    }
    F2(i, 1, n) {
        int t = 0;
        scanf("%d", &t);
        pre2[i] = pre2[i-1] + (t?a[i]:0);
    }
    LL ans = 0;
    F2(i, 1, n-k+1) {
        ans = max(ans, pre2[i-1]-pre2[0]+pre2[n]-pre2[i+k-1]+pre[i+k-1]-pre[i-1]);
    }
    printf("%I64d
", ans);
    return 0;
}

C. Chessboard
に言及
合法的な碁盤では、隣接する格子の色(黒、白)が異なります.
現在、1つの(2 ntimes 2 n)の碁盤が4つの(ntimes n)の碁盤に砕け、いくつかの格子の色が変化しています.
それをつなぎ合わせて、最小限の格子の色を修正して、合法的な碁盤を得ることを要求します.
構想
碁盤をつなぎ合わせると(4!=24)種類のスキームがあり、各スキームに対して1つの数を計算し、最後に最小値をとる.
合法的な碁盤は2種類しかなく,左上隅の格子によって一意に決定されることに気づいた.
したがって,各シナリオに対して数を計算するには,この2つの碁盤と比較して最小化する必要がある.
時間複雑度(O(48 n^2))
Code

#include 
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 110
#define maxm 210
using namespace std;
typedef long long LL;
char s[maxn];
int n;
bool b[maxm][maxm], st1[maxm][maxm], st2[maxm][maxm];
struct board {
    int c[maxn][maxn];
}a[4];
void concat(int x1,int x2,int x3,int x4) {
    F(i, 0, n) F(j, 0, n) b[i][j] = a[x1].c[i][j];
    F(i, n, n<<1) F(j,0,n) b[i][j] = a[x2].c[i-n][j];
    F(i, 0, n) F(j, n, n<<1) b[i][j] = a[x3].c[i][j-n];
    F(i, n, n<<1) F(j, n, n<<1) b[i][j] = a[x4].c[i-n][j-n];
    int m = n<<1;
}
void init() {
    int m=n<<1;
    F(i, 0, m) F(j, 0, m) st1[i][j] = (i+j)&1, st2[i][j] = !st1[i][j];
}
int work() {
    int m = n<<1, ret1=0, ret2=0;
    F(i, 0, m) F(j, 0, m) ret1 += st1[i][j]!=b[i][j];
    F(i, 0, m) F(j, 0, m) ret2 += st2[i][j]!=b[i][j];
    return min(ret1, ret2);
}
int main() {
    scanf("%d", &n);
    init();
    F(i, 0, 4) {
        F(j, 0, n) {
            scanf("%s", s);
            F(k, 0, n) a[i].c[j][k] = s[k]=='1'?1:0;
        }
    }
    int ans = n*n*4;
    F(x1,0,4) {
        F(x2,0,4) {
            if (x2==x1) continue;
            F(x3,0,4) {
                if (x3==x2||x3==x1) continue;
                F(x4,0,4) {
                    if (x4==x1||x4==x2||x4==x3) continue;
                    concat(x1,x2,x3,x4);
                    ans = min(ans, work());
                }
            }
        }
    }
    printf("%d
", ans);
    return 0;
}

D. Pair Of Lines
に言及
平面上のいくつかの点は、平面上のすべての点を通過するように2つの直線を描くことができるかどうかを尋ねます.
構想
点数(leq 3)の場合、明らかに可能です.
そうでなければ、最初の3つの点を取るには、必ず(1,2)共線または(1,3)共線または(2,3)共線(2,3が共線でなければ、少なくとも1つの点が1と共線)があり、この3つの場合(check)他の点が要求を満たすかどうか、いずれも満たさなければ(NO)である.
(check)の場合は共線のすべての点を捨て、残りのすべての点が共線であるかどうか.
共線はフォーク積で計算する.
Code

#include 
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 100010
using namespace std;
typedef long long LL;
struct Point {
    LL x, y;
    Point operator - (const Point& p) const { return {x-p.x, y-p.y}; }
}p[maxn];
int n;
inline bool cross(Point a, Point b) { return a.y*b.x==a.x*b.y; }
inline bool collinear(int x, int y, int z) { return cross(p[x]-p[y], p[x]-p[z]); }
bool ok(int x, int y) {
    vector v;
    F(i, 0, n) {
        if (!collinear(x,y,i)) v.push_back(i);
    }
    if (v.size()<=2) return true;
    x=v[0], y=v[1];
    for (auto i : v) {
        if (!collinear(x,y,i)) return false;
    }
    return true;
}
int main() {
    scanf("%d", &n);
    F(i, 0, n) scanf("%I64d%I64d", &p[i].x, &p[i].y);
    if (n<=4) puts("YES");
    else if (ok(0, 1)) puts("YES");
    else if (ok(0, 2)) puts("YES");
    else if (ok(1, 2)) puts("YES");
    else puts("NO");
    return 0;
}

E. Tufurama
に言及
一つのシーケンスを与えて、どれだけのペア(i,j)が(a[i]geq j,a[j]geq i)を満たすかを尋ねる.
構想
ある(i)に対してどれだけの(j)が条件を満たすかを考えると、まず、探す下付き範囲は(jin[1,a[i])であり、また満たす必要がある条件は(a[j]geq i)である.
下の範囲の条件は扱いやすいですが、2番目の条件はどうしますか?計算するたびに範囲内の点が2番目の条件を満たすといいでしょう.
だから、計算が終わるたびに条件を満たさないものを捨てればいいのです.(i)が増えているので、安心して大胆に投げることができます.
小さいときから大きいときまで、各(i)について、何個の下付き文字が([1,a[i])の範囲内にあるかを統計し、値が(i)のすべての下付き文字を捨て、計算するたびに2番目の条件を満たす下付き文字を統計します.
//実はよくあるアイデアです….//ひっくり返すと簡単にhdu 3887が見つかりました....
(vector[x])で値が(x)のすべての下付き文字を記録し、下付き文字の個数をツリー配列で維持します.
注意最后に多算の部分を除いて、一部は自分と、もう一部はその関系が等価な関系なので2回计算します.
Code

#include 
#define F(i, a, b) for (int i = (a); i < (b); ++i)
#define F2(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i > (b); --i)
#define dF2(i, a, b) for (int i = (a); i >= (b); --i)
#define maxn 200010
using namespace std;
typedef long long LL;
int c[maxn], a[maxn], n;
vector v[maxn];
inline int lowbit(int x) { return x & (-x); }
inline void add(int x, int d) { while (x<=n) c[x]+=d, x+=lowbit(x); }
inline LL query(int x) { LL ret=0; while (x) ret+=c[x], x-=lowbit(x); return ret; }
int main() {
    scanf("%d", &n);
    F2(i, 1, n) {
        scanf("%d", &a[i]);
        if (a[i]<=n) v[a[i]].push_back(i);
        add(i, 1);
    }
    LL ans = 0;
    F2(i, 1, n) {
        ans += query(min(a[i], n));
        for (auto x : v[i]) add(x, -1);
    }
    F2(i, 1, n) if (a[i]>=i) --ans;
    printf("%I64d
", ans>>1);
    return 0;
}

転載先:https://www.cnblogs.com/kkkkahlua/p/8724918.html