2018南京区域赛银牌题解

待我称王封你为后i 2024-04-20 08:42 24阅读 0赞

题目链接：http://codeforces.com/gym/101981  
周三晚打了一场去年南京的复现。彻彻底底的把自信心给打没了。  
还剩一个月就区域赛了，如果是这样的情况去打。那完全就是送钱当分母，作死。还不如不去。  
还有一个月，加油吧。  
银牌题解：  
**J - Prime Game**  
大水题，可是我们复现的时候竟然没写出来。智障人生。  
这个题是一场多校的进阶版。  
我们根据样例来进行分析：  
10  
6 7 5 5 4 9 9 1 8  
输出： 134  
我们看第一个数字6的质因子为2和3.分开考虑：  
第一个数字的作用区间有：  
1-1，1-2，1-3，1-10；共10次；  
则2和3都有10次，共20次。  
第2个数作用区间有：  
1-2，2-2，2-3，2-10  
共10个  
第3个数作用的区间有：  
1-3，2-3，3-3，3-10；  
共10个  
第4个数的作用区间有（注意第4个数和第3个数一样）：  
4-4，4-5，4-6，4-10；  
如是分析，对于每个数字分析可得到公式：  
(n - pos + 1) \* (pos - pre\[i\]);

#include"stdio.h"
        #include"string.h"
        #include"algorithm"
        using namespace std;
         
        int pre[1000100];
        int n,a[1001000];
        long long sum = 0;
         
        void init(int x,int pos)
        {
            for(int i = 2;i * i <= x; i ++)
            {
                if(x % i) continue;
                while(x % i == 0) 
                {
                    x = x / i;
                }
                //又爆long long 难顶
                sum += (long long)(n - pos + 1) * (pos - pre[i]);
                pre[i] = pos;
            }
            if(x != 1)
            {
                sum += (long long)(n - pos + 1) * (pos - pre[x]);
                pre[x] = pos;
            }
        }
        int main()
        {
            scanf("%d",&n);
            for(int i = 1; i <= n; i ++)
               scanf("%d",&a[i]);
            for(int i = 1; i <= n ;i ++)
            {
                init(a[i],i);
            }
            printf("%lld\n",sum);
        }

**I. Magic Potion**  
一开始的思路是跑两遍二分图，细想一遍，第一次跑出来后不同结果是会影响，第二次的二分图的。估计通过某种玄学操作可以把这个影响消除掉~~ 可是我不会。  
思路就仅限于知道是个图论，可是不会~~呜呜呜  
其实这个题如果想到怎么建图，就是一个水题了。  
样例建图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTA2MTM4_size_16_color_FFFFFF_t_70]在此图上跑最大流模板即可。  
模板题  
一开始模板打错了 猝死

#include"stdio.h"
        #include"string.h"
        #include"algorithm"
        #include"queue"
        #include"math.h"
        using namespace std;
        typedef long long ll;
         
        const int inf = 1 << 29,N = 50010,M = 300010;
        int head[N],ver[M],edge[M],Next[M],d[N];
        int n,m,s,t,tot,maxflow;
        int k;
        queue<int> q;
        void add(int x,int y,int z){
            ver[++ tot] = y,edge[tot] = z,Next[tot] = head[x],head[x] = tot;
            ver[++ tot] = x,edge[tot] = 0,Next[tot] = head[y],head[y] = tot;
        }
        bool bfs(){
            memset(d,0,sizeof(d));
            while(q.size()) q.pop();
            q.push(s); d[s] = 1;
            while(q.size()){
                int x = q.front(); q.pop();
                for(int i = head[x]; i; i = Next[i])
                if(edge[i] && !d[ver[i]]){
                    q.push(ver[i]);
                    d[ver[i]]= d[x] + 1;
                    if(ver[i] == t) return 1;
                }
            }
            return 0;
        }
         
        int dinic(int x,int flow){
            if(x == t) return flow;
            int rest = flow,k;
            for(int i = head[x]; i && rest; i = Next[i])
            if(edge[i] && d[ver[i]] == d[x] + 1){
                k = dinic(ver[i],min(rest,edge[i]));
                if(!k) d[ver[i]] = 0;
                edge[i] -= k;
                edge[i ^ 1] += k;
                rest -= k;
            }
            return flow - rest;
        }
         
        int main(){
            scanf("%d%d%d",&n,&m,&k);
    tot = 1;
            s = n + m + 1; t = s + m + 2;
            int mid = n + m + 3;
            add(s,mid,k);
            for(int i = 1; i <= n; i ++)
                {
                    add(mid,i,1);
                    add(s,i,1);
                }
            for(int i = n + 1; i <= n + m; i ++)
                add(i,t,1);
            for(int i = 1; i <= n; i ++){
                int x;
                scanf("%d",&x);
                while(x --){
                    int v;
                    scanf("%d",&v);
                    add(i,v + n,1);
                }
            }
            int flow = 0;
            while(bfs()){
                while(flow = dinic(s,inf)) maxflow += flow;
            }
           printf("%d\n",maxflow);
        }

**G. Pyramid**  
打表找规律。不知道大佬们都是怎么找到规律的~~打完表后的我还是不敢做声。  
打完表后发现为  
0 1 5 15 35 70 126 210  
不断差分下去：  
1 4 10 20 35 56 84  
3 6 10 15 21 28  
3 4 5 6 7  
1 1 1 1  
0 0 0  
到此，就是[差分的应用][Link 1]：

//https://blog.csdn.net/li_yuanze/article/details/88564787
    //https://www.cnblogs.com/wrjlinkkkkkk/p/10041144.html
    //https://blog.csdn.net/qq_41746268/article/details/90601779
    #include"stdio.h"
    #include"string.h"
    #include"algorithm"
    #include"queue"
    #include"math.h"
    using namespace std;
    typedef long long ll;
    
    const ll mod = 1000000007;
    int T;
    ll n;
    
    ll pow_quick(ll a,ll b)
    {
        ll ans = 1;
        while(b)
        {
            if(b & 1){
                ans = ans * a % mod;
            }
            a = a * a % mod; b >>= 1;
        }
        return n * (n + 1) % mod * (n + 2) % mod * (n + 3) % mod * ans % mod;
    }
    int main()
    {
        scanf("%d",&T);
        while(T --)
        {
            scanf("%lld",&n);
            printf("%lld\n",pow_quick(24LL,mod - 2));
        }
    }

**D. Country Meow**  
垃圾选手看不懂退火，还是三分友好。  
三分适应单峰函数求极值。

//参考博客： https://blog.csdn.net/qq_41785863/article/details/89432434
    #include"stdio.h"
    #include"string.h"
    #include"math.h"
    #include"algorithm"
    using namespace std;
    
    int n;
    double point[4];
    double a[110][4];
    double eps = 1e-8;
    double dis()
    {
        double maxx = 0;
        for(int i = 1; i <= n; i ++)
            maxx = max(maxx,sqrt((a[i][0] - point[0]) * (a[i][0] - point[0]) + ((a[i][1] - point[1]) * (a[i][1] - point[1])) + ((a[i][2] - point[2]) * (a[i][2] - point[2]))));
        return maxx;
    }
    double dfs(int num)
    {
        if(num >= 3)
        {
            return dis();
        }
        double l = -100000,r = 100000;
        double ans;
        while(r - l >= eps)
        {
            double lmid = l + (r - l) / 3.0;
            double rmid = r - (r - l) / 3.0;
            point[num] = lmid;
            double ans1 = dfs(num + 1);
            point[num] = rmid;
            double ans2 = dfs(num + 1);
            if(ans1 <= ans2)
            {
                ans = ans1;
                r = rmid;
            }
            else
            {
                ans = ans2;
                l = lmid;
            }
        }
        return ans;
    }
    int main()
    {
        scanf("%d",&n);
        for(int i = 1; i <= n; i ++)
            scanf("%lf%lf%lf",&a[i][0],&a[i][1],&a[i][2]);
        printf("%0.7lf\n",dfs(0));
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNTA2MTM4_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/8e7152f1d2114e96a321b2192e742bd3.png
[Link 1]: http://xueshu.baidu.com/s?wd=paperuri:%281d6cf25a905f1951b577cf287a82e1a3%29&filter=sc_long_sign&tn=SE_xueshusource_2kduw22v&sc_vurl=http://wenku.baidu.com/view/ef155ff1a26925c52dc5bf32.html&ie=utf-8&sc_us=12108961739379565888