终于拿到衣服了，算是小小的圆梦了。进决赛，还是太naive了，菜鸟再好好努力吧。

退役狗一枚，即将研一，今年的icpc无法（不）打了，算是小小的遗憾吧。。。

以后打比赛的次数也能也会少很多了，毕竟读研究生，菜鸟要搞'科研'了。。。。。。

打完csp，再参加一下hust的校赛（maybe），应该就没有然后了。。。。。

 

P.S.:

我也想参加一下像今天银川这样的ICPC网络赛，享受一下AK的感觉~~~

祝lzu ICPC/CCPC成绩越来越好吧。。。。。。

 

1001

我写的是树上dp，应该不是正解。

前6分钟看前两题。然后9分钟写一个长达七十多行(-头文件)的代码，小小的成就感，以前手速没这么快。

感觉大佬们真是手速快，第6~8分钟时，已经有几十个对了。

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=1e5+10; 15 16 struct node 17 { 18 int d; 19 node *to; 20 }*e[maxn]; 21 22 bool vis[maxn]; 23 ll l[maxn],r[maxn],vl[maxn],vr[maxn]; 24 25 void dfs(int d) 26 { 27 int dd; 28 vl[d]=vr[d]=0; 29 vis[d]=1; 30 node *p=e[d]; 31 while (p) 32 { 33 dd=p->d; 34 if (!vis[dd]) 35 { 36 dfs(dd); 37 vl[d]+=max(vl[dd]+abs(l[d]-l[dd]) , vr[dd]+abs(l[d]-r[dd])); 38 vr[d]+=max(vl[dd]+abs(r[d]-l[dd]) , vr[dd]+abs(r[d]-r[dd])); 39 } 40 p=p->to; 41 } 42 } 43 44 int main() 45 { 46 node *p; 47 int t,n,i,x,y; 48 scanf("%d",&t); 49 while (t--) 50 { 51 scanf("%d",&n); 52 for (i=1;i<=n;i++) 53 e[i]=0; 54 for (i=1;i
            
             d=y; 59 p->to=e[x]; 60 e[x]=p; 61 62 p=new node(); 63 p->d=x; 64 p->to=e[y]; 65 e[y]=p; 66 } 67 68 for (i=1;i<=n;i++) 69 scanf("%lld%lld",&l[i],&r[i]); 70 71 memset(vis,0,sizeof(vis)); 72 dfs(1); 73 printf("%lld\n",max(vl[1],vr[1])); 74 } 75 return 0; 76 } 77 /* 78 3 79 5 80 1 2 81 2 3 82 3 4 83 4 5 84 1 5 85 2 7 86 7 9 87 5 8 88 3 4 89 90 5 91 1 2 92 2 3 93 3 4 94 4 5 95 1 5 96 2 7 97 7 9 98 5 8 99 3 4100 101 4102 1 2103 1 3104 2 4105 1 3106 3 4107 1 3108 -1 3109 */110 111 112
            
           
          
         
        
       
      
     

 

1003

一开始想着从小到大，1,2,...依次确定位置。

换了一个思路，二叉树，一个点所在的子树，其编号是连续的。要确定先分配给左子节点所在的子树还是先分配给右子节点所在的子树，详见代码。

编号从小到大

左子树 + 根节点 + 右子树

or

右子树 + 根节点 + 左子树

 

memset导致两个WA，真是尴尬。

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=2.5e6+10; 15 16 int e[maxn][2]; 17 18 bool vis[maxn],ro[maxn]; 19 int siz[maxn],minp[maxn],v[maxn]; 20 ll c233[maxn]; 21 22 void dfs(int d) 23 { 24 int dd,i; 25 vis[d]=1; 26 minp[d]=d; 27 siz[d]=1; 28 29 for (i=0;i<2;i++) 30 { 31 dd=e[d][i]; 32 // if (!dd) 33 // continue; 34 if (!vis[dd]) 35 { 36 dfs(dd); 37 siz[d]+=siz[dd]; 38 minp[d]=min(minp[d],minp[dd]); 39 } 40 } 41 } 42 43 void work(int d,int l) 44 { 45 int cond; 46 47 if (d==minp[d]) 48 { 49 if (siz[e[d][0]] < siz[e[d][1]]) 50 cond=0; 51 else if (siz[e[d][0]] > siz[e[d][1]]) 52 cond=1; 53 else if (minp[e[d][0]] < minp[e[d][1]]) 54 cond=0; 55 else if (minp[e[d][0]] > minp[e[d][1]]) 56 cond=1; 57 } 58 else 59 { 60 if (minp[e[d][0]] < minp[e[d][1]]) 61 cond=0; 62 else if (minp[e[d][0]] > minp[e[d][1]]) 63 cond=1; 64 } 65 66 if (cond==0) 67 { 68 if (e[d][0]) 69 work(e[d][0],l); 70 v[d]=l+siz[e[d][0]]; 71 if (e[d][1]) 72 work(e[d][1],l+1+siz[e[d][0]]); 73 } 74 else 75 { 76 if (e[d][1]) 77 work(e[d][1],l); 78 v[d]=l+siz[e[d][1]]; 79 if (e[d][0]) 80 work(e[d][0],l+1+siz[e[d][1]]); 81 } 82 83 } 84 85 int main() 86 { 87 int t,n,i,x,root; 88 ll sum; 89 90 c233[0]=1; 91 for (i=1;i<=2500000;i++) 92 c233[i]=c233[i-1]*233%mod; 93 minp[0]=1e9; 94 95 scanf("%d",&t); 96 while (t--) 97 { 98 scanf("%d",&n); 99 // memset(ro,0,sizeof(ro));100 for (i=1;i<=n;i++)101 ro[i]=0;102 103 for (i=1;i<=n;i++)104 {105 scanf("%d",&x);106 e[i][0]=x;107 if (x!=0)108 ro[x]=1;109 110 scanf("%d",&x);111 e[i][1]=x;112 if (x!=0)113 ro[x]=1;114 }115 for (root=1;root<=n;root++)116 if (!ro[root])117 break;118 119 // memset(vis,0,sizeof(vis));120 for (i=1;i<=n;i++)121 vis[i]=0;122 123 vis[0]=1;124 dfs(root);125 126 work(root,1);127 128 sum=0;129 for (i=1;i<=n;i++)130 (sum+=(v[i]^i)*c233[i])%=mod;131 printf("%lld\n",sum);132 }133 return 0;134 }135 /*136 5137 138 5139 0 0140 0 0141 0 4142 2 0143 1 3144 145 5146 0 0147 0 0148 0 4149 2 0150 1 3151 152 1153 0 0154 155 2156 0 0157 1 0158 159 5160 0 0161 0 0162 0 4163 2 0164 1 3165 166 167 1168 8169 3 4170 7 6171 0 0172 0 0173 1 2174 0 0175 0 8176 0 0177 178 1179 3180 3 2181 0 0182 0 0183 184 1185 3186 2 3187 0 0188 0 0189 190 1191 5192 2 3193 5 4194 0 0195 0 0196 0 0197 */198 199 200
           
          
         
        
       
      
     

 

1002

环境有点吵，再加上没什么思路，卡了半天……

一开始想的是矩阵的乘积，然后就没有然后了。

觉得这么多人过很可怕，再加上想了很久没什么思路，于是果断打了一个表。

于是发现规律了。

比赛结束5分钟的时候A，心情大起大落。毕竟我很少比赛结束前A题，更多的是赛后1~2分钟A题，参见CodeForces。

感觉纯想出来/证明较难，也许是我太菜了。

 

1 5 11 2  3 -97 95 4 -85 11 5 -79 17 6 -73 23 7 -67 29 8 -61 35 9 -55 4110 -49 4711 -43 5312 -37 1113 -37 5914 -31 1715 -31 6516 -25 2317 -25 7118 -19 2919 -19 7720 -13 1121 -13 3522 -13 8323 -7 1724 -7 4125 -7 8926 -1 1127 -1 2328 -1 4729 -1 9530 5 1131 5 1732 5 2933 5 53

 

 

 

 

 

 

 

 

 

 

打表

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6 #include 
          
            7 #include 
           
             8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=5e3;///5e3 15 int z=100; 16 17 bool vis[maxn*2+10][maxn*2+10]; 18 19 void dfs(int x,int y,int u,int v) 20 { 21 if (abs(x)>=maxn || abs(y)>=maxn) 22 return; 23 if (vis[x+maxn][y+maxn]) 24 { 25 if (abs(x)<=z && abs(y)<=z) 26 printf("completed %d %d <- %d %d\n",x,y,u,v); 27 return; 28 } 29 if (abs(x)<=z && abs(y)<=z) 30 printf("%d %d <- %d %d\n",x,y,u,v); 31 vis[x+maxn][y+maxn]=1; 32 dfs(x,y*2-x,x,y); 33 dfs(2*x-y,y,x,y); 34 } 35 36 int main() 37 { 38 int x,y,i,j; 39 // x=5,y=5;///same only 5 5 40 // x=5,y=10;///gcd(5,10)=5 41 x=6,y=7; 42 dfs(x,y,x,y); 43 // for (i=-z;i<=z;i++) 44 // for (j=-z;j<=z;j++) 45 // if (vis[i+maxn][j+maxn]) 46 // printf("%d %d\n",i,j); 47 return 0; 48 }
           
          
         
        
       
      
     

 

 

代码

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 #include 
        
           5 #include 
         
            6 #include 
          
            7 #include 
           
             8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const ll inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=1e5+10; 15 16 int op[1000]; 17 char pr[5]="AB"; 18 19 void work() 20 { 21 ll a,b,c,d,cha,aa,bb,e; 22 int cond,i,ans,tot; 23 scanf("%lld%lld%lld%lld",&a,&b,&c,&d); 24 if (a==b) 25 { 26 if (c==d && a==c) 27 { 28 printf("Yes\n"); 29 printf("\n"); 30 return; 31 } 32 else 33 { 34 printf("No\n"); 35 return; 36 } 37 } 38 39 if (a>b) 40 { 41 cond=1; 42 swap(a,b); 43 swap(c,d); 44 } 45 else 46 cond=0; 47 cha=b-a; 48 49 if ((a-c)%cha!=0 || c>a) 50 { 51 printf("No\n"); 52 return; 53 } 54 55 e=(a-c)/cha; 56 tot=0; 57 while (e) 58 { 59 op[++tot]=(e&1); 60 e>>=1; 61 } 62 // for (i=tot;i>=1;i--) 63 for (i=1;i<=tot;i++) 64 if (op[i]==0) 65 { 66 aa=a; 67 bb=2*b-a; 68 69 a=aa; 70 b=bb; 71 } 72 else 73 { 74 aa=2*a-b; 75 bb=b; 76 77 a=aa; 78 b=bb; 79 } 80 81 ans=0; 82 while (b
            
             =1;i--) 92 for (i=1;i<=tot;i++) 93 printf("%c",pr[op[i]^cond]); 94 for (i=1;i<=ans;i++) 95 printf("%c",pr[0^cond]); 96 printf("\n"); 97 return; 98 } 99 else100 {101 printf("No\n");102 return;103 }104 }105 106 int main()107 {108 int t;109 scanf("%d",&t);110 while (t--)111 {112 work();113 }114 return 0;115 }116 /*117 1000118 1 0 3 -1119 5 11 -1 23120 5 11 -25 23121 5 11 -25 71122 5 11 -37 11123 5 11 -19 77124 5 11 -67 29125 126 127 100128 5 11 -19 77129 130 */
            
           
          
         
        
       
      
     

 

1004

稍微看了一下,但由于被1002卡住了，没细想。

以下纯属yy：

a_{i}分为c_{i}和非c_{i}。

if c_{i} >c_{i+1}，

则a_{i}不能为c_{i}。

每个数都有它的上限。受到前面的数和c_{i}的影响。

感觉能推导出若干个关系式，形成一个图之类。

毕竟c_{i}太大，不可能求每一个数为确定数值时的情况数目。