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