[CCF2015.09]题解-白红宇

[CCF2015.09]题解

阅读量：4687 次

发布时间：2019-06-09

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

201509-1 数列分段

水，记下前一个数，看看跟当前是否一样，不一样就ans+1

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 #include 
                     
                      17 #include 
                      18 #include 
                       
                        19 20 using namespace std;21 22 int n, a;23 24 int main() {25 // freopen("in", "r", stdin);26 while(~scanf("%d", &n)) {27 scanf("%d", &a);28 int cur = a, cnt = 1;29 for(int i = 1; i < n; i++) {30 scanf("%d", &a);31 if(cur != a) {32 cnt++;33 cur = a;34 }35 }36 printf("%d\n", cnt);37 }38 return 0;39 }

201509-2 日期计算

打表，注意细节就行

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 #include 
                     
                      17 #include 
                      18 #include 
                       
                        19 20 using namespace std;21 22 const int com[15] = { 0,31,59,90,120,151,181,212,243,273,304,334, 365};23 const int lep[15] = { 0,31,60,91,121,152,182,213,244,274,305,335, 366};24 int y, c, m, d;25 26 int main() {27 // freopen("in", "r", stdin);28 while(~scanf("%d %d", &y, &c)) {29 d = 0;30 if((y % 4 == 0 && y % 100 != 0) || (y % 400 == 0)) {31 for(int i = 1; i <= 12; i++) {32 if(lep[i] < c) {33 m = i;34 }35 else break;36 }37 d = c - lep[m];38 m++;39 if(d != 0) printf("%d\n%d\n", m, d);40 else printf("%d\n%d\n", m, lep[m]-lep[m-1]);41 }42 else {43 for(int i = 1; i <= 12; i++) {44 if(com[i] < c) {45 m = i;46 }47 else break;48 }49 d = c - com[m];50 m++;51 if(d != 0) printf("%d\n%d\n", m, d);52 else printf("%d\n%d\n", m, com[m]-com[m-1]);53 }54 }55 return 0;56 }

201509-3 模版生成系统

字符串大模拟，无耻地大量使用了STL，甚至出现了vector<pair<vector<int>,vector<int> > >这样的结构。思路就是首先定位此行输入的字符串的需要替换的变量起止位置，再记录当前字符串。接下来读取模式串的键值，放到set中。接下来替换。要注意使用string中的replace时候会让字符串长度发生变化，这时候只要从末尾开始匹配，最后再输出就行了。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
               10 #include 
               
                11 #include 
                
                 12 #include 
                 
                  13 #include 
                  
                   14 #include 
                   
                    15 #include 
                    
                     16 #include 
                     
                      17 #include 
                      18 #include 
                       
                        19 20 using namespace std;21 typedef vector
                        
                         ::iterator it;22 typedef vector
                         
                          
                            >::iterator iit;23 typedef pair
                           
                            
                             ,vector
                             
                               > pvv;24 const int maxn = 111;25 26 int n, m;27 vector
                              
                                start, end;28 vector
                               
                                 sig;29 vector
                                
                                  str;30 map
                                 
                                   var;31 char tmp[maxn];32 33 int main() {34 // freopen("in", "r", stdin);35 while(~scanf("%d %d", &m, &n)) {36 sig.clear();37 var.clear();38 getchar();39 for(int i = 0; i < m; i++) {40 start.clear();41 end.clear();42 gets(tmp);43 int len = strlen(tmp);44 for(int j = 0; j < len; j++) {45 if(tmp[j] == ' ' && tmp[j-1] == '{ ' && tmp[j-2] == '{ ') start.push_back(j+1);46 if(tmp[j] == ' ' && tmp[j+1] == '}' && tmp[j+2] == '}') end.push_back(j-1);47 }48 sig.push_back(pvv(start, end));49 str.push_back(string(tmp));50 }51 for(int i = 0; i < n; i++) {52 gets(tmp);53 string raw(tmp);54 int j;55 for(j = 0; j < raw.length(); j++) {56 if(raw[j] == ' ') break;57 }58 var[raw.substr(0, j)] = raw.substr(j+2, raw.length()-j-3);59 }60 for(int i = 0; i < sig.size(); i++) {61 if(sig[i].first.empty()) {62 printf("%s\n", str[i].c_str());63 continue;64 }65 for(int j = sig[i].first.size() - 1; j >= 0; j--) {66 str[i].replace(67 sig[i].first[j]-3, sig[i].second[j]-sig[i].first[j]+7, 68 var[str[i].substr(sig[i].first[j], sig[i].second[j]-sig[i].first[j]+1)]);69 // cout << sig[i].first[j] << " " << sig[i].second[j] << endl;70 // cout << str[i].substr(sig[i].first[j], sig[i].second[j]-sig[i].first[j] + 1) << endl;71 }72 printf("%s\n", str[i].c_str());73 }74 }75 return 0;76 }

201509-4 高速公路

求多少个连通对。先tarjan跑出所有连通分量，然后枚举任意两个不相等的点，看看是否属于同一个连通分量里。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 #include 
           
             7 #include 
            
              8 #include 
             
               9 #include 
              
                10 #include 
               
                 11 #include 
                
                  12 #include 
                 
                   13 #include 
                  
                    14 #include 
                   
                     15 #include 
                    
                      16 #include 
                     
                       17 #include 
                       18 #include 
                       
                         19 20 using namespace std; 21 22 const int maxn = 10010; 23 const int maxm = 100010; 24 typedef struct Edge { 25 int u; 26 int v; 27 int next; 28 Edge() { next = -1; } 29 }Edge; 30 31 int head[maxn], ecnt; 32 Edge edge[maxm]; 33 int n, m; 34 35 int bcnt, dindex; 36 int dfn[maxn], low[maxn]; 37 int stk[maxn], top; 38 int belong[maxn]; 39 bool instk[maxn]; 40 41 void init() { 42 memset(edge, 0, sizeof(edge)); 43 memset(head, -1, sizeof(head)); 44 memset(instk, 0, sizeof(instk)); 45 memset(dfn, 0, sizeof(dfn)); 46 memset(low, 0, sizeof(low)); 47 memset(belong, 0, sizeof(belong)); 48 ecnt = top = bcnt = dindex = 0; 49 } 50 51 void adde(int uu, int vv) { 52 edge[ecnt].u = uu; 53 edge[ecnt].v = vv; 54 edge[ecnt].next = head[uu]; 55 head[uu] = ecnt++; 56 } 57 58 void tarjan(int u) { 59 int v = u; 60 dfn[u] = low[u] = ++dindex; 61 stk[++top] = u; 62 instk[u] = 1; 63 for(int i = head[u]; ~i; i=edge[i].next) { 64 v = edge[i].v; 65 if(!dfn[v]) { 66 tarjan(v); 67 low[u] = min(low[u], low[v]); 68 } 69 else if(instk[v] && dfn[v] < low[u]) { 70 low[u] = dfn[v]; 71 } 72 } 73 if(dfn[u] == low[u]) { 74 bcnt++; 75 do { 76 v = stk[top--]; 77 instk[v] = 0; 78 belong[v] = bcnt; 79 } while(v != u); 80 } 81 } 82 83 int main() { 84 // freopen("in", "r", stdin); 85 int uu, vv; 86 while(~scanf("%d %d", &n, &m)) { 87 init(); 88 for(int i = 0; i < m; i++) { 89 scanf("%d %d", &uu, &vv); 90 adde(uu, vv); 91 } 92 for(uu = 1; uu <= n; uu++) { 93 if(!dfn[uu]) { 94 tarjan(uu); 95 } 96 } 97 int ans = 0; 98 for(int i = 1; i <= n; i++) { 99 for(int j = i + 1; j <= n; j++) {100 if(belong[i] == belong[j]) {101 ans++;102 }103 }104 }105 printf("%d\n", ans);106 }107 return 0;108 }

转载于:https://www.cnblogs.com/kirai/p/5354649.html

你可能感兴趣的文章