Codeforces Round #179 (Div. 2)A、B、C、D

タイトルリンク
A.Yaroslav and Permutations
タイトル:
n個の要素の配列で、各要素は1000を超えず、隣接する2つの要素を交換することができ、限られた操作の後に隣接する2つの要素の値を異なるようにすることができるかどうかを尋ねることができる.

#include <stdio.h>
#include <string.h>
int cnt[1005];
int main()
{
    int n, a;
    while (scanf("%d", &n) != EOF)
    {
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; i++)
        {
            scanf("%d",&a);
            cnt[a]++;
        }
        int m = -1;
        for (int i = 0; i <= 1000;i++)
        {
            if (cnt[i] > m)
                m = cnt[i];
        }
        if (n%2 == 0)
        {
            if (m > (n/2))
                puts("NO");
            else
                puts("YES");
        }
        else
        {
            if (m > (n/2+1))
                puts("NO");
            else
                puts("YES");
        }
    }
    return 0;
}

B.Yaroslav and Two Strings(原文アドレス転載)
2つの文字列ch 1とch 2について、4つの配列a[i],b[i],c[i],d[i]がそれぞれすべてのケース数、ch 1[i]<=ch 2[i]のケース数、ch 1[i]>=ch 2[i]のケース数、ch 1[i]=ch 2[i]のケース数を表すと、反発原理によりans=∏a[i]-∏b[i]-∏c[i]+∏d[i]がある.
コード#コード#

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
template <class T> void checkmin(T &t,T x) {if(x < t) t = x;}
template <class T> void checkmax(T &t,T x) {if(x > t) t = x;}
template <class T> void _checkmin(T &t,T x) {if(t==-1) t = x; if(x < t) t = x;}
template <class T> void _checkmax(T &t,T x) {if(t==-1) t = x; if(x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
typedef long long ll;
#define foreach(it,v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end ; it ++)
#define MOD 1000000007
int n ;
ll a[101000] , b[101000] , c[101000] , d[101000];
char ch1[101000] , ch2[101000];

void gcd(ll a , ll b , ll &d , ll &x , ll &y) {
    if(!b) {d = a; x = 1; y = 0;}
    else { gcd(b , a%b,d,y , x); y -= x * (a/b); }
}
ll inv(ll a , ll n) {
    ll d , x , y;
    gcd(a , n , d,  x , y);
    return d == 1 ? (x+n)%n : -1;
}

void debug() {
    for(int i=0;i<n;i++) cout << a[i] << " ";
    cout << endl;
    for(int i=0;i<n;i++) cout << b[i] << " ";
    cout << endl;
    for(int i=0;i<n;i++) cout << c[i] << " ";
    cout << endl;
    for(int i=0;i<n;i++) cout << d[i] << " ";
    cout << endl;
}

int main() {
    cin >> n;
    scanf("%s%s",ch1,ch2);
    for(int i=0;i<n;i++) {
        if(ch1[i] == '?' && ch2[i] == '?') { a[i] = b[i] = 55;c[i] = 10; d[i] = 100; }
        else if(ch1[i] == '?') { a[i] = ch2[i] - '0'+1; b[i] = 11-a[i]; c[i] = 1; d[i] = 10; }
        else if(ch2[i] == '?') { b[i] = ch1[i] - '0'+1; a[i] = 11-b[i]; c[i] = 1; d[i] = 10; }
        else {
            if(ch1[i] <= ch2[i]) a[i] = 1;
            if(ch1[i] >= ch2[i]) b[i] = 1;
            if(ch1[i] == ch2[i]) c[i] = 1;
            d[i] = 1;
        }
    }
    ll a1 = 1 , a2 = 1 , a3 = 1 , a4 = 1;
        for(int i=0;i<n;i++) {
            a1 *= a[i]; a1 %= MOD;
            a2 *= b[i]; a2 %= MOD;
            a3 *= c[i]; a3 %= MOD;
            a4 *= d[i]; a4 %= MOD;
        }
        ll ans = (a4-a1-a2+a3) % MOD;
        if(ans < 0) ans += MOD;
        cout << ans << endl;
        //debug();
    return 0;
}

C.Greg and Array
タイトル:
1つの配列n個の数、そしてm群の操作、各群の操作はlからrまでの各要素値にvを加算し、次いでk群の操作であり、各群はx、x+1......y群の操作を実行し、配列要素を出力することを意味する.
考え方:
区間修正の問題については,間違いなく線分ツリーを用いるが,ここには2つの線分ツリーがあるが,ここでは配列に対してのみツリーを構築し,操作回数に対してツリーを構築せず,lazyの考え方で,その操作のセットが何回実行されたかをより簡単に知ることができ,その後線分ツリーを更新し,ちょうど更新されたval値はその操作の元のvに操作回数を乗じたものである.
コード:

#include <stdio.h>
#include <string.h>
typedef __int64 ll;
const ll maxn = 100005;
ll a[maxn];

struct node
{
    ll l, r, m;
    ll sum, mark;
}tree[maxn<<2];

ll cnt[maxn];

struct operation
{
    ll l, r, v;
}op[maxn];

void build(ll l, ll r, ll o)
{
    tree[o].l = l;
    tree[o].r = r;
    ll m = (l+r)>>1;
    tree[o].m = m;
    tree[o].mark = 0;
    if (l == r)
    {
        tree[o].sum = a[l];
        return;
    }
    build(l, m, o<<1);
    build(m+1, r, (o<<1)+1);
    tree[o].sum = tree[o<<1].sum + tree[(o<<1)+1].sum;
 }

 void update(ll l, ll r, ll v, ll o)
 {
     if (tree[o].l == l && tree[o].r == r)
     {
        tree[o].mark += v;
        return;
     }
     tree[o].sum += (ll)(r-l+1)*v;
     if (tree[o].m >= r)
        update(l, r, v, o<<1);
     else if (l > tree[o].m)
        update(l, r, v, (o<<1)+1);
     else
     {
         update(l, tree[o].m, v, o<<1);
         update(tree[o].m+1, r, v, (o<<1)+1);
     }
 }

ll query(ll l, ll r, ll o)
 {
     if (tree[o].l == l && tree[o].r == r)
        return tree[o].sum + tree[o].mark*(r-l+1);
     if (tree[o].mark != 0)
     {
         tree[o<<1].mark += tree[o].mark;
         tree[(o<<1)+1].mark += tree[o].mark;
         tree[o].sum += (ll)(tree[o].r -tree[o].l +1)*tree[o].mark;
         tree[o].mark = 0;
     }
     if (tree[o].m >= r)
        return query(l, r, o<<1);
     else if (tree[o].m <l)
        return query(l, r, (o<<1)+1);
     else
        return query(l, tree[o].m, o<<1) + query(tree[o].m+1, r, (o<<1)+1);
 }

int main()
{
    ll n, m, k, l, r, x;
    while (scanf("%I64d%I64d%I64d",&n,&m,&k) != EOF)
    {
        for(ll i = 1; i <= n; i++)
            scanf("%I64d",&a[i]);
        build(1, n, 1);
        for (ll i = 1; i <= m; i++)
            scanf("%I64d %I64d %I64d",&op[i].l, &op[i].r, &op[i].v);
        memset(cnt, 0, sizeof(cnt));
        for (ll i = 1; i <= k; i++)
        {
            scanf("%I64d %I64d",&l, &r);
            cnt[l] += 1;
            cnt[r+1] -= 1;
        }
        ll sum = 0;
        for (ll i = 1; i <= m; i++)
        {
            sum += cnt[i];                              //lazy   
            update(op[i].l, op[i].r, sum*op[i].v, 1);
        }
        for (ll i = 1; i < n; i++)
            printf("%I64d ",query(i, i, 1));
        printf("%I64d
",query(n, n, 1));
    }
    return 0;
}

D.Greg and Graph(原文転載)
この問題を話す前に、Floyd-Warshallアルゴリズムを簡単に紹介します.この問題をもっとよく理解するのに便利です.
Floyd-Warshallアルゴリズムの原理は動的計画である.
D[i][j][k]をiからjまで1~kのノードのみを中間ノードとする最短経路長とすると、
(1)最短経路が点kを通過すると、D[i][j][k]=D[i][k][k-1]+D[k][j][k-1]
(2)最短経路が点kを通らなければD[i][j][k]=D[i][j][k-1]
したがってD[i][j][k]=min(D[i][k][k-1]+D[k][j][k-1],D[i][j][k]=D[i][j][k-1]).
kを最外層のサイクルに置くと,3位は実装上省略できる.
この問題は逆に考えることができて、私たちは1つの点から1つずつ追加することを考えて、それでは答えは逆に出力すればいいです.
私たちが追加するたびに点はkに相当し、まずk点とすべての点との間の最短経路を見つける二重ループを行う必要があります.そしてkポイント判定ノードで更新する前のk-1ポイントで時間複雑度がO(n^3)に低下し、暴力解法は毎回floydを行い、時間複雑度がO(n^4)である.それに比べて前述の解法はfloydアルゴリズムの性質を考慮し,アルゴリズムの内質をよりよく運用した.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
template <class T> void checkmin(T &t,T x) {if(x < t) t = x;}
template <class T> void checkmax(T &t,T x) {if(x > t) t = x;}
template <class T> void _checkmin(T &t,T x) {if(t==-1) t = x; if(x < t) t = x;}
template <class T> void _checkmax(T &t,T x) {if(t==-1) t = x; if(x > t) t = x;}
typedef pair <int,int> PII;
typedef pair <double,double> PDD;
typedef long long ll;
#define foreach(it,v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end ; it ++)
int n ;
const int N = 555;
int g[N][N];
ll ans[N];
int a[N];
int main() {
    cin >> n;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++) cin >> g[i][j];
    for(int i=n;i>=1;i--) cin >> a[i];
    ans[1] = 0;
    for(int i=2;i<=n;i++) {
        int aa = a[i];
        ans[i] += ans[i-1];
        for(int j=1;j<i;j++)
            ans[i] += g[a[i]][a[j]] + g[a[j]][a[i]];
        for(int j=1;j<i;j++)
        for(int k=1;k<i;k++) {
            if(g[a[j]][a[i]] > g[a[j]][a[k]]+g[a[k]][a[i]]) {
                ans[i] -= g[a[j]][a[i]];
                ans[i] += g[a[j]][a[k]]+g[a[k]][a[i]];
                g[a[j]][a[i]] = g[a[j]][a[k]]+g[a[k]][a[i]];
            }
            if(g[a[i]][a[j]] > g[a[i]][a[k]] + g[a[k]][a[j]]) {
                ans[i] -= g[a[i]][a[j]];
                ans[i] += g[a[i]][a[k]] + g[a[k]][a[j]];
                g[a[i]][a[j]] = g[a[i]][a[k]] + g[a[k]][a[j]];
            }
        }
        for(int j=1;j<i;j++)
        for(int k=1;k<i;k++) {
            if(g[a[j]][a[k]] > g[a[j]][a[i]] + g[a[i]][a[k]]) {
                ans[i] -= g[a[j]][a[k]];
                ans[i] += g[a[j]][a[i]] + g[a[i]][a[k]];
                g[a[j]][a[k]] = g[a[j]][a[i]] + g[a[i]][a[k]];
            }
        }
    }
    cout << ans[n];
    for(int i=n-1;i>=1;i--) cout << " "<< ans[i];
    cout << endl;
    return 0;
}