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);
        }
    }
}

Codeforces 2A Winner

记录一下序列即可

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

namespace _2A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            IDictionary<string, List<Tuple<int, int>>> score = new Dictionary<string, List<Tuple<int, int>>>();

            for (int i = 0; i < n; i++)
            {
                string[] tmp = Console.ReadLine().Split();
                int s = int.Parse(tmp[1]);
                if (!score.Keys.Contains(tmp[0]))
                {
                    score.Add(new KeyValuePair<string, List<Tuple<int, int>>>(tmp[0], new List<Tuple<int, int>>()));
                }
                else
                {
                    s += score[tmp[0]].Last().Item1;
                }
                score[tmp[0]].Add(new Tuple<int, int>(s, i));
            }
            List<string> names = new List<string>();
            int finalScore = 0;
            foreach (var item in score)
            {
                if (names.Count == 0)
                {
                    names.Add(item.Key);
                    finalScore = item.Value.Last().Item1;
                }
                else
                {
                    if (item.Value.Last().Item1 > finalScore)
                    {
                        names.Clear();
                        names.Add(item.Key);
                        finalScore = item.Value.Last().Item1;
                    }
                    else if (item.Value.Last().Item1 == finalScore)
                    {
                        names.Add(item.Key);
                    }
                }
            }

            string maxName = "";
            if (names.Count > 1)
            {
                int earliestRound = 99999;
                foreach (var name in names)
                {
                    for (int i = 0; i < score[name].Count; i++)
                    {
                        if (score[name][i].Item1 >= finalScore && score[name][i].Item2 < earliestRound)
                        {
                            maxName = name;
                            earliestRound = score[name][i].Item2;
                            break;
                        }
                    }
                }
            }
            else
            {
                maxName = names[0];
            }

            Console.WriteLine(maxName);
        }
    }
}

Codeforces 852F Product transformation

根据题意首先整理一下规律:

假如原始数组为 2 2 2 2,那么变换几次之后的数组分别为:

 

2 2 2 2
4 4 4 2
16 16 8 2
256 128 16 2

我们只关心指数,每个数的指数为:

1 1 1 1
2 2 2 1
4 4 3 1
8 7 4 1

这样原来每两个数相乘,就变成了每两个数相加。为了让规律再明显一点,我们计算前后两个数的差:

0 0 0
0 0 1
0 1 1
1 2 1

可以发现这是杨辉三角。杨辉三角第m行的第i个数字就是\(C_m^i\)因此数组从右往左第k个数的指数就是\(Sigma_{i=1}^k C_m^i\),其中m是变换的次数。下面的任务就是如何计算出每一个\(C_m^i\)。

计算mCi时,分子或分母相乘时很容易造成溢出。不过,由于题目只要求计算对某个Q取模的结果,我们可以充分利用这一点。不过需要注意的是,mCi这里并不是对Q取模,而应该对\(\phi\)取模。考虑到\(a^0 === 1\),即\(a^0 mod Q == 1\),\(\phi\)是下一次对Q取模等于一的幂——即余数每\(\phi\)次循环一遍。要计算\(\phi\),只需要不断计算a的幂取模的结果即可,这些结果后面还用得上;如果发现取模为1了,就可以停止计算。

回到计算mCi的问题上,分子的计算可以利用\(ab mod c = (a mod c)(b mod c) mod c\)计算,比较难办的是分母如何计算。分母的计算可以利用费马小定理,得到\(a^{-1} = a^{p-2} mod p\),将\(a^{-1}\)的计算改为计算\(a^{p-2} mod p\)。利用快速幂取模即可。

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

namespace _852F
{
    class Program
    {
        static long exp_mod(long a, long b, int mod)
        {
            if (b == 0)
                return 1;
            if (b == 1)
                return a % mod;
            long t = exp_mod(a, b / 2, mod);
            t = (t * t) % mod;

            if (b % 2 == 1)
                t = (t * a) % mod;
            return t;
        }

        static long[] C(int n, int q)
        {
            int k = n / 2;
            if (n % 2 == 0)
            {
                k--;
            }
            List<long> arr = new List<long>();
            arr.Add(1);
            long a = 1;
            int n2 = n;
            for (int i = 1; i <= k; i++)
            {
                a = (a * n2) % q;
                a = (a * exp_mod(i, q-2, q)) % q;
                n2--;
                arr.Add(a);
            }

            List<long> arr2 = ((IEnumerable<long>)arr).Reverse().ToList();

            if (n % 2 == 0)
            {
                a = (a * n2) % q;
                a = (a * exp_mod(k + 1, q - 2, q)) % q;
                arr.Add(a);
            }

            arr.AddRange(arr2);

            return arr.ToArray();
        }

        static void Main(string[] args)
        {
            int[] t = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
            int n = t[0];
            int m = t[1];
            int a = t[2];
            int q = t[3];

            List<long> pow = new List<long>();
            pow.Add(1);
            long p = 1;
            while (true)
            {
                p = (p * (a % q)) % q;
                if (p != 1)
                {
                    pow.Add(p);
                }
                else
                {
                    break;
                }
            }

            long[] c = C(m, pow.Count);

            List<long> arr = new List<long>();
            arr.Add(a % q);
            int tmp = 1;
            for (int i = 1; i < n; i++)
            {
                if (i <= m)
                {
                    tmp += (int)c[i];
                    tmp %= pow.Count;
                }
                arr.Add(pow[tmp]);
            }

            arr.Reverse();

            Console.WriteLine(string.Join(" ", arr));
        }
    }
}

Codeforces 852G Bathroom terminal

对于每一个Pattern,建立一个Trie树。在遍历Pattern串构建Trie树时,用一个数组来保存哨兵指针,用以标记当前状态。初始时数组中只有一个指针,指向根节点。如果遇到了a~e(以a为例),则将在当前(所有)的哨兵节点下均增加一个合法的a的输入,用每一个新的a子节点代替当前结点作为哨兵;如果遇到了?,则扩充当前的哨兵数组:为当前的哨兵数组中的每一个哨兵节点添加a、b、c、d、e五个合法输入,将新的子节点全部添加进哨兵数组。此时哨兵数组由6个部分组成:原来的哨兵节点、新的a子节点、新的b子节点……新的e子节点。

匹配时一个一个字符进行匹配即可。

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

namespace _852G
{
    class Program
    {
        class Trie
        {
            private bool Matched = false;
            private Trie[] next = new Trie[5];

            public void SetMatched()
            {
                Matched = true;
            }

            public bool IsMatched()
            {
                return Matched;
            }

            private int GetIndex(char c)
            {
                return c - 'a';
            }

            public Trie AddChar(char c)
            {
                return GetOrAdd(GetIndex(c));
            }

            public Trie GetNext(char c)
            {
                return next[GetIndex(c)];
            }

            private Trie GetOrAdd(int index)
            {
                if (next[index] == null)
                {
                    next[index] = new Trie();
                }
                return next[index];
            }
        }

        static bool Match(string words, Trie pattern)
        {
            for (int i = 0; i < words.Length; i++)
            {
                pattern = pattern.GetNext(words[i]);
                if (pattern == null)
                {
                    return false;
                }
            }
            return pattern.IsMatched();
        }

        static void Main(string[] args)
        {
            int[] MN = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
            int M = MN[0];
            int N = MN[1];
            string[] words = new string[M];

            for (int i = 0; i < M; i++)
            {
                words[i] = Console.ReadLine();
            }

            for (int i = 0; i < N; i++)
            {
                string pattern = Console.ReadLine();
                Trie trie = new Trie();
                List<Trie> pivot = new List<Trie>();
                pivot.Add(trie);
                for (int j = 0; j < pattern.Length; j++)
                {
                    if (pattern[j] != '?')
                    {
                        pivot = pivot.Select(p => p.AddChar(pattern[j])).ToList();
                    }
                    else
                    {
                        List<Trie> q = new List<Trie>();
                        for (int c = 0; c < 5; c++)
                        {
                            q.AddRange(pivot.Select(p => p.AddChar((char)('a' + c))).ToList());
                        }
                        pivot.AddRange(q);
                    }
                }
                pivot.ForEach(p => p.SetMatched());

                int sum = 0;

                for (int j = 0; j < M; j++)
                {
                    if (Match(words[j], trie))
                    {
                        sum++;
                    }
                }

                Console.WriteLine(sum);
            }

        }
    }
}

Codeforces 158A Next Round

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

namespace _158A
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
            int n = arr[0];
            int k = arr[1] - 1;
            int[] score = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
            if (score[k] > 0)
            {
                int s = score[k];
                while(k < n && score[k] == s)
                {
                    k++;
                }
            }
            else
            {
                while(k >= 0 && score[k] <= 0)
                {
                    k--;
                }
                k++;
            }
            Console.WriteLine(k);
        }
    }
}

Codeforces 50A Domino piling

能横着放就横着放,放不下就竖着放

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

namespace _50A
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] arr = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray();
            int w_horizon = arr[0] / 2;
            int h_horizon = arr[1];
            int h_vertical = arr[1] / 2;
            Console.WriteLine(w_horizon * h_horizon + (arr[0] % 2 == 0 ? 0 : h_vertical));
        }
    }
}