xzm2019

第十三届北邮校赛(2019) 个人存档
仅为个人存档~SolvedABCDEFGHIJKLM8/13OO.OO..OO.O.OO for passing ...
扫描右侧二维码阅读全文
22
2019/04

第十三届北邮校赛(2019) 个人存档

仅为个人存档~

SolvedABCDEFGHIJKLM
8/13OO.OO..OO.O.O
  • O for passing during the contest
  • Ø for passing after the contest
  • ! for attempted but failed
  • · for having not attempted yet

A. Sequence (xzm2019, 0:06, +2)

其实题目很简单,就是判断一下$abs(A-B) \leq 1\ \&\&\ (A+B>0)$即可

一开始没想到后面那个,成功拿了全场最快提交(

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

int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        long long a,b;
        scanf("%lld%lld",&a,&b);
        if (abs(a - b) <= 1 && (!(a == 0 && b == 0))) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

B. Key (SingleZombie, 1:14, +3)

直接按照顺序去买钥匙,如果满了就优先丢弃下一次出现晚的钥匙即可,用STL维护。

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

const int MAXN = 1e5 +5;
typedef pair<int, int> pii;
queue<int> graph[MAXN];
int crt[MAXN];
int arr[MAXN];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        for (int i = 0; i < MAXN; i++)
        {
            while (!graph[i].empty())
            {
                graph[i].pop();
            }
        }
        int n, m;
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++)
        {
            int a;
            scanf("%d", &a);
            arr[i] = a;
            graph[a].push(i);
            crt[a] = -1;
        }
        int ans = 0;
        set<pii> st;
        for (int i = 0; i < n; i++)
        {
            int id = arr[i];
            //cout << crt[id] << " " << id << endl;
            if (st.count({crt[id], id}))
            {
                st.erase({crt[id], id});
                graph[id].pop();
                if (!graph[id].empty())
                {
                    crt[id] = graph[id].front();
                    st.insert({crt[id], id});
                }
                continue;
            }
            ans++;

            if (st.size() == m)
            {
                st.erase(prev(st.end()));
            }
            graph[id].pop();
            if (graph[id].empty())
            {
                continue;
            }
            st.insert({graph[id].front(), id});
            crt[id] = graph[id].front();
        }

        printf("%d\n", ans);
    }

    return 0;
}

D. Wander (SingleZombie, 3:50, +)

题目要求从每个点出发的最小时间,如果有$n$个人肯定是要$n-1$圈然后最后找个最近的,队友说STL瞎搞就行了。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 +5;
int sz[MAXN], minv[MAXN];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    int maxSize = 0;
    memset(minv, 0x3f, sizeof(minv));
    for (int i = 0; i < m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        sz[u]++;
        maxSize = max(maxSize, sz[u]);
        if (v < u)
        {
            v += n;
        }
        minv[u] = min(minv[u], v);
    }
    multiset<int> st;
    for (int i = 1; i <= n; i++)
    {
        if (sz[i] == maxSize)
        {
            st.insert(minv[i]);
            //cout << minv[i] << endl;
        }
    }
    for (int i = 1; i <= n; i++)
    {
        //cout << i << " " << *prev(st.end()) << endl;
        int ans = (maxSize - 1) * n + (*prev(st.end()) - i);
        if (sz[i] == maxSize)
        {
            st.erase(st.find(minv[i]));
            st.insert(minv[i] + n);
        }
        printf("%d%c", ans, i == n ? '\n' : ' ');
    }

    return 0;
}

E.Race Car (xzm2019, 4:02, +8)

先用floyd跑一遍最短路,然后把整个图变成$K+2$个点,状压dp即可。

一开始读入忘记存双向边然后血WA……

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

long long mapp[205][205];
long long tmap[15][15];
long long dp[15][1<<15];
int tu[15];
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        memset(mapp,0x3f,sizeof(mapp));
        for (int i = 1; i <= m; i++)
        {
            int u,v; long long c;
            scanf("%d%d%lld",&u,&v,&c);
            mapp[v][u] = mapp[u][v] = min(mapp[u][v], c);
        }
        for (int i = 1; i <= n; i++) mapp[i][i] = 0;
        for (int k = 1; k <= n; k++)
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= n; j++)
                    mapp[i][j] = mapp[j][i] = min(mapp[i][j], mapp[i][k] + mapp[k][j]);
        int K;
        scanf("%d",&K);
        if (K == 0)
        {
            if (mapp[1][n] == mapp[0][0]) printf("-1\n");
            else printf("%lld\n",mapp[1][n]);
            continue;
        }
        int s = K, t = K + 1;
        memset(tmap, 0x3f, sizeof(tmap));
        memset(tu,0,sizeof(tu));
        for (int i = 0; i < K; i++)
        {
            scanf("%d",&tu[i]);
            tmap[i][s] = tmap[s][i] = mapp[1][tu[i]];
            tmap[i][t] = tmap[t][i] = mapp[n][tu[i]];
        }
        for (int i = 0; i < K; i++)
            for (int j = 0; j < K; j++)
                tmap[i][j] = mapp[tu[i]][tu[j]];
        memset(dp,0x3f,sizeof(dp));
        dp[s][1<<s] = 0;
        for (int j = 0; j < (1 << t); j++)
            for (int i = 0; i < t; i++)
            {
                if (j & (1 << i));
                else continue;
                for (int k = 0; k < t; k++)
                {
                    if (k == i) continue;
                    if (j & (1 << k))
                    {
                        dp[i][j] = min(dp[i][j], dp[k][j ^ (1 << i)] + tmap[i][k]);
                    }
                }
            }
        long long ans = 0x3f3f3f3f3f3f3f3f;
        for (int i = 0; i < t; i++)
        {
            ans = min(ans, dp[i][(1 << t) - 1] + tmap[i][t]);
        }
        if (ans == 0x3f3f3f3f3f3f3f3f) printf("-1\n");
        else printf("%lld\n",ans);
    }
}

H. Melborp Kcaspank (xzm2019, 1:22, +2)

这题很明显是一个分数规划,直接二分答案即可,第一发WA了,一开始没找到哪里写残了,于是又想了个dp算法(总觉得题目教背包是在指引dp)。$dp[i][j]$表示前$i$个物品里选$j$个的最大平均值,直接转移即可,注意精度问题和爆long long问题。

然后dp写残又WA了一发,在后面疯狂修对两种做法然后交了4发rejudge都过了。

  • 二分版本:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 +5;
const long double EPS = 1e-8;
long long v[MAXN],w[MAXN];
long double t[MAXN];
int n,k;
pair<long double, int> tmp[MAXN];
bool check(long double x)
{
    for (int i = 1; i <= n; i++)
        t[i] = v[i] - x * w[i];
    sort(t + 1, t + n + 1, greater<long double>());
    long double sum = 0;
    for (int i = 1; i <= k; i++)
        sum += t[i];
    return sum > -EPS;
}
bool cmp(const pair<long double, int> & a, const pair<long double, int> & b)
{
    return a.first > b.first;
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld",&v[i],&w[i]);
    long double l = 0, r = 1e12;
    for (int i = 1; i <= 200; i++)
    {
        long double mid = (l + r) / 2.0;
        if (check(mid)) l = mid;
        else r = mid;
    }
    long double mid = (l + r) / 2.0;
    //printf("%.6LF %.6LF %.6LF\n",l,r,mid);
    for (int i = 1; i <= n; i++)
    {
        tmp[i].first = v[i] - mid * w[i];
        tmp[i].second = i;
    }
    sort(tmp + 1, tmp + n + 1, cmp);
    long long sumv = 0, sumw = 0;
    for (int i = 1; i <= k; i++)
    {
        sumv += v[tmp[i].second]; sumw += w[tmp[i].second];
    }
    long long xx = __gcd(sumv,sumw);
    sumv /= xx; sumw /= xx;
    if (sumw == 1) printf("%lld\n",sumv);
    else printf("%lld\\%lld\n",sumv,sumw);
    return 0;
}
  • dp版本:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 +5;

long long f[2][MAXN][MAXN];
long long v[MAXN],w[MAXN];
int n,k;
void print()
{
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= k; j++)
            printf("%lld\\%lld%c",f[0][i][j],f[1][i][j],j == k? '\n' : ' ');
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld",&v[i],&w[i]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= i; j++)
        {
            long long nowp = f[0][i - 1][j - 1] + v[i], nowq = f[1][i - 1][j - 1] + w[i];
            long long lastp = f[0][i - 1][j], lastq = f[1][i - 1][j];
            //printf("%d %d %lld\\%lld %lld\\%lld\n",i,j,nowp,nowq,lastp,lastq);
            if ((long double)nowp * lastq >= (long double)nowq * lastp)
            {
                f[0][i][j] = nowp; f[1][i][j] = nowq;
            }
            else
            {
                f[0][i][j] = lastp; f[1][i][j] = lastq;
            }
        }

    long long p = f[0][n][k], q = f[1][n][k];
    long long tmp = __gcd(p,q);
    p /= tmp; q /= tmp;
    if (q == 1) printf("%lld\n",p);
    else printf("%lld\\%lld\n",p,q);
    return 0;
}

I. Poeroz & YYOJ (zhanggengchen, 0:23, +)

直接dp即可,只有三个字母构成,这里用$dp[i][j][0/1]$标识到第$i$位,前一个字母是$j$,当前是否出现过AC

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000+10;
const int mo = 1e9+7;

int n;
int i,j,k;
int f[maxn][3][2];

int main()
{
    scanf("%d",&n);
    for (j=0;j<3;j++) f[1][j][0]=1;
    for (i=1;i<n;i++)
    {
        for (j=0;j<3;j++)
        {
            for (k=0;k<3;k++)
            {
                if (j==0&&k==1)
                {
                    f[i+1][k][1]=(f[i+1][k][1]+f[i][j][0])%mo;
                    f[i+1][k][1]=(f[i+1][k][1]+f[i][j][1])%mo;
                } else
                if (j==2&&k==0)
                {
                } else
                {
                    f[i+1][k][1]=(f[i+1][k][1]+f[i][j][1])%mo;
                    f[i+1][k][0]=(f[i+1][k][0]+f[i][j][0])%mo;
                }
            }
        }
    }
    int ans=0;
    for (j=0;j<3;j++)
    {
        ans=(ans+f[n][j][1])%mo;
    }
    printf("%d\n",ans);
    return 0;
}

K. Candy & Magic (zhanggenchen, 3:00, +1)

当时根本没细想,就瞎搞了一下就出来了……

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 +5;

int n;
int i,j,k;
int a[MAXN],b[MAXN];
int ans;

int main()
{
    while (scanf("%d",&n)!=EOF)
    {
        for (i=1;i<=n;i++) scanf("%d",&a[i]);
        for (i=1;i<=n;i++) b[i]=a[i];
        ans=-1000000000;
        for (i=1;i<=n;i++)
        {
            for (k=-100;k<=100;k++)
            {
                int cur=0;
                if (k==a[i]) continue;
                for (j=1;j<=n;j++) b[j]=a[j];
                b[i]=k;
                for (j=1;j<=n;j+=2) cur+=max(b[j]-b[j+1],b[j+1]-b[j]);
                ans=max(ans,cur);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

M. Deadlock (SingleZombie, 2:27, +3)

直接根据题目的要求加边,然后判断是否有环即可。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 +5;
int rT[MAXN];
vector<int> graph[MAXN];
pair<int, int> qs[100005];
bool vis[MAXN];
int inDegree[MAXN];
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n, m, k;
        scanf("%d%d%d", &n, &m, &k);
        bool yes = true;
        for (int i = 0; i < m; i++)
        {
            scanf("%d", &rT[i]);
        }
        for (int i = 0; i < k; i++)
        {
            int ct, cr;
            scanf("%d%d", &ct, &cr);
            qs[i] = {ct, cr};
        }
        {
            for (int i = 0; i < n; i++)
            {
                graph[i].clear();
                vis[i] = false;
                inDegree[i] = 0;
            }
            for (int i = 0; i < k; i++)
            {
                int ct = qs[i].first, cr = qs[i].second;
                if (rT[cr] == -1)
                {
                    //rT[cr] = ct;
                }
                else
                {
                    int u = ct, v = rT[cr];
                    graph[u].push_back(v);
                    inDegree[v]++;
                }
            }
            queue<int> que;
            int tmp = 0;
            for (int i = 0; i < n; i++)
            {
                if (inDegree[i] == 0)
                {
                    que.push(i);
                }
            }
            while (!que.empty())
            {
                int u = que.front();
                que.pop();
                tmp++;
                for (int i = 0; i < graph[u].size(); i++)
                {
                    int v = graph[u][i];
                    if (--inDegree[v] == 0)
                    {
                        que.push(v);
                    }
                }
            }
            if (tmp == n)
            {

            }
            else
            {
                yes = false;
            }
        }
        if (!yes)
        {
            puts("YES");
        }
        else
        {
            puts("NO");
        }
    }

    return 0;
}
Last modification:April 22nd, 2019 at 12:36 am
If you think my article is useful to you, please feel free to appreciate

2 comments

  1. singlezombie

    你竟然有每题的代码
    我们队可以考虑搞一个一起的博客

    1. xzm2019
      @singlezombie

      账号带回来了,回来登陆了下就复制下来了

Leave a Comment