这是一道动态规划题。

首先来分析：题干中对于桥梁的限制，其实是在说：某个点不能与自己集合中的点相连，也不能同时与同一个集合中的两个点相连，即题目下方示例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);
        }
    }
}

暴力即可

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

挨个乘一下，如果结果是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);
        }
    }
}

水

记录一下序列即可

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

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

假如原始数组为 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));
        }
    }
}

对于每一个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);
            }

        }
    }
}

水

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

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

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

水

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

namespace _118A
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] vow = new char[] { 'a', 'o', 'y', 'e', 'u', 'i' };
            Console.WriteLine(string.Join("", Console.ReadLine().Select(c => char.ToLower(c)).Where(c => !vow.Contains(c)).Select(c =>"." + c).ToArray()));
        }
    }
}

水

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

namespace _231A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int solve = 0;
            while(n-- != 0)
            {
                int sure = Console.ReadLine().Split().Select(i => int.Parse(i)).ToArray().Count(i => i == 1);
                if (sure >= 2)
                {
                    solve++;
                }
            }
            Console.WriteLine(solve);
        }
    }
}

简单贪心一下即可：从第k分钟开始，每一次都选择能起飞的飞机中代价最大的那个。

贪心选择性

设代价最大的飞机为i；假设：不选择i而选择了某个飞机j（cost[j] < cost[i]），最终得到了全局最优解，设为S。此时如果将j和i的位置调换，新的解将比S更优，即S不是全局最优解，与假设矛盾。因此，在某个全局最优解中，在当前这一步一定会选择i。

最优子结构

在选择了i之后，剩下的航班安排问题为子问题。在选择i之后所形成的全局最优解S中，这个子问题的解一定是该子问题的最优解。如果不是的话，则必然能够有某个更优的子问题的解，与i合并之后，将会得到一个更优的全局解。这与S是全局最优解矛盾。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct tmp {
    int id;
    long long cost;
    int new_time;

    bool operator<(const tmp& rhs) const {
        return cost < rhs.cost;
    }
};

int main() {
    int n, k;
    cin >> n >> k;
    tmp* cost = new tmp[n];

    for (int i = 0; i < n; i++) {
        cost[i].id = i;
        cin >> cost[i].cost;
    }

    priority_queue<tmp> q;

    for (int i = 0; i < k; i++) {
        q.push(cost[i]);
    }

    long long int total_cost = 0;
    for (int i = k; i < n + k; i++) {
        if (i < n)
            q.push(cost[i]);
        tmp t = q.top();
        q.pop();
        cost[t.id].new_time = i + 1;
        total_cost += (i - t.id) * t.cost;
    }

    cout << total_cost << endl;

    for (int i = 0; i < n; i++) {
        if (i != 0)
            cout << " ";
        cout << cost[i].new_time;
    }
    cout << endl;

    delete[] cost;
    return 0;
}

下面以去往城市0的航班为例（从城市0返回的航班同理）进行分析：

• 首先，将去的航班按照日期排好序。
• 然后我们可以发现：对于同一个城市来说，如果有航班A和航班B两次航班，A的时间早、票价低，B的时间晚、票价高，则B无需考虑。根据这样的规律，可以过滤掉一波无用的数据。接下来只考虑过滤后的数据。
• 过滤之后可以发现：对于同一个城市来说，目前剩下的航班的价格是按照时间依次递减的。或者说，此时如果有C和D两个航班从同一个城市起飞，C比D早，那么D一定比C便宜。如果在时间允许的情况下（即航班D能够满足k天的要求），那么D之前的所有航班都可以选择；而此时D又是从该城市起飞的航班中最便宜的，因此此时选择D是最优的。如果有航班E比D要晚，并且E满足k天的需求，那么选择E一定比选择D更优。
• 根据这样的规律，我们可以计算出to_cost数组。to_cost数组中的第i项存放的是：如果只从前i个航班中进行选择，所有人飞往城市0花费的最小总和。这个数组是递减的 – 如果选择了第i个航班，它是从城市j起飞的，那么一定比选择比i更早的从城市j起飞的航班要优。这个数组的计算方法也很简单：假设第i个航班从城市j起飞，上一个从城市j起飞的航班的花费设为last_j_cost， 则 to_cost[i] = to_cost[i - 1] - (last_j_cost - flight[i].cost)
• 回来的航班也如此计算出 back_cost。
• 接下来只要同时对两个数组进行遍历就可以了。两个数组都从头开始，如果满足k天的要求，则计算出新的最小值，然后to_cost向后遍历；如果不满足k天的要求，则back_cost向后遍历。

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;


struct Flight {
    int day;
    int city;
    int cost;

    bool operator < (const Flight& rhs) const {
        return day < rhs.day;
    }
};

struct TotalCost {
    int day;
    long long total_cost;

    TotalCost(int _day, long long _total_cost)
        : day(_day), total_cost(_total_cost) {

    }
};

long long calc_cost(vector<Flight>& choice) {
    long long cost = 0;
    for (int i = 0; i < choice.size(); i++) {
        cost += choice[i].cost;
    }
    return cost;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<Flight> flights_to;
    vector<Flight> flights_back;

    for (int i = 0; i < m; i++) {
        Flight flight;
        int from, to;
        cin >> flight.day >> from >> to >> flight.cost;

        if (to == 0) {
            flight.city = from - 1;
            flights_to.push_back(flight);
        }
        else {
            flight.city = to - 1;
            flights_back.push_back(flight);
        }
    }

    sort(flights_to.begin(), flights_to.end());
    sort(flights_back.begin(), flights_back.end());

    set<int> city_id;
    vector<Flight> choices_to(n);
    vector<Flight> choices_back(n);
    int start_day = 999999;
    int end_day = 0;
    int start_id, end_id;

    // Choose the earlest start day
    for (int i = 0; i < flights_to.size(); i++) {
        if (city_id.find(flights_to[i].city) != city_id.end()) {
            if (choices_to[flights_to[i].city].cost > flights_to[i].cost) {
                choices_to[flights_to[i].city] = flights_to[i];
            }
            continue;
        }
        city_id.insert(flights_to[i].city);
        choices_to[flights_to[i].city] = flights_to[i];
        if (city_id.size() == n) {
            start_day = flights_to[i].day;
            start_id = i;
            break;
        }
    }

    if (city_id.size() != n) {
        cout << -1 << endl;
        return 0;
    }

    city_id.clear();

    // Choose the latest end day
    for (int i = flights_back.size() - 1; i >= 0; i--) {
        if (city_id.find(flights_back[i].city) != city_id.end()) {
            if (choices_back[flights_back[i].city].cost > flights_back[i].cost) {
                choices_back[flights_back[i].city] = flights_back[i];
            }
            continue;
        }
        city_id.insert(flights_back[i].city);
        choices_back[flights_back[i].city] = flights_back[i];
        if (city_id.size() == n) {
            end_day = flights_back[i].day;
            end_id = i;
            break;
        }
    }

    if (city_id.size() != n) {
        cout << -1 << endl;
        return 0;
    }

    if (end_day - start_day - 1 < k) {
        cout << -1 << endl;
        return 0;
    }

    vector<TotalCost> to_cost, back_cost;
    to_cost.push_back(TotalCost(flights_to[start_id].day, calc_cost(choices_to)));
    back_cost.push_back(TotalCost(flights_back[end_id].day, calc_cost(choices_back)));

    vector<Flight> mins = choices_to;
    for (int i = start_id; i < flights_to.size(); i++) {
        int city_id = flights_to[i].city;
        long long m = mins[city_id].cost - flights_to[i].cost;
        if (m > 0) {
            to_cost.push_back(TotalCost(flights_to[i].day, to_cost.back().total_cost - m));
            mins[city_id] = flights_to[i];
        }
    }

    mins = choices_back;
    for (int i = end_id; i >= 0; i--) {
        int city_id = flights_back[i].city;
        long long m = mins[city_id].cost - flights_back[i].cost;
        if (m > 0) {
            back_cost.push_back(TotalCost(flights_back[i].day, back_cost.back().total_cost - m));
            mins[city_id] = flights_back[i];
        }
    }

    reverse(back_cost.begin(), back_cost.end());
    int i = 0, j = 0;
    long long min_cost = LLONG_MAX;
    while (true) {
        if (back_cost[j].day - to_cost[i].day - 1 >= k) {
            if (to_cost[i].total_cost + back_cost[j].total_cost < min_cost) {
                min_cost = to_cost[i].total_cost + back_cost[j].total_cost;
            }
            i++;
        }
        else {
            j++;
        }
        if (i >= to_cost.size() || j >= back_cost.size())
            break;
    }

    while (j < back_cost.size()) {
        if (to_cost[i - 1].total_cost + back_cost[j].total_cost < min_cost) {
            min_cost = to_cost[i - 1].total_cost + back_cost[j].total_cost;
        }
        j++;
    }

    cout << min_cost << endl;

    return 0;
}