水

记录一下序列即可

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