2018ICPC 南京训练赛

桃扇骨 2023-10-11 13:27 35阅读 0赞

赛后总结：

1.补字符串

2.前期交题看三遍

3.认真听取zcz兄弟的意见 最后时间该冲的时候就要冲

A.分情况讨论一下 K > 2先手必胜

N可能是0

solved by gbs

00:17:41(-2)  没有考虑0 WA2发

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

D.经典的最小球覆盖问题，方法一般分为三分套三分套三分或者随机算法

网络上有很多类似的解法，就不赘述了

solved by hl

0:41:43

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

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 110;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    int N,M,K;
    struct Point{
        double x,y,z;
        Point(){}
        Point(double x,double y,double z):x(x),y(y),z(z){}
    }point[maxn],ans;
    double A;
    double ansx,ansy;
    const double delta = 0.999;
    double check(double x,double y,double z){
        double t = 0;
        for(int i = 1; i <= N ; i ++){
            double d = (x - point[i].x) * (x - point[i].x) + (y - point[i].y) * (y - point[i].y) + (z - point[i].z) * (z - point[i].z);
            d = sqrt(d);
            t = max(d,t);
        }
        return t;
    }
    void sa(){
        double t = 3000;
        Point a = ans;
        while(t > 1e-18){
            Point anstmp = a;
            anstmp.x += (rand() * 2 - RAND_MAX) * t;
            anstmp.y += (rand() * 2 - RAND_MAX) * t;
            anstmp.z += (rand() * 2 - RAND_MAX) * t;
            double newans = check(anstmp.x,anstmp.y,anstmp.z);
            double DE = newans - A;
            if(DE < 0){
                ans = a = anstmp;
                A = newans;
            }else if(exp(-DE / t) * RAND_MAX > rand()){
                a = anstmp;
            }
            t = t * delta;
        }
    }
    void SA(){
        sa(); sa(); sa();
        sa(); sa(); sa();
    }
    int main(){
        Sca(N); srand(time(NULL));
        for(int i = 1; i <= N ; i ++){
            scanf("%lf%lf%lf",&point[i].x,&point[i].y,&point[i].z);
            ans.x += point[i].x; ans.y += point[i].y; ans.z += point[i].z;
        }
        ans.x /= N; ans.y /= N; ans.z /= N;
        A = check(ans.x,ans.y,ans.z);
        //cout << A << endl;
        //cout << ans.x << " " << ans.y << " " << ans.z <<endl;
        SA();
        printf("%.15lf",A);
        return 0;
    }

G.数学功底强的直接把式子推出来

不想推式子的证明他的式子是一个4次以下的多项式 然后拉格朗日插值

solved by gbs

1:49:51(-3)

参数没调好TLE + RE

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

#include <iostream>
    #include<stack>
    #include<math.h>
    #include<stdlib.h>
    #include<string.h>
    #include<string>
    #include<ctime>
    #include<complex>
    #include<stdio.h>
    #include<algorithm>
    #include<map>
    #include<deque>
    using namespace std;
    typedef long long LL;
    const int mod =1e9+7;
    LL ans ;
    LL qpow(LL a,int k){
        LL ans =1;
        while(k!=0)
        {
            if (k&1)ans =(ans*a)%mod;
            a= (a*a)%mod;
            k/=2;
        }
        return ans;
    }
    int xn[6];
    int yna[6];
    int hn[6];
    int sizea= 5;
    int main()
    {
        //LL inv6=qpow(6,mod-2);
        int inv[45];
        yna[1] =1;
        yna[2] = 5;
        yna[3] = 15;
        yna[4] = 35;
        yna[5] = 70;
        for (int i=1; i<=35; i++)
            inv[i] =qpow(i-10,mod-2);
        int t;
        int n;
        cin>>t;
        for (int i=1; i<=5; i++)
        {
            LL llans = 1;
            for (int j =1; j<=5; j++)
                {
                    if (j == i)continue;
                    llans = ((llans *inv[i-j+10])%mod+mod)%mod;
                }
            hn[i] = llans;
        }
        while(t--)
        {
            scanf("%d",&n);
            LL ans = 0;
            for (int i=1; i<=5; i++)
            {
                LL llans = 1;
                for (int j =1; j<=5; j++)
                {
                    if (j == i)continue;
                    llans = ((llans *(n-j))%mod+mod)%mod;
                }
                llans =(llans*hn[i])%mod;
    
                //cout<<llans<<endl;
                ans = (ans+llans*yna[i])%mod;
    
            }
            printf("%lld\n",ans);
            /*ans = n;
            ans =(ans*(n+1))%mod;
            ans =(ans*(2LL*n+1))%mod;
            ans =(ans*i)%mod;*/
        }
    
        return 0;
    }

I.似乎是个最大流模型

不过似乎也有非网络流做法。

将每个hero对每个monster连接一条容量为1的边，然后源点对每个hero连接一条容量为1的边，monster对汇点连1的边。

然后源点连出一个点作为魔药，容量为K，魔药点对每个hero连接一条容量为1的边

solved by hl

1:04:51

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

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    typedef vector<int> VI;
    int read(){
         int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
         if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 1210;
    const int maxm = 1e6 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    int N,M,K;
    struct Dinic{
        struct Edge{
            int from,to,next,cap,flow;
            Edge(){}
            Edge(int from,int to,int next,int cap,int flow):from(from),to(to),next(next),cap(cap),flow(flow){}
        }edge[maxm * 2];
        int n,s,t,head[maxn],tot;
        int dep[maxn],cur[maxn];
        void init(int n,int s,int t){
            this->n = n; this->s = s; this->t = t;
            tot = 0;
            for(int i = 0 ; i <= n ; i ++) head[i] = -1;
        }
        inline void add(int s,int t,int w){
         //   cout << s << " " << t << " " << w <<endl;
            edge[tot] = Edge(s,t,head[s],w,0);
            head[s] = tot++;
            edge[tot] = Edge(t,s,head[t],0,0);
            head[t] = tot++;
        }
        inline bool BFS(){
            for(int i = 0 ; i <= n ; i ++) dep[i] = -1;
            dep[s] = 1;
            queue<int>Q; Q.push(s);
            while(!Q.empty()){
                int u = Q.front(); Q.pop();
                for(int i = head[u]; ~i ; i = edge[i].next){
                    int v = edge[i].to;
                    //cout <<edge[i].flow << "     " << edge[i]
                    //cout << v << "  " << dep[v] << endl;
                    if(~dep[v] || edge[i].flow >= edge[i].cap) continue;
                    dep[v] = dep[u] + 1;
                    Q.push(v);
                }
            }
            return ~dep[t];
        }
        inline int DFS(const int& u,int a){
            if(u == t || !a) return a;
            int flow = 0;
            for(int &i = cur[u]; ~i; i = edge[i].next){
                int v = edge[i].to;
                if(dep[v] != dep[u] +1) continue;
                int f = DFS(v,min(a,edge[i].cap - edge[i].flow));
                if(!f) continue;
                edge[i ^ 1].flow -= f;
                edge[i].flow += f;
                a -= f;
                flow += f;
            }
            return flow;
        }
        inline int maxflow(){
            return maxflow(s,t);
        }
        inline int maxflow(int s,int t){
            int flow = 0;
            while(BFS()){
                //cout << "bug" <<endl;
                for(int i = 0 ; i <= n ; i ++) cur[i] = head[i];
                flow += DFS(s,INF);
            }
            return flow;
        }
    }g;
    int main(){
        Sca3(N,M,K);
        int S= N + M + 3,T = N + M + 4;
        g.init(T,S,T);
        g.add(S,N + M + 1,INF);
        g.add(S,N + M + 2,K);
        for(int i = 1; i <= N ; i ++){
            g.add(N + M + 1,M + i,1);
            g.add(N + M + 2,M + i,1);
        }
        for(int i = 1; i <= M ; i ++) g.add(i,T,1);
        for(int i = 1; i <= N ; i ++){
            int k = read();
            while(k--){
                int x = read();
                g.add(M + i,x,1);
            }
        }
        Pri(g.maxflow());
        return 0;
    }

当仅考虑素数的时候，当一个点i含素数因子时，对答案产生的贡献是(i + 1) \* (N - i + 1),即包括这个点的所有范围都会出现这个素数，每个范围产生1的贡献，总贡献就是范围的个数

所以说我们用素数筛预处理出每个数含有的所有素数因子，对于每一个素数因子，出现的时候都会产生以上的贡献。

剩下的就是考虑出现相同的素数重复计算的部分了

形如 2 1 1 2 1 1 2 1 1 1的样例

素数2的下标为1 4 7

素数2产生的贡献应当是(1 - 0) \* (10 - 1 + 1) + (4 - 1) \* (10 - 4 + 1) + (7 - 4) \* (10 - 7 + 1)

所以还需要一个数组记录每个素数当前出现的最右端的位置

solved by hl

0:25:30 (-1)

运算过程中爆LL WA一发

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

用脑子想策略 (×)

随机盲一发 (√)

![1468815-20190804174059113-1960600418.png][]

在这些奇怪的类似构造题上 就要想一些奇怪的方法。

unsolved by gbs

应该是manacher计算回文串的贡献 + 计算LCP

写了AC自动机最后发现爆时间复杂度

unsolved by hl

补题：[18ICPC南京M 字符串][18ICPC_M]

转载于:https://www.cnblogs.com/Hugh-Locke/p/11298952.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif
[1468815-20190804174059113-1960600418.png]: https://img2018.cnblogs.com/blog/1468815/201908/1468815-20190804174059113-1960600418.png
[18ICPC_M]: https://www.cnblogs.com/Hugh-Locke/p/11302904.html