月份:2016年11月

REPORT HIHOCODER1353-满减优惠

REPORT HIHOCODER1353-满减优惠

http://hihocoder.com/problemset/problem/1353
==========================================================================
枚举。
DP应该也是可以的
==========================================================================

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

namespace HIHOCODER1353
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] inp;
            inp = Console.ReadLine().Trim().Split(' ');
            int n = Convert.ToInt32(inp[0]);
            int m = Convert.ToInt32(inp[1]);
            inp = Console.ReadLine().Trim().Split(' ');
            int[] price = new int[n];
            int totalvalue = 0;
            for (int i = 0; i < n; i++)
            {
                price[i] = Convert.ToInt32(inp[i]);
                totalvalue += price[i];
            }
            if (totalvalue < m)
            {
                Console.WriteLine(-1);
                return;
            }
            FIND f = new HIHOCODER1353.FIND(price, n, m);
            Console.WriteLine(f.ANS);
        }
    }
    class FIND
    {
        int[] value;
        int N, M;
        int CUR = 0;
        int MAX, SUM;
        public int ANS;
        public FIND(int[] v, int n, int m)
        {
            value = new int[n];
            v.CopyTo(value, 0);
            N = n;
            M = m;
            MAX = int.MaxValue;
            SUM = value.Sum();

            int max = 1 << N;
            for (int i = 1; i <= max; i++)
            {
                CUR = 0;
                for (int j = 0; j < N; j++)
                {
                    if (((1 << j) & i) != 0)
                    {
                        CUR += value[j];
                    }
                    if (CUR > SUM)
                    {
                        break;
                    }
                    if (CUR >= M && CUR <= MAX)
                    {
                        MAX = CUR;
                        break;
                    }
                }
            }
            ANS = MAX;
        }
    }
}

HIHOCODER-WEEK125 GeoHash编解码

HIHOCODER-WEEK125 GeoHash编解码

WEEK124我选择鸽了……

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

namespace GeoHash
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] inp = Console.ReadLine().Trim().Split(' ');
            int N = Convert.ToInt32(inp[0]);
            int M = Convert.ToInt32(inp[1]);
            for (int i = 0; i < N; ++i)
            {
                inp = Console.ReadLine().Trim().Split(' ');
                decimal A = Convert.ToDecimal(inp[0]);
                decimal B = Convert.ToDecimal(inp[1]);
                GeoHash geohash = new GeoHash();
                Console.WriteLine(geohash.Encode(A, B, 10));
            }
            for (int i = 0; i < M; ++i)
            {
                string inpt = Console.ReadLine().Trim();
                GeoHash geohash = new GeoHash();
                decimal[] red = geohash.DeCode(inpt);
                Console.WriteLine("{0} {1}", red[0].ToString("f6"), red[1].ToString("f6"));
            }
        }
    }
    class GeoHash
    {
        private List<char> Base32Coding;
        public GeoHash()
        {
            Base32Coding = new List<char> { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'j', 'k', 'm', 'n', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
        }
        public string Encode(decimal latitude, decimal longitude, int precision)
        {
            decimal latitudeLeft = -90, latitudeRight = 90;
            decimal longitudeLeft = -180, longitudeRight = 180;
            int length = precision * 5;
            string hash = "";
            int bits = 0;
            for (int i = 1; i <= length; ++i)
            {
                if (i % 2 == 0)
                {
                    decimal mid = (latitudeLeft + latitudeRight) / 2;
                    if (latitude > mid)
                    {
                        bits = bits * 2 + 1;
                        latitudeLeft = mid;
                    }
                    else
                    {
                        bits = bits * 2;
                        latitudeRight = mid;
                    }
                }
                else
                {
                    decimal mid = (longitudeLeft + longitudeRight) / 2;
                    if (longitude > mid)
                    {
                        bits = bits * 2 + 1;
                        longitudeLeft = mid;
                    }
                    else
                    {
                        bits = bits * 2;
                        longitudeRight = mid;
                    }
                }
                if (i % 5 == 0)
                {
                    hash += Base32Coding[bits];
                    bits = 0;
                }
            }
            return hash;
        }
        public decimal[] DeCode(string hash)
        {
            bool odd = true;
            decimal latitudeLeft = -90, latitudeRight = 90;
            decimal longitudeLeft = -180, longitudeRight = 180;
            int length = hash.Length;
            for (int i = 0; i < length; ++i)
            {
                char currentcode = hash[i];
                int bits = Base32Coding.IndexOf(currentcode);
                for (int j = 4; j >= 0; --j)
                {
                    int bit = (bits >> j) & 1;
                    if (odd)
                    {
                        decimal mid = (longitudeLeft + longitudeRight) / 2m;
                        if (1 - bit == 0)
                            longitudeLeft = mid;
                        else longitudeRight = mid;
                    }
                    else
                    {
                        decimal mid = (latitudeLeft + latitudeRight) / 2m;
                        if (1 - bit == 0)
                            latitudeLeft = mid;
                        else latitudeRight = mid;
                    }
                    odd = !odd;
                }
            }
            decimal[] ret = new decimal[2];
            ret[0] = (latitudeLeft + latitudeRight) / 2;
            ret[1] = (longitudeLeft + longitudeRight) / 2;
            return ret;
        }
    }
}

REPORT-The 2016 ACM-ICPC Asia Beijing Regional Contest Problem D. What a Beautiful Lake

REPORT-The 2016 ACM-ICPC Asia Beijing Regional Contest Problem D. What a Beautiful Lake

Problem D. What a Beautiful Lake
Description
Weiming Lake, also named “Un-named Lake”, is the most famous scenic spot in Peking University. It is located in the north of the campus and is surrounded by walking paths, small gardens, and old red buildings with typical Chinese curly roofs. The lake was once the royal garden in Qing Dynasty. Boya tower stands on a little hill beside the lake. The lake and the tower form a distinctive landscape and a symbol of Peking University.
Weiming Lake is a very good place for studying, reading, skating in the winter, and of course, jogging. More and more students and teachers run or walk around Weiming Lake every day and show how many paces they have covered in the mobile app WeChat Sports to get “Zans” (applauses).
ACMer X also enjoys jogging around Weiming Lake. His watch can measure and record an altitude value every meter. After a round of running, X collected the altitude data around the lake. Now he wants to find out the longest slope around the lake.
Input
There are no more than 20 test cases.
Each case has two lines.
The first line is an integer N (2 <= N <= 100) meaning that the length of the road around the lake is N meters. The second line contains N integers a1,a2...aN, (0<= a1,a2...aN <= 100) indicating N altitude sample values around the lake. The samples are given in clockwise order, and the distance between two adjacent samples is one meter. Of course the distance between a1 and aN is also one meter. The input ends by a line of 0. Output For each test case, print the length of the longest slope in meters. A slope is a part of the road around the lake, and it must keep going up or going down. If there are no slope, print 0. Sample Input 4 1 1 1 1 8 5 1 2 3 4 5 6 2 6 5 4 3 2 1 2 10 1 0 2 3 2 2 3 4 3 2 0 Sample Output 0 5 4 4 ============================================================== 最长连续上升子序列 将数组复制一遍连接起来,然后正着反着做两遍LICS就好了 ============================================================== [csharp] using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace What_a_Beautiful_Lake { class Program { static void Main(string[] args) { int n = 0; do { n = Convert.ToInt32(Console.ReadLine().Trim()); if (n == 0) break; int[] a = new int[n * 2]; string[] inp = Console.ReadLine().Trim().Split(' '); for (int i = 0; i < n; i++) { a[i] = Convert.ToInt32(inp[i]); a[i + n] = Convert.ToInt32(inp[i]); } int len = LICS(a); Array.Reverse(a); len = Math.Max(LICS(a), len); Console.WriteLine(len - 1); } while (true); } static int LICS(int[] A) { if (A.Length == 0) { return 0; } else if (A.Length == 1) { return 1; } int sublen = 0, templen = 1; for (int i = 1; i < A.Length; i++) { if (A[i] > A[i - 1]) { templen++; } else { templen = 1; } if (sublen < templen) { sublen = templen; } } return sublen; } } } [/csharp]

REPORT-hihoCoder太阁最新面经算法竞赛15(AC #1 #2 #3) – 16.11.19

REPORT-hihoCoder太阁最新面经算法竞赛15(AC #1 #2 #3) – 16.11.19

#1 Boarding Passes
如果有一个城市A,不在终点城市里或者它作为终点城市的次数比比作为起点城市的次数少一次,那么这个就是总起点城市。
总终点城市同理。
最开始我还以为是拓扑排序,结果只过了20%然后才意识到这个图可能会有环。

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

namespace Boarding_Passes
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = Convert.ToInt32(Console.ReadLine().Trim());
            
            Dictionary<string, int> startcities = new Dictionary<string, int>();
            Dictionary<string, int> endcities = new Dictionary<string, int>();
            int startcitycount = 0, endcitycount = 0;
            for (int i = 0; i < n; ++i)
            {
                string[] inp = Console.ReadLine().Trim().Split();
                if (!startcities.ContainsKey(inp[0]))
                {
                    startcitycount++;
                    startcities.Add(inp[0], 1);
                }
                else
                {
                    startcities[inp[0]]++;
                }
                if (!endcities.ContainsKey(inp[1]))
                {
                    endcitycount++;
                    endcities.Add(inp[1], 1);
                }
                else
                {
                    endcities[inp[1]]++;
                }
            }

            foreach (var temp in startcities)
            {
                if (!endcities.ContainsKey(temp.Key) || endcities[temp.Key] + 1 == startcities[temp.Key])
                {
                    Console.Write(temp.Key);
                    break;
                }
            }
            Console.Write(" ");
            foreach (var temp in endcities)
            {
                if (!startcities.ContainsKey(temp.Key) || startcities[temp.Key] + 1 == endcities[temp.Key])
                {
                    Console.Write(temp.Key);
                    break;
                }
            }
        }
    }
}

#2 Sorting Photo Files
排序。

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

namespace Sorting_Photo_Files
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> partStr = new List<string>();
            Dictionary<string, List<int>> partInt = new Dictionary<string, List<int>>();
            int N = Convert.ToInt32(Console.ReadLine().Trim());
            for (int i = 0; i < N; i++)
            {
                string filename = Console.ReadLine().Trim();
                var sp = split(filename);
                if (!partInt.ContainsKey(sp.Key))
                {
                    List<int> l = new List<int>();
                    partStr.Add(sp.Key);
                    l.Add(sp.Value);
                    partInt.Add(sp.Key, l);
                }
                else
                {
                    partInt[sp.Key].Add(sp.Value);
                }
            }
            foreach(var temp in partInt)
            {
                temp.Value.Sort();
            }
            partStr.Sort();
            foreach(var temp in partStr)
            {
                foreach (var temp2 in partInt[temp])
                {
                    Console.WriteLine("{0}{1}", temp, temp2);
                }
            }
        }
        public static KeyValuePair<string, int> split(string str)
        {
            KeyValuePair<string, int> retdata = new KeyValuePair<string, int>();
            for (int i = 0; i < str.Length; i++)
            {
                if (str[i] >= '0' && str[i] <= '9')
                {
                    string partA = str.Substring(0, i);
                    string partB = str.Substring(i);
                    retdata = new KeyValuePair<string, int>(partA, Convert.ToInt32(partB));
                    break;
                }
            }
            return retdata;
        }
    }
}

#3 Circle Detect
判环。DFS。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Circle_Detect
{
class Program
{
static void Main(string[] args)
{
int T = Convert.ToInt32(Console.ReadLine().Trim());
for (int Times = 0; Times < T; Times++) { string[] inp = Console.ReadLine().Trim().Split(' '); int n = Convert.ToInt32(inp[0]); int m = Convert.ToInt32(inp[1]); List[] g = new List[n + 5];
for (int i = 0; i < n + 5; i++) { g[i] = new List();
}
bool[] visited = new bool[n + 5];
for (int i = 0; i < n + 5; i++) visited[i] = false; for (int i = 0; i < m; i++) { inp = Console.ReadLine().Trim().Split(' '); int a = Convert.ToInt32(inp[0]) - 1; int b = Convert.ToInt32(inp[1]) - 1; if (!g[a].Contains(b)) g[a].Add(b); } bool flag = false; for (int i = 0; i < n; i++) { if (dfs(visited, i, g)) { flag = true; break; } } if (flag) Console.WriteLine("YES"); else Console.WriteLine("NO"); } } static bool dfs(bool[] vis,int p,List[] g)
{
if (vis[p]) return true;
vis[p] = true;
for (int i = 0; i < g[p].Count(); i++) { if (dfs(vis, g[p][i], g)) return true; } vis[p] = false; return false; } } }

HIHOCODER-WEEK123 重复次数最多的连续字串

HIHOCODER-WEEK123 重复次数最多的连续字串

拼拼凑凑,修修补补

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

namespace HIHOCODER_WEEK123
{
    class Program
    {
        static RMQ r;
        const int MAXN = 100005;
        static int[] wa = new int[MAXN];
        static int[] wb = new int[MAXN];
        static int[] ws = new int[MAXN];
        static int[] wv = new int[MAXN];
        static int[] rank = new int[MAXN];
        static int[] height = new int[MAXN];
        static int[] sa = new int[MAXN];
        static int n;
        static string ss;
        static int[] aa = new int[MAXN];
        static int[,] mn = new int[MAXN, 20];
        static bool cmp(int[] r, int a, int b, int l)
        {
            return (r[a] == r[b]) && (r[a + l] == r[b + l]);
        }
        static void DA(int[] r, int[] sa, int n, int m)
        {
            int i, j, p;
            int[] x = wa, y = wb, t = new int[MAXN];
            for (i = 0; i < m; i++) ws[i] = 0;
            for (i = 0; i < n; i++) ws[x[i] = r[i]]++;
            for (i = 1; i < m; i++) ws[i] += ws[i - 1];
            for (i = n - 1; i >= 0; i--) sa[--ws[x[i]]] = i;
            for (j = 1, p = 1; p < n; j *= 2, m = p)
            {
                for (p = 0, i = n - j; i < n; i++) y[p++] = i;
                for (i = 0; i < n; i++) if (sa[i] >= j) y[p++] = sa[i] - j;
                for (i = 0; i < n; i++) wv[i] = x[y[i]];
                for (i = 0; i < m; i++) ws[i] = 0;
                for (i = 0; i < n; i++) ws[wv[i]]++;
                for (i = 1; i < m; i++) ws[i] += ws[i - 1];
                for (i = n - 1; i >= 0; i--) sa[--ws[wv[i]]] = y[i]; //基数排序部分
                for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i++)
                    x[sa[i]] = cmp(y, sa[i - 1], sa[i], j) ? p - 1 : p++;  //更新名次数组x[],注意判定相同的
            }
        }
        static void calheight(int[] r, int[] sa, int n)
        {
            int i, k = 0;
            for (i = 0; i <= n; i++) rank[sa[i]] = i;
            for (i = 0; i < n; i++)
            {
                if (k != 0) k--;
                int j = sa[rank[i] - 1];
                while (r[i + k] == r[j + k]) k++;
                height[rank[i]] = k;
            }
        }
        static int solve(int n)
        {
            int ans = 0;
            for (int l = 1; l <= n; l++)
            {
                for (int i = 1; i + l <= n; i += l)
                {
                    int ra = r.findRMQ(i, i + l,rank);
                    if (i - l + ra % l > 0)
                        ans = Math.Max(ans, r.findRMQ(i - l + ra % l, i + ra % l, rank) / l + 1);
                }
            }
            return ans;
        }


        static void Main(string[] args)
        {
            ss = Console.ReadLine();

            n = ss.Length;
            for (int i = 0; i < n; i++)
            {
                aa[i] = ss[i] - 'a' + 1;
            }
            aa[n] = 0;
            DA(aa, sa, n + 1, 30);
            calheight(aa, sa, n);
            r = new RMQ(n, height, MAXN);
            int ans = solve(n);
            Console.WriteLine(ans);
        }
    }
    class RMQ
    {
        int[,] dp;
        public RMQ(int n, int[] array, int MAXM)
        {
            dp = new int[MAXM, Convert.ToInt32(Math.Log(MAXM) / Math.Log(2)) + 2];
            for (int i = 1; i <= n; ++i)
            {
                dp[i, 0] = array[i];
            }
            for (int i = 1; (1 << i) <= n; i++)
            {
                for (int j = 1; j + (1 << i) - 1 <= n; j++)
                {
                    dp[j, i] = Math.Min(dp[j, i - 1], dp[j + (1 << i - 1), i - 1]);
                }
            }
        }
        public int findRMQ(int  a, int b,int[] rank)
        {

            a--; b--;
            int l = Math.Min(rank[a], rank[b]) + 1, r = Math.Max(rank[a], rank[b]);
            int len = r - l + 1, i;
            for (i = 0; (1 << i) <= len; i++) ;
            i--;
            int k = Convert.ToInt32(Math.Floor((Math.Log(r - l + 1)) / Math.Log(2)));
            return Math.Min(dp[l, k], dp[r - (1 << k) + 1, k]);
        }
    }
}

RMQ问题-ST算法

RMQ问题-ST算法

ST算法(Sparse Table)
\(f(i,j) = min(f(i,j-1),f(i+{2}^{(j-1)},j-1))\)
\(f(i,j)\)是区间\([i,i+{2}^{(j-1)}]\)中的最小值,\(f[i,0]=a[i]\)
对于每一个查询\([m,n]\),找到一个k有\({2}^{k}\leq n-m+1\)
那么有两个区间:\([m,m+{2}^{k-1}]\)和\([n-{2}^{k+1},n]\)
前者为\(f(m,k)\)后者为\(f(n-{2}^{k+1},k)\)
这两个区间的最小值即为查询\([m,n]\)的最小值。

    class RMQ
    {
        int[,] dp;
        public RMQ(int n, int[] array, int MAXM)
        {
            dp = new int[MAXM, Convert.ToInt32(Math.Log(MAXM) / Math.Log(2)) + 2];
            for (int i = 0; i < n; ++i)
            {
                dp[i, 0] = array[i];
            }
            for (int j = 1; (1 << j) <= n; j++)
            {
                for (int i = 0; i + (1 << j) - 1 < n; i++)
                {
                    dp[i, j] = Math.Min(dp[i, j - 1], dp[i + (1 << (j - 1)), j - 1]);
                }
            }
        }
        public int findRMQ(int l, int r)
        {
            int k = Convert.ToInt32(Math.Floor((Math.Log(r - l + 1)) / Math.Log(2)));
            return Math.Min(dp[l, k], dp[r - (1 << k) + 1, k]);
        }
    }
REPORT-hihoCoder太阁最新面经算法竞赛14(AC #1 #2 #3) – 16.11.12

REPORT-hihoCoder太阁最新面经算法竞赛14(AC #1 #2 #3) – 16.11.12

#1 Bigint Multiplication
高精度

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

namespace Bigint_Multiplication
{
    class Program
    {
        static void calcmut(int[] n1, int[] n2, int[] res)
        {
            int pos = 0;
            foreach (var n in n2)
            {
                int[] temp = new int[n1.Length + 1];
                int co = 0;//carry-over
                int ro = 0;//rest
                for (int i = 0; i < n1.Length; ++i)
                {
                    int t = n1[i] * n + co;
                    co = t / 10;
                    ro = t % 10;
                    temp[i] = ro;
                }
                if (co > 0) temp[n1.Length] = co;
                co = 0;
                for (int i = pos; i < temp.Length + pos; ++i)
                {
                    int t = temp[i - pos] + co + res[i];
                    res[i] = t % 10;
                    co = t / 10;
                }
                pos++;
            }
        }
        static void Main(string[] args)
        {
            string[] inp = Console.ReadLine().Trim().Split(' ');
            string n1 = inp[0];
            string n2 = inp[1];
            int[] a1 = new int[n1.Length];
            int[] a2 = new int[n2.Length];
            int[] res = new int[(n1.Length + 1) * (n2.Length + 1)];
            for (int i = n1.Length - 1; i >= 0; --i)
            {
                a1[n1.Length - i - 1] = Convert.ToInt32(n1[i]) - 48;
            }
            for (int i = n2.Length - 1; i >= 0; --i)
            {
                a2[n2.Length - i - 1] = Convert.ToInt32(n2[i]) - 48;
            }
            calcmut(a1, a2, res);
            bool flag = false;
            for (int i = 0; i < res.Length; ++i)
            {
                if ((res[res.Length - i - 1] == 0) && !flag) continue;
                else { flag = true; }
                Console.Write(res[res.Length - i - 1]);
            }
            if (!flag) Console.WriteLine(0);
            //Console.ReadKey();
        }
    }
}

#2数论一·Miller-Rabin质数测试
算法导论P565
把powermod写错了,万万没想到是模幂运算写错了然后WA了三次……

using System;

namespace Milonger_Rabin
{
    class Program
    {
        static long multMod(long a, long b, long n)//a*b%n
        {
            long temp = 0;
            while (b != 0)
            {
                if ((b & 1) == 1) temp = (temp + a) % n;
                a = (a + a) % n;
                b >>= 1;
            }
            return temp;
        }
        static long powerMod(long a, long b, long n)//a^b%n
        {
            long temp = 1;
            while (b != 0)
            {
                if ((b & 1) == 1) temp = multMod(temp, a, n);
                a = multMod(a, a, n);
                b >>= 1;
            }
            return temp;
        }
        static long[] arrayA = new long[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };

        static bool Witness(long a, long n)
        {
            long m = n - 1;
            int j = 0;
            while ((m & 1)==0)
            {
                j++;
                m >>= 1;
            }
            long x = powerMod(a, m, n);
            if (x == 1 || x == n - 1) return false; // n may be prime
            while (j-->0)
            {
                //    x = exp_mod(x,2,n);
                x = x * x % n;
                if (x == n - 1) return false;
            }
            return true; //n must be composite
        }

        static bool miller_rabin(long n, int S)
        {
            if (n == 2 || n == 3 || n == 5 || n == 7 || n == 11) return true;
            if (n == 1 || (n % 2) == 0 || (n % 3) == 0 || (n % 5) == 0 || (n % 7) == 0 || (n % 11) == 0) return false;

            long x, pre, u;
            int i, j, k = 0;
            u = n - 1;

            while ((u & 1)==0)
            {
                k++; u >>= 1;
            }

            Random r = new Random();
            for (i = 0; i < S; ++i)
            {
                x = r.Next() % (n - 2) + 2;
                if ((x % n) == 0) continue;

                x = powerMod(x, u, n);
                pre = x;
                for (j = 0; j < k; ++j)
                {
                    x = multMod(x, x, n);
                    if (x == 1 && pre != 1 && pre != n - 1) return false;
                    pre = x;
                }
                if (x != 1) return false;
            }
            return true;
        }

        static void Main(string[] args)
        {
            long n = Convert.ToInt64(Console.ReadLine().Trim());
            for (long i = 0; i < n; i++)
            {
                long k = Convert.ToInt64(Console.ReadLine().Trim());
                Console.WriteLine(miller_rabin(k, 12)?"Yes":"No");
            }
        }
    }
}

#3数论二·Eular质数筛法
题目里讲的很清楚了

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

namespace EularPrimeSieve
{
    class Program
    {
        static int Sieve(int n)
        {
            bool[] prime = new bool[1000005];
            for (int i = 0; i < prime.Length; i++) prime[i] = true;
            int[] primeList = new int[100000];
            int primeCount = 0;
            for (int i = 2; i <= n; ++i)
            {
                if (prime[i])
                {
                    primeList[++primeCount] = i;
                }
                for (int j = 1; j <= primeCount; ++j) 
                {
                    if (primeList[j] * i > n)
                    {
                        break;
                    }
                    prime[i * primeList[j]] = false;
                    if (i % primeList[j] == 0)
                    {
                        break;
                    }
                }
            }
            return primeCount;
        }
        static void Main(string[] args)
        {
            int n = Convert.ToInt32(Console.ReadLine().Trim());
            Console.WriteLine(Sieve(n));
        }
    }
}
HIHOCODER-WEEK122 最长公共子串

HIHOCODER-WEEK122 最长公共子串

本来看到两个最长公共子串,我就直接掏\(O({n^2})\)算法了……比如这个……

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

namespace HIHOCODER_WEEK122
{
    class Program
    {
        static void Main(string[] args)
        {
            string str1 = Console.ReadLine();
            string str2 = Console.ReadLine();
            LCS lcs = new LCS(str1, str2);
            Console.WriteLine(lcs.Length);
        }
    }
    class LCS
    {
        public int Length { get; private set; }
        public LCS(string str1,string str2)
        {
            Length = 0;
            int lStr1 = str1.Length;
            int lStr2 = str2.Length;
            if (lStr1 == 0 || lStr2 == 0)
            {
                Length = 0;
                return;
            }
            int[,] table = new int[lStr1, lStr2];
            int longest = 0;
            for (int i = 0; i < lStr2; ++i)
                table[0, i] = (str1[0] == str2[i] ? 1 : 0);
            for (int i = 1; i < lStr1; ++i)
            {
                table[i, 0] = (str1[i] == str2[0] ? 1 : 0);

                for (int j = 1; j < lStr2; ++j)
                {
                    if (str1[i] == str2[j])
                    {
                        table[i, j] = table[i - 1, j - 1] + 1;
                    }
                }
            }
            for (int i = 0; i < lStr1; ++i)
            {
                for (int j = 0; j < lStr2; ++j)
                {
                    if (longest < table[i, j])
                    {
                        longest = table[i, j];
                    }
                }
            }
            Length = longest;
        }
    }
}

然后我就TLE了……
我想不对啊,然后一看……
要用后缀数组……
求完height之后判断一下,SA[i]和SA[i-1]是不是分别在两个串里。

//code source:http://www.xuebuyuan.com/2116000.html
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn = 420000;
int s[maxn], rs[maxn], sa[maxn], t[maxn], t2[maxn], c[maxn], Rank[maxn], height[maxn];
int n, m, k, tt, l1, l2;
char s1[maxn], s2[maxn];
#define min(x,y) x>y?y:x
#define max(x,y) x<y?y:x
inline int idx(char s)
{
	return s - 'a' + 2;
}
void getheight(int n)
{
	int i, k = 0;
	for (i = 0; i <= n; i++) Rank[sa[i]] = i;
	for (i = 0; i < n; i++)
	{
		if (k) k--;
		int j = sa[Rank[i] - 1];
		while (s[i + k] == s[j + k]) k++;
		height[Rank[i]] = k;
	}
}
void build_ss(int m, int n)
{
	n++;
	int i, *x = t, *y = t2;
	for (int i = 0; i < m; i++) c[i] = 0;
	for (int i = 0; i < n; i++) c[x[i] = s[i]]++;
	for (int i = 1; i < m; i++) c[i] += c[i - 1];
	for (int i = n - 1; i >= 0; i--)
		sa[--c[x[i]]] = i;
	for (int k = 1; k <= n; k <<= 1)
	{
		int p = 0;
		for (i = n - k; i < n; i++) y[p++] = i;
		for (i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;

		for (i = 0; i < m; i++) c[i] = 0;
		for (i = 0; i < n; i++) c[x[y[i]]]++;
		for (i = 1; i < m; i++) c[i] += c[i - 1];
		for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
		swap(x, y);
		p = 1;
		x[sa[0]] = 0;
		for (i = 1; i < n; i++)
			x[sa[i]] = (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) ? p - 1 : p++;
		if (p >= n) break;
		m = p;
	}
}
bool diff(int x, int y)
{
	int a = min(x, y);
	int b = max(x, y);
	if (a<l1 && b>l1) return true;
	return false;
}
int main()
{
	cin >> s1;
	cin >> s2;
	l1 = strlen(s1);
	l2 = strlen(s2);
	for (int i = 0; i < l1; i++)
		s[i] = idx(s1[i]);
	s[l1] = 0;
	n = l1 + 1;
	for (int i = 0; i < l2; i++)
	{
		s[n++] = idx(s2[i]);
	}
	s[n] = 1;
	build_ss(128, n);
	getheight(n);
	int ans = 0;
	for (int i = 2; i < n; i++)
	{
		if (diff(sa[i], sa[i - 1]))
			ans = max(ans, height[i]);
	}
	cout << ans;
	return 0;
}