slove 6/11

 

Code:zz

Thinking:zz

贪心即可。这条路线里，点n1和点n2肯定是相连的，接下来，点（n-1）1和点（n-1）2分别是和n1和点n2相连的，一共有两种情况，选择距离短的即可，就这样一直往前贪心。

//#pragma comment(linker, "/STACK:102400000,102400000")#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
             
            
           
          
         
        
       
      

 

Code:kk

Thinking:kk zz

用树形dp找每个联通块 树的直径，树的直径大于等于4的就肯定不行，有孤立的点也不行，就这样。

然而别人都是用结论做的，每条边连上去后，边两边的点只能有一个入度大于1.

我就是个弟弟。

#include
      
       #define CLR(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;const int maxn=200010;const int inf=0x3f3f3f3f;int fa[maxn],n,m;bool vis[maxn];int head[maxn],tot;struct edge{    int to,Next;}a[maxn<<2];void init() {    CLR(vis,0);    CLR(head,-1),tot=0;}void addv(int u,int v){    a[++tot].to=v;    a[tot].Next=head[u];    head[u]=tot;}int u,v,maxx;int dfs(int u,int deep,int fa){//    printf("u:%d\n",u);    int fmax=0,smax=0;    vis[fa]=1;    for(int i=head[u];i!=-1;i=a[i].Next)    {        int v=a[i].to;        if(v==fa)continue;        if(vis[v]==1)        {            maxx=inf;            return inf;        }        vis[v]=1;        int tep=dfs(v,deep+1,u);        if(fmax==0)fmax=max(fmax,tep);        else if(smax==0){            smax=tep;            if(fmax
       
        fmax){            smax=fmax,fmax=tep;        }else if(tep>smax){            smax=tep;        }    }//    printf("u:%d\n",u);//    printf("maxx:%d\n",maxx);//    printf("fmax:%d  smax:%d\n",fmax,smax);    maxx=max(maxx,max(fmax+smax,fmax+deep));    if(maxx>=inf)return inf;    return fmax+1;}int main() {    while(cin>>n>>m) {        init();        while(m--) {            scanf("%d%d",&u,&v);            addv(u,v),addv(v,u);        }        for(int i=1;i<=n;i++)        {            if(vis[i]==0)            {                dfs(i,0,-1);            }            if(maxx>=3)            {                break;            }        }        for(int i=1;i<=n;i++)        {            if(vis[i]==0){                puts("No\n");                return 0;            }        }        if(maxx>=3){            printf("No\n");        }else{            puts("Yes");        }    }}
       
      

 

题解待补。

 

Code:zz

Thinking:zz

马是走日字的，因此走一步后，他所在的格子的颜色和上一格肯定是不一样的，因此，如果他的起点颜色和终点颜色是一样的，那么肯定是No；如果颜色是一样的，那么只要起点和终点是互相可达的，那么是Yes，反之是No。除了3*3的棋盘和2*n的棋盘需要判断是否可达外，其他都能可达。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
             
            
           
          
         
        
       
      

 

Code：pai爷

Thinking：pai爷

dp，注意到上凸和下凸的答案是一样的，从下到大枚举插入的数用组合数搞一下方案

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;typedef long long ll;const int p=1e9+7;ll dp[1010],sum[1010],fac[1010],inv[1010];ll qpow(ll a,ll b){ ll ret=1;a%=p; while(b) { if(b&1) ret=ret*a%p; b/=2;a=a*a%p; } return ret;}ll C(ll n,ll m){ if(m>n) return 0; return 1ll * fac[n] * inv[m] % p * inv[n - m] % p;} int main(){ fac[0]=1;inv[0]=1; for(int i=1;i<=1000;i++) { fac[i]=1ll*fac[i-1]*i%p; inv[i]=qpow(fac[i],p-2); } int n; scanf("%d",&n); dp[0]=dp[1]=1; sum[1]=1; for(int i=2;i<=n;i++) { sum[i]=0; for(int j=1;j<=i;j++) { sum[i]=(sum[i]+dp[j-1]*dp[i-j]%p*C(i-1,j-1)%p) %p; } dp[i]=sum[i]*qpow(2,p-2)%p; } printf("%lld\n",dp[n]); return 0;}
           
          
         
        
       
      

 

Code：pai爷

Thinking：pai爷

一个裸的贪心，计算一下式子枚举保留了k个物品，之后sort一下。取前k个。

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;struct node{ int c,id;}sum[1010];int a[1010],b[1010];long long p,q,ans=0;int n;bool cmp(node a,node b){ return a.c>b.c;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); } for(int k=1;k<=n;k++) { p=0;q=0; for(int i=1;i<=n;i++) { sum[i].c=a[i]-k*b[i]; sum[i].id=i; } sort(sum+1,sum+1+n,cmp); for(int i=1;i<=k;i++) { p=p+a[sum[i].id]; } for(int i=k+1;i<=n;i++) { q=q+b[sum[i].id]; } ans=max(ans,p+1ll*q*k); } printf("%lld\n",ans);}
           
          
         
        
       
      

 

Code:kk zz

Thinking:kk

选取的两条链交点是x，所以就是选取和x有关的两条大链，而且查询次数非常少，所以就是求每个节点的四条子链的总和，如果子链为负数，则不取。

#include
      
       #define CLR(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;const int maxn=100010;const int inf=0x3f3f3f3f;int n,m;bool vis[maxn];int head[maxn],tot;struct edge{    int to,Next;}a[maxn<<2];ll val[maxn];ll pre[40];void init() {    CLR(vis,0);    CLR(head,-1),tot=0;    pre[1]=1;    for(int i=2;i<=30;i++)    {        pre[i]=pre[i-1]*2;    }}void addv(int u,int v){    a[++tot].to=v;    a[tot].Next=head[u];    head[u]=tot;}int u,v;ll son[maxn][4];ll dfs(int u,int fa){    for(int i=head[u];i!=-1;i=a[i].Next)    {        int v=a[i].to;        if(v==fa)continue;        ll tep=dfs(v,u);        int flag = 1;        for(int j=0;j<4;j++)        {            if(son[u][j]==0){                son[u][j]=tep;                flag = 0;                break;            }        }        sort(son[u],son[u]+4);        if(son[u][0]
       
        >n) {        init();        for(int i=1;i<=n;i++)        {            scanf("%d",&u);            if(u>=0)            {                val[i]=pre[u];            }else{                val[i]=-pre[-u];            }        }                for(int i=1;i
        
         >q;        while(q--)        {            memset(son,0,sizeof(son));            scanf("%d",&u);            dfs(u,-1);            ll ans=val[u];            for(int i=0;i<4;i++)            {                ans+=max((ll)0,son[u][i]);                //printf("%lld ",son[u][i]);            }            //printf("\n");            //printf("%lld\n",ans);            int op= (ans<0);            if(ans < 0)            {                ans = -ans;            }            int cc[100],cnt = 0;            while(ans)            {                cc[cnt++] = ans %2;                ans /= 2;            }            if(op)            {                printf("-");            }            if(cnt == 0)            {                printf("0");            }            for(int i = cnt - 1;i >= 0;i--)            {                printf("%d",cc[i]);            }            printf("\n");        }    }}
        
       
      

 

---

 

赛后总结：

kk：今天有蛮多图的题目的，但是读c题的题意没读懂，别人用简单结论一小时不到就做出的题目，我写了树形dp求树的直径两小时后才ac，k题也是个树形dp的题，套了上一题的代码，结果int忘记改成long long了，wawawawawa，贼菜，把队友的腿都给抱断了。

pai爷：今天状态很差，那道DP题一直在想DP[i][j]表示枚举到第i个位置填了j的方案数，但是无法满足排列，想了很久才写出来，之后那道欧拉回路的时间不多了，找规律的题还是缺少一个系统的操作，最后时刻还是没有写出来。

zz：今天很快写掉了两个签到题，然后帮队友看c题，看了很久没看出来，后来发现题读错了，然后又一起看了k，做法很快就出了，代码打出来以后要出了很多bug，wa了很多次，改了很久才过，写代码还是要仔细点，不然小bug改到死。