补题 2019陕西省赛

曾经终败给现在 2021-11-29 11:56 295阅读 0赞

真的很难想象这个是我打过的比赛，好难啊，我一个人写了七八个小时，还没有写完，主要是我的代码出现了一些思想性的错误，

而且自己还没有意识到，很郁闷。

就补了五个题目。

第一个很简单的题目，随便写写就好了

[https://nanti.jisuanke.com/t/39268][https_nanti.jisuanke.com_t_39268]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <algorithm>
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn = 6e3 + 10;
    int a[maxn];
    int dp[maxn];
    int main()
    {
        int n, v;
        scanf("%d%d", &n, &v);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for(int i=1;i<=n;i++)
        {
            for(int j=v;j>=a[i];j--)
            {
                dp[j] = max(dp[j], dp[j - a[i]]+1);
            }
        }
        printf("%d\n", dp[v]);
        return 0;
    }

背包or贪心

第二个就是一个找规律题目，可以打表找，不过我不会。

[https://nanti.jisuanke.com/t/39279][https_nanti.jisuanke.com_t_39279]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <algorithm>
    #define inf 0x3f3f3f3f
    using namespace std;
    const int maxn = 6e3 + 10;
    int main()
    {
        int n, x;
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &x);
        if (n == 1) printf("1\n");
        else if (n == 3) printf("6\n");
        else if(n%2==0)
        {
            if ((n/2)%2 == 0) printf("4\n");
            else printf("%d\n", n);
        }
        else
        {
            if ((n / 2) % 2 == 1) printf("12\n");
            else printf("%d\n", n * 2);
        }
        return 0;
    }

打表找规律

第三个就是一个最短路

我之前用最短路的思想去写，但是wa了，一直wa，因为思想错了。

这个应该是二分答案+最短路，二分答案之后就很简单了，因为升级次数确定了。

[https://nanti.jisuanke.com/t/39280][https_nanti.jisuanke.com_t_39280]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <queue>
    #include <cmath>
    #include <stack>
    #include <vector>
    #include <algorithm>
    #define pi acos(-1)
    #define inf 0x3f3f3f3f3f3f3f3f
    using namespace std;
    typedef long long ll;
    const int maxn = 5e5 + 10;
    int n, m;
    int a[maxn];
    struct node
    {
        int v;
        ll dist;
        node(int v=0,ll dist=0):v(v),dist(dist){}
    };
    
    struct heapnode
    {
        int u;
        ll d;
        heapnode(int u=0,ll d=0):u(u),d(d){}
        bool operator<(const heapnode &a)const
        {
            return a.d < d;
        }
    };
    
    vector<node>vec[maxn];
    ll d[maxn];
    bool vis[maxn];
    
    void dij(int s,ll l)
    {
        priority_queue<heapnode>que;
        memset(d, inf, sizeof(d));
        memset(vis, 0, sizeof(vis));
        d[s] = 0;
        que.push(heapnode(s, 0));
        while(!que.empty())
        {
            heapnode x = que.top(); que.pop();
            int u = x.u;
            if (vis[u]) continue;
            vis[u] = 1;
            int len = vec[u].size();
            for(int i=0;i<len;i++)
            {
                node e = vec[u][i];
                if(d[u]+1<d[e.v]&&e.dist<=l)
                {
                    d[e.v] = d[u] + 1;
                    que.push(heapnode(e.v, d[e.v]));
                }
            }
        }
    }
    
    bool ok(ll l,ll num)
    {
        dij(1, l);
        if (d[n] > num) return false;
        return true;
    }
    
    int main()
    {
        int num, cost, dis;
        scanf("%d%d", &n, &m);
        scanf("%d%d%d", &cost, &dis, &num);
        for(int i=1;i<=m;i++)
        {
            int u, v;
            ll w;
            scanf("%d%d%lld", &u, &v, &w);
            vec[u].push_back(node(v, w));
            vec[v].push_back(node(u, w));
        }
        int l = 0, r = 1e5 + 10;
        while(l<r)
        {
            int mid = (l + r) >> 1;
            if (ok(mid*1ll*dis,mid*1ll*num)) r = mid;
            else l = mid + 1;
        }
        printf("%lld\n", r*1ll*cost);
        return 0;
    }

二分答案+最短路

第四个就是一个有点像计算几何的题目

[https://nanti.jisuanke.com/t/39270][https_nanti.jisuanke.com_t_39270]

但是呢，实质就是求切点，这个切点需要你推公式。

这个公式还是很好推的，但是细节需要注意，比如说这个有a等于0的情况（这个基于我自己的写法）

但是呢，这个题目的写法很多。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <queue>
    #include <cmath>
    #include <stack>
    #include <vector>
    #include <algorithm>
    #define pi acos(-1)
    #define inf 0x3f3f3f3f3f3f3f3f
    using namespace std;
    typedef long long ll;
    const int maxn = 5e5 + 10;
    
    double dis(double sx, double sy, double gx, double gy) {
        double ans = (sx - gx)*(sx - gx) + (sy - gy)*(sy - gy);
        return ans;
    }
    
    int main() {
        int t;
        scanf("%d", &t);
        while (t--) {
            double rx, ry, r, sx, sy;
            scanf("%lf%lf%lf%lf%lf", &rx, &ry, &r, &sx, &sy);
            double circle = 2 * pi*r / 4;
            if (sx >= rx + r) {
                double d = sqrt(dis(rx + r, ry, sx, sy));
                printf("%.4lf\n", d + circle);
            }
            else if (sx <= rx - r) {
                double d = sqrt(dis(rx - r, ry, sx, sy));
                printf("%.4lf\n", d + circle);
            }
            else {
                double a = (ry - sy)*(ry - sy) - r * r;
                double b = -(ry - sy)*(ry - sy) * 2 * rx + 2 * r*r*sx;
                double c = (ry - sy)*(ry - sy)*(rx*rx - r * r) - r * r*sx*sx;
                //    printf("%lf %lf %lf\n", a, b, c);
                double ex = sqrt(b*b - 4 * a*c);
                double x1, x2, x;
                if (a != 0) {
                    x1 = (-b - ex) / (2 * a);
                    x2 = (-b + ex) / (2 * a);
                    x = min(fabs(rx - x1), fabs(rx - x2));
                }
                else x = fabs(rx + c / b);
                double ans = fabs(acos(r / x));
                //    printf("%lf\n", ans);
                double l = ans * r;
                double tx = sqrt(dis(sx, sy, rx, ry));
                double len = sqrt(tx*tx - r * r);
                printf("%.4lf\n", l + circle + len);
            }
        }
        return 0;
    }

数学计算几何or自己手推公式

第五个就是一个dp

[https://nanti.jisuanke.com/t/39271][https_nanti.jisuanke.com_t_39271]

先对这个东西进行分组，分组之后不可以用分组的思想去写，因为分组是至少选一个或者至多选一个。

这个想法我觉得我挺难想到的，这个是对差值进行dp。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <cstdio>
    #include <cstring>
    #include <cstdlib>
    #include <queue>
    #include <cmath>
    #include <stack>
    #include <vector>
    #include <algorithm>
    #define pi acos(-1)
    #define inf 0x3f3f3f3f
    using namespace std;
    typedef long long ll;
    const int maxn = 1e5 + 10;
    int a[210];
    int dp[220][maxn];
    int sum1, sum2;
    bool vis[210];
    vector<int>vec[210];
    
    void dfs(int s, int flag) {
        if (flag) sum1 += a[s];
        else sum2 += a[s];
        for (int i = 0; i < vec[s].size(); i++) {
            int u = vec[s][i];
            if (vis[u]) continue;
            vis[u] = 1;
            dfs(u, !flag);
        }
    }
    vector<int>v;
    int main() {
        int t;
        scanf("%d", &t);
        while (t--) {
            int n, m, sum = 0;
            scanf("%d%d", &n, &m);
            memset(vis, 0, sizeof(vis));
            for (int i = 0; i <= n + m; i++) {
                vec[i].clear();
            }
            v.clear();
            for (int i = 1; i <= n; i++) {
                scanf("%d", &a[i]);
                a[i] /= 100;
                sum += a[i];
            }
            for (int i = 1; i <= m; i++) {
                int u, v;
                scanf("%d%d", &u, &v);
                vec[u].push_back(v);
                vec[v].push_back(u);
            }
            for (int i = 1; i <= n; i++) {
                if (vis[i]) continue;
                vis[i] = 1;
                sum1 = sum2 = 0;
                dfs(i, 0);
                v.push_back(abs(sum1 - sum2));
            }
            memset(dp, 0, sizeof(dp));
            dp[0][v[0]] = 1;
            for(int i=1;i<v.size();i++)
            {
                for(int j=0;j<=sum;j++)
                {
                    if (dp[i - 1][j]) dp[i][abs(j - v[i])] = dp[i][abs(j + v[i])] = 1;
                }
            }
            int ans = 0;
            for(int i=0;i<=sum;i++)
            {
                if(dp[v.size()-1][i])
                {
                    ans = (sum + i)*100 / 2;
                    break;
                }
            }
            printf("%d\n", ans);
        }
        return 0;
    }

差值进行dp

转载于:https://www.cnblogs.com/EchoZQN/p/10932005.html

[https_nanti.jisuanke.com_t_39268]: https://nanti.jisuanke.com/t/39268
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211129/1e10a3e5e3a44b45bc6c73ed04a81e71.png
[https_nanti.jisuanke.com_t_39279]: https://nanti.jisuanke.com/t/39279
[https_nanti.jisuanke.com_t_39280]: https://nanti.jisuanke.com/t/39280
[https_nanti.jisuanke.com_t_39270]: https://nanti.jisuanke.com/t/39270
[https_nanti.jisuanke.com_t_39271]: https://nanti.jisuanke.com/t/39271