【题目链接】 Problem Description Before the start of contest, there are n ICPC contestants waiting in a long queue. They are labeled by 1 to n from left to right. It can be easily found that the i-th contestant’s QodeForces rating is ai. Little Q, the coach of Quailty Normal University, is bored to jus...

【题目链接】 int cursor = 0; for (int i = 0; ; ++i) { for (int j = 0; j <= i; ++j) { M[j][i - j] = A[cursor]; cursor = (cursor + 1) % L; } } 题目意思 给你一个T，表示案例数量，给次给一个n，n个数字，要求按上面公式打表，每次询问，给两个点，要求计算以两个点位顶点的矩阵中元素的和。 多打几次表，可以发现当n为奇数时，a[i][j]=a[i-2n][j]=a[i][j-2n]，所以对每个点分块化，其中query函数是求（0，0）与（i，j）构成...

【题目链接】 题目意思 给你一个T，表示案例数量，给次给4*4块的数独，其中每一块数独都是4*4且不重复的，每一块数独只能顺时针反转，求使得数独合法的最少翻转次数。 直接暴搜加上可行性剪枝和最优性剪枝即可。 数独的限制较强，可行性剪枝的效果很好。 对每一块数独从上到下，从左到右遍历，每遍历一块，判断是否合法，若不合法就旋转一次再判断。 判断过程如下图所示，假设我们现在搜到了红色块区域，我们要对每一条蓝线和绿线查找有没有相同的元素，若有，则红色块不合法，反之，搜索下一块。 这里flag和book作为一个全局变量，flag作为标记每一次查询都是不同的，book数组标记这个数字在第...

【题目链接】 题目意思 题目：给定平面上 n 个点，起点横坐标最小，终点横坐标最大。每一个点都在 x 轴上方，每次可以飞到一个横坐标严格更大的点，代价为两个坐标的叉积。求起点到终点总代价最小的飞行路线，并输出字典序最小的路线。 给定平面上 n 个点，起点横坐标最小，终点横坐标最大。每次可以飞到一个横坐标严格更大的点，代价为两个坐标的叉积。 求起点到终点总代价最小的飞行路线，并输出字典序最小的路线。 显然坐标相同的点里只保留编号最小的点最优。 将起点到终点的路径补全为终点往下走到无穷远处，再往左 走到起点正下方，再往上回到起点。 任意路径中回到起点部分的代价相同，观察代价和的几何意 义...

【题目链接】 题目意思 给你T组数据，每组数据给你两个正整数n,k，你每次可以交换任意两个数，总的交换次数不超过k次，问你在k次之内这个数可以变成的最大值和最小值是多少 思路分析 下面所有思路分析都是看了杜老师代码才想到的。 首先对其预处理，枚举所有可能情况（init函数）： 枚举1-9的全排列，假设当前枚举到6，判断当前的排列是由123456经过多少次数字交换得到的，然后我们计算出这个排列的数值并压入v[6][交换次数]。 代码中v[i][j]指的是里面存的是i位数字，并且可以通过j次交换，将里面的数字转化为123…i。 apply函数用来计算若数字下标按*it所指示的下标位...

【题目链接】 题目意思 给n,m两个数字，n表示有n个人，m表示总时长，要你求最大同时观看人数，下面n行给出两个数字si,ti，表示第i个人的观看时间si-ti，求最大同时观看人数和平均观看人数。 好像就是一个板子题？给你n个区间，让你求n个区间中某个值出现的最大次数。 #include<iostream> #include<algorithm> using namespace std; int a[250001], b[250001], n; int main() { int m, in = 1, mx = 1, f; double sum =...

【题目链接】 题目意思 给你一个正整数N(N<10000)，随后给出N个正整数，从这N个数中选任意个数字，要求任意个数字的和能整除N，先输出数字个数，然后按任意序列输出所有数字。 Sample Input 5 1 2 3 4 1 Sample Output 2 2 3 思路分析 求序列的前缀和（并对N取模），当发现两个相等的前缀和时（s[i]%n==s[j]%n），即可判断，sum[k] k from i+1 to j，可以整除N，包括s[0]=0，共有n+1个前缀和，因为前缀和都是小于N的，所以一定存在前缀和相等的两项。（抽屉定理） #incl...

一开始的思路就是暴力，先求出最后一个值的位置op，然后遍历数组，找到第op个没有被占领的点，将最后一个值存到这个点，然而TLE了。 TLE代码 #include <iostream> #include <cmath> using namespace std; int a[100001], ans[100001], book[100001]; //book[i]记录点i是否被占领 int main() { int n; scanf("%d", &n); int t = n; for (int i = 1;...

【题目链接】 题目意思 给你一个序列，从第一个数字开始，当这个数字大于我之前找到的最大值时，（一定）取这个数字并更新最大值，每次询问给两个数字p,q，将a[p]的值修改为q，问每次单点修改后最多可以取多少个数字。 Sample Input 1 5 3 1 2 3 4 4 1 5 5 5 2 3 Sample Output 1 5 3 Hint For the first query, the heights of the apples were 5, 2, 3, 4, 4, so Taotao would only pick the first a...

【题目链接】 题目意思 T组案例，每组案例给两个整数n,m，表示n个怪物和m个能力值，下面一行给出人的m个能力值，下面n行，每行给出2m个数字，表示怪物的m个能力值和打败该怪物后，人的各m个能力可以增加的数值，求人最多打败多少个怪物并输出人的各项能力值。 这里吐槽一下题目，必须要加读入挂才能过，不然TLE。 Sample Input 1 4 3 7 1 1 5 5 2 6 3 1 24 1 1 1 2 1 0 4 1 5 1 1 6 0 1 5 3 1 Sample Output 3 23 8 4 Hint For the sample, ini...

【题目链接】 题目意思 T组案例，每组案例两行，第一行三个数字表示第一个人的剪刀牌，石头牌，布牌的数量，第二行表示第二个人的牌的数量，求第一个人赢过第二个人的期望。 Sample Input 4 2 0 0 0 2 0 1 1 1 1 1 1 1 0 0 0 0 1 123 456 789 100 200 1068 Sample Output 2 0 -1 3552/19 解题思路 枚举九种可能情况就过了？赛后吉老师说还要证明公式啥的，好复杂，算了，还是枚举吧。 听说还要特判是个负数？提交还WA了一发，赛后发现负数好像可以取模啊，...

【题目链接】 题目意思 T组案例，给一个n，根据下面的代码求cnt. for (int i = 1; i <= n; i++) { for (int j = 1; j < i; j++) { if (gcd(i + j, i - j) == 1) cnt++; } } Sample Input 4 978 438 233 666 Sample Output 194041 38951 11065 89963 解题思路 看题目第一想法，肯定和欧拉函数有关，先打个表，丢...

【题目链接】 题目意思 T组案例，给一个n，然后给n个数字，给出n个数字，从第一个点走到最后一个点，可以在任意一个点以ai的价格买或者卖物品，求最大利润和最大利润下的最少次数。 Sample Input 3 4 1 2 10 9 5 9 5 9 10 5 2 2 1 Sample Output 16 4 5 2 0 0 Hint In the first case, he will buy in 1, 2 and resell in 3, 4. profit = - 1 - 2 + 10 + 9 = 16 In the second cas...

【题目链接】 题目意思 T组案例，给一个n，下面n行，每行三个数字(x,y,v)表示点（x,y）处的值为v，只有当从(x-1,y-1)走到(x,y)时，才能获得点(x,y)的v值，求从(0,0)走到(1e9,1e9)时的最大收获值。 Sample Input 1 3 1 1 1 1 2 2 3 3 1 Sample Output 3 解题思路 离散化+树状数组维护区间最大值，首先看到题目肯定想到简单dp，无奈数据量实在太大了，遍历O(n)都会超时的那种，因为n<100 000，所以想到离散化，将n的坐标离散化处理，使其均小于等于100 000，然后排序用...