ÉèΪÊ×Ò³ ¼ÓÈëÊÕ²Ø

TOP

Codeforces Round #288 (Div. 2)
2015-07-20 17:22:59 À´Ô´: ×÷Õß: ¡¾´ó ÖРС¡¿ ä¯ÀÀ:1´Î
Tags£ºCodeforces Round #288 Div.

A,B,CË®

D¡£

ÓÐÒ»¸ö´®£¬³¤¶ÈΪn+2£¬

ÏÖÔÚÖªµÀËûµÄËùÓÐn¸ö ³¤¶ÈΪ3µÄ×Ó´®ÊÇʲô

Çó³öԭʼµÄ´®


ÕâÌâ¸úPOJ 2337ÓеãÏñ

×îºó³éÏó³öµÄÎÊÌâ¾ÍÊÇÇóÅ·À­Í¨Â·£º

½«Ã¿¸ö³¤¶ÈΪ3µÄ×Ó´®£¬ ǰÁ½¸ö×Öĸ(Êý×Ö£©¿´³ÉÒ»¸ö½áµã£¬ ºóÁ½¸ö×Öĸ(Êý×Ö£©¿´³ÉÒ»¸ö½áµã£¬

È»ºóÕâ¸ö×Ó´®¾ÍÏ൱ÓÚ Ò»Ìõ´Óǰһ¸ö½áµãµ½ºóÒ»¸ö½áµãµÄ±ß

Å·À­Í¨Â·µÄÒªÇó¾ÍÊÇËùÓб߶¼Òª×ßÒ»±é£¬ ËùÒÔ×îºó¾ÍÊÇÇóÅ·À­Í¨Â·ÁË

½áµãµÄ¸öÊý×î´óΪ62*62£¬±ßµÄÊýÁ¿ÏÔÈ»¾ÍÊÇnÁË

ÒòΪÁ½¸ö×Öĸ£¨Êý×Ö£©hash³ÉÊý×ֵĻ°Ò²¾ÍÊÇ62*62ÖÖ


Ê×ÏÈÒªÅжÏÕâ¸öÅ·À­Í¨Â·ÊÇ·ñ´æÔÚ

Ê×ÏȼÆËãÿ¸ö½áµãµÄÈë¶ÈºÍ³ö¶È£¬

È»ºóÈç¹ûÒ»¸öÓÐÏòͼ´æÔÚÅ·À­Í¨Â·¡£

ÔòÈÎÒâ½áµãµÄ³ö¶È¸úÈë¶ÈµÄ²îµÄ¾ø¶ÔÖµ ²»´óÓÚ1

²¢ÇÒͳ¼Æabs(³ö¶È-Èë¶È)==1 µÄ½áµãµÄÊýÁ¿£¬¼ÙÉèΪx¸ö

Ôòx±ØÈ»Îª0»òÕß2

Èç¹ûΪ0¸ö£¬ÔòÅ·À­Í¨Â·ÔÚÈÎÒâÒ»µã¶¼¿Éµ±×öÆðµã

Èç¹ûΪ2¸ö£¬ÔòÅ·À­Í¨Â·´Ó£¨³ö¶È-Èë¶È£©==1 µÄ½áµã³ö·¢


ÇóÅ·À­Í¨Â·µÄʱºòÎÒÃÇdfs¼´¿É£¬Ã¿Ìõ±ß»áÓÐÒ»¸ö±àºÅ£¬±£Ö¤Ã¿Ìõ±ßÖ»×ßÒ»´Î¡£

µ«ÊÇÐèҪעÒâµÄÊÇ£¬Õâ¸önÊÇÓÐ20ÍòµÄ£¬ ÖØ±ßºÍ×Ô»·¶àÁË»á³öһЩÎÊÌâ¡£

ËùÒÔÎҾͽ«Öر߿´³É1Ìõ£¬µ«ÊÇ¶ÔÆä¼ÆÊý£¬ÔÚdfsµÄʱºòÓñߵÄÊýÁ¿µ±×öÊÇ·ñ·ÃÎʹýµÄ±ê¼Ç


#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #define MAXN 111111 #define MAXM 1122222 #define INF 1000000007 #define eps 1e-8 using namespace std; int n; typedef pair
           
             PII; vector
            
              g[66 * 66]; int num[66 * 66]; int in[66 * 66], out[66 * 66]; int fa[66 * 66], v[66 * 66]; int en[66 * 66][66 * 66]; int vis[222222], nv[222222]; int st[222222]; char s[211111][6]; int find(int x) { if(x == fa[x]) return x; int t = find(fa[x]); fa[x] = t; return t; } void join(int x, int y) { int fx = find(x); int fy = find(y); if(fx != fy) fa[fx] = fy; } int getc(char c) { if(c >= 'a' && c <= 'z') return c - 'a'; if(c >= 'A' && c <= 'Z') return c - 'A' + 26; return c - '0' + 52; } int ind; void dfs(int u, int eid) { for(int i = 0; i < g[u].size(); i++) { int tid = g[u][i].second; if(vis[tid]) { vis[tid] --; dfs(g[u][i].first, tid); } } if(eid) st[ind++] = eid; } int main() { scanf("%d", &n); for(int i = 0; i < 66 * 66; i++) fa[i] = i; for(int i = 1; i <= n; i++) { scanf("%s", s[i]); int a = getc(s[i][0]); int b = getc(s[i][1]); int c = getc(s[i][2]); int id1 = a * 62 + b; int id2 = b * 62 + c; v[id1] = 1; v[id2] = 1; join(id1, id2); if(en[id1][id2] == 0) en[id1][id2] = i, g[id1].push_back(PII(id2, i)); in[id2]++; out[id1]++; vis[en[id1][id2]]++; } int tmp = -1, flag = 0; for(int i = 0; i < 66 * 66; i++) { if(!v[i]) continue; if(tmp == -1) tmp = find(i); else { if(tmp != find(i)) { flag = 1; break; } } } int cnt = 0, src = -1; for(int i = 0; i < 66 * 66; i++) { if(!v[i]) continue; if(abs(in[i] - out[i]) >= 2) { flag = 1; break; } else if(abs(in[i] - out[i]) == 1) { cnt ++; if(out[i] - in[i] == 1) src = i; } } if(src == -1) src = tmp; if(flag) { printf("NO\n"); } else if(cnt == 0 || cnt == 2) { dfs(src, 0); printf("YES\n"); for(int i = ind - 1; i >= 0; i--) { int tid = st[i]; if(i == ind - 1) printf("%s", s[tid]); else printf("%c", s[tid][2]); } printf("\n"); } else { printf("NO\n"); } return 0; }
            
           
          
        
       
      
     
    
   
  




E

ÌâÒâÊÇ

¸ø³ön¸öÇø¼ä¡£

È»ºóµÚi¸öÇø¼ä±íʾµÄÊǵÚi¸ö×óÀ¨ºÅÓëÓÒÀ¨ºÅµÄ ϱê¾àÀ뷶Χ

Çó³öÒ»¸öºÏ·¨µÄÀ¨ºÅÐòÁÐ ²¢ÇÒÂú×ãÕâЩ·¶Î§

È»ºóºóÀ´ÏëÁËÏë£¬Ã²ËÆÊǸö¼ÇÒ仯dp£¬ ¶øÇÒ²¢²»ÄÑ¡£¡£

Áîdp[i][j]±íʾµÚi¸öµ½µÚj¸ö×óÀ¨ºÅÊÇ·ñ¶¼³É¹¦µÄÆ¥Åäµ½ÁËÓÒÀ¨ºÅ

ÄÇôÔÚdfsµÄʱºò£¬¶ÔÓÚdp[i][j] £¬ ÎÒÃÇö¾Ùi±»µÚ¼¸¸öÓÒÀ¨ºÅÆ¥ÅäÁË£¬ÏÔÈ»ÊÇ´ÓµÚi¸öÓÒÀ¨ºÅö¾Ùµ½µÚj¸öÓÒÀ¨ºÅ£¬¼ÙÉè±»µÚk¸öÓÒÀ¨ºÅÆ¥Åä²¢ÇÒÂú×ã֮ǰ¸øµÄ·¶Î§ÁË

È»ºó¾Í¿ÉÒÔȥѰÕÒÆä×Ó״̬ dp[i + 1][k] ÒÔ¼°dp[k+1][j]


#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
          #include 
          
            #define MAXN 111111 #define MAXM 1122222 #define INF 1000000007 #define eps 1e-8 using namespace std; int dp[666][666]; int l[666], r[666]; char s[3333]; int n; int p[3333]; int dfs(int L, int R) { if(L > R) return 1; if(dp[L][R]) return dp[L][R]; for(int i = L; i <= R; i++) { if(i - L + 1 >= l[L] && i - L + 1 <= r[L] ) { if(dfs(L + 1, i) == 1 && dfs(i + 1, R) == 1) { p[L] = (i - L) * 2 + 1; return dp[L][R] = 1; } } } return dp[L][R] = -1; } int main() { scanf("%d", &n); int flag = 1; for(int i = 1; i <= n; i++) { scanf("%d%d", &l[i], &r[i]); if(l[i] % 2 == 0) l[i]++; if(r[i] % 2 == 0) r[i]--; if(l[i] > r[i]) { flag = 0; } l[i] = (l[i] + 1) / 2; r[i] = (r[i] + 1) / 2; } if(flag == 0) { printf("IMPOSSIBLE\n"); return 0; } dfs(1, n); if(dp[1][n] != 1) { printf("IMPOSSIBLE\n"); return 0; } int j = 0; for (int i = 1 ; i <= n; i++){ while(s[j]) ++j; s[j] = '('; s[j + p[i]] = ')'; } puts(s); return 0; }
          
        
       
      
     
    
   
  



¡¾´ó ÖРС¡¿¡¾´òÓ¡¡¿ ¡¾·±Ìå¡¿¡¾Í¶¸å¡¿¡¾Êղء¿ ¡¾ÍƼö¡¿¡¾¾Ù±¨¡¿¡¾ÆÀÂÛ¡¿ ¡¾¹Ø±Õ¡¿ ¡¾·µ»Ø¶¥²¿¡¿
·ÖÏíµ½: 
ÉÏһƪ£ºDictionary and Array value cann.. ÏÂһƪ£ºpoj1113--Wall(͹°ü)

ÆÀÂÛ

ÕÊ¡¡¡¡ºÅ: ÃÜÂë: (ÐÂÓû§×¢²á)
Ñé Ö¤ Âë:
±í¡¡¡¡Çé:
ÄÚ¡¡¡¡ÈÝ:

¡¤Spring Boot Java£º (2025-12-26 16:20:19)
¡¤Spring Boot¤ÇHello (2025-12-26 16:20:15)
¡¤Spring ¤Î»ù±¾¤«¤éŒ (2025-12-26 16:20:12)
¡¤C++Ä£°å (template) (2025-12-26 15:49:49)
¡¤C ÓïÑÔÖÐÄ£°åµÄ¼¸ÖÖ (2025-12-26 15:49:47)