月份:2016年10月

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

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

#1 Inventory is Full
贪心,每个格子优先取最大价值的可放物品,可放物品价值为最大可堆叠数量*单个价值,无法达到最大堆叠数量的或者剩下来的另外作为一个可放物品。

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

namespace InventoryIsFull
{
    public class Item
    {
        public long Amount { get; set; }
        public long Value { get; set; }
        public long SSize { get; set; }
        public long maxStackCount { get; set; }
        public long StackValue { get; set; }
        public long extraStackValue { get; set; }
        public Item(long A, long V, long S)
        {
            Amount = A;
            Value = V;
            SSize = S;
            maxStackCount = Amount / SSize;
            StackValue = Value * SSize;
            extraStackValue = Value * (Amount - SSize * maxStackCount);
        }
        public Item(long extSV)
        {
            StackValue = extSV;
            maxStackCount = 1;
        }
    }
    public class ItemComparer : IComparer<Item>
    {
        public int Compare(Item x, Item y)
        {
            Item ItemX = x;
            Item ItemY = y;
            if (ItemX.StackValue > ItemY.StackValue)
                return -1;
            if (ItemX.StackValue < ItemY.StackValue)
                return 1;
            return 0;
        }
    }
    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]);
            List<Item> items = new List<Item>();
            string[] strAmount = Console.ReadLine().Trim().Split(' ');
            string[] strValue = Console.ReadLine().Trim().Split(' ');
            string[] strSize = Console.ReadLine().Trim().Split(' ');
            for (int i = 0; i < M; i++)
            {
                int A = Convert.ToInt32(strAmount[i]);
                int V = Convert.ToInt32(strValue[i]);
                int S = Convert.ToInt32(strSize[i]);
                Item item = new Item(A, V, S);
                items.Add(item);
            }
            for (int i = 0; i < M; i++)
            {
                if (items[i].extraStackValue != 0)
                {
                    Item item = new Item(items[i].extraStackValue);
                    items.Add(item);
                }
            }
            items.Sort(new ItemComparer());
            
            long ans = 0;
            long count = 0;
            int f = 0;
            while (N > count)
            {
                if (items[f].maxStackCount>(N-count))
                {
                    ans += items[f].StackValue * (N - count);
                    break;
                }
                else
                {
                    ans += items[f].StackValue * items[f].maxStackCount;
                    count += items[f].maxStackCount;
                    f++;
                }
            }
            Console.WriteLine(ans);
         }
    }
}

#2 Total Hamming Distance
统计所有二进制每一位的1的个数,这一位对答案的贡献就是C1*(n-C1),然后加起来

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

namespace TotalHammingDistance
{
    class Program
    {
        public static void OneCount(long x,long[] M)
        {
            long pos = 0;
            while (x != 0)
            {
                if ((x & 1) == 1) M[pos]++;
                x >>= 1;
                pos++;
            }
        }
        static void Main(string[] args)
        {
            long n;
            n = Convert.ToInt64(Console.ReadLine().Trim());
            long[] k = new long[n];
            string[] inp = Console.ReadLine().Trim().Split(' ');
            for (long i = 0; i < n; i++)
            {
                k[i] = Convert.ToInt64(inp[i]);
            }
            long[] Count1 = new long[128];
            for (long i = 0; i < n; i++)
            {
                OneCount(k[i], Count1);
            }
            long ans = 0;
            for (long i = 0; i < 128; i++)
            {
                ans += Count1[i] * (n - Count1[i]);
            }
            Console.WriteLine(ans);
        }
    }
}

#3 Target Sum

HIHOCODER-WEEK121 最长不可重叠重复子串问题

HIHOCODER-WEEK121 最长不可重叠重复子串问题

换了个新手机然后沉文明6不能自拔……
感觉自己MDZZ……
========================================
讲道理这个题直接用WEEK120的主题代码就好,求出height数组之后二分一个k,这个k满足max{sa} – min{sa} >= k那么就说明存在一个k长度的不可重叠重复子串
好拗口
呸……
========================================

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 110000;
char str[maxn];
int wa[maxn], wb[maxn], wv[maxn], wn[maxn], a[maxn], sa[maxn];
int Rank[maxn], height[maxn];
int cmp(int* r, int a, int b, int l)
{
	return r[a] == r[b] && r[a + l] == r[b + l];
}
void DA(int* r, int* sa, int n, int m)
{
	int i, j, p, *x = wa, *y = wb, *t;
	for (i = 0; i<m; i++)wn[i] = 0;
	for (i = 0; i<n; i++)wn[x[i] = r[i]]++;
	for (i = 1; i<m; i++)wn[i] += wn[i - 1];
	for (i = n - 1; i >= 0; i--)sa[--wn[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++)wn[i] = 0;
		for (i = 0; i<n; i++)wn[wv[i]]++;
		for (i = 1; i<m; i++)wn[i] += wn[i - 1];
		for (i = n - 1; i >= 0; i--)sa[--wn[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++;
	}
	return;
}
void calheight(int* r, int* sa, int n)
{
	int i, j, k = 0;
	for (i = 1; i <= n; i++)Rank[sa[i]] = i;
	for (i = 0; i<n; height[Rank[i++]] = k)
		for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k++);
	return;
}
int minsa, maxsa;
bool check(int K, int n)
{
	for (int i = 1; i <= n; i++)
		if (height[i]< K)
		{
			minsa = sa[i];
			maxsa = sa[i];
		}
		else
		{
			minsa = min(minsa, sa[i]);
			maxsa = max(maxsa, sa[i]);
			if (maxsa - minsa >= K)return true;
		}
	return false;
}

int main()
{
	int n, k = 2;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i]; a[i]++;
	}
	a[n] = 0;
	DA(a, sa, n + 1, maxn);
	calheight(a, sa, n);
	int l = 0, r = n, mid, ans = 0;
	int Min = 1, Max = n / 2, Mid;
	while (Min <= Max)
	{
		Mid = (Min + Max) / 2;
		if (check(Mid, n))
			Min = Mid + 1;
		else Max = Mid - 1;
	}
	if (Max >= 1) cout << Max;
	else cout << 0;
	return 0;
}
HIHOCODER-WEEK120 最长可重叠重复K次子串问题

HIHOCODER-WEEK120 最长可重叠重复K次子串问题

不是我懒
而是文明6的锅
我真的不想点下一回合的,但是它就是被点下去了
这锅我不背
讲道理,这题是POJ的3882= =
用一个比较规整的模板吧,自己写实在是丑的自己都不想看第二遍
这回不写C#了,偷懒偷懒w
题目地址:http://hihocoder.com/contest/hiho120/problem/1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1010000;
char str[maxn];
int wa[maxn], wb[maxn], wv[maxn], wn[maxn], a[maxn], sa[maxn];
int Rank[maxn], height[maxn];
int cmp(int* r, int a, int b, int l)
{
	return r[a] == r[b] && r[a + l] == r[b + l];
}
void DA(int* r, int* sa, int n, int m)
{
	int i, j, p, *x = wa, *y = wb, *t;
	for (i = 0; i<m; i++)wn[i] = 0;
	for (i = 0; i<n; i++)wn[x[i] = r[i]]++;
	for (i = 1; i<m; i++)wn[i] += wn[i - 1];
	for (i = n - 1; i >= 0; i--)sa[--wn[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++)wn[i] = 0;
		for (i = 0; i<n; i++)wn[wv[i]]++;
		for (i = 1; i<m; i++)wn[i] += wn[i - 1];
		for (i = n - 1; i >= 0; i--)sa[--wn[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++;
	}
	return;
}
void calheight(int* r, int* sa, int n)
{
	int i, j, k = 0;
	for (i = 1; i <= n; i++)Rank[sa[i]] = i;
	for (i = 0; i<n; height[Rank[i++]] = k)
		for (k ? k-- : 0, j = sa[Rank[i] - 1]; r[i + k] == r[j + k]; k++);
	return;
}
int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i]; a[i]++;
	}
	a[n] = 0;
	DA(a, sa, n + 1, maxn);
	calheight(a, sa, n);
	int l = 0, r = n, mid, ans = 0;
	while (l < r)
	{
		mid = (l + r) >> 1;
		int cnt = 0, flag = 0;
		for (int i = 1; i <= n; i++)
		{
			if (height[i] >= mid) cnt++;
			if (height[i] < mid || i == n)
			{
				if (cnt + 1 >= k)
				{
					ans = max(ans, mid), flag = 1;
					break;
				}
				cnt = 0;
			}
		}
		if (flag) l = mid + 1;
		else r = mid;
	}
	cout << ans;
	return 0;
}
REPORT-2017微软秋季校园招聘在线编程笔试(AC #1,#2,#3,#4)

REPORT-2017微软秋季校园招聘在线编程笔试(AC #1,#2,#3,#4)

更新中,慢慢写
题目地址:
http://hihocoder.com/problemset/problem/1399
http://hihocoder.com/problemset/problem/1400
http://hihocoder.com/problemset/problem/1401
http://hihocoder.com/problemset/problem/1402

第一题:
简单题,数列中只要奇数与偶数相连就应该消去,那么只要还同时剩下奇数和偶数那么就必然可以消去一对。

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

namespace HIHOCODER1339
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = Convert.ToInt32(Console.ReadLine().Trim());
            string[] inp = Console.ReadLine().Trim().Split(' ');
            int a = 0, b = 0;
            for (int i = 0; i < n; i++)
            {
                if (Convert.ToInt32(inp[i]) % 2 == 0) a++;
                else b++;
            }
            int ans = a - b;
            Console.WriteLine(Math.Abs(ans));
            Console.ReadKey();
        }

    }
}

第二题:

http://hihocoder.com/discuss/question/3967
我思路是这样的 求出满足条件的最长子序列 然后与原始长度相减即可
假设valid(ch1, ch2)表示ch1、ch2可以连在一起(很好实现,二维26*26的bool矩阵即可)
用一个数组dp[26]表示目前以’a’+i结尾的最长子序列的长度,dp初始化为全0。 然后线性扫描原始串,每次更新table表即可
复杂度O(N*26)

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

namespace HIHOCODER1400
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = Convert.ToInt32(Console.ReadLine().Trim());
            string s = Console.ReadLine();
            int m = Convert.ToInt32(Console.ReadLine().Trim());
            bool[,] ban = new bool[30, 30];
            for (int i = 0; i < 30; i++) for (int j = 0; j < 30; j++) ban[i, j] = false;
            for (int i = 0; i < m; i++)
            {
                string inp = Console.ReadLine().Trim();
                ban[inp[0] - 'a', inp[1] - 'a'] = true;
                ban[inp[1] - 'a', inp[0] - 'a'] = true;
            }
            int[] dp = new int[26];

            for (int i = 0; i < n; ++i)
            {
                char ch1 = s[i];
                int temp = 1;
                for (int j = 0; j != 26; ++j)
                {
                    if (ban[ch1 - 'a', j])
                    {
                        continue;
                    }
                    else
                    {
                        temp = Math.Max(temp, dp[j] + 1);
                    }
                }
                dp[ch1 - 'a'] = temp;
            }
            Console.WriteLine(n - dp.Max());
        }
    }
}

第三题:
模拟,优先队列维护先后顺序,然后记录每个办公室空闲的时间。
顺便怒斥C#没有优先队列qwq
自己代码写得太丑了,帖我感觉比较好的一个代码把~
地址:http://blog.csdn.net/accelerator_2016/article/details/52798308#

#include <cstdio>  
#include <queue>  
#include <cstring>  
  
using namespace std;  
  
struct student_info{  
    int id,s,time,goWhich;  
    bool operator < (const student_info &a) const{  
        if(time == a.time){  
            return s > a.s;  
        }  
        return time > a.time;  
    }  
};  
  
struct student{  
    int s,t,p;  
    int order[105];  
    int time[105];  
};  
  
int n,m,k;  
student stu[10005];  
int ans[10005];  
int endTime[105];  
priority_queue<student_info> q;  
  
int main()  
{  
    int n,m,k;  
    scanf("%d%d%d",&n,&m,&k);  
    for(int i = 0; i < n; i ++){  
        scanf("%d%d%d",&stu[i].s,&stu[i].t,&stu[i].p);  
        for(int j = 0; j < stu[i].p; j ++){  
            scanf("%d%d",&stu[i].order[j],&stu[i].time[j]);  
        }  
        q.push((student_info){i,stu[i].s,stu[i].t + k,0});  
    }  
    /*while(!q.empty()){ 
        student_info now = q.top(); 
        q.pop(); 
        printf("%d %d\n",now.s,now.time); 
    }*/  
    memset(endTime,0,sizeof(endTime));  
    while(!q.empty()){  
        student_info now = q.top();  
        q.pop();  
        //printf("%d %d\n",now.s,now.time);  
        if(now.goWhich == stu[now.id].p - 1){  
            if(endTime[stu[now.id].order[stu[now.id].p-1]] < now.time){  
                ans[now.id] = now.time + stu[now.id].time[stu[now.id].p-1];  
                endTime[stu[now.id].order[stu[now.id].p-1]] = now.time + stu[now.id].time[stu[now.id].p-1];  
            }  
            else{  
                ans[now.id] = endTime[stu[now.id].order[stu[now.id].p-1]] + stu[now.id].time[stu[now.id].p-1];  
                endTime[stu[now.id].order[stu[now.id].p-1]] += stu[now.id].time[stu[now.id].p-1];  
            }  
        }  
        else{  
            if(endTime[stu[now.id].order[now.goWhich]] < now.time){  
                endTime[stu[now.id].order[now.goWhich]] = now.time + stu[now.id].time[now.goWhich];  
                now.time += stu[now.id].time[now.goWhich] + k;  
            }  
            else{  
                now.time = endTime[stu[now.id].order[now.goWhich]] + stu[now.id].time[now.goWhich] + k;  
                endTime[stu[now.id].order[now.goWhich]] += stu[now.id].time[now.goWhich];  
            }  
            now.goWhich ++;  
            q.push(now);  
        }  
    }  
    for(int i = 0; i < n; i ++){  
        printf("%d\n",ans[i]);  
    }  
    return 0;  
}  

第四题:
http://hihocoder.com/discuss/question/3970
先按照这个思路做了一遍。
我还有个想法就是先用BFS或者并查集找出独立的每个图形,然后根据中心空白的比例来判断是M还是S,毕竟S的中心是黑的M的中心是白的w

HIHOCODER-WEEK119 最大权闭合子图

HIHOCODER-WEEK119 最大权闭合子图

Source:HihoCoder http://hihocoder.com/contest/hiho119/problem/1

1. 最小割一定是简单割
简单割指得是:割(S,T)中每一条割边都与s或者t关联,这样的割叫做简单割。
因为在图中将所有与s相连的点放入割集就可以得到一个割,且这个割不为正无穷。而最小割一定小于等于这个割,所以最小割一定不包含无穷大的边。因此最小割一定一个简单割。
2. 简单割一定和一个闭合子图对应
闭合子图V和源点s构成S集,其余点和汇点t构成T集。
首先证明闭合子图是简单割:若闭合子图对应的割(S,T)不是简单割,则存在一条边(u,v),u∈S,v∈T,且c(u,v)=∞。说明u的后续节点v不在S中,产生矛盾。
接着证明简单割是闭合子图:对于V中任意一个点u,u∈S。u的任意一条出边c(u,v)=∞,不会在简单割的割边集中,因此v不属于T,v∈S。所以V的所有点均在S中,因此S-s是闭合子图。
由上面两个引理可以知道,最小割也对应了一个闭合子图,接下来证明最小割就是最大权的闭合子图。
首先有割的容量C(S,T)=T中所有正权点的权值之和+S中所有负权点的权值绝对值之和。
闭合子图的权值W=S中所有正权点的权值之和-S中所有负权点的权值绝对值之和。
则有C(S,T)+W=T中所有正权点的权值之和+S中所有正权点的权值之和=所有正权点的权值之和。
所以W=所有正权点的权值之和-C(S,T)
由于所有正权点的权值之和是一个定值,那么割的容量越小,W也就越大。因此当C(S,T)取最小割时,W也就达到了最大权。

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

namespace HIHOCODER_WEEK119
{
    class Program
    {
        static void Main(string[] args)
        {
            const int inf = 0x3F3F3F3F;
            int[,] flow = new int[1100, 1100];
            int n, m, negtivepoint = 0;
            string[] inp;
            inp = Console.ReadLine().Trim().Split(' ');
            n = Convert.ToInt32(inp[0]);
            m = Convert.ToInt32(inp[1]);
            inp = Console.ReadLine().Trim().Split(' ');
            for (int i = 0; i < m; i++)
            {
                int c = Convert.ToInt32(inp[i]);
                flow[n + 2 + i, n + m + 2] = c;
            }
            for (int i = 0; i < n; i++)
            {
                inp = Console.ReadLine().Trim().Split(' ');
                int c = Convert.ToInt32(inp[0]);
                negtivepoint += c;
                flow[1, i + 2] = c;
                int k = Convert.ToInt32(inp[1]);
                for (int j = 0; j < k; j++)
                {
                    int v = Convert.ToInt32(inp[j + 2]);
                    flow[i + 2, n + 1 + v] = inf;
                }
            }
            DINIC d = new DINIC(n + m + 2, flow);
            Console.WriteLine(negtivepoint-d.ans);
        }
    }
    class DINIC
    {
        const int INF = 0x3F3F3F3F;
        const int MAXN = 40005;
        int[,] flow;
        int[] dis;
        int n, res;
        public int ans;
        public DINIC(int a, int[,] f)//a:arc count  b:point count f:squre
        {
            n = a;
            flow = f;
            ans = 0;
            while (bfs() != 0)
            {
                while ((res = dfs(1, INF)) != 0) ans += res;
            }
        }
        private void set(int[] a, int present)
        {
            for (int i = 0; i < a.Length; i++)
            {
                a[i] = present;
            }
        }
        private int bfs()
        {
            dis = new int[MAXN];
            set(dis, -1);
            dis[1] = 0;
            Queue<int> q = new Queue<int>();
            q.Enqueue(1);
            while (q.Count != 0)
            {
                int k = q.Dequeue();
                for (int i = 1; i <= n; i++)
                {
                    if (flow[k, i] > 0 && dis[i] < 0)
                    {
                        dis[i] = dis[k] + 1;
                        q.Enqueue(i);
                    }
                }
            }
            if (dis[n] > 0) return 1;
            else return 0;
        }
        private int dfs(int x, int mx)
        {
            int a;
            if (x == n) return mx;
            for (int i = 1; i <= n; i++)
            {

                if ((flow[x, i] > 0) && (dis[i] == dis[x] + 1))
                {
                    a = dfs(i, Math.Min(mx, flow[x, i]));
                    if (a != 0)
                    {
                        flow[x, i] -= a;
                        flow[i, x] += a;
                        return a;
                    }
                }
            }
            return 0;
        }
    }
}

维吉尼亚密码分析 (密码学/c++)

维吉尼亚密码分析 (密码学/c++)


英文字母使用频率统计\(p\):
从A到Z:0.082,0.015,0.028,0.043,0.127,0.022,0.020,0.061,0.070,0.002,0.008,0.040,0.024,0.067,0.079,0.019,0.001,0.060,0.063,0.091,0.028,0.010,0.023,0.001,0.020,0.001

密钥长度推测:重合指数法
设定\(X = {x_1}{x_2}..{x_n}\)是一个含有\(n\)个字符的字符串,\(X\)的重合指数记为\({I_c}(x)\),定义为\(X\)中两个随机元素相同的概率。
假设\({f_0},{f_1},..,{f_{25}}\)分别表示字母\(A,B,..,Z\)在串X中出现的频率,则共有\(\left( {\begin{array}{*{20}{c}}n\\2\end{array}} \right)\)种方法来选取\(X\)中任两个元素。对于每一个\(i \in [0,25]\),有\[{I_c}(x) =\frac{{\sum\limits_{i = 0}^{25} {\left( {\begin{array}{*{20}{c}}{{f_i}}\\2\end{array}} \right)} }}{{\left( {\begin{array}{*{20}{c}}n\\2\end{array}} \right)}} = \frac{{\sum\limits_{i = 0}^{25} {{f_i}({f_i} – 1)} }}{{n(n – 1)}}\]
对于文本中字母\(A,B,..,Z\)出现的期望概率\({p_0},{p_1},..,{p_{25}}\),我们对于\({I_c}(x)\)的期望为\[{I_c}(x) \approx \sum\limits_{i = 0}^{25} {p_i^2} = 0.065\]
假设一个维吉尼亚密码加密的密文串为\({Y_0},{Y_1},..,{Y_{25}}\),那么我们假设密钥长度为\(m\),则有
\[\begin{array}{l}{Y_1} = {y_1}{y_{m + 1}}{y_{2m + 1}}…\\{Y_2} = {y_2}{y_{m + 2}}{y_{2m + 2}}…\\{Y_3} = {y_3}{y_{m + 3}}{y_{2m + 3}}…\\…\end{array}\]
如果密钥长度为\(m\),那么每一个\({I_c}(x)\)都应大约为0.065,如果\(m\)不是密钥长度,则这个串的\({I_c}(x)\)则应接近随机串。
对于一个完全随机串\[{I_c}(x) \approx 26{(1/26)^2} = 0.038\]

密钥推测:
知道密钥长度之后,我们还是将密文分为\(m\)列,定义数值\[{M_g} = \sum\limits_{i = 0}^{25} {{p_i}{f_{_i + g}}} \]
对于\(g \in [0,25]\),最接近0.065的\({M_g}\)可以被认定为当前列数的密钥。

注意:
必须在一定数据规模下才可以,小规模数据极易出错。
以上分析证明了维吉尼亚密码在惟密文攻击下不是安全的。

#include<iostream>
#include<string>
#include<ctype.h>
using namespace std;

double cp[] = { 0.082,0.015,0.028,0.043,0.127,0.022,0.020,0.061,0.070,0.002,0.008,0.040,0.024,0.067,0.079,0.019,0.001,0.060,0.063,0.091,0.028,0.010,0.023,0.001,0.020,0.001 };

char encode(char, char);
char decode(char, char);
int findlength(string);
int *crack(int, string);

int main()
{
	string key;
	string cipherText = "";
	cin >> key;
	int l = key.length();
	char inChar;
	int p = 0;
	while (cin >> inChar)
	{
		if (isalpha(inChar))
		{
			cipherText += encode(inChar, key[p % l]);
			p++;		
		}
	}
	cout << cipherText;
	l = findlength(cipherText);
	int *k = crack(l, cipherText);
	cout << "Key length: " << l << endl;
	cout << "Key: ";
	for (int i = 0; i < l; i++)
	{
		cout << (char)(k[i] + 'A');
	}
	cout << endl;
	for (int i = 0; i < cipherText.length(); i++)
	{
		cout << decode(cipherText[i], (k[i % l] + 'A'));
	}
	cout << endl;
	system("pause");
	return 0;
}

char encode(char c, char k)
{
	char upperC = toupper(c) - 65;
	char upperK = toupper(k) - 65;
	char code = (upperC + upperK) % 26 + 65;
	return code;
}

char decode(char c, char k)
{
	char code;
	char upperC = toupper(c) - 65;
	char upperK = toupper(k) - 65;
	if (upperC - upperK > 0)
		code = ((upperC - upperK) % 26) + 65;
	else code = (26 - abs(upperC - upperK))%26+65;
	return code;
}

int findlength(string c)
{
	int count = c.length();
	bool find = false;
	int m = 1;
	while (!find)
	{
		int ln = count / m + 1;
		char *k = new char[ln];
		double f = 0;
		for (int i = 0; i < m; i++)
		{
			int co = 0;
			for (int j = 0; j < ln; j++)
			{
				if ((j * m + i) < (c.length() - 1))
				{
					k[j] = c[j * m + i]; 
					co++;
				}
			}
			int cco = 0;
			int eq = 0;
			for (int j = 0; j < co - 2; j++)
			{
				for (int g = j + 1; g < co - 1; g++)
				{
					if (j == g) continue;
					if (k[j] == k[g]) eq++;
					cco++;
				}
			}
			double ff = (double)eq / (cco);
			f += ff;
		}
		f /= m;
		if (abs(f - 0.065) < 0.005) find = true;
		m++;
	}
	return m - 1;
}
int *crack(int m, string c)
{
	int *key = new int[m];
	int count = c.length();
	int ln = count / m + 1;
	char *k = new char[ln];
	double f = 0;
	for (int i = 0; i < m; i++)
	{
		int co = 0;
		double f[26] = { 0 };
		for (int j = 0; j < ln; j++)
		{
			if ((j * m + i) < (c.length() - 1))
			{
				k[j] = c[j * m + i];
				f[k[j] - 'A'] += 1;
				co++;
			}
		}
		
		for (int j = 0; j < 26; j++)
		{
			f[j] /= (double)co;
		}
		double Mgi[26] = { 0 };
		for (int g = 0; g < 26; g++)
		{
			double Mg = 0;
			for (int j = 0; j < 26; j++)
			{
				Mg += cp[j] * f[(j + g) % 26];
			}
			Mgi[g] = Mg;
		}
		int p = 0;
		double min = INT_MAX;
		for (int j = 0; j < 26; j++)
		{
			if (abs(Mgi[j] - 0.065) < min)
			{
				min = abs(Mgi[j] - 0.065);
				p = j;
			}
		}
		key[i] = p;
	}
	return key;
}
HIHOCODER-WEEK118 最小路径覆盖

HIHOCODER-WEEK118 最小路径覆盖

对于一个有向无环图,最少路径覆盖数=点数-二分图最大匹配
例题+题解:http://hihocoder.com/contest/hiho118/problem/1
代码:

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

namespace DINIC
{
    class Program
    {
        static void Main(string[] args)
        {
            int n;
            int[,] flow = new int[1100, 1100];
            int a, b;
            string[] inp;
            inp = Console.ReadLine().Trim().Split(' ');
            a = Convert.ToInt32(inp[0]);
            b = Convert.ToInt32(inp[1]);
            n = 2 * a + 2;
            for (int i = 0; i < b; i++)
            {
                int u, v;
                inp = Console.ReadLine().Trim().Split(' ');
                u = Convert.ToInt32(inp[0]);
                v = Convert.ToInt32(inp[1]);
                u += 1;
                v = v + a + 1;
                flow[u, v] = 1;
            }
            for (int i = 0; i < a; i++)
            {
                flow[1, i + 2] = 1;
                flow[i + 2 + a, n] = 1;
            }
            DINIC d = new DINIC(n, flow);
            a = a - d.ans;
            Console.WriteLine(a);
        }
    }

    class DINIC
    {
        const int INF = 50000;
        const int MAXN = 40005;
        int[,] flow;
        int[] dis;
        int n, res;
        public int ans;
        public DINIC(int a, int[,] f)//a:arc count  b:point count f:squre
        {
            n = a;
            flow = f;
            ans = 0;
            while (bfs() != 0)
            {
                while ((res = dfs(1, INF)) != 0) ans += res;
            }
        }
        private void set(int[] a, int present)
        {
            for (int i = 0; i < a.Length; i++)
            {
                a[i] = present;
            }
        }
        private int bfs()
        {
            dis = new int[MAXN];
            set(dis, -1);
            dis[1] = 0;
            Queue<int> q = new Queue<int>();
            q.Enqueue(1);
            while (q.Count != 0)
            {
                int k = q.Dequeue();
                for (int i = 1; i <= n; i++)
                {
                    if (flow[k, i] > 0 && dis[i] < 0)
                    {
                        dis[i] = dis[k] + 1;
                        q.Enqueue(i);
                    }
                }
            }
            if (dis[n] > 0) return 1;
            else return 0;
        }
        private int dfs(int x, int mx)
        {
            int a;
            if (x == n) return mx;
            for (int i = 1; i <= n; i++)
            {

                if ((flow[x, i] > 0) && (dis[i] == dis[x] + 1))
                {
                    a = dfs(i, Math.Min(mx, flow[x, i]));
                    if (a != 0)
                    {
                        flow[x, i] -= a;
                        flow[i, x] += a;
                        return a;
                    }
                }
            }
            return 0;
        }
    }
}