A Friends Meeting
题意：有两个人在数轴上的不同位置，现在他们需要到一个位置碰面。每次每人只能向左或向右走1个单位，轮流进行。每个人第一次走时疲劳度＋1，第二次走时疲劳度+2，以此类推。问两个人碰面时总的疲劳度最小为多少？
思路：碰面位置为(a+b)/2.
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
int a,b;
scanf("%d%d", &a, &b);
long long ans = ;
int mid = (a + b) / ;
ans += ( + abs(mid - a))*abs(mid - a) / + ( + abs(mid - b))*abs(mid - b) / ;
printf("%I64d\n", ans);
return ;
}
B World Cup
题意：有n只球队编号为1~n,每轮从编号小的开始，选择编号比其大的最小的编号的球队比赛。问想要编号为a和b的球队进行比赛，最好情况会在第几轮？（假设在遇见之前能打败其他队伍）
思路：如果编号分别在n/2两侧，那么肯定在最后一轮碰面，否则，肯定在这之前碰面。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int main()
{
int n, a, b;
scanf("%d%d%d", &n, &a, &b);
if (a > b) a = a ^ b, b = a ^ b, a = a ^ b;
int rounds = log2(n);
int total = rounds;
while (rounds >= )
{
int tmp = n / ;
if (a <= tmp && b > tmp) break;
else if (b <= tmp) n = tmp;
else
{
n -= tmp;
a -= tmp;
b -= tmp;
}
rounds--;
}
if (rounds == total) printf("Final!\n");
else printf("%d\n", rounds);
return ;
}
C Laboratory Work
题意：有n个整数，最大和最小之差不超过2.现在让你构建一个含有n个整数的集合，其平均值和已给出的集合的平均值相同，同时最小值不超过已知最小，最大值不超过已知最大。求构建的集合和原来已知中相同的数目最小为多少？
思路：要使个数为n,且平均值还想相同，由于极差不超过2，则a,a+1,a+2的个数已知，并且只能用2个a+1替换a与a+2.
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = ;
int X[maxn],Num[];
int main()
{
int n;
scanf("%d", &n);
int Min = maxn;
for (int i = ; i <= n; i++) scanf("%d", &X[i]),Min=min(Min,X[i]);
for (int i = ; i <= n; i++) Num[X[i] - Min]++;
int n1 = Num[] + Num[] + Num[] % ;
int n2 = n - * min(Num[], Num[]);
if (n1 <= n2&&Num[]>&&Num[]>)
{
Num[] += Num[] / ;
Num[] += Num[] / ;
Num[] -= *(Num[] / );
printf("%d\n", n1);
}
else
{
int tmp = min(Num[], Num[]);
Num[] -= tmp;
Num[] += * tmp;
Num[] -= tmp;
printf("%d\n", n2);
}
bool isfirst = true;
for (int i = ; i <= ; i++)
{
while (Num[i]--)
{
if (isfirst) isfirst = false,printf("%d",i+Min);
else printf(" %d", i + Min);
}
}
printf("\n");
return ;
}
D Peculiar apple-tree
题意：有一颗苹果树，一年结一次果。苹果成熟时，每过一秒，第i个苹果会落到第Pi个苹果最初的位置(i>1),当有多个苹果同时落在一个位置时，每有两2个则相互湮灭。现在在第1个苹果的位置收苹果，问最后能够收到多少？
思路：建树，确定每个苹果所在的层次，同一层的苹果肯定最后会一同落在根上或是其他结点。判断每层苹果的奇偶数即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = ;
struct edge
{
int to, next;
edge(int tt=,int nn=):to(tt),next(nn){}
}Edge[maxn*];
int Head[maxn],totedge,ans=;
bool vis[maxn];
int Lvl[maxn],maxlevel;
void AddEdge(int from, int to)
{
Edge[totedge] = edge(to, Head[from]);
Head[from] = totedge++;
Edge[totedge] = edge(from, Head[to]);
Head[to] = totedge++;
}
void getAns(int st,int level)
{
vis[st] = true;
for (int i = Head[st]; i != -; i = Edge[i].next)
{
int to = Edge[i].to;
if (!vis[to])
{
getAns(to, level + );
Lvl[level]++;
if (level > maxlevel) maxlevel = level;
}
}
}
int main()
{
ans = ;
totedge = ;
memset(Head, -, sizeof(Head));
memset(vis, , sizeof(vis));
int n;
scanf("%d", &n);
for (int i = ; i <= n; i++)
{
int to;
scanf("%d", &to);
AddEdge(i, to);
}
Lvl[] = ;
maxlevel = ;
getAns(,);
for (int i = ; i <= maxlevel; i++) if (Lvl[i] % ) ans++;
printf("%d\n", ans);
return ;
}
E Game with String
题意：A构造一个字符串s1，并将其前k个循环左移得到s2.B现在知道s1,可以询问B在s2中的第一个字符和另一个位置上的字符为多少，如果能够唯一确定，则B赢。求B赢的最大概率？
思路：首先得到所有子串的个数（只需确定起始字符和终止字符以及字符数）。然后枚举第一个字符、字符数和第二个字符，如果只出现一次，则记录。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int Num[][][];
char str[ * ];
int main()
{
scanf("%s", str + );
int len = strlen(str + );
for (int i = ; i <= len; i++) str[len + i] = str[i];
str[len * + ] = '\0';
for (int i = ; i <=len; i++)
{
for (int j = i; j < i+len; j++) Num[str[i] - 'a'][str[j] - 'a'][j - i + ]++;
}
int ensure_string = ;
for (int i = ; i < ; i++)
{
int sum = ;//以字母i+'a'开头的字符串能够唯一确定的个数
for (int L = ; L <=len; L++)
{
int tmp = ;//以字母i+'a'开头、第二个字符为第L位能确定的个数
for (int j = ; j < ; j++)
{
if (Num[i][j][L] == ) tmp++;
}
sum = max(sum, tmp);//选择概率最大的
}
ensure_string += sum;
}
printf("%.15lf\n", 1.0*ensure_string / len); return ;
}
F Teodor is not a liar!
题意：坐标范围为[1,m]，有n个线段，给出其起点和终点。问最多问多少次可以确定有没有一个点被所有线段覆盖。
思路：如果有一个点被全部线段覆盖，那么这点两侧的所有点的覆盖段数小于等于该点。而当有猜到2、1、2这样序列时则可以确定中间这一点没有被所有线段覆盖。为了使猜的次数最多，应当所猜序列只有一个“山峰”。因此，分别从前、从后计算从1到i、从m到i的最长非严格递增子序列，最后求max(Pre[i],Suf[i+1])。
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = ;
int Pre[maxn], Suf[maxn];//Pre[i]表示[0,i]的最长非严格递增子序列的长度
int N[maxn];
int Stk[maxn], top;
const int INF = 0x3f3f3f3f;
int main()
{
int n, m;
scanf("%d%d", &n, &m);
memset(N, , sizeof(N));
for (int i = ; i <= n; i++)
{
int l, r;
scanf("%d%d", &l, &r);
N[l]++, N[r + ]--;
}
for (int i = ; i <= m; i++) N[i] += N[i - ];//得到所有端点被覆盖的线段数
top = -;
for (int i = ; i <= m; i++)
{
if (top == -)
{
Stk[++top] = N[i];
Pre[i] = top + ;
}
else
{
if (Stk[top] <= N[i])
{
Stk[++top] = N[i];
Pre[i] = top + ;
}
else
{
int index = upper_bound(Stk, Stk + top + , N[i]) - Stk;
Stk[index] = N[i];
Pre[i] = top + ;
}
}
}
top = -;
for (int i = m; i >= ; i--)
{
if (top == -)
{
Stk[++top] = N[i];
Suf[i] = top + ;
}
else
{
if (Stk[top] <= N[i])
{
Stk[++top] = N[i];
Suf[i] = top + ;
}
else
{
int index = upper_bound(Stk, Stk + top + , N[i]) - Stk;
Stk[index] = N[i];
Suf[i] = top + ;
}
}
}
int ans = ;
for (int i = ; i <= m; i++) ans = max(ans, Pre[i] + Suf[i + ]);
printf("%d\n", ans);
return ;
}