【链接】
http://www.codeforces.com/contest/253【A. Boys and Girls】
【题目大意】
让N个男孩，M个女孩排在一行，使得相邻的孩子（i && i+1）性别不同的个数最大
【参考算法】
让男孩和女孩相间排列显然是一种比较优秀的选择。
如果男孩比女孩多，那么先排男孩，然后女孩，直到女孩都被领走了，后面排剩下的男孩。
反之相同。
【小结】
No？
【参考代码】
A.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MaxN = 100001;
int a[MaxN];
int n , m , i;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
while (cin >> n >> m)
{
if (n>=m)
{
for (i=1;i<=m;i++) cout << "BG";
for (i=1;i<=n-m;i++) cout << "B";
cout << endl;
} else
{
for (i=1;i<=n;i++) cout << "GB";
for (i=1;i<=m-n;i++) cout << "G";
cout << endl;
}
}
return 0;
}【B. Physics Practical】
【题目大意】
有N个数，让你取出k个数，使得剩下的n-k个数中的最大值y和最小值x满足 x*2 >= y
让你求最小的k
【参考算法】
先将这N个数按升序排序。这样我们给每个数定义一个值F[i]表示以它为最小的数时最多可以囊括到序列的第几个数
显然F[i]是升序的，所以我们可以用一个指针j来表示第i个数的F[i]值
最终答案就是min( N - (F[i]-i+1) )
【小结】
No.
【参考代码】
B.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int MaxN = 100001;
int a[MaxN];
int n , m , i;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
while (cin >> n)
{
for (i=1;i<=n;i++) cin >> a[i];
sort(a+1,a+n+1);
int j = 0 , ans = 0;
for (i=1;i<n;i++)
{
while (a[i]*2 >= a[j+1] && j < n) j++;
if (ans < (j - i + 1)) ans = j - i + 1;
}
cout << n - ans << endl;
}
return 0;
}
【C. Text Editor】
【题目大意】
模拟在TXT文件中光标的移动，使得给定的开始位置(r1,c1)到结束位置(r2,c2)的按上下左右的次数最少。
【参考算法】
用 y 表示 从 r1 行到 x 行 再从 x 行到 r2 行 的光标位置
则答案就是min(abs(c2-y) + abs(r1-x) + abs(r2-x))
【小结】
y = min(c1,a[x..r1],a[x..r2])
n 只有100，所以枚举或者n^2预处理出来就行了。。
唉。。我还写了个RMQ。。屌丝了。。。
【参考代码】
C.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MaxN = 100001;
int a[MaxN];
int rmq[MaxN][20];
int n , i , r1 , c1 , r2 , c2;
int abs(int x)
{
if (x > 0) return x; else return -x;
}
void RMQ()
{
for(int i=1;i<=n;i++) rmq[i][0] = a[i];
int t = (int)floor(log((double)n)/log(2.0));
for (int j=1;j<=t;j++)
for (int i=1;i<=n-(1 << j)+1;i++)
{
if (rmq[i][j-1] <= rmq[i + (1 << (j-1))][j-1])
rmq[i][j] = rmq[i][j-1]; else
rmq[i][j] = rmq[i + (1 << (j-1))][j-1];
}
}
int find(int l , int r)
{
if (l > r)
{
int temp = l;
l = r;
r = temp;
}
int t = (int)floor(log((double)(r-l)+1.0)/log(2.0));
if (rmq[l][t] <= rmq[r - (1 << t) + 1][t]) return rmq[l][t]; else
return rmq[r - (1 << t) + 1][t];
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
while (cin >> n)
{
int t , x;
for (i=1;i<=n;i++) { cin >> a[i]; a[i]++; }
RMQ();
cin >> r1 >> c1 >> r2 >> c2;
int ans = 1000000007;
for (i=1;i<=n;i++)
{
t = find(i,r1);
x = 0;
x += abs(r1-i);
t = min(t,find(i,r2));
x += abs(r2-i);
t = min(c1,t);
t = abs(c2-t);
if (x + t < ans) ans = x + t;
}
cout << ans << endl;
}
return 0;
} 【Table with Letters - 2】
【题目大意】
给你一个N*M的字符矩阵，让你求它规定的矩阵存在多少
规定的矩阵要求：
1.矩阵四个角必须一样
2.矩阵里面包含的'a'字符不能超过K
【参考算法】
枚举I行和J行(或列，以下使用行进行计算) (其中 I < J )
然后找出 ch 字符（'a'..'z'）在两行中共同出现的位置E[i]
将E[i]排序
定义两个指针i ，j 表示在E[i]位置时，在满足矩阵包含的'a'字符不超过K时最多可以到E[J] (i < j)
这样ANS = ∑ 满足条件的i ，j的( j - i )
在读入数据的时候 利用边表 得到 每行的 ch 字符 的降序序列C[I]
然后比较 C[I] 和 C[J] 就可以得到 E[i]
对于条件2可以预处理出 sum[i][j]表示 (1,1) 到 (i,j)的'a'的个数
判断的时候就可以这样 sum[J][E[j]] - sum[I-1][E[j]] - sum[J][E[i]-1] + sum[I-1][E[i]-1] <= K
【小结】
写的好像有点渣。。
最大的答案是 （400*399）^2/4 超过了int ，所以要用long long 表示ANS
【参考代码】
D.
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
const int MaxN = 401;
char a[MaxN][MaxN];
int sum[MaxN][MaxN];
int first[MaxN][27];
int next[MaxN*MaxN];
int b[MaxN*MaxN];
int c[MaxN] , d[MaxN] , e[MaxN];
int n , m , limit , tot;
int l1 , l2 , l;
long long ans;
int find(int r1 , int c1 , int r2 , int c2)
{
return sum[r2][c2] - sum[r1-1][c2] - sum[r2][c1-1] + sum[r1-1][c1-1];
}
void calc(int r1 , int r2)
{
l = 0;
int i = 1, j = 1 , t;
if (l1 < 2 || l2 < 2) return;
while (i <= l1 && j <= l2)
{
if (c[i] == d[j])
{
l++;
e[l] = c[i];
i++;
j++;
} else
if (c[i] < d[j]) j++; else i++;
}
if (l < 2) return;
i = 1; j = 1;
while (i <= l)
{
if (i > j) j = i;
t = find(r1,e[j+1],r2,e[i]);
while (t <= limit && j < l)
{
j++;
t = find(r1,e[j+1],r2,e[i]);
}
ans += (long long)(j-i);
i++;
}
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
while (cin >> n >> m >> limit)
{
memset(first,0,sizeof(first));
int t , i , j , k ;
tot = 0; ans = 0;
for (i=1;i<=n;i++)
{
getchar();
for (j=1;j<=m;j++)
{
scanf("%c",&a[i][j]);
t = a[i][j] - 96;
tot++;
next[tot] = first[i][t];
b[tot] = j;
first[i][t] = tot;
}
}
for (i=1;i<=n;i++)
for (j=1;j<=m;j++)
{
sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1];
sum[i][j] += (a[i][j] == 'a');
}
for (i=1;i<n;i++)
for (j=i+1;j<=n;j++)
{
for (k=1;k<=26;k++)
{
l1 = 0; l2 = 0;
t = first[i][k];
while (t)
{
l1++;
c[l1] = b[t];
t = next[t];
}
t = first[j][k];
while (t)
{
l2++;
d[l2] = b[t];
t = next[t];
}
calc(i,j);
}
}
cout << ans << endl;
}
return 0;
}