编程之美2013资格赛水结-白红宇的个人博客

编程之美2013资格赛水结

发布日期：2021-08-26 12:38:22 浏览次数：3 分类：技术文章

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

很久没有在线编程了，实力大大减弱。为了保持算法与编程的技能，继续找一下在线比赛来复习复习。只为找感觉，不求排名与晋级。

一传话游戏

题目简意：一句由若干个单词组成的话，经过N个人传承。每个人在听取前一个人的口述时，都会把某些单词听成另外的单词。求最终被流传下来的句子。

解：不能再水了，就是简单的字符串替换。不想用c写字符串的东西，于是用了java的HashMap<String,String>，还是第一次用java提交。注意类名一定要是Main

View Code

1   2 import java.util.HashMap; 3 import java.util.Scanner; 4  5 public class Main{ 6      7      8 public static int T, N, M; 9 10 public static int count = 1;11 public static HashMap
      
        rule;12 13 public static String   orignal, result;14 public static Scanner cin = new Scanner(System.in);15 16 17     public static void main(String[] args){18         19         T = cin.nextInt();20         21         while(T-- > 0)22         {23             N = cin.nextInt();24             M = cin.nextInt();25             result = "";26              27             rule = new HashMap
       
        ();28             for(int i = 0; i < M; i++)29             {30                 String ori = cin.next().toString();31                 String swp = cin.next().toString();32                 rule.put(ori, swp);33             }34             35             orignal = cin.next().toString();36             orignal += cin.nextLine().toString();37              38             39             String[] sentence = orignal.split(" ");40             41             42             while(N > 1)43             {44                 for(int i = 0; i < sentence.length; i++)45                     if (rule.containsKey(sentence[i]))46                         sentence[i] = rule.get(sentence[i]);                     47                 N--;48             }49             50             String result = "";51             for (int i=0;i

二长方形

题目概要：在 N 条水平线与 M 条竖直线构成的网格中，放 K 枚石子，每个石子都只能放在网格的交叉点上。问在最优的摆放方式下，最多能找到多少四边平行于坐标轴的长方形，它的四个角上都恰好放着一枚石子。

输入：第一行，给出一个整数T，为数据组数。接下来依次给出每组测试数据。

每组数据为三个用空格隔开的整数 N，M，K。

1 ≤ T ≤ 100

0 ≤ K ≤ N * M

小数据：0 < N, M ≤ 30

大数据：0 < N, M ≤ 30000

解：这是一道排列组合的问题。假设我们已经知道从K个石子中取X*Y个组成一个大的饱满的矩形，它上面每一行的石子数目相同，剩余L个石子，0<L<X。则此时的矩形总数为：在饱满的大矩形中，共有C(x,2)*C(y,2)个小矩形，剩下的和L有关的矩形数是X*C(L,2) 。两者的和即为所求。

如何选取X和Y呢？应该可以理论证明的，但是我懒得去推，因为N，M<= 30000，可以枚举每一个X的值。（似乎真的太懒了。。。）

View Code

1 #include
      
        2 #include
       
         3  4 unsigned long long solve() 5 { 6     int i,j,k; 7     int t,n,m; 8     unsigned long long mx = 0; 9     int x,y,l;10     unsigned long long cur;11     12     scanf("%d%d%d",&n,&m,&k);13     if (n>m)14     {15         t=n;n=m;m=t;16     }17     for (i=2;i<=n;i++)18     {19         x=i; 20         y = k / i;21         l = k % i;22         if (y>m || y==m && l>0)23           continue;24         cur = x*y*(x-1)*(y-1)/4 + y * (l-1)*l/2;25         if (cur>mx)26           mx = cur;        27     }28     return mx;    29 }30 31 int main()32 {33     int T,i;34     scanf("%d",&T);35     for (i=1;i<=T;i++)36         printf("Case #%d: %llu\n",i,solve());37     return 0;38 }

这个平台和杭电的又有所不同，输出不能用%I64d ,而要用%llu 来输出 unsigned long long。

三树上的三角形

有一棵树，树上有只毛毛虫。它在这棵树上生活了很久，对它的构造了如指掌。所以它在树上从来都是走最短路，不会绕路。它还还特别喜欢三角形，所以当它在树上爬来爬去的时候总会在想，如果把刚才爬过的那几根树枝/树干锯下来，能不能从中选三根出来拼成一个三角形呢？

1 ≤ T ≤ 5

小数据：1 ≤ N ≤ 100, 1 ≤ M ≤ 100, 1 ≤ len ≤ 10000

大数据：1 ≤ N ≤ 100000, 1 ≤ M ≤ 100000, 1 ≤ len ≤ 1000000000

解：一看就让人想到用最近公共祖先和并查集。但是我现在不想花太多精力去实现它，于是就决定水一下小数据。

首先要说的是，小数据的范围是1000，而不是100！害我检查了N次，太无耻了。

拿到树的结构以后，任取一个节点，遍历一遍树，为了得到每个节点的深度（假设根节点的深度为0）和它的父节点。

然后对每一对节点s和t，沿着他们的父节点一层一层上移，直到遇到第一个公共祖先。（利用每个节点的深度）。并把这条路径上的边压入一个数组中。

接着对保存有边的数组进行排序。遍历一次排序好的数组，如果存在相邻的三条边能构成三角形，那么就yes，否则就no。

View Code

1 #include
      
         2 #define size 900  3 int N,M;  4 int c[size][size];  5 int dep[size];  6 int father[size];  7 int visited[size];  8 int edge[size];  9 int cnt; 10  11 void Broadcast(int s, int d  ) 12 { 13     int i; 14      15     visited[s] = 1; 16     dep[s] = d; 17     int fa,fb; 18      19         20     for (i=1;i<=N;i++) 21        if (visited[i]==0 && c[s][i]>0) 22        { 23           father[i] = s; 24           Broadcast(i,d+1 ); 25        } 26 } 27   28 void sort(int s[] , int cnt) 29 { 30     int t; 31     int i,j; 32     for (i=0;i
       
        s[j]) 35         { 36           t = s[i]; 37           s[i] = s[j]; 38           s[j] = t; 39         } 40 } 41  42 void solve() 43 { 44  45     int i,j,k; 46     int s,t,w; 47     int ok ; 48     int fa,fb; 49     scanf("%d",&N); 50      51      52     for (i=1;i<=N;i++) 53     { 54       visited[i] = 0; 55       for (j=1;j<=N;j++) 56       { 57          c[i][j] = 0; 58          c[j][i] = 0; 59          } 60     } 61      62     for (i=1;i
        
         dep[fb]) 85             { 86                 fa = father[fa]; 87             } 88             else fb = father[fb]; 89         } 90          91         while (s != fa) 92         { 93             edge[cnt++] = c[s][father[s]]; 94             s = father[s]; 95         } 96         while (t != fa) 97         { 98             edge[cnt++] = c[t][father[t]]; 99             t = father[t];100         }101      102          //qsort(edge,0,cnt-1);103         sort(edge,cnt-1);104         ok = 0;105         for (i=0;i
         
           edge[i+2])108             {109               ok = 1;110               break;111             }112         }113         if (ok==1)114           printf("Yes\n");115           else printf("No\n");116     }117 }118 119 int main()120 {121     int T;122     int i;123     scanf("%d",&T);124     for (i=1;i<=T;i++)125     {126         printf("Case #%d:\n",i);127         solve();           128     }129     return 0;130 }

转载于:https://www.cnblogs.com/sylvanas2012/archive/2013/04/08/3009194.html

转载地址：https://blog.csdn.net/weixin_33885253/article/details/93303901 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：Fastjson简单使用方法

下一篇：读书笔记--MapReduce 适用场景及常见应用

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章