### 月份：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;

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)
{
int N = Convert.ToInt32(inp[0]);
int M = Convert.ToInt32(inp[1]);
List<Item> items = new List<Item>();
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);
}
for (int i = 0; i < M; i++)
{
if (items[i].extraStackValue != 0)
{
Item item = new Item(items[i].extraStackValue);
}
}
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

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

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;
long[] k = new long[n];
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 最长不可重叠重复子串问题

========================================

========================================

#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次子串问题

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

namespace HIHOCODER1339
{
class Program
{
static void Main(string[] args)
{
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));
}

}
}


http://hihocoder.com/discuss/question/3967

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

namespace HIHOCODER1400
{
class Program
{
static void Main(string[] args)
{
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++)
{
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());
}
}
}



#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

HIHOCODER-WEEK119 最大权闭合子图

## HIHOCODER-WEEK119 最大权闭合子图

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

1. 最小割一定是简单割

2. 简单割一定和一个闭合子图对应

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

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;
n = Convert.ToInt32(inp[0]);
m = Convert.ToInt32(inp[1]);
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++)
{
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++)

$\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}$

#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 最小路径覆盖

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

namespace DINIC
{
class Program
{
static void Main(string[] args)
{
int n;
int[,] flow = new int[1100, 1100];
int a, b;
string[] inp;
a = Convert.ToInt32(inp[0]);
b = Convert.ToInt32(inp[1]);
n = 2 * a + 2;
for (int i = 0; i < b; i++)
{
int u, v;
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;
}
}
}