Codeforces 118A String Task

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

Codeforces 231A Team

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

Codeforces 853A Planning

简单贪心一下即可:从第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;
}

Codeforces 853B Jury Meeting

下面以去往城市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;
}

Codeforces 71A Way Too Long Words

去年面谷歌的时候还被问过这道题。最后还是悲剧了,好伤心:sob:

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

namespace _71A
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            while (n-- != 0)
            {
                string word = Console.ReadLine();
                if (word.Length <= 10)
                {
                    Console.WriteLine(word);
                }
                else
                {
                    string abbr = word[0].ToString() + (word.Length - 2).ToString() + word[word.Length - 1].ToString();
                    Console.WriteLine(abbr);
                }
            }
        }
    }
}

Codeforces 4A Watermelon

判断是否为大于2的偶数即可。

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

namespace _4A
{
    class Program
    {
        static void Main(string[] args)
        {
            int w = Convert.ToInt32(Console.ReadLine());
            if (w > 2 && w % 2 == 0)
            {
                Console.WriteLine("YES");
            }
            else
            {
                Console.WriteLine("NO");
            }
        }
    }
}

Codeforces 1B Spreadsheets

首先需要判断输入是Excel格式还是RC格式的串。判断方法:如果在读入到数字之后又读到字母,就是RC格式;否则就是Excel格式。

转换时,Excel格式的列名相当于26进制的数,但不完全一致:Z代表26而不是0。需要在转换时注意一下trick。

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

namespace _1B
{
    class Program
    {

        static int mod26(int col)
        {
            int ret = col % 26 - 1;
            if (ret == -1)
            {
                ret += 26;
            }
            return ret;
        }

        static int CalcRCColName(string Excel_C)
        {
            int C = 0;
            for (int i = 0; i < Excel_C.Length; i++)
            {
                C *= 26;
                C += Excel_C[i] - 'A' + 1;
            }
            return C;
        }

        static string CalcExcelColName(int col)
        {
            string ret = "";
            while(true)
            {
                ret = ((char)('A' + (mod26(col)))).ToString() + ret;
                int adjust = 0;
                if (col % 26 == 0)
                {
                    adjust = 1;
                }
                col = col / 26 - adjust;
                if (col == 0 )
                    break;
            }
            return ret;
        }

        static string RCToExcel(string position)
        {
            int c_pos = position.IndexOf('C');
            int R = int.Parse(position.Substring(1, c_pos - 1));
            int C = int.Parse(position.Substring(c_pos + 1));
            string Excel_C = CalcExcelColName(C);
            return Excel_C + R.ToString();
        }

        static string ExcelToRC(string position)
        {
            int num_pos = position.IndexOfAny("0123456789".ToArray());
            string C = position.Substring(0, num_pos);
            string R = position.Substring(num_pos);
            int RC_C = CalcRCColName(C);

            return "R" + R + "C" + RC_C.ToString();
        }

        static bool IsExcelFormat(string position)
        {
            int state = 0;
            foreach(var c in position)
            {
                if (char.IsDigit(c))
                {
                    if (state == 0)
                        state = 1;
                }
                else
                {
                    if (state == 1)
                        return false;
                }
            }
            return true;
        }

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            while(n-- != 0)
            {
                string pos = Console.ReadLine();
                if (IsExcelFormat(pos))
                {
                    Console.WriteLine(ExcelToRC(pos));
                }
                else
                {
                    Console.WriteLine(RCToExcel(pos));
                }
            }
        }
    }
}

Codeforces 1A Theatre Square

长和宽除以边长后向上取个整。

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

namespace _1A
{
    class Program
    {
        static Int64 calc(Int64 i, Int64 a)
        {
            return i / a + (i % a == 0 ? 0 : 1);
        }

        static void Main(string[] args)
        {
            Int64[] ints = Console.ReadLine().Split().Select(i => Int64.Parse(i)).ToArray();
            Int64 w = calc(ints[0], ints[2]);
            Int64 h = calc(ints[1], ints[2]);

            Console.WriteLine(w * h);
        }
    }
}