xindoo is
always here

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


题目链接

A.Yaroslav and Permutations

题意:

   n个元素的数组,每个元素不超过1000,可以交换相邻两个元素,问是否可以在有限次的操作之后使得相邻两个元素的值不相同。

#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(转载 原文地址

对于两个字符串ch1和ch2,开四个数组a[i],b[i],c[i],d[i]分别表示 所有的情况数 、ch1[i]<=ch2[i]的情况数、ch1[i]>=ch2[i]的情况数、ch1[i]==ch2[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

题意:

       一个数组n个数,然后又m组操作,每组操作是将从l到r 的每个元素值加v,然后是k组操作,每组的意思是执行第x、x+1……y组操作,然后输出数组元素。

思路:

      对于区间修改的问题,毫无疑问是用线段树,但这里有两个线段树,不过我们在这里只对数组建树,不对操作次数建树,用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\n",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放在最外层的循环,那么第三位在实现上可以省去。

这道题可以反着思考,我们考虑从一个点开始一个个添加,那么答案倒着输出就行了。

我们每次加进来的点相当于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;
}


打赏
未经允许不得转载:XINDOO » Codeforces Round #179 (Div. 2)A、B、C、D
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏