DQS DQS

HIT Summer Training Contest1

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

又考炸,非常崩溃……感觉没过的题太多就很虚,然后都想开,然后就都做不出来,非常尴尬。


A : codeforces - 831D

给n个人,m个钥匙,n个人和m个钥匙在坐标轴上。指定终点,要求每个人需要拿到一个钥匙然后去终点,一个钥匙只能给一个人拿,一个人只能拿一个钥匙。求所有方案中走路最长的那个人最短走多少。$n<=1000,m<=2000$

算法一:

显然我们发现排序后人拿钥匙的关系是不能交叉的,所以可以dp[i][j]表示前i个人拿前j个钥匙的答案,转移即可。复杂度$O(n*m)$。

算法二:

二分答案,然后每个人可拿的钥匙是一个连续区间,贪心让每个人选这个区间最前面的钥匙即可。复杂度$O(nmlog INF)$。

算法三:

贪心。仔细思考发现:两个相邻的人拿的钥匙一定相邻。若两个人在三个钥匙中选了第一个和第三个,若两个人在三个钥匙同侧,那么靠近钥匙的那个人选择第二个钥匙不会使答案变差。若两个人在三把钥匙之间,不管终点在哪边,一定选中间的钥匙不会使答案变差。

于是发现n个人选的钥匙是连续的n个区间,所以可以直接暴力枚举区间。复杂度$O(n*m)$。

算法四:二分答案后用网络流跑二分图匹配,复杂度O((n+m)\sqrt{n+m}logINF)

贪心代码:

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

typedef long long LL;
const int SZ = 2000010;
const int INF = 2000000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int f[3010][3010],a[3010],b[3010],n,m,e;

int main()
{
    scanf("%d%d%d",&n,&m,&e);
    for(int i = 1;i <= n;i ++) scanf("%d",&a[i]);
    for(int i = 1;i <= m;i ++) scanf("%d",&b[i]);
    sort(a + 1,a + 1 + n),sort(b + 1,b + 1 + m);
    int ans = INF;
    for(int i = 1;i <= m - n + 1;i ++)
    {
        int tmp = -INF;
        for(int j = 1;j <= n;j ++)
            tmp = max(tmp,abs(a[j] - b[i + j - 1]) + abs(e - b[i + j - 1]));
        ans = min(ans,tmp);
    }
    printf("%d\n",ans);
    return 0;
}


B : hdu - 5694

可以用前缀和简化问题:ans=sum[r]-sum[l - 1]。于是答案变成求前x个字符中B的个数。

发现性质:S(n)的字符串长度为$2^n-1$,B的个数为$2^{n-1}$。

发现对于一个S(n)的长度为x的后缀中D的个数等于长度为x的前缀中B的个数。

于是发现,若S(k)是第一个长度大于x的串,那么

$$ans=Bnum(str(1,2^k-1))-Bnum(str(x+1,2^k-1))$$

其中str(l,r)表示l到r的字符串,Bnum(s)表示字符串s中B的数目。

然后发现对于前面一项,答案是$2^{k-1}$,对于后一项,等于长度为$2^k-1-x$的前缀中D的个数,即为$2^k-1-x-Bnum(1,2^k-1-x)$,这便成为了一个子问题。

容易发现每次区间长度都减少一半,所以复杂度是$O(logn)$的

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

typedef long long LL;
const int SZ = 200010;
const int INF = 1000000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};


LL dfs(LL x)
{
    if(x == 0) return 0;
    LL r;
    for(LL i = 0;;i ++)
        if((1ll << i) > x)
            { r = 1ll << i; break; }
    LL nB = r >> 1,len = r - x - 1;
    return nB - (len - dfs(len));
}


int main()
{
    int T;
    scanf("%d",&T);
    while(T --)
    {
        LL L,R;
        scanf("%lld%lld",&L,&R);
        printf("%lld\n",dfs(R) - dfs(L - 1));
    }
    return 0;
}


C : hdu - 1231

求最大子段和,输出答案区间两段元素。

我用单调队列扫过来的……讲题的时候才发现可以$f[i]=max(f[i-1],f[i-1]+a[i])$直接转移,傻逼了…

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

const int SZ = 200010;
const int INF = 1000000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

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

deque<int> q;

int main()
{
    while(~scanf("%d",&n) && n)
    {
        memset(sum,0,sizeof(sum));
        for(int i = 1;i <= n;i ++)
            scanf("%d",&a[i]),sum[i] = sum[i - 1] + a[i];
        q.clear();
        int ans = -1,L = a[1],R = a[n];
        for(int i = 1;i <= n + 1;i ++)
        {
            int x = i - 1;
            while(q.size() && sum[q.front()] > sum[x])
                q.pop_front();
            q.push_front(x);
            int d = sum[q.front()] - sum[q.back()];
    //        cout << d << " " << q.back() + 1 << " " << q.front() << endl;
            if(d > ans && q.back() + 1 <= q.front())
            {
                ans = d,R = a[q.front()],L = a[q.back() + 1];
            }
        }
        printf("%d %d %d\n",max(ans,0),L,R);
    }
    return 0;
}


D : hdu - 1603

给最多五个积木,问能否全部用上、不能翻转折叠的情况下拼成一个4*4的正方形,输出答案。

直接暴力搜,没了……写起来竟然挺好写的。

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

typedef long long LL;
const int SZ = 30;
const int INF = 1000000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int n;

int blk[SZ][SZ][SZ];
int bn[SZ],bm[SZ],mp[SZ][SZ];


bool check()
{
    for(int i = 1;i <= 4;i ++)
        for(int j = 1;j <= 4;j ++)
            if(!mp[i][j]) return false;
    return true;
}

bool can(int x,int y,int id)
{
    if(x + bn[id] - 1 > 4) return false;
    if(y + bm[id] - 1 > 4) return false;
    for(int i = x;i <= x + bn[id] - 1;i ++)
        for(int j = y;j <= y + bm[id] - 1;j ++)
            if(blk[id][i - x + 1][j - y + 1] && mp[i][j])
                return false;
    return true;
}

void fil(int x,int y,int id,int c)
{
    for(int i = x;i <= x + bn[id] - 1;i ++)
        for(int j = y;j <= y + bm[id] - 1;j ++)
            if(blk[id][i - x + 1][j - y + 1])
                mp[i][j] = c;
}

bool dfs(int x)
{
    if(x == n + 1)
    {
        if(check()) return true;
        return false;
    }
    for(int i = 1;i <= 4;i ++)
        for(int j = 1;j <= 4;j ++)
        {
            if(can(i,j,x))
            {
                fil(i,j,x,x);
                if(dfs(x + 1)) return true;
                fil(i,j,x,0);
            }
        }
    return false;
}


char str[SZ];
int main()
{
    while(~scanf("%d",&n))
    {
        memset(mp,0,sizeof(mp));
        int t = 0;
        for(int i = 1;i <= n;i ++)
        {
            scanf("%d%d",&bn[i],&bm[i]); getchar();
            for(int j = 1;j <= bn[i];j ++)
            {
                scanf("%s",str + 1);
                for(int k = 1;k <= bm[i];k ++)
                    blk[i][j][k] = str[k] - '0',t += blk[i][j][k];
            }
        }
        if(t == 16 && dfs(1))
        {
            for(int i = 1;i <= 4;i ++,puts(""))
                for(int j = 1;j <= 4;j ++)
                    printf("%d",mp[i][j]);
        }
        else
            puts("No solution possible");
        puts("");
    }
    return 0;
}


E : codeforces - 460C

给一个长度为n的序列,一次操作为给一个长度为w的区间元素加1,问至多m次操作后最小元素最大是多少。

显然二分答案。验证时,若一个值小于二分的答案,那么就以这个值为左端点操作$mid-a_i$次。

操作可以用前缀和的思想:sum[i]+=d,sum[i+w]-=d

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

typedef long long LL;
const int SZ = 200010;
const LL INF = 1000000000000000010ll;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int n,w,m;
LL a[SZ],tmp[SZ];

LL check(int mid)
{
    memset(tmp,0,sizeof(tmp));
    LL ans = 0,d = 0;
    for(int i = 1;i <= n;i ++)
    {
        d += tmp[i];
        if(a[i] + d < mid)
        {
            ans += mid - a[i] - d;
            tmp[i + w] -= mid - a[i] - d;
            d += mid - a[i] - d;
        }
    }
//    int j = 1;
//    for(int i = 1;i <= n;i ++)

//    cout << ans << endl;
    return ans;
}

LL div()
{
    LL l = -1,r = 20000000000010;
    while(r - l > 1)
    {
        int mid = l + r >> 1;
        if(check(mid) > m) r = mid;
        else l = mid;
    }
    return l;
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&w))
    {
        for(int i = 1;i <= n;i ++)
            scanf("%d",&a[i]);
    //    check(500);
        printf("%I64d\n",div());
    }
    return 0;
}


F : codeforces - 468B

给你n个数,还有a、b两个数,要求把n个数划分到两个集合AB,需要满足

1.若x在A集合,那么a-x必须也在A集合。

2.若x在B集合,那么b-x必须也在B集合。

第一眼看sb题啊,直接贪心不就行了……

其实是错的,比如a=7,b=10,划分2 5 8.若2 5划到B,那么8就没有集合可以放了。

算法一:

并查集的思想。对于一个数x,考虑a-x与b-x是否存在:

1.若均不存在,那么x无法划分,为NO

2.若存在一个,那么就划分到对应区间

3.若均存在,就需要考虑如何划分

接下来讨论均存在的情况。这时我们不知道x应该放到哪个集合,于是考虑寻找一个y使得a-y=b-x或者b-y=a-x成立。

我们发现这两种情况的y至少有一种不存在。若两种都存在,那么两式相减,得到a-b=b-a,即a=b,答案便很容易求。所以a!=b时,就只存在y满足一个式子或者都不满足。因为b-x和a-x都存在序列中,那么在处理b-x和a-x时,一定有一个会有情况2出现。

这时可以想到:如果b-x不存在,那么x就划分到A集合;如果a-x不存在,那么x就划分到B集合。

可以用并查集实现。

或者可以这么想:

对于每一对x与a-x、x与b-x。

发现如果x属于A,那么a-x也属于A。如果x属于B,那么a-x一定不能属于A,所以a-x属于B。

即x与a-x必须在一个集合,x与b-x必须在一个集合。

如果a-x不存在,x在B。如果b-x不存在,x在A。

并查集维护。

算法二:

对于a!=x,可以把x向a-x,b-x分别连边。每个点的度数一定小于等于2。

可以发现只会形成链。不存在环。

对于链,如果链的端点有自环那么可行,如果链的长度是奇数并且端点没有自环那么为NO。

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

const int SZ = 200010;
const int INF = 1000000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

int n,a,b,fa[SZ],num[SZ];
map<int,int> mp;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

int Union(int a,int b)
{
    int x = find(a),y = find(b);
    if(x != y) fa[x] = y;
}

int main()
{
    while(~scanf("%d%d%d",&n,&a,&b))
    {
        mp.clear();
        for(int i = 1;i <= n;i ++)
            scanf("%d",&num[i]),mp[num[i]] = i,fa[i] = i;
        fa[0] = 0,fa[n + 1] = n + 1;
        for(int i = 1;i <= n;i ++)
        {
            int x = num[i];
            if(mp[a - x]) Union(i,mp[a - x]);
            else Union(i,n + 1);
            if(mp[b - x]) Union(i,mp[b - x]);
            else Union(i,0);
        }
        int A = find(0),B = find(n + 1);
        if(A != B)
        {
            puts("YES");
            for(int i = 1;i <= n;i ++)
                if(find(i) == A)  printf("0 ");
                else printf("1 ");
            puts("");
        }
        else puts("NO");
    }
    return 0;
}


G : hdu - 4528

对于两个人为中心以十字型拓展,然后从起点bfs。答案是$min(ans[x][y][1][1])$。

就是加两维状态表示这个人有没有被看见。

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

const int SZ = 210;
const int INF = 1000000010;
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

char mp[SZ][SZ];
int zb[SZ][SZ],n,m,Time;

bool isin(int x,int y) { return x >= 1 && x <= n && y >= 1 && y <= m; }

char peo[3] = {'D','E'};

void bj(int x,int y,int d)
{
    zb[x][y] |= 1 << d;
    int sx = x,sy = y;
    while(isin(sx + 1,sy) && mp[sx + 1][sy] != 'X' && mp[sx + 1][sy] != peo[d ^ 1])
        zb[++ sx][sy] |= 1 << d;

    sx = x,sy = y;
    while(isin(sx,sy + 1) && mp[sx][sy + 1] != 'X' && mp[sx][sy + 1] != peo[d ^ 1])
        zb[sx][++ sy] |= 1 << d;

    sx = x,sy = y;
    while(isin(sx - 1,sy) && mp[sx - 1][sy] != 'X' && mp[sx - 1][sy] != peo[d ^ 1])
        zb[-- sx][sy] |= 1 << d;

    sx = x,sy = y;
    while(isin(sx,sy - 1) && mp[sx][sy - 1] != 'X' && mp[sx][sy - 1] != peo[d ^ 1])
        zb[sx][-- sy] |= 1 << d;
}

struct haha
{
    int x,y,d,t;
};

queue<haha> q;
bool vis[SZ][SZ][2][2];
int ans[SZ][SZ][2][2];
int bfs(int x,int y)
{
    memset(ans,63,sizeof(ans));
    while(q.size()) q.pop();
    memset(vis,0,sizeof(vis));
//    cout << zb[x][y] << endl;
    q.push((haha){x,y,zb[x][y],0});
    vis[x][y][zb[x][y] >> 1][zb[x][y] & 1] = 1;
    while(q.size())
    {
        haha u = q.front(); q.pop();
        ans[u.x][u.y][u.d >> 1][u.d & 1] = u.t;
        for(int i = 0;i < 4;i ++)
        {
            int x = u.x + dx[i];
            int y = u.y + dy[i];
            if(!isin(x,y)) continue;
            int d1 = (u.d >> 1) | (zb[x][y] >> 1);
            int d2 = (u.d & 1) | (zb[x][y] & 1);
        //    cout << x << " " << y << " " << d1 << " " << d2 << endl;
            if(!vis[x][y][d1][d2] && mp[x][y] == '.')
            {
                vis[x][y][d1][d2] = 1;
                int d = u.d | zb[x][y];
                q.push((haha){x,y,d,u.t + 1});
            }
        }
    }
    int Ans = INF;
    for(int i = 1;i <= n;i ++)
        for(int j = 1;j <= m;j ++)
        //    cout << ans[i][j][1][1] << " " ,
            Ans = min(Ans,ans[i][j][1][1]);
    return Ans > Time ? -1 : Ans;
}

void init()
{
    memset(zb,0,sizeof(zb));
}

int main()
{
    int T;
    scanf("%d",&T);
    for(int Case = 1;Case <= T;Case ++)
    {
        init();
        scanf("%d%d%d",&n,&m,&Time);
        getchar();
        for(int i = 1;i <= n;i ++)
            scanf("%s",mp[i] + 1);
        int sx,sy;
        for(int i = 1;i <= n;i ++)
            for(int j = 1;j <= m;j ++)
            {
                if(mp[i][j] == 'D')
                    bj(i,j,0);
                else if(mp[i][j] == 'E')
                    bj(i,j,1);
                else if(mp[i][j] == 'S')
                    sx = i,sy = j;
            }
        printf("Case %d:\n%d\n",Case,bfs(sx,sy));
    }
    return 0;
}


H : hdu - 5696


I : hdu - 5726

给n个数,每次询问一个区间的gcd的值,以及有多少个区间的gcd与这个区间的gcd相等。

第一个线段树或者st表都行。

对于第二个:固定区间左端点,考虑右端点向右。

对于一个数x,他的gcd个数为logx级别,所以右端点向右gcd会变小,并且至多变小logx次。

可以存下所有的gcd然后查表。


J : poj - 3071

jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

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

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