月度归档：2017年10月

组织哈工大技术兴趣讨论班的心路历程

3条回复

去年的秋季学期还没开始的时候，我就在考虑技术兴趣讨论班计划——让对某方面技术感兴趣的同学聚集在一起，定期轮流做一些分享。一晃眼今年都快过完了，想着把去年一年的经过和想法整理一下，如果将来有人还想办一办类似的活动的话，这就算作是宝贵的经验吧。

1

其实这是一连串的事件。办技术讨论班并不是我突然想做的，还有很多前戏。最最前的事件，大概就是IBM技术俱乐部暂停招新，随后 run.hit.edu.cn 镜像站又挂掉了。每次打开USTC Mirror，打开TUNA，心里面总是有一点嫉妒，现在仍旧如此。哈工大坐落在东北荒凉之地，哪有机会去参加Ubuntu Release Party，甚至连一个小小的镜像站都倒了。

所以，我想活跃一下校园里面的技术氛围。其实计算机和软件学院有很多的技术社团，也有很多人技术很不错的，但我总觉得差了点东西。

最开始大概在2015年，我想办一个技术社区。http://techo.io ，现在已经凉了，大家可以上去再给它续一续命。虽说当时本来就没有抱着办成功的态度去做，但还是有一点点的遗憾。把techo搭起来了之后，刚好学校Z老师有意向办一个技术咖啡馆，交给了我的基友们去做。线上线下联动，看起来甚至还有那么点希望。场地有了，线上讨论区有了，我甚至有着很多美好的设想：给各个技术社团提供线上讨论板块，线下活动场地，技术氛围搞起来啊。

2016年年中，线上论坛已经搭的差不多，咖啡店也已经装修完毕了。

2

每年的六七八月份，正是高考结束，考生撕书相庆的时节。高考结束之后就是填报志愿了，大概六月底七月初成绩公布，学生们未来的去处也就大致确定了。此时，多半会诞生新的新生群，诸如“2017级哈工大新生1群”。早就计划了要搞一点事情的我，必然要混进新生群去，因为之后的学院群的创建（比如“哈工大2017计算机”之类）多半可以从这样的新生群里面得知，同时还可以先混个脸熟，将来搞事情的时候不会冷场。

当然，技术兴趣讨论班不仅仅面向大一新生，但这是需要对大一新生做出的额外准备。因为大二大三大四这几届，在他们入学的时候，我已经基本做完了这些操作。

那一段时间，在跟学弟学妹们扯皮的同时，我也在思考讨论班究竟以什么样的形式来进行活动。哈工大大一的所有学生都在黄河路的二校区，大二以上年级的学生基本都在西大直街的一校区。一起活动吗？还是分开活动？让高年级的学生直接给大一同学开小灶吗？还是内部轮流分享？能做到每周都有东西可以拿来分享吗？

最终，我采取的方案是：讲书。比如我对CSAPP感兴趣，那么看看大家谁还对CSAPP感兴趣，组成一个“CSAPP讨论班”，大家一起来学，每周安排一个人将书中的一章或半章。不限制校区，地点安排服从多数人方便的标准。如果有人对SICP感兴趣，那么就组成另一个“SICP讨论班”，等等。

继续阅读 →

Codeforces 869C The Intriguing Obsession

发表评论

这是一道动态规划题。

首先来分析：题干中对于桥梁的限制，其实是在说：某个点不能与自己集合中的点相连，也不能同时与同一个集合中的两个点相连，即题目下方示例2中那两种不合法的连接方法。也就是说，对于红色点A来说，它可以与蓝色集合中至多一个点相连；同时，也可以与紫色集合中至多一个点相连。它是否与蓝色集合中的点相连并不影响其与紫色集合的点相连，即桥梁搭建的全部情况，应该等于红蓝相连的情况数×红紫相连的情况数×蓝紫相连的情况数。因为不论红紫、蓝紫之间如何相连，红蓝之间相连的情况数跟它们均无关。

现在我们把问题由三个集合简化到了两个集合。这两个集合之间的点相连接需要满足刚才那两个条件：

  • 集合内部的点不能相连
  • 集合A中的一个点要么与集合B中的一个点相连，要么就不连接集合B中的任何点

第二个条件其实就是动态规划的转移方程了。对于集合A中的第I个点：

  • 第一种情况，它不跟集合B中的任何一个点相连。此时即变为一个子问题：集合A中的i-1个点与集合B中的j个点搭建桥梁；
  • 第二种情况，他跟集合B中的某一个点相连。连接方法共有j种，连接后变为另一个子问题：集合A中剩余的i-1个点与集合B中剩余的j-1个点相连。

因此，转移方程为：

dp[i, j] = dp[i - 1, j] + dp[i - 1, j - 1] * j

dp[i, j]代表的就是当集合A中有i个点、集合B中有j个点时，桥梁的连接方法。

由于只用到了i – 1，因此只需要存储一行即可。不过由于每个集合中的点数最多只有5000，即便用long存也大概只有200MB，内存勉强够用。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _869C
{
    class Program
    {
        public static void Swap<T>(ref T lhs, ref T rhs)
        {
            T temp = lhs;
            lhs = rhs;
            rhs = temp;
        }

        static void Main(string[] args)
        {
            int[] tmp = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
            if (tmp[1] < tmp[0])
            {
                Swap(ref tmp[0], ref tmp[1]);
            }
            if (tmp[2] < tmp[0])
            {
                Swap(ref tmp[0], ref tmp[2]);
            }

            long[,] dp = new long[tmp[1] + 1, tmp[2] + 1];
            for (int i = 0; i <= tmp[1]; i++)
            {
                for (int j = 0; j <= tmp[2]; j++)
                {
                    if (i == 0 || j == 0)
                    {
                        dp[i, j] = 1;
                    }
                    else
                    {
                        dp[i, j] = (dp[i - 1, j] + dp[i - 1, j - 1] * j) % 998244353;
                    }
                }
            }

            long r = (((dp[tmp[1], tmp[0]] * dp[tmp[1], tmp[2]]) % 998244353) * dp[tmp[0], tmp[2]]) % 998244353;
            Console.WriteLine(r);
        }
    }
}

Codeforces 869A The Artful Expedient

发表评论

暴力即可

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _869A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int[] x = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
            int[] y = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();

            ISet<int> xset = new HashSet<int>(x);
            ISet<int> yset = new HashSet<int>(y);

            int sum = 0;

            foreach (var xe in xset)
            {
                foreach (var ye in yset)
                {
                    int r = xe ^ ye;
                    if (xset.Contains(r) || yset.Contains(r))
                    {
                        sum++;
                    }
                }
            }

            if (sum % 2 == 0)
            {
                Console.WriteLine("Karen");
            }
            else
            {
                Console.WriteLine("Koyomi");
            }
        }
    }
}

Codeforces 869B The Eternal Immortality

发表评论

挨个乘一下，如果结果是0了跳出即可。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _869B
{
    class Program
    {
        static void Main(string[] args)
        {
            long[] tmp = Console.ReadLine().Split().Select(i => long.Parse(i)).ToArray();
            long a = tmp[0];
            long b = tmp[1];
            long r = 1;
            while(b > a)
            {
                r *= b;
                r = r % 10;
                if (r == 0)
                {
                    break;
                }
                b--;
            }
            Console.WriteLine(r);
        }
    }
}