2018ICPC 沈阳训练赛

Dear 丶 2023-10-11 13:27 32阅读 0赞

C.1:33:41(-1) solved by zcz

推式子 找规律

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

#include<iostream>
    using namespace std;
    
    long long F(long long n,long long mod)
    {
        long long rec=1;
        for(long long i=1;i<=n;i++)
        {
            rec*=i;
            rec%=mod;
        }
        return rec;
    }
    
    long long F2(long long t)
    {
        return t*t-2*t+2;
    }
    
    int main()
    {
        int T;
        cin>>T;
        int cas=1;
        while(T--)
        {
            long long n,k,q;
            scanf("%lld %lld %lld",&n,&k,&q);
            if(k>n) k=n;
            long long ans=F(k,q)*(k*(n-k)+F2(n-k)+n-k-1)%q;
            if(k==1)   ans=F2(n)%q;
            if(k==n)   ans=F(n,q);
            if(k==2&&n==3)  ans=6%q;
            printf("Case #%d: %lld\n",cas++,ans);
        }
        return 0;
    }

E. unsolved  补题：[2018ICPC 沈阳 E][2018ICPC _ E]

G.2:18:23(-4) solved by hl

预处理出1 - 1e7范围内的k可以被哪些i² + j²得出,显然对于每个k，符合条件的i,j不会很多

所以预处理完了直接暴力就是了

![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 = 2e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    int N,M,K;
    PII point[maxn];
    LL Point[6010][6010];
    const int a[4][2] = {
         1,1,1,-1,-1,1,-1,-1};
    vector<PII>Q[10000010];
    int main(){
        int T = read();
        for(int i = 0; i <= 6000; i ++){
            for(int j = 0; j <= 6000; j ++){
                //if(i == 0 && j == 0) continue;
                LL k = i * i + j *j;
                if(k <= 10000000){
                    Q[k].pb(mp(i,j));
                }
            }
        }
        int CASE = 1;
         while(T--){
            Sca2(N,M);
            int cnt = 0;
            for(int i = 1; i <= N ; i ++){
                int x,y; LL w;
                scanf("%d%d%lld",&x,&y,&w);
                Point[x][y] = w;
                point[++cnt] = mp(x,y);
            }
            LL ans = 0;
            printf("Case #%d:\n",CASE++);
            while(M--){
                int op,x,y; scanf("%d%d%d",&op,&x,&y);
                x = (x + ans) % 6000 + 1;
                y = (y + ans) % 6000 + 1;
                if(op == 1){
                    LL w; Scl(w); Point[x][y] = w;
                    point[++cnt] = mp(x,y);
                }else if(op == 2){
                    Point[x][y] = 0;
                }else if(op == 3){
                    LL k,w; scanf("%lld%lld",&k,&w);
                    for(int i = 0 ; i < Q[k].size(); i ++){
                        PII t = Q[k][i];
                        for(int j = 0 ; j < 4; j ++){
                            if(t.fi == 0 && (j == 2 || j == 3)) continue;
                            if(t.se == 0 && (j == 1 || j == 3)) continue;
                            int X = t.fi * a[j][0],Y = t.se * a[j][1];
                            if(x + X <= 6000 && x + X >= 1 &&y + Y <= 6000 && y + Y >= 1 && Point[X + x][Y + y]){
                                Point[X + x][Y + y] += w;
                            }
                        }
                    }
                }else{
                    LL k; Scl(k); LL sum = 0;
                    for(int i = 0 ; i < Q[k].size(); i ++){
                        PII t = Q[k][i];
                        for(int j = 0 ; j < 4; j ++){
                            if(t.fi == 0 && (j == 2 || j == 3)) continue;
                            if(t.se == 0 && (j == 1 || j == 3)) continue;
                            int X = t.fi * a[j][0],Y = t.se *a[j][1];
                            if(x + X <= 6000 && x + X >= 1 &&y + Y <= 6000 && y + Y >= 1 && Point[X + x][Y + y]){
                                sum += Point[x + X][y + Y];
                            }
                        }
                    }
                    Prl(sum);
                    ans = sum;
                }
            }
            for(int i = 1; i <= cnt; i ++) Point[point[i].fi][point[i].se] = 0;
        }
        return 0;
    }

J.0:39:20(-2) solved by hl

简单的阅读理解题，

注意搞清楚每个定义的空间，否则就会象我一样签到题 WA \* 2

![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;
    char op[50];
    int main(){
        int T = read(); int CASE = 1;
        while(T--){
            Sca(N);
            LL sum = 0;
            while(N--){
                LL base = 0;
                scanf("%s",op);
                if(op[0] == 'b') base = 1;   //bool
                else if(op[0] == 'c') base = 1;   //char
                else if(op[0] == 'i') base = 4;   //int
                else if(op[0] == 'l'){
                    scanf("%s",op);
                    if(op[0] == 'l') base = 8;   //LL
                    else base = 16;    //long double
                }else if(op[0] == '_') base = 16;  //int128
                else if(op[0] == 'f') base = 4;  // float
                else if(op[0] == 'd') base = 8;  //double
              //  cout << base <<endl;
                scanf("%s",op);
                int l = strlen(op); l --;
                if(op[l - 1] == ']'){
                    LL ans = 0;
                    int pos = -1;
                    for(int i = 0 ; i < l - 1; i ++){
                        if(op[i] < '0' || op[i] > '9') pos = -1;
                        if(op[i] == '[' && i != l - 2){
                             pos = i;
                        }
                    }
                    if(pos == -1){
                        ans += base;continue;
                    }
                    for(int i = pos + 1; i < l - 1; i ++){
                        ans = ans * 10 + op[i] - '0';
                    }
                    sum += ans * base;
                }else{
                    sum += base;
                }
            }
            sum = (sum + 1023) / 1024;
            printf("Case #%d: ",CASE++);
            Prl(sum);
        }
        return 0;
    }

K.4:40:51(-4) solved by gbs

![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 =100000073 ;
    /*
    LL llans,rans;
    LL llck;
    LL gn(LL c1)
    {
        //cout<<endl<<n<<' '<<m<<' '<<c1<<endl;
        if (n+c1 >=k)
        {
            llans = (n+c1)/k;
            if (m<= llans)
            {
                return m*k-c1;
            }
    
            n-=llans;
            m-=llans;
            llans= gn((n+llans+c1)%k);
            rans = llans;
    
            while(rans - (rans+c1)/k < llans)
            {//cout<<llans<<' '<<rans<<' '<<rans - (rans+c1)/k<<' '<<k<<endl;
                rans += llans - (rans - (rans+c1)/k);
            }
            return rans;
        }
        else
        {
            llck = k%n;
            llck --;
            llck -=c1;
            while (llck <0)
                llck+=n;
    
    
            llck++;
            //cout<<"ASsa"<<endl;
            if (m == 1)
            {
                return llck;
            }//cout<<"ASa"<<endl;
            n--;
            m--;
    
            llans = gn(n+1-llck);
            if (llans >=llck)
            {
                llans++;
            }
            return llans;
    
    
        }
    }*/
    const int maxn = 6e7+16;
    int cnt;
    LL llans,rans;
    LL n,m,k;
    LL fin_ans[maxn];
    LL c1[maxn];
    LL llck;
    bool flag[maxn];
    int main()
    {
        int t;
        int case1 = 1;
        cin >>t;
        while(t--)
        {
            scanf("%lld%lld%lld",&n,&m,&k);
            cnt = 0;
            c1[0] = 0;
            while (m != 0)
            {
                //if (cnt>maxn)
                //    cout<<"sdfsf"<<n<<' '<<m<<endl;
                if (n+c1[cnt] >=k)
                {
                    flag[cnt] = true;
                    llans = (n+c1[cnt])/k;
                    if (m<= llans)
                    {
                        //cout<<"SDD"<<m*k-c1[cnt]<<' '<<c1[cnt]<<endl;
                        fin_ans[cnt] =  m*k-c1[cnt];
                        break;
                    }
                    n-=llans;
                    m-=llans;
                    c1[cnt+1] = ((n+llans+c1[cnt])%k);
                }
                else
                {
                    flag[cnt] = false;
                    llck = k%n;
                    llck --;
                    llck -=c1[cnt];
                    while (llck <0)
                        llck+=n;
                    llck++;
                    if (m == 1)
                    {
                        fin_ans[cnt] = llck;
                        //cout<<endl<<"AS"<<llck<<endl;
                        //return llck;
                        break;
                    }//cout<<"ASa"<<endl;
                    n--;
                    m--;
                    c1[cnt] = llck;
                    c1[cnt+1] = n+1-llck;
                }
                cnt++;
    
            }
            for (int i=cnt-1; i>=0; i--)
            {
                if (flag[i])
                {
                    llans= fin_ans[i+1];
                    rans = llans;
                    //cout<<"ASAS"<<llans<<endl;
    
                    while(rans - (rans+c1[i])/k < llans)
                    {
                        //cout<<llans<<' '<<rans<<' '<<rans - (rans+c1[i])/k<<' '<<k<<endl;
                        rans += llans - (rans - (rans+c1[i])/k);
                    }
                    //cout<<"ASS"<<llans<<endl;
                    //cout<<rans<<' '<<(rans+c1[i])/k<<' '<<llans<<endl;
                    fin_ans[i] = rans;
                }
                else
                {
                    //cout<<"sdfsf"<<endl;
                    llans = fin_ans[i+1];
                    if (llans >=c1[i])
                    {
                        llans++;
                    }
                    fin_ans[i] = llans;
                }
            }
    
            printf("Case #%d: ",case1++);
            printf("%lld\n",fin_ans[0]);
        }
        return 0;
    }
    
    
    /*
    3
    1000000000000000000 1000000000000000000 2000000
    13
    5 1 10
    5 2 10
    5 3 10
    5 4 10
    5 5 10
    2      :1 2 2 1
    3      :1 3 5 6 5 3 1
    4      :1 4 9 15 20 23 20 15 9 4 1
    5      :1 5 14 29 49 72 92 107 107 92 72 49 29 14 5 1
    6      :1 6 20 49 98 170 262 369 476 568 640 640 568 476 369 262 170 98 49 20 6 1
    7      :1 7 27 76 174 344 606 975 1451 2019 2659 3299 3867 4343 4712 4343 3867 3299 2659 2019 1451 975 606 344 174 76 27 7 1
    8      :1 8 35 111 285 629 1235 2210 3661 5680 8339 11638 15505 19848 24560 28903 32770 36069 38728 36069 32770 28903 24560 19848 15505 11638 8339 5680 3661 2210 1235 629 285 111 35 8 1
    9      :1 9 44 155 440 1069 2304 4514 8175 13855 22194 33832 49337 69185 93745 122648 155418 191487 230215 266284 299054 327957 352517 352517 327957 299054 266284 230215 191487 155418 122648 93745 69185 49337 33832 22194 13855 8175 4514 2304 1069 440 155 44 9 1
    */

L.4:10:40(-8) solved by zcz

1.一个端点在圆与中心圆相交的点上的所有线段中，至少有一条是和答案一样长的

2.所以枚举每个端点，然后判断它对面的点是否被其他圆吃了，如果没被吃那就是直径，如果被吃了就是被吃的两端最近的没被吃的点

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

#include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    long double P[505];
    struct Line
    {
        long double a1,a2;
    };
    Line L[505];
    
    const long double pi=acos(-1.0);
    
    
    int main()
    {
        int T;
        cin>>T;
        int cas=1;
        while(T--)
        {
            int n;
            long double R0;
            scanf("%d %Lf",&n,&R0);
            long double x,y,R1;
            int l1=0,l2=0;
            for(int i=1;i<=n;i++)
            {
                scanf("%Lf %Lf %Lf",&x,&y,&R1);
                long double l=sqrt(x*x+y*y);
                if(R0>=l+R1)    continue;
                if(l>=R0+R1)    continue;
                if(R1>=R0+l)    continue;
                long double a=acos((R0*R0+l*l-R1*R1)/(2*R0*l));
                L[l1].a1=atan2(x,y)-a+pi;
                L[l1].a2=atan2(x,y)+a+pi;
               // if(L[l1].a1<=0) L[l1].a1+=2*pi,L[l2].a2+=2*pi;
                int flag=0;
                for(int j=0;j<l1;j++)
                {
                    if(L[j].a2>=L[l1].a2&&L[j].a1<=L[l1].a1)    flag=1;
                }
                if(flag)    continue;
                //cout<<L[l1].a1<<' '<<L[l1].a2<<endl;
                l1++;
            }
            long double ans=-1;
            for(int i=0;i<l1;i++)
            {
                long double t=L[i].a1+pi;
    
                int flag=0;
                for(int j=0;j<l1;j++)
                {
                    if((L[j].a1<=t&&L[j].a2>=t))
                    {
          if(flag) while(1);
                        flag=1;
                        ans=max(ans,max(fabs(sin(fabs(L[i].a1-L[j].a1)/2)),fabs(sin(fabs(L[i].a1-L[j].a2)/2))));
                    }
                    if((L[j].a1<=t-2*pi&&L[j].a2>=t-2*pi))
                    {
          if(flag) while(1);
                        flag=1;
                        ans=max(ans,max(fabs(sin(fabs(L[i].a1-L[j].a1)/2)),fabs(sin(fabs(L[i].a1-L[j].a2)/2))));
                    }
                    if((L[j].a1<=t+2*pi&&L[j].a2>=t+2*pi))
                    {
          if(flag) while(1);
                        flag=1;
                        ans=max(ans,max(fabs(sin(fabs(L[i].a1-L[j].a1)/2)),fabs(sin(fabs(L[i].a1-L[j].a2)/2))));
                    }
                    //cout<<L[i].a1<<' '<<L[j].a1<<' '<<sin(fabs(L[i].a1-L[j].a2)/2)<<' '<<ans<<endl;
                }
    
                if(!flag)   ans=1;
                t=L[i].a2+pi;
                //cout<<t<<' '<<t-2*pi<<endl;
                flag=0;
                for(int j=0;j<l1;j++)
                {
                    if((L[j].a1<=t&&L[j].a2>=t))
                    {
          if(flag) while(1);
                        flag=1;
                        ans=max(ans,max(fabs(sin(fabs(L[i].a2-L[j].a1)/2)),fabs(sin(fabs(L[i].a2-L[j].a2)/2))));
                    }
                    if((L[j].a1<=t-2*pi&&L[j].a2>=t-2*pi))
                    {
          if(flag) while(1);
                        flag=1;
                        ans=max(ans,max(fabs(sin(fabs(L[i].a2-L[j].a1)/2)),fabs(sin(fabs(L[i].a2-L[j].a2)/2))));
                    }
                    if((L[j].a1<=t+2*pi&&L[j].a2>=t+2*pi))
                    {
                        if(flag) while(1);
                        flag=1;
                        ans=max(ans,max(fabs(sin(fabs(L[i].a2-L[j].a1)/2)),fabs(sin(fabs(L[i].a2-L[j].a2)/2))));
                    }
                    //cout<<i<<' '<<j<<' '<<ans<<endl;
                }
                //cout<<flag<<endl;
                if(!flag)   ans=1;
            }
            printf("Case #%d: %.11Lf\n",cas++,2*fabs(ans)*R0);
        }
    
        return 0;
    }

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

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif
[2018ICPC _ E]: https://www.cnblogs.com/Hugh-Locke/p/11342318.html