DQS DQS

CCPC2017 Final hdu6243~hdu6253

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

谷歌的题真好!!


A.Dogs and Cages

题意:求n的排列中a[i]!=i的期望。

概率没学好,于是错排硬推…
即错排数为k时的概率之和,式子为

$$\sum_{k=0}^n\frac{kf_kC_n^k}{n!}=\sum_{k=0}^n\frac{k*f_k}{n!(n-k)!}$$

f是错排递推公式。
打表得答案是n-1

(题解说,期望具有可加性,单个的概率是(n-1)/n,个数是n,乘起来就是n-1)

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') { n = n * 10 + a - '0',a = getchar(); }
    if(flag) n = -n;
    return n;
}

double f[SZ],fac[SZ];

int main()
{
    int T = read(),cc = 0;
    while(T --)
    {
        int n = read();
        printf("Case #%d: %d.0000000000\n",++ cc,n - 1);
    }
    return 0;
}


B.Same Digit

大爆搜,防ak题,溜了


C.Rich Game

题意:两个人打乒乓球,每11小局是一大局。每小局若我赢,则给对方X元,对方赢则给我Y元。一共玩K大局。
每大局中必须领先对方两分才能结束,否则无限进行下去。我们可以任意操控每局的输赢情况,并且一开始我的钱为0。问在钱数大于等于0的情况下最多赢多少大局。

题意很麻烦,其实很简单…若x<y,则钱数无限,可以全赢。若x>=y,要么0:11输,要么11:9赢。一个简单贪心。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') { n = n * 10 + a - '0',a = getchar(); }
    if(flag) n = -n;
    return n;
}

double f[SZ],fac[SZ];

int main()
{
    int T = read(),cc = 0;
    while(T --)
    {
        LL x = read(),y = read(),k = read(),ans = 0;
        if(x > y) ans = k;
        else
        {
            LL now = 0,a = 11 * y;
            for(int i = 1;i <= k;i ++)
            {
                if(now + 9 * x - 11 * y < 0) now += 11 * x;
                else ans ++,now -= 11 * y,now += 9 * x;
            }
        }
        printf("Case #%d: %d\n",++ cc,ans);
    }
    return 0;
}


D.Mr. Panda and Circles

好像要fft,我要先学一套这个理论


E.Evil Forest

签到题,n个数*1.1上取整加起来。
然而要注意误差……以后能不浮点数就不浮点数了…………太坑了…………

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') { n = n * 10 + a - '0',a = getchar(); }
    if(flag) n = -n;
    return n;
}

double f[SZ],fac[SZ];

int main()
{
    int T = read(),cc = 0;
    while(T --)
    {
        int n = read();
        LL ans = 0;
        for(int i = 1,x;i <= n;i ++) x = read(),ans += (x * 11 + (x * 11 % 10 ? 10 : 0)) / 10;
        printf("Case #%d: %lld\n",++ cc,ans);
    }
    return 0;
}

F.Fair Lottery

听说是线性规划,单纯形…好吧还是要学一套这个理论


G.Alice’s Stamps

题意:给m个区间,问选k个区间至多包含多少个不同的元素。坐标范围、m、k都是2000以内。

这题竟然想了好久,怎么想都是n^2log…傻了

对于一个点,尽量向右拓展,更新它能拓展的最右边的点,这样一定不会变差。
于是按左端点排序,这样线段的考虑是递增的,更新即可。要注意这个点向右推的时候,新覆盖的点数要-1。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') { n = n * 10 + a - '0',a = getchar(); }
    if(flag) n = -n;
    return n;
}

struct haha
{
    int l,r;
}p[SZ];

bool cmp(haha a,haha b) { return a.l < b.l; }

int f[2010][2010],a[2010];

int main()
{
    int T = read(),cc = 0;
    while(T --)
    {
        int n = read(),m = read(),K = read();
        for(int i = 1;i <= m;i ++)
        {
            p[i].l = read(),p[i].r = read();
        }
        sort(p + 1,p + 1 + m,cmp);
        for(int i = 0;i <= n;i ++)
            for(int j = 0;j <= K;j ++) 
                f[i][j] = 0;
        for(int i = 0,pos = 1,num = 0;i < n;i ++)
        {
            while(pos <= m && p[pos].l == i + 1) 
                num = max(num,p[pos].r - i),pos ++;
            for(int j = 0;j < K;j ++)
            {
                f[i + num][j + 1] = max(f[i + num][j + 1],f[i][j] + num);
                f[i + 1][j + 1] = max(f[i + 1][j + 1],max(f[i][j + 1],f[i + 1][j]));
                //f[i][j + 1] = max(f[i][j + 1],f[i][j]);
                //f[i + 1][j] = max(f[i + 1][j],f[i][j]);
            }
            if(num) num --;
        }
        printf("Case #%d: %d\n",++ cc,f[n][K]);
    }
    return 0;
}


H.Equidistance

听说是线代题………emmm…容我复习一下……


I.Inkopolis

我写的题里最难的吧……不过写起来还是很爽的。

题意:给一个基环树,每条边一个颜色。每次给一条边染色,并询问当前图中联通块个数。两条边联通当且仅当两边有至少一个公共点。
n,m<=2e5

这种基环树要先考虑树。考虑树,不如先考虑一条链。

链上,可以统计每个点周围连着几种颜色。那么长度为k的一段色块(上面有k+1个点),总共被统计了k+1次,所以要减去k。那么推广到一棵树上,答案就是每个点连的颜色数-(n-1)。

对于基环树,除了环以外其他都相同。同样的思路,可以知道环上的答案是减去点数,那么基环树的答案就是每个点连的颜色数之和-n。需要注意环上若只有一个颜色,那么答案需要+1

对于每个点连的颜色,我用multiset维护,然后再用一个数组维护环上的颜色数。还要注意常数

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef unsigned long long ULL;
typedef long long LL;
typedef pair<double,double> pii;
const int SZ = 1000010;
const LL INF = 1000000010;
const LL mod = 1000000007;
const int Dx[] = {0,1,0,-1};
const int Dy[] = {1,0,-1,0};
const double eps = 1e-6;

LL read()
{
    LL n = 0;
    char a = getchar();
    int flag = 0;
    while(a < '0' || a > '9') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') n = n * 10 + a - '0',a = getchar();
    if(flag) n = -n;
    return n;
}

int n,m;
int head[SZ],nxt[SZ],tot = 1;

struct edge
{
    int t,d;
}l[SZ];

void build(int f,int t,int d)
{
    l[++ tot] = (edge){t,d};
    nxt[tot] = head[f];
    head[f] = tot;
}

bool ins[SZ],vis[SZ];
int pre[SZ];
map<int,int> is[SZ];
stack<int> S;

bool find_r(int u)
{
    S.push(u);
    ins[u] = 1;
    for(int i = head[u];i;i = nxt[i])
    {
        int v = l[i].t;
        if(vis[i] || vis[i ^ 1]) continue;
        vis[i] = vis[i ^ 1] = 1;
        if(ins[v])
        {
            is[v][u] = is[u][v] = 1;
            while(233)
            {
                int x = S.top(); S.pop();
                ins[x] = 0;
                if(x == v) break;
                is[pre[x]][x] = is[x][pre[x]] = 1;
            }
            return true;
        }
        else if(pre[v] = u,find_r(v)) return true;
        vis[i] = vis[i ^ 1] = 0;
    }
    S.pop();
    ins[u] = 0;
    return false;
}

multiset<int> c[SZ];
int rc[SZ],sum;

int ans = 0;
void calc()
{
    for(int u = 1;u <= n;u ++)
    {
        for(int i = head[u];i;i = nxt[i])
        {
            int d = l[i].d;
            if(c[u].find(d) == c[u].end()) ans ++;
            c[u].insert(d);
            if(is[u][l[i].t]) if(rc[d] ++ == 0) sum ++;
        }
    }
}

void change(int u,int d,int pre,bool flag)
{
    multiset<int> :: iterator it = c[u].find(pre);
    c[u].erase(it);
    if(c[u].find(pre) == c[u].end()) ans --;
    
    if(c[u].find(d) == c[u].end()) ans ++;
    c[u].insert(d);
    if(flag)
    {
        if(-- rc[pre] == 0) sum --;
        if(rc[d] ++ == 0) sum ++;
    }
}

map<int,int> mp[SZ];

void init()
{
    for(int i = 1;i <= tot;i ++)
        pre[i] = rc[i] = head[i] = ins[i] = vis[i] = 0,c[i].clear(),mp[i].clear(),is[i].clear();
    while(S.size()) S.pop();
    tot = 1; ans = 0;
    sum = 0;
}

int main()
{
    int T = read(),cc = 0;
    while(T --)
    {
        init();     
        n = read(),m = read();
        for(int i = 1;i <= n;i ++)
        {
            int x = read(),y = read(),z = read();
            build(x,y,z); build(y,x,z);
            mp[x][y] = mp[y][x] = z;
        }
        find_r(1);
        calc(); /// 统计每个点连的颜色数
        printf("Case #%d:\n",++ cc);
        for(int i = 1;i <= m;i ++)
        {
            int x = read(),y = read(),z = read(),pre = mp[x][y];
            mp[x][y] = mp[y][x] = z;
            bool flag = is[x][y];
            change(x,z,pre,flag); change(y,z,pre,flag);
            int d = 0;
            if(sum == 1) d = 1;
            printf("%d\n",ans + d - n);
        }
    }
    return 0;
}


J.Subway Chasing

题意:P、S两个人坐车,一共n个站,S比P早走x分钟。他们的车的速度是相同的。
给出m个关系:当P在车站A和B之间时,S在C和D之间。
问能否构造出一组相邻两车站的距离的解,满足这个关系。

我们发现,两人之间差x分钟的路程是时刻不变的。于是条件转化为:[B,C]之间的距离<x,[A,D]之间的距离>x。如果A=B并且C=D时要特判。

转化成前缀和,于是就有了许多不等式,可以差分约束构造解。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int SZ = 1000010;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') { n = n * 10 + a - '0',a = getchar(); }
    if(flag) n = -n;
    return n;
}

int n,m,x;
int head[SZ],nxt[SZ],tot = 1;

struct edge
{
    int t;
    LL d;
}l[SZ];

void build(int f,int t,LL d)
{
    //cout <<f << " " << t << " " << d << "   FUCK " << endl;
    l[++ tot] = (edge){t,d};
    nxt[tot] = head[f];
    head[f] = tot;
}

bool use[SZ];
LL dist[SZ],t[SZ];
queue<int> q;

bool spfa(int s)
{
    for(int i = 0;i <= n + 1;i ++) dist[i] = 1e18,t[i] = 0,use[i] = 0;
    while(q.size()) q.pop();
    dist[s] = 0;
    q.push(s);
    use[s] = 1;
    while(q.size())
    {
        int u = q.front(); q.pop();
        use[u] = 0;
        for(int i = head[u];i;i = nxt[i])
        {
            int v = l[i].t;
            if(dist[v] > dist[u] + l[i].d)
            {
                dist[v] = dist[u] + l[i].d;
                if(!use[v])
                {
                    use[v] = 1,q.push(v);
                    if(++ t[v] == n) return false;
                }
            }
        }
    }
    return true;
}

int main()
{
    int T = read(),cc = 0;
    while(T --)
    {
        for(int i = 0;i <= n + 1;i ++) head[i] = 0;
        tot = 1;
        n = read(),m = read(),x = read();
        for(int i = 1;i <= m;i ++)
        {
            int a = read(),b = read(),c = read(),d = read();
            if(a == b && c == d)
                build(a,c,x),build(c,a,- x);
            else
                build(b,c,x - 1),build(d,a,- x - 1);
        }
        for(int i = 2;i <= n;i ++) build(i,i - 1,-1);
        int s = n + 1;
        for(int i = 0;i <= n;i ++) build(s,i,1);
        printf("Case #%d: ",++ cc);
        if(!spfa(s)) {puts("IMPOSSIBLE"); continue;}
        for(int i = 2;i <= n;i ++)
            printf("%lld%c",dist[i] - dist[i - 1],i == n ? '\n' : ' ');
    }
    return 0;
}


K.Knightmare

题意:在一个无限大的棋盘上,求马走n步有可能走过的格子数。

不!会!做!
然而发现是数学,于是先打表。

打表出前八项,看不出规律
直觉发现增长速率并没有很快,于是做差分。
然后发现好像是等差,再做差分。
这时发现后面几个每个差分都是28,前五项特判。

于是反推回去,答案是一个二次多项式的形式。然后发现就过了…

非要解释的话,我觉得是这个的增量显然越来越多,增量的增量随着步数的增大,本来的基数增大,于是就收敛了(瞎说的

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
const int SZ = 1000010;
const int INF = 1e9 + 10;
const int mod = 1e9 + 7;
const int dx[] = {-1,-1,1,1,-2,-2,2,2};
const int dy[] = {2,-2,-2,2,1,-1,-1,1};

LL read()
{
    LL n = 0;
    char a = getchar();
    bool flag = 0;
    while(a > '9' || a < '0') { if(a == '-') flag = 1; a = getchar(); }
    while(a >= '0' && a <= '9') { n = n * 10 + a - '0',a = getchar(); }
    if(flag) n = -n;
    return n;
}


int main()
{
    int T = read(),cc = 0;
    int a[] = {1,9,41,109,205};
    while(T --)
    {
        unsigned long long ans,n = read();
        if(n <= 4) ans = a[n];
        else ans = 14 * n * n - 6 * n + 5;
        printf("Case #%d: %llu\n",++ cc,ans);
    }
    return 0;
}
jrotty WeChat Pay

微信打赏

jrotty Alipay

支付宝打赏

文章二维码

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

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