2017 CCPC 哈尔滨

我会带着你远行 2023-10-11 13:27 34阅读 0赞

A. 3:20:22(-1) solved by hl

WA点:三年竞赛一场空，不开LL见祖宗

由题意化为 要求左右两回文串都是奇数长度且相互覆盖对方的回文串中点。

用Manacher预处理之后 对于每个回文串x产生的后效性,在经过中点i的时候加入树状数组，经过终点i + Mp\[i\] + 1的移出树状数组

对于每个中点为i回文串作为后边那个产生的贡献，将所有中点位于 i + Mp\[i\] - 1  到 i - 1的回文串计出贡献

树状数组负责维护后缀和

![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 = 5e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    int N,M,K;
    char str[maxn];
    char Ma[maxn << 1];
    int Mp[maxn <<1];
    void Manacher(char s[],int len){
        int l = 0;
        Ma[l++] = '$';
        Ma[l++] = '#';
        for(int i = 0 ; i < len; i ++){
            Ma[l++] = s[i];
            Ma[l++] = '#';
        }
        Ma[l] = 0;
        int mx = 0,id = 0;
        for(int i = 0 ; i < l; i ++){
            Mp[i]  = mx > i?min(Mp[2 * id - i],mx - i):1;
            while(Ma[i + Mp[i]] == Ma[i - Mp[i]]) Mp[i]++;
            if(i + Mp[i] > mx){
                mx = i + Mp[i];
                id = i;
            }
        }
    }
    vector<int>Q[maxn * 2];
    LL tree[maxn * 2],l;
    void add(int p,int x){
        for(;p > 0; p -= p & -p) tree[p] += x;
    }
    LL getsum(int p){
        if(!p) p ++;
        LL ans = 0;
        for(;p <= 2 * l + 2; p += p & -p) ans += tree[p];
        return ans;
    }
    int main(){
        int T; Sca(T);
        while(T--){
            scanf("%s",str);
            l = strlen(str);
            Manacher(str,l);
            LL ans = 0;
            for(int i = 0 ; i < 2 * l + 2; i ++) Q[i].clear();
            for(int i = 0 ; i <= 2 * l + 2; i ++) tree[i] = 0;
            for(int i = 2; i < 2 * l + 2; i += 2){
                Mp[i]--;
                ans += getsum(i - Mp[i] + 1);
                if(Mp[i] > 1){
                    Q[i + Mp[i] - 1].pb(i);
                    add(i,1);
                }
                for(int j = 0 ; j < Q[i].size(); j ++){
                    add(Q[i][j],-1);
                }
                Q[i].clear();
            }
            Prl(ans);
        }
        return 0;
    }
    /*
    
    */

B.3:44:10(-1) solved by hl

二分最终答案，将原序列大于等于二分值的视为1,剩下的视为0

那么满足条件的区间的个数就是所有序列中区间和 >= K的区间的个数

线性时间求解完之后判断是否大于M

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

F.0:11:37 solved by hl

下标为奇数的构造为1,2,3,4,5 ... x

下标为偶数的构造为x + 1,x + 2.. N

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

H.3:09:34(-5) solved by gbs

很显然最终状态的最大公因数只要考虑质数就够了

预处理出1e5以下的所有素数，枚举所有素数然后贪心check

![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<queue>
    #include<deque>
    using namespace std;
    typedef long long LL;
    const int mod =1e9+7;
    //10*n
    const int maxn =1e5+35;
    int n;
    bool if_p[maxn+15];
    int p_list[maxn/2+15];
    int an[maxn];
    LL sum ;
    int p_num =0;
    LL fen_list[500];
    int fen_num;
    LL fin_ans;
    void pre()
    {
        memset(if_p,true,sizeof(if_p));
        for (int i=2; i<maxn; i++)
        {
            if (if_p[i])
            {
                p_list[p_num++] = i;
                //cout<<i<<endl;
                for (int j = i<<1; j<maxn; j+= i)
                {
                    if_p[j] =false;
                }
            }
        }
    }
    void fen(LL n)
    {
    
        fen_num =0;
        for (int i=0; i<p_num; i++)
        {
            if (p_list[i]>n)
                break ;
            if(n%p_list[i] == 0)
            {
                fen_list[fen_num++] = p_list[i];
                while(n%p_list[i] == 0)
                    n/=p_list[i];
            }
        }
        if (n> 1)
        {
            fen_list[fen_num++] =n;
        }
    }
    int remain[maxn+15];
    void judge(LL a)
    {
        LL now_time = 0;
        LL best_time =0;
        int h1;
        if (a<= 100000)
        {
            memset(remain,0,sizeof(int)*(a+4));
            for (int i=0; i<n; i++)
            {
                h1= an[i]%a;
                if (h1==0)
                    continue;
                remain[h1]++;
                best_time += min(0LL+h1,a-h1);
                if (best_time>=(fin_ans<<1))
                    return ;
            }
        }
        else
        {
            sort(an,an+n);
            int time2 = sum/a;
            for (int i=0; i<n-time2; i++)
            {
                now_time += an[i];
            }
            fin_ans = min(fin_ans,now_time);
            return ;
        }
        if (a == 2)
        {
            fin_ans = min(fin_ans,0LL+remain[1]/2);
            return ;
        }
        int lef = 1;
        int rif = a-1;//a-1
        now_time += 1LL* (a-rif)*remain[rif] + 1LL * lef*remain[lef];
        LL now_c = (a-rif)*remain[rif] - 1LL * lef*remain[lef];
        while(lef!= rif-1)
        {
            if (now_c<0)
            {
                rif--;
                now_c += (a-rif)*remain[rif];
                now_time += (a-rif)*remain[rif];
            }
            else
            {
                lef++;
                now_c -= 1LL*lef*remain[lef];
                now_time += 1LL*lef*remain[lef];
            }
        }
        LL time1 ;
        time1 = abs(now_c)/a;
        if (now_c >0)
        {
            now_time+= time1 * (2*rif-a);
        }
        else
        {
            now_time+= time1 * (a-lef-lef);
        }
        fin_ans = min(fin_ans,now_time/2);
    
    }
    /*void judge(LL a)
    {
        LL now_time = 0;
        LL best_time =0;
        int h1;
        deque<LL>dqu;
        if (a<= 100000)
        {
            memset(remain,0,sizeof(int)*(a+4));
            for (int i=0; i<n; i++)
            {
                h1= an[i]%a;
                if (h1==0)
                    continue;
                remain[h1]++;
                best_time += min(0LL+h1,a-h1);
                if (best_time>=fin_ans<<1)
                    return ;
            }
            if (a == 2)
            {
                fin_ans = min(fin_ans,0LL+remain[1]/2);
                return ;
            }
            for (int i=1; i<a; i++)
            {
                while(remain[i]--)
                {
                    dqu.push_back(i);
                }
            }
    
        }
        else
        {
            sort(an,an+n);
            for (int i=0; i<n; i++)
            {
               dqu.push_back(an[i]);
               best_time +=min(0LL+an[i],a-an[i]);
               if (best_time>=fin_ans<<1)
                   return ;
            }
    
        }
    
        LL t1,t2,t3;
        while(!dqu.empty())
        {
            t1 = dqu.front();
            t2 = dqu.back();
            dqu.pop_back();
            dqu.pop_front();
            t3 = min(t1,a-t2);
            t1-=t3;
            t2+=t3;
            now_time += t3;
            if (now_time >=fin_ans)
                return ;
            if (t1!= 0)
                dqu.push_front(t1);
            if (t2 != a)
                dqu.push_back(t2);
        }
        fin_ans = min(fin_ans,now_time);
    }*/
    int main()
    {
        pre();
        int t;
    
        cin >>t;
        while(t--)
        {
            cin >>n;
            sum =0;
            for (int i=0; i<n; i++)
            {
                scanf("%d",&an[i]);
                //an[i] = 100000;
                sum += an[i];
            }
    
            fin_ans = 1e17;
            fen(sum);
            if (sum == 0)
            {
                cout<<0<<endl;
                continue;
            }
            for (int i =0; i<fen_num; i++)
            {
                //cout<<fen_list[i]<<"D"<<endl;
                //cout<<sum<<"S"<<fen_list[i]<<endl;
                judge(fen_list[i]);
            }
            cout<<fin_ans<<endl;
    
    
    
        }
    
    
        return 0;
    }
    
    
    /*
    111
    5111111 11111116 12133215 251111111
    111
    5 15 5 25
    5 14 5 25
    5 13 5 25
    5 12 5 25
    3
    14 14 5 5
    14 14 5 5
    */

J. 5:10:01 solved by zcz

HL:他弄了一个很复杂的公式给我敲，至于怎么整出来的，咱也不知道，咱也不敢问

![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;
    LL quick_power(LL a,LL b){
        LL ans = 1;
        while(b){
            if(b & 1) ans = ans * a % mod;
            b >>= 1;
            a = a * a % mod;
        }
        return ans;
    }
    LL inv(LL a){
        return quick_power(a,mod - 2);
    }
    LL x[10],y[10];
    LL fac(LL v){
        x[1] = 2; y[1] = 2;
        x[2] = 3; y[2] = 8;
        x[3] = 4; y[3] = 20;
        x[4] = 5; y[4] = 40;
        x[5] = 6; y[5] = 70;
        LL ans = 0;
        for(int i = 1; i <= 5; i ++){
            LL sum = 1;
            for(int j = 1; j <= 5; j ++){
                if(i != j) sum = sum * (x[i] + mod - x[j]) % mod;
            }
            sum = inv(sum);
            sum = sum * y[i] % mod;
            for(int j = 1; j <= 5; j ++){
                if(i != j) sum = sum * (v - x[j] + mod) % mod;
            }
            ans = (ans + sum) % mod;
        }
        return ans;
    }
    LL fac2(LL v){
        x[1] = 1; y[1] = 6;
        x[2] = 2; y[2] = 30;
        x[3] = 3; y[3] = 90;
        x[4] = 4; y[4] = 210;
        x[5] = 5; y[5] = 420;
        LL ans = 0;
        for(int i = 1; i <= 5; i ++){
            LL sum = 1;
            for(int j = 1; j <= 5; j ++){
                if(i != j) sum = sum * (x[i] + mod - x[j]) % mod;
            }
            sum = inv(sum);
            sum = sum * y[i] % mod;
            for(int j = 1; j <= 5; j ++){
                if(i != j) sum = sum * (v - x[j] + mod) % mod;
            }
            ans = (ans + sum) % mod;
        }
        return ans;
    }
    inline LL mul(LL a,LL b){
        return a % mod * b % mod;
    }
    inline LL add(LL a,LL b){
        return ((a + b) % mod + mod) % mod;
    }
    LL S3(LL x){
        return x * (x + 1) % mod * x % mod * (x + 1) % mod * inv(2) % mod * inv(2) % mod;
    }
    LL S1(LL x){
        return (x + 1) * x % mod * inv(2) % mod;
    }
    LL S2(LL x){
        return mul(mul(mul(x,add(x,1)),add(2 * x % mod,1)),inv(6));
    }
    
    int main(){
        int T;
        Sca(T);
        LL inv2 = inv(2);
        while(T--)
        {
            LL a,b;
            scanf("%lld %lld",&a,&b);
            long long ans;
            LL n = a;
            if(b==1)
            {
                ans = mul(inv2,(add(add(-S3(n),-S2(n)),mul(add(S1(n),S2(n)),n))));
                ans = mul(ans,inv(add(mul(S1(n),n),-S2(n))));
            }
            else
            {
                ans= mul(mul(inv2,add(S3(n),-S1(n))),inv(add(S2(n),-S1(n))));
            }
            printf("%lld\n",ans);
        }
    
    
        return 0;
    }

L. unsolved by hl

赛后补题   [HDU6241 17CCPC哈尔滨L][HDU6241 17CCPC_L]

M.2:56:06(-14) solved by zcz

每次随机找3个点，求出他们的圆心去check是否为最终答案

因为至少一半的点在最终答案的圆上，每次就有1 / 8的概率中奖

因为每次都直接随机点，显然出题人不能构造出让我们TLE的数据

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

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<ctime>
    #include<cstdlib>
    #include<cmath>
    using namespace std;
    
    int random(int n)
    {
        return (long long)rand()*rand()%n;
    }
    
    struct Point
    {
        double x,y;
        Point(double x0=0,double y0=0) : x(x0) , y(y0) { }
        friend Point operator-(const Point &a,const Point &b)
        {
            return Point(a.x-b.x,a.y-b.y);
        }
        friend Point operator+(const Point &a,const Point &b)
        {
            return Point(a.x+b.x,a.y+b.y);
        }
        friend Point operator*(const Point &a,double b)
        {
            return Point(a.x*b,a.y*b);
        }
    };
    
    double Cross(Point a,Point b)
    {
        return a.x*b.y-b.x*a.y;
    }
    
    Point getLineIntersection(const Point &P,const Point &v,const Point &Q,const Point &w)
    {
        Point u=P-Q;
        double t=Cross(w,u)/Cross(v,w);
        return P+v*t;
    }
    Point p[100005];
    
    
    int n;
    
    const double eps=1e-9;
    
    int dcmp(double x)
    {
        return x>eps||x<-eps;
    }
    
    
    Point Get(Point a,Point b,Point c)
    {
        Point p1,p2,v1,v2;
        p1.x=(a.x+b.x)/2;
        p1.y=(a.y+b.y)/2;
        p2.x=(a.x+c.x)/2;
        p2.y=(a.y+c.y)/2;
        v1.x=a.y-b.y;
        v1.y=b.x-a.x;
        v2.x=a.y-c.y;
        v2.y=c.x-a.x;
        if(dcmp(v1.x*v2.y-v2.x*v1.y)==0)    return Point(0,0);
        return getLineIntersection(p1,v1,p2,v2);
    }
    
    double dis(Point a,Point b)
    {
        return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
    }
    
    
    bool judge(Point T,double R)
    {
        int cnt=0;
        for(int i=0;i<n;i++)
        {
            if(dcmp(sqrt(dis(T,p[i]))-sqrt(R))==0)
            {
                cnt++;
            }
        }
        return cnt>=(n+1)/2;
    }
    
    
    void solve()
    {
        int t1,t2,t3;
        if(n<=4)
        {
            if(n==1)
            {
                double tt=1;
                printf("%lf %lf %lf\n",p[0].x+1,p[0].y,tt);
            }
            else
            {
                printf("%.10lf %.10lf %.10lf\n",(p[0].x+p[1].x)/2,(p[0].y+p[1].y)/2,sqrt(dis(p[0],p[1]))/2);
            }
            return ;
        }
    
    
        while(1)
        {
            t1=random(n);
            do
            {
                t2=random(n);
            }
            while(t2==t1);
            do
            {
                t3=random(n);
            }
            while(t3==t2||t3==t1);
            Point T=Get(p[t1],p[t2],p[t3]);
            double R=dis(p[t1],T);
            double MAX=1e9;
            if(sqrt(R)>=MAX||T.x>=MAX||T.x<=-MAX||T.y>=MAX||T.y<=-MAX)  continue;
            if(judge(T,R))
            {
                printf("%.10lf %.10lf %.10lf\n",T.x,T.y,sqrt(R));
                break;
            }
        }
    }
    
    
    int main()
    {
        srand((unsigned)time(NULL));
        int T;
        cin>>T;
        while(T--)
        {
            cin>>n;
            for(int i=0;i<n;i++)
            {
                scanf("%lf%lf",&p[i].x,&p[i].y);
            }
            solve();
        }
    
    
        return 0;
    }

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

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif
[HDU6241 17CCPC_L]: https://www.cnblogs.com/Hugh-Locke/p/11324108.html