DQS DQS

HIT Summer Training Day4 分治

in 算法,模拟赛read (189) 文章转载请注明来源!

如果我不弃赛,而是用最后一个半小时调出来D,就能rank1了…

我发现D只差一句代码就能A了…计算了儿子的答案忘了加上父亲的了…………


A : poj - 1002

注意无解要输出那个东西。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int SZ = 10000010;
const int mp[] = {2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,0,7,7,8,8,8,9,9,9,0};

bool isnum(char x) { return x >= '0' && x <= '9'; }
bool isalp(char x) { return x >= 'A' && x <= 'Z'; }

int read()
{
    char a = getchar();
    int ans = 0,t = 0;
    while(233)
    {
        if(t == 7) break;
        if(isnum(a)) ans = ans * 10 + a - '0',t ++;
        if(isalp(a)) ans = ans * 10 + mp[a - 'A'],t ++;
        a = getchar();
    }
    return ans;
}

int t[SZ];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
    {
        int x = read();
        t[x] ++;
    }
    bool flag = 0;
    for(int i = 0;i <= 9999999;i ++)
        if(t[i] > 1)
            printf("%03d-%04d %d\n",i / 10000,i % 10000,t[i]),flag = 1;
    if(!flag)
        puts("No duplicates.");
    return 0;
}


B : poj - 3641

给定a和p,问是否满足p不是质数且满足$a^p = a(mod p)$。

写个快速幂和判断素数就行了。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;

typedef long long LL;
const int SZ = 10000010;

int a,p;

bool check(int x)
{
    if(x <= 1) return false;
    int d = sqrt(x);
    for(int i = 2;i <= d;i ++)
        if(x % i == 0)
            return false;
    return true;
}

int ksm(int a,int b)
{
    int ans = 1;
    while(b)
    {
        if(b & 1) ans = (LL)ans * a % p;
        a = (LL)a * a % p;
        b >>= 1;
    }
    return ans;
}


int main()
{
    while(~scanf("%d%d",&p,&a) && p)
    {
        if(!check(p) && ksm(a,p) == a) puts("yes");
        else puts("no");
    }
    return 0;
}
// 1000000007 1000000000


C : poj - 3070

矩阵快速幂求fib第n项…

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int SZ = 1000010;
const int INF = 1000000010;
const int mod = 10000;

struct matrix
{
    int n,m;
    int mp[5][5];
    matrix() { n = m = 0,memset(mp,0,sizeof(mp)); }
}a,f;

matrix operator *(const matrix &a,const matrix &b)
{
    matrix ans;
    ans.n = a.n,ans.m = b.m;
    for(int i = 1;i <= a.n;i ++)
        for(int j = 1;j <= b.m;j ++)
            for(int k = 1;k <= a.m;k ++)
                ans.mp[i][j] = (ans.mp[i][j] + a.mp[i][k] * b.mp[k][j] % mod) % mod;
    return ans;
}

matrix ksm(matrix a,int b)
{
    matrix ans;
    ans.n = a.n,ans.m = a.m;
    for(int i = 1;i <= a.n;i ++)
        ans.mp[i][i] = 1;
    while(b)
    {
        if(b & 1) ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

void init()
{
    a.n = 1,a.m = 2;
    a.mp[1][1] = 0,a.mp[1][2] = 1;

    f.n = f.m = 2;
    f.mp[1][1] = 0,f.mp[1][2] = 1;
    f.mp[2][1] = 1,f.mp[2][2] = 1;
}

int main()
{
    int n;
    while(~scanf("%d",&n) && ~n)
    {
        init();
        if(n <= 1) {printf("%d\n",n); continue;}
        a = a * ksm(f,n - 1);
        printf("%d\n",a.mp[1][2]);
    }
    return 0;
}


D : codeforces - 448C

给n个木板,每个高度为$a_i$,一个刷子的宽度为1,长度任意,同一块区域可以刷多次。

问最少刷几次可以将所有的木板全部刷上颜色。

注意这个题可以竖着刷。

考虑对于一块矩形区域,最少次数为min{w,h}。而若是进行w次竖着刷的操作,必然会一下刷到底。

于是对于一个区间[l,r]的答案,为$min{len,\sum son + h}$。

其中len是区间长度,h是$min{a_i}$,相当于把它底部抠出来一个矩形。然后递归剩下的计算答案。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int SZ = 1000010;
const int INF = 1000000010;

int ans = 0,a[SZ];

int dfs(int l,int r)
{
    if(l > r) return 0;
    if(l == r)  return 1;
    int minn = INF;
    for(int i = l;i <= r;i ++)
        minn = min(minn,a[i]);
    for(int i = l;i <= r;i ++)
        a[i] -= minn;
    int len = r - l + 1,tmp = 0;
    int s = l;
    for(int i = l;i <= r;i ++)
    {
        if(a[i] == 0)
            tmp += dfs(s,i - 1),s = i + 1;
    }
    tmp += dfs(s,r);
    tmp += minn;
//    cout << l << " " << r << " " << min(tmp,len) <<endl;
    return min(tmp,len);
}

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        scanf("%d",&a[i]);
    int ans = dfs(1,n);
    printf("%d\n",ans);
    return 0;
}


E : hoj - 3205

2*n个人,m轮比赛,每个人有一个score和ability。每轮按score排序,然后2*k和2*k+1的两个人比赛,赢了的人score+1,输了的不变。ability大的人一定胜利。问m轮比赛后score排名第k大的是谁。

每轮后sort会T,这里需要改成O(n)的。

具体怎么做我忘了233

这题没数据。不过好像是NOIP原题?!


F : hoj - 2558

最大权子矩阵,暴力就能过……

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

const int SZ = 110;
const int INF = 1000000010;
const int mod = 10000;

int a[SZ][SZ],sum[SZ][SZ];

int main()
{
    int n;
    scanf("%d",&n);
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
            scanf("%d",&a[i][j]);
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j];
    int ans = -INF;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= n;j ++)
            for(int a = i;a <= n;a ++)
                for(int b = j;b <= n;b ++)
                    ans = max(ans,sum[a][b] - sum[i - 1][b] - sum[a][j - 1] + sum[i - 1][j - 1]);
    printf("%d\n",ans);

    return 0;
}


G : codeforces - 768b

给一个序列,一开始只包含一个数n,一次操作是将序列中每个数$x$替换成$\lfloor \frac{x}{2} \rfloor,x mod 2,\lfloor \frac{x}{2} \rfloor$。若干次操作后形成一个只含有0和1的序列,问这个序列的[l,r]区间和是多少。$n<=2^{50}$

容易发现最终序列中元素值之和就是n,并且每次操作后左右两个区间是相同的。可以计算出最终区间长度,然后像线段树那样递归下去,若区间被全部包含则累加答案。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long LL;
const int SZ = 110;
const int INF = 1000000010;
const int mod = 10000;

LL n,l,r;

LL dfs(LL now,LL s,LL t)
{
    if(s > t) return 0;
    if(l <= s && t <= r) return now;
    LL mid = s + t >> 1;
    LL ans = 0;
    if(l <= mid && mid <= r) ans = now % 2;
    if(l <= mid) ans += dfs(now / 2,s,mid - 1);
    if(mid < r) ans += dfs(now / 2,mid + 1,t);
    return ans;
}

LL get_sz(LL x)
{
    if(x <= 1) return 1;
    LL ans = get_sz(x / 2);
    return ans * 2 + 1;
}

int main()
{
    scanf("%I64d%I64d%I64d",&n,&l,&r);
    LL len = get_sz(n);
    LL ans = dfs(n,1,len);
    printf("%I64d",ans);
    return 0;
}

H : poj - 2299

求逆序对。归并排序。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;
const int mod = 10000;

LL ans = 0;
int a[SZ],tmp[SZ],n;

void mergesort(int l,int r)
{
    if(l == r) return ;
    int mid = l + r >> 1;
    mergesort(l,mid); mergesort(mid + 1,r);
    int i = l,j = mid + 1,p = l;
    while(i <= mid && j <= r)
    {
        if(a[i] > a[j]) ans += mid - i + 1,tmp[p ++] = a[j ++];
        else tmp[p ++] = a[i ++];
    }
    while(i <= mid) tmp[p ++] = a[i ++];
    while(j <= r) tmp[p ++] = a[j ++];
    for(int i = l;i <= r;i ++)
        a[i] = tmp[i];
}

int main()
{
    while(~scanf("%d",&n) && n)
    {
        ans = 0;
        for(int i = 1;i <= n;i ++)
            scanf("%d",&a[i]);
        mergesort(1,n);
        //for(int i = 1;i <= n;i ++)    printf("%d ",a[i]);
        printf("%lld\n",ans);
    }
    return 0;
}
/*
100
41 18467 6334 26500 19169 15724 11478 29358 26962 24464 5705 28145 23281 16827 9961 491 2995 11942 4827 5436 32391 14604 3902 153 292 12382 17421 18716 19718 19895 5447 21726 14771 11538 1869 19912 25667 26299 17035 9894 28703 23811 31322 30333 17673 4664 15141 7711 28253 6868 25547 27644 32662 32757 20037 12859 8723 9741 27529 778 12316 3035 22190 1842 288 30106 9040 8942 19264 22648 27446 23805 15890 6729 24370 15350 15006 31101 24393 3548 19629 12623 24084 19954 18756 11840 4966 7376 13931 26308 16944 32439 24626 11323 5537 21538 16118 2082 22929 16541
*/


I : hoj - 2275

问满足$a_i<a_j>a_k,i<j<k$的三元组个数。

计算f1[i]为i左边比a[i]小的数的个数,f2[i]为i右边比a[i]小的个数,乘法原理。

可以用树状数组计算。

也可以在归并排序上魔改,和逆序对的思路差不多。

这个题多组数据

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1000000010;
const int mod = 10000;

int a[SZ];

int bit[SZ],f1[SZ],f2[SZ],n;

void insert(int x,int d)
{
    for(int i = x;i <= 50000;i += i & -i)
        bit[i] += d;
}

int ask(int x)
{
    int ans = 0;
    while(x > 0)
    {
        ans += bit[x]; x -= x & -x;
    }
    return ans;
}

int main()
{
    while(~scanf("%d",&n))
    {
        for(int i = 1;i <= n;i ++)
            scanf("%d",&a[i]),a[i] += 2;
        memset(bit,0,sizeof(bit));
        for(int i = 1;i <= n;i ++)
            f1[i] = ask(a[i] - 1),insert(a[i],1);
        memset(bit,0,sizeof(bit));
        for(int i = n;i >= 1;i --)
            f2[i] = ask(a[i] - 1),insert(a[i],1);
        LL ans = 0;
        for(int i = 1;i <= n;i ++)
            ans += (LL)f1[i] * f2[i];
        printf("%lld\n",ans);
    }
    return 0;
}


J : codeforces - 744b

交互题…

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

扫描二维码,在手机上阅读!

算法模拟赛
最后由DQS修改于2017-08-06 02:39
发表新评论
博客已萌萌哒运行
© 2018 由 Typecho 强力驱动.Theme by Yodu
前篇 后篇
雷姆
拉姆