cf掉分记——Avito Code Challenge 2018-白红宇

cf掉分记——Avito Code Challenge 2018

阅读量：4706 次

发布时间：2019-06-10

本文共 3090 字，大约阅读时间需要 10 分钟。

再次作死的打了一次cf的修仙比赛感觉有点迷。。

还好掉的分不多（原本就太低没法掉了QAQ）

把会做的前三道水题记录在这。。

emmmm...直接暴力枚举

code：

//By Menteur_Hxy#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;int n,ans;char ch[100];bool jud(int l,int len) {    int r=l+len-1;    for(int i=0;i<(len>>1);i++)         if(ch[l+i]!=ch[r-i]) return 1;    return 0;}bool check(int len) {    for(int i=1;i+len-1<=n;i++)         if(jud(i,len)) return 1;    return 0;}int main() {    scanf("%s",ch+1);    n=strlen(ch+1);    for(int i=n;i>1;i--) {        if(check(i)) {ans=i;break;}    }    if(!ans) printf("0");    else printf("%d",ans);    return 0;}

用map直接上记下每个元素的最大值最后加起来

code:

//By Menteur_Hxy#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #define M(a,b) memset(a,(b),sizeof(a))#define F(i,a,b) for(register int i=(a);i<=(b);i++)#define LL long longusing namespace std;LL rd() {    LL x=0,fla=1; char c=' ';    while(c<'0'||c>'9') {c=getchar();if(c=='-') fla=-fla;}    while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();    return x*fla;}map 
         
           M;int main() { int n=rd(); F(i,1,n) { int x=rd(),y=rd(); M[x]=y; } int m=rd(); F(i,1,m) { int x=rd(),y=rd(); if(M.count(x)) { M[x]=max(M[x],y); }else { M[x]=y; } } LL ans=0; for(map
          
           ::iterator it=M.begin(); it!=M.end();it++) { if(it->second) ans+=it->second; } printf("%lld",ans); return 0;}

题面略迷。。

大概意思是找到一种方式分配他所给你的一些边使组成一些简单路径要求每两条简单路径都有一个公共点

保证给出的边组成一棵树，输出路径数和每条路径的起点和终点（顺序无所谓）~~这么水的题题面就让我看了半天QAQ~~

显然考虑只有一个公共点，记录每个点连着几条边然后分情况：

1.如果有两个点连着超过两条边说明无法完成

2.如果仅有一个点连边超过两条答案为以它为端点的所有简单路径

3.如果无连边超过两条的那么只有一条简单路径且两个只连一条边的点为两端点

code: (略暴力)

//By Menteur_Hxy#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #define M(a,b) memset(a,(b),sizeof(a))#define F(i,a,b) for(register int i=(a);i<=(b);i++)#define LL long longusing namespace std;inline LL rd() { LL x=0,fla=1; char c=' '; while(c>'9'|| c<'0') {if(c=='-') fla=-fla; c=getchar();} while(c<='9' && c>='0') x=x*10+c-'0',c=getchar(); return x*fla;}inline void out(LL x){ int a[25],wei=0; if(x<0) putchar('-'),x=-x; for(;x;x/=10) a[++wei]=x%10; if(wei==0){ puts("0"); return;} for(int j=wei;j>=1;--j) putchar('0'+a[j]); putchar('\n');}const int N=10010;const int INF=0x3f3f3f3f;int n,rt,cnt;int du[N],head[N];struct edges{ int to,next;}e[N<<2];void add(int x,int y) { e[++cnt].next=head[x]; e[cnt].to=y; head[x]=cnt;}int dfs(int x,int pre) { for(int i=head[x];i;i=e[i].next) { int v=e[i].to; if(v!=pre) return dfs(v,x); } return x;}int main() { n=rd(); F(i,1,n-1) { int u=rd(),v=rd(); add(u,v);add(v,u); du[u]++,du[v]++; } F(i,1,n) if(du[i]>2) rt=i; F(i,1,n) if(du[i]>2&&i!=rt) { printf("No"); return 0; } if(!rt) { printf("Yes\n1\n"); F(i,1,n) if(du[i]==1) printf("%d ",i); return 0; } printf("Yes\n%d\n",du[rt]); for(int i=head[rt];i;i=e[i].next) { int v=e[i].to; printf("%d %d\n",rt,dfs(v,rt)); } return 0;}