首页 > 其他 > 详细

春训团队赛补题

时间：2019-07-08 09:12:24      阅读：67      评论：0      收藏：0      [点我收藏+]

第一场

第二场

第三场

第四场

题目链接

题解链接

代码&简易题解（有待补充）

A

按照题意对图预处理，得到一棵树，对于每对询问求LCA的同时求距离，累加即为答案。

注意离散化操作带来的越界问题。。。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#define N 1000010

using namespace std;

char a, str[2005];
char s[2005][2005];


int n, m,lsum=1,L=0,i,j,k,x,y,cnt;
long long Ans;
int head[2*N],v[2*N],d[2*N];
int f[N][22],p[22];
int q[10010],Q[10010];

struct Egde{
    int t,next;
}e[N*8];

vector <int> son[N];
map <int,int> M;

char sw(char a) {
    if (a == ' ') return 'k';
    if (a == '_') return 'h';
    if (a == '|') return 's';
    if (a == '  ') return 'z';
    if (a == '\n') return '\n';
}

int ID(int x, int y) {
    if (M[x*10000+y])   return M[x*10000+y];
    else {
        ++cnt;
        M[x*10000+y]=cnt;
        return cnt;
    }
}

inline void Swap(int &x,int &y){x^=y^=x^=y;}

inline void add(int s,int t){
    e[lsum].t=t;    e[lsum].next=head[s];   head[s]=lsum++;
    e[lsum].t=s;    e[lsum].next=head[t];   head[t]=lsum++;
}

inline void Maketree(int x){
    int i=0;
    v[x]=1;
    for (i=head[x];i;i=e[i].next){
        if (v[e[i].t])  continue;
        f[e[i].t][0]=x; d[e[i].t]=d[x]+1;
        Maketree(e[i].t);   son[x].push_back(e[i].t);
    }
}

inline void Dfs(int x){
    int i=0,s=0;
    for (i=1;i<=20;i++) f[x][i]=f[f[x][i-1]][i-1];
    if (!son[x].size()) return;
    for (s=son[x].size(),i=0;i<s;i++)   Dfs(son[x][i]);
}

inline int LCA(int x,int y){
    int l=0,i=0;    L=0;
    if (d[x]<d[y])  Swap(x,y);
    l=d[x]-d[y];
    for (i=0;i<=20;i++)
        if (l&p[i]) x=f[x][i];
    L=l;
    if (x==y)   return x;
    for (i=20;i>=0;i--)
        if (f[x][i]!=f[y][i]){
            L+=2*p[i],x=f[x][i],y=f[y][i];
        }
    L+=2;
}

int main(){
    scanf("%d%d\n", &n, &m);
    for (i = 1; i <= 2*m+1; i++) scanf("%c", &a);
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= 2*m+2; j++) scanf("%c", &s[i][j]);
    }
    for (i = 1; i <= n; i++) {
        int l = 0;
        for (j = 3; j <= 2*m-1; j+=2) {
            l++;
            if (s[i][j] == ' ') add(ID(i, l), ID(i, l+1));
        }
    }
    for (i = 1; i < n; i++) {
        int l = 0;
        for (j = 2; j <= 2*m; j+=2) {
            l++;
            if (s[i][j] == ' ') add(ID(i, l), ID(i+1, l));
        }
    }
    for (i=1,p[0]=1;i<=20;i++)  p[i]=p[i-1]*2;
    d[ID(1,1)]=1;   Maketree(ID(1,1));  Dfs(ID(1,1));
    scanf("%d",&k);
    for (i=1;i<=k;i++)      scanf("%d%d",&q[i],&Q[i]);
    for (i=1;i<k;i++){
        x=ID(q[i],Q[i]);    y=ID(q[i+1],Q[i+1]);
        LCA(x,y);   Ans+=L;
    }
    cout<<Ans<<endl;
    return 0;
}

B

先求两点与红圈切线长度，以此求得两切点间的弧上距离，答案为该距离加两切点到两点的距离。

注：int会带来奇怪的精度问题

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdlib>
#include<cmath>
using namespace std;

inline double Sqr(double x){
    return (double)1.0*x*x;
}

inline double Dis(double a,double b,double c,double d){
    return (sqrt(Sqr(a-c)+Sqr(b-d)));
}

double X1,X2,X3,X4,Y1,Y2,Y3,Y4,r1,r2;
double d1,d2,d3,dis1,dis2,p,Ans;
double J1,J2,J3;

int main(){
    scanf("%lf%lf",&X1,&Y1);
    scanf("%lf%lf",&X2,&Y2);
    scanf("%lf%lf%lf",&X3,&Y3,&r1);
    scanf("%lf%lf%lf",&X4,&Y4,&r2);
    d1=Dis(X1,Y1,X4,Y4);
    d2=Dis(X2,Y2,X4,Y4);
    d3=Dis(X1,Y1,X2,Y2);
    double hh=sqrt(Sqr(d1)-Sqr(d3/2));
    J1=acos((double)1.0*r2/d1);
    J2=acos((double)1.0*r2/d2);
    p=1.0*Sqr(d1)+Sqr(d2)-Sqr(d3);
    p/=2.0*d1*d2;
    J3=acos(p);
    dis1=sqrt(Sqr(d1)-Sqr(r2));
    dis2=sqrt(Sqr(d2)-Sqr(r2));
    Ans=dis1+dis2+(double)1.0*r2*(J3-J1-J2);
    printf("%.10lf\n",Ans);
    return 0;
}

C

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

int ans = 0, anss[50005];
int tot, adj[50005], fir[50005], nxt[50005], w[50005];

void add(int a, int b, int c) {
    adj[++tot] = b;
    nxt[tot] = fir[a];
    fir[a] = tot;
    w[tot] = c;
    return ;
}

int ask(int a) {
    if (anss[a]) return anss[a];
    int now = 0;
    for (int t = fir[a]; t; t = nxt[t]) {
        now = max(now, w[t]+ask(adj[t]));
    }
    anss[a] = now;
    return now;
}

int main()
{
    int n, m, a, b, c;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c);
    }
    for (int i = 1; i <= n; i++) {
        ans = max(ans, ask(i));
    }
    cout << ans << endl;
    return 0;
}

D

设第一项为x，以此求得之后的每一项，根据非负这一条件求x的范围(或者无解)

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdlib>
#define N 1000010
#define LL long long
#define INF 0x3f3f3f3f
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
using namespace std;

int n,i,cnt;
LL up,down;
LL a[N],z[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline LL Min(LL a,LL b){return (a<b)?a:b;}
inline LL Max(LL a,LL b){return (a>b)?a:b;}

inline int read(){
    int p=0,c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

int main(){
//  freopen("zht.in","r",stdin);
//  freopen("zht.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++)  scanf("%lld",&a[i]);
    z[++cnt]=0;
    for (i=1;i<=n;i++){
        z[cnt+1]=a[i]-z[cnt];   cnt++;
    }
    down=-INF*2;    up=INF*2;
    for (i=1;i<=n+1;i++)
        if (i%2)    down=Max(down,-z[i]);
        else up=Min(up,z[i]);
    if (up>=down)   cout<<up-down+1<<endl;
    else cout<<"0"<<endl;
    return 0;
}

E

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>

using namespace std;

int prime[10000005], noprime[10000005], cnt_p;

void Euler(int top) {
    int i, j;
    for (i = 2; i <= top; i++) {
        if (!noprime[i])
            prime[++cnt_p] = i;
        for (j = 1; j <= cnt_p && prime[j]*i <= top; j++) {
            noprime[prime[j]*i] = true;
            if (i%prime[j]==0) {
                break;
            }
        }
    }
    return ;
}

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a%b);
} 

char s[100];
int get() {
    scanf("%s", s);
    int len = strlen(s);
    int point = 0;
    for (int i = 0; i < len; i++)
        if (s[i] == '.') {
            point = i;
            break;
        }
    if (point == 0) {
        int ans = 0;
        int now = 100000;
        for (int i = len - 1; i >= 0; i--) {
            ans += now*(s[i]-'0');
            now *= 10;
        }
        return ans;
    } else {
        int ans = 0;
        int now = 100000;
        for (int i = point - 1; i >= 0; i--) {
            ans += now*(s[i]-'0');
            now *= 10;
        }
        now = 10000;
        for (int i = point + 1; i < len; i++) {
            ans += now*(s[i]-'0');
            now /= 10;
        }
        return ans;
    }
}

int main(){
    int n;
    double a, b;
    Euler(10000000);
    noprime[1] = true;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int aa = get();
        int bb = get();
        int g = gcd(aa, bb);
        aa /= g; bb /= g;
        if (aa == bb) {
            printf("2 2\n");
            continue ;
        }
        if (noprime[aa]||noprime[bb]) {
            printf("impossible\n");
            continue ;
        } else {
            printf("%d %d\n", aa, bb);
        }
    }
    return 0;
}

F

根据题意，有且仅有斐波那契相邻两项符合要求

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdlib>
#define N 100010
#define LL long long
#define INF 0x3f3f3f3f
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
using namespace std;

int n,i,flag;
int a[N],b[30*N],d[30*N];

vector <int> c[30*N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

int main(){
//  freopen("zht.in","r",stdin);
//  freopen("zht.out","w",stdout);
    scanf("%d",&n);
    for (i=1;i<=n;i++)  scanf("%d",&d[i]);  
    a[1]=1; a[2]=2;
    for (i=3;i<=30;i++) a[i]=a[i-1]+a[i-2];
    for (i=1;i<=30;i++) b[a[i]]=1;
    for (i=1;i<=n;i++)  c[d[i]].push_back(i);
    if (c[1].size()>=2){
        cout<<c[1][0]<<" "<<c[1][1]<<endl;
        return 0;
    }
    for (i=1;i<30;i++)
        if (c[a[i]].size()&&c[a[i+1]].size()){
            cout<<c[a[i]][0]<<" "<<c[a[i+1]][0]<<endl;
            return 0;
        }
    cout<<"impossible"<<endl;
    return 0;
}

G

有待填坑

H

#include <cstdio>
#define LL long long

const LL INF = 10000000000000000;

int main()
{
    LL x, n;
    scanf("%lld", &x);
    int a1, a2;
    bool ok = false;
    for (int p=2; p<59; ++p)
    {
        LL s = 0;
        for (int i=1; i<=INF; ++i)
        {
            LL pro = 1;
            for (int k=0; k<p; ++k)
            {
                pro *= i;
                if (pro > INF)
                    break;
            }
            if (pro > INF)
                break;
            s += pro;
            if (s == x)
            {
                a1 = p, a2 = i;
                ok = true;
                goto ex;
            }
        }
    }
    
    ex:;
    if (ok)
        printf("%d %d", a1+1, a2);
    else
        puts("impossible");
    
    return 0;
}

I

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdlib>
#define LL long long
#define INF 0x3f3f3f3f
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
using namespace std;

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

int a[12345], b[12345];

int main(){
//  freopen("zht.in","r",stdin);
//  freopen("zht.out","w",stdout);
    int n;
    scanf("%d", &n);
    for (int i=0; i<n; ++i)
        scanf("%d", a+i);
    for (int i=0; i<n; ++i)
        scanf("%d", b+i);
    
    if (a[0] > b[0])
        return puts("0"), 0;

    int dis = b[0]-a[0];
    for (int i=0; i<n; ++i)
        a[i] += dis;
    
    bool ok = false, ne = false;
    for (int i=0; i<n; ++i)
        if (a[i] != b[i])
            ne = true;
    if (!ne)
        return printf("%d", dis), 0;

    for (int i=0; i<n; ++i)
    {
        if (a[i] > b[i])
        {
            ok = true;
            break;
        }
        if (a[i] < b[i])
        {
            ok = false;
            break;
        }
    }
    printf("%d", dis+!ok);
    
    return 0;
}

J

有待填坑

K

有待填坑

L

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

int s[105][105];
int ans[105][105];
int map[105][105];

void clean(int a, int b) {
    s[a-1][b-1] --;
    s[a-1][b]--;
    s[a-1][b+1] --;
    s[a][b-1]--;
    s[a][b] --;
    s[a][b+1] --;
    s[a+1][b-1]--;
    s[a+1][b] --;
    s[a+1][b+1] --;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n+2; i++) 
        for (int j = 1; j <= m+2; j++)
            scanf("%d", &s[i][j]);
    for (int i = 1; i <= n+2; i++)
        for (int j = 1; j <= m+2; j++) {
            if (s[i][j] == 1) {
                map[i+1][j+1] = 1;
                clean(i+1, j+1);
            }
        }
    for (int i = 1; i <= n+3; i++) for (int j = 1; j <= m+3; j++) {
        if (s[i][j] < 0) {
            printf("impossible\n");
            return 0;
        }
    }
    for (int i = 1; i <= m+3; i++) if (map[1][i]||map[n+2][i]) {
        printf("impossible\n");
        return 0;
    }
    for (int i = 1; i <= n+3; i++) if (map[i][1]||map[i][m+2]) {
        printf("impossible\n");
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            if (map[i+1][j+1]) printf("X");
            else printf(".");
        cout << endl;
    }
    return 0;
}

M

首先在每两条边之间连边，边权为点权最大值，之后建一棵最小生成树，对于每次讯问，在生成树上求两点路径上边权最小值即可。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<cstdlib>
#define N 500010
#define LL long long
#define INF 0x3f3f3f3f
#define l(x) (x<<1)
#define r(x) ((x<<1)+1)
using namespace std;

int n,m,i,cnt,x,y,X,Y,L,lsum=1,q,j;
int head[N],fa[N],f[N][20],cost[N][20],v[N],d[N];
int a[510][510],p[20];

struct Tree{
    int x,y,l;
}t[N*2];

struct Edge{
    int t,next,l;
}e[N*4];

vector <int> son[N];

inline int Abs(int x){return (x<0)?-x:x;}
inline void Swap(int &x,int &y){x^=y^=x^=y;}
inline int Min(int a,int b){return (a<b)?a:b;}
inline int Max(int a,int b){return (a>b)?a:b;}

inline int read(){
    int p=0,c=getchar();
    while (c<48||c>57)  c=getchar();
    while (c>=48&&c<=57)    p=(p<<1)+(p<<3)+c-48,c=getchar();
    return p;
}

inline int ID(int x,int y){
    return  (x-1)*m+y;
}

bool cmp(Tree x,Tree y){
    return x.l<y.l;
}

inline int Find(int x){return (fa[x]==x)?x:fa[x]=Find(fa[x]);}

inline void Add(int s,int t,int l){
    e[lsum].t=t;    e[lsum].next=head[s];   e[lsum].l=l;    head[s]=lsum++;
    e[lsum].t=s;    e[lsum].next=head[t];   e[lsum].l=l;    head[t]=lsum++;
}

inline void Dfs(int x){
    int i=0,s=0;
    for (i=1;i<=18;i++){
        f[x][i]=f[f[x][i-1]][i-1];
        cost[x][i]=Max(cost[x][i-1],cost[f[x][i-1]][i-1]);
    }
    if (!son[x].size()) return;
    for (s=son[x].size(),i=0;i<s;i++)   Dfs(son[x][i]);
}

inline void Maketree(int x){
    int i=0;
    v[x]=1;
    for (i=head[x];i;i=e[i].next){
        if (v[e[i].t])  continue;
        cost[e[i].t][0]=e[i].l; f[e[i].t][0]=x; d[e[i].t]=d[x]+1;
        Maketree(e[i].t);   son[x].push_back(e[i].t);
    }
}

inline void Ready(){
    int i=0,j=0,P=0,q=0,s=0;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++){
            if (j<m)    t[++cnt]=(Tree){ID(i,j),ID(i,j+1),Max(a[i][j],a[i][j+1])};
            if (i<n)    t[++cnt]=(Tree){ID(i,j),ID(i+1,j),Max(a[i][j],a[i+1][j])};
        }
    sort(t+1,t+1+cnt,cmp);
    for (i=1;i<=n*m;i++)    fa[i]=i;
    for (i=1;i<=cnt;i++){
        P=Find(t[i].x); q=Find(t[i].y);
        if (P==q)   continue;
        s++;    fa[P]=q;    Add(t[i].x,t[i].y,t[i].l);
        if (s>=n*m-1)   break;
    }
    for (i=1,p[0]=1;i<=18;i++)  p[i]=p[i-1]*2;
    d[1]=1; Maketree(1);    Dfs(1);
}

inline int LCA(int x,int y){
    int l=0,i=0;    L=0;
    if (d[x]<d[y])  Swap(x,y);
    l=d[x]-d[y];
    for (i=0;i<=18;i++)
        if (l&p[i]) L=Max(L,cost[x][i]),x=f[x][i];
    if (x==y)   return x;
    for (i=18;i>=0;i--)
        if (f[x][i]!=f[y][i]){
            L=Max(L,cost[x][i]),L=Max(L,cost[y][i]),x=f[x][i],y=f[y][i];
        }
    L=Max(L,cost[x][0]);    L=Max(L,cost[y][0]);
}

int main(){
    scanf("%d%d%d",&n,&m,&q);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            scanf("%d",&a[i][j]);
    Ready();
    while (q--){
        x=read();   y=read();   X=read();   Y=read();
        if (x==X&&y==Y) {
            printf("%d\n",a[x][y]);
            continue;
        }
        x=ID(x,y);  y=ID(X,Y);
        LCA(x,y);   printf("%d\n",L);
    }
    return 0;
}

补题方案

A,M均为LCA+树上路径，值得补题

春训团队赛补题

原文：https://www.cnblogs.com/403-forbidden/p/11149116.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！