共 14 篇文章
传送门 题目大意 现在有四种随从： 圣盾亡语圣盾亡语白板 如果对方随从没有免疫，以上随从都能做到一击必杀。 词缀的效果如下： 圣盾：免疫一次伤害，免疫后圣盾消失。亡语：死亡时召唤一只1/1的藤蔓。 每回合只能发动一次攻击，游戏结束时你还有随从存活就算你获胜。你很会玩，所以你一定能找到制胜策略，哪怕只有一点可能。 给你双方随从信息，请告诉我你能否获胜。 思路 贪心处理。 藤蔓没法拿来解场，只能破圣盾，因为每个随从的血量都是1e9。没有藤蔓时只能硬解，为了亏得少一些，优先用有亡语的随从解。上述条件都满足不了了，用圣盾亡语的随从。 ```cpp #include using namespace std; int t; int a[5], b[5]; void battle() { if(b[3]) { b[3]--; b[5]++; } else if(b[4]) b[4]--; else if(b[1]) { b[1]--; b[3]++; } else { b[2]--; b[4]++; } …
传送门 题目大意 有n个球队，每个球队都和其它所有球队比一场，即一共有 [图片缺失] 原图：https://www.nowcoder.com/equation?tex=%5Cfrac%7Bn(n-1)%7D%7B2%7D&preview=true 场比赛，每天只有一场比赛。每个球队会在第一场比赛开始时到，最后一场比赛后走。请安排一个日程表，使所有球队停留的天数之和最小。输出这个日程表。 思路 样例害人啊，出题人编了一个长得很像全排列的样例... 其实仔细一想会发现全排列不仅不是通解，而且大多数情况下都不是答案。当队伍多起来时，全排列会优先满足第一个队伍，这时候其他队伍只能一个一个挨着上场，浪费了大量的等待时间。 所以最优的方案可能会是一种“折中”的方案，即不去强调每一个队的最优。 ```cpp #include using namespace std; const int INF = 0X7F7F7F7F; int t, n; int main() { cin >> t; while(t--) { cin >> n; for(int i = 2; i <= n/2; i++) …
传送门 题目大意 定义S(x)为x数位和，给出N,满足S(A)>S(B),1≤A≤B≤N的A,B组数。 ```cpp #include using namespace std; typedef long long ll; const ll mod = 1e9 + 7; ll dp[110][1810][2][2]; char c[910]; int l; ll dfs( int x, int y, int u, int v ) { ll res = 0, a, …
传送门 题目大意 定义矩阵压强=F/S，其中压力F=矩阵所有项之和，面积S=矩阵最后一行的所有项之和，求出最大压强的子矩阵，并输出这个压强。 思路 根据题设老老实实算就行了，因为面积由最后一行的元素和决定，所以倒过来去枚举每一列的所有子列求最大值就行了。 ```cpp #include using namespace std; int t; double a[205][205]; int main() { scanf("%d", &t;); while(t--) { int n, m; scanf("%d%d", &n;, &m;); for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) scanf("%lf",&a;[i][j]); …
传送门 题目大意 给定n,k，构造一个1-n的排列P，满足对于1-n中的每个i，P都存在一个长为i的子序列，并且每个子序列的和模n都余k。有解则输出任意P，无解输出-1。 思路 首先考虑判断解存在的问题。根据题意，因为P也是自己的子集，所以一定也应该满足“所有元素的和模n余k”的题设，也就是sum(1~n)%n==k，如果不满足，那自然无解。 假设k满足上述条件，接下来的命题就是判断k了。 这种看似要进行复杂的动态处理的问题大多都有规律，这题也不例外。多写两行数据会发现，当n为奇数时，sum(1~n)一定是n的整数倍，即k==0；n为偶数时，k==n/2。 根据这个写代码就好了。 ```cpp #include using namespace std; int n, k; int main() { scanf( "%d%d", &n;, &k; ); if ( n % 2 ) { if ( !k ) { for ( int i = 1; …
传送门 题目大意 有一个n 维向量空间，从这里面拿出n个01向量，设fn为选出的这n个01向量相互线性独立的概率，求 f1^ f2^...^ fn 的值。 思路 有n个向量，它们都线性无关，所以它们的空间秩也是n。每次随机的向量都会加入之前的向量空间，那么每一个向量都一定不属于之前的空间，则一共有2n个向量。 观察规律不难得到对于每个i，都有2i个向量线性相关，那么反之则有2n-2i个向量线性无关。那么有： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/image-1.png 递推计算出每个f就行了。 ```cpp #include using namespace std; typedef long long ll; const int N = 2e7 + 10; const ll MOD = 1e9 + 7; const ll INF = 500000004; …
传送门 题目大意 游戏地图可以解释为一个无穷大的矩形网格。在每个格子里，你可以安放一台金矿，或者是一部圣水采集器，又或者是大本营。你也可以把一些格子留成绿色，充满生机。然而，存在一个限制：一个大本营必须紧挨着至少一个金矿和至少一个圣水采集器。请让你地图中的大本营数量尽可能地多，并输出它在地图中的占比。 思路 赛时这题卡了很久，最后队友的答案因为精度问题就差了0.000001，属实倒霉。 情况其实挺好想的。让金矿与圣水采集器相间排布，任意的一台金矿与一部圣水采集器都不相邻，大本营插在它们之间。 ```cpp #include using namespace std; int main() { printf("%.6f", 2.0 / 3); return 0; } ```
传送门 题目大意 有t(t<1e5)次查询，每次查询给出两个数a,b(a,b<2e6)。输出一组满足下列要求的四个正整数cdef作为答案。若不存在满足条件的cdef，则输出"-1 -1 -1 -1" [图片缺失] 原图：https://uploadfiles.nowcoder.com/images/20200719/272741694_1595159660992_6C354C0B6A13C2EFCC877EBE585BFDD3 ```cpp #include using namespace std; typedef long long ll; int a, b, g, t; ll c, d, e, f; int gcd( int a, int b ) { if ( b == 0 ) return(a); return(gcd( …
传送门 题目大意 按顺时针或逆时针顺序给出n个端点的平面坐标，它们组成一个形如下图的二维几何图形， [图片缺失] 原图：https://uploadfiles.nowcoder.com/images/20200709/329336_1594306194154_C59ABE339F9E82759BF07A316C74BFF6 判断这个图形是右手形还是左手形。图形可以被旋转但不能被缩放。 思路 题设中提到图形的大小不会被改变，也就是说即使所给出的点不同，但他们之间的相对大小是绝对地，可以从这个关系入手。 可以看见，图示中最长边就是底边，它的长度是9，而大拇指是一条紧挨着它且长度为6的边，小拇指则为8。 那么可以去找相邻的3个点，如果找到长度为9的边，就去验证是否存在长度为6或8的相邻边。因为方向不确定，所以使用向量积来判断，向量积大于0时验证大拇指，反之验证小拇指。 具体地，因为题中数据均为浮点数，所以计算距离时存在小数点的精度问题。而例图中的长度均是整数。这里采用忽略小数位的方法来近似判等，即用计算所得的距离值-目标距离值，如果所得差小于一个极小数e，那么则判二者相等。 ```cpp #include using namespace std; const double E = 1e-5; const int LIM = 20; struct node { double x, y; } a[30]; int t; bool isLeft; double dis( node x, node …
传送门 题目大意 一个游戏包含n个阶段，每个阶段有四种类型： 类型0：没有鱼也没有蛤。类型1：只有一只蛤。类型2：只有一条鱼。类型3：有一条鱼和一只蛤。 在每个阶段都可以执行四种操作之一： 用一只蛤换一包鱼饵。如果有一条鱼，可以无需鱼饵抓到这条鱼。无论在此阶段有没有鱼，都可以使用一包鱼饵捕获一条鱼。跳过阶段。 要求求出每局游戏中能抓到鱼的最大条数。 思路 采用贪心的思想。首先，对于类型2、3，显然直接抓鱼是最优的，即有鱼抓鱼。但是类型0时只能用鱼饵抓鱼，类型1时只能做鱼饵或者用鱼饵抓鱼。 根据上面的分析，前导0是可以忽略的，因为我们什么都做不了。忽略后如果遇到类型2、3就直接答案++。其余情况下，优先用鱼饵抓鱼，其次用蛤来换鱼饵。在执行完整个过程后如果还有鱼饵，那么消耗两次类型1来换一条鱼。 值得注意的是，第一次遇见类型0时是没有鱼饵去捕鱼的，所以需要用一个bool来判断当前遇到类型0时是否有鱼饵。 ```cpp #include using namespace std; string s; int t, n, bait, ans; int main() { scanf( "%d", &t; ); while ( t-- ) { int i = 0; scanf( "%d", &n; ); …
传送门 题目大意 现有函数 [图片缺失] 原图：https://www.nowcoder.com/equation?tex=%5Cbegin%7Balign%7D%0Af_c(x)%26%3D%5Cmax_%7Bi%3D1%20%5Cdots%20x-1%7D%20c%20%5Ccdot%20f_c(%5Cgcd(i%2C%20x))%20%26%20x%20%3E%201%5C%5C%0Af_c(x)%26%3D1%20%26%20x%3D1%0A%5Cend%7Balign%7D 给定一些正整数对(ni, ci)，输出fci(ni)在模1e9+7意义下的函数值。 思路 观察公式不难看出fc(x)=ck，k与函数递归次数相关。要求到最大值，贪心的想法是尽可能多地递归，这样就能累乘到更多的c。最好的情况是每次递归都只消去一个 质因子，这样k=质因子的个数。 实现上，从x开始递归 ，找每个数除了自己外最大的因数，直到当前数是质数或1。记录这个过程中递归层数，这个层数就是k。可以先预存好值来提升效率。 ```cpp #include using namespace std; typedef long long ll; const int LIM = 1e6 + 10; const ll MOD = 1e9 + 7; //arr[i]中存i的质因子个数 int arr[LIM], t, n, …
传送门 题目大意 给定一个由小写字母组成的字符串S。你要执行一系列操作。有以下两种操作：1、修改：给定一个整数x，你需要根据x的值来修改S。如果x是正数，就把S中最左边的x个字母移到S的右边；否则，就把S中最右边的|x|个字母移到S的左边。2、查询：给定一个正整数x，输出字符串中第x个字符。 思路 题面很简单，朴实的字符串位移操作。上手十分钟写了个string模拟 ```cpp #include using namespace std; int q; string str; int main() { cin >> str; scanf("%d", &q;); while(q--) { int x; char op; scanf("%d", &op;); switch (op) { case 'A': scanf("%d", &x;); printf("%c\n", str[x-1]); break; case 'M': scanf("%d", &x;); …
传送门 题目大意 对于字符串s，定义s∞=ss...sss。给定字符串s,t，判断 s∞ 与 t∞ 的字典序大小关系。(|s|<1e5) 思路 两个字符串长度相等自然没话说，直接比较就行。这题的核心在处理字符串长度不等的情况。 最开始想到的朴素做法是延长两个字符串至长度为二者的最小公倍数，再来比较，但是会双超。参阅了大佬的题解后了解到了一种全新的做法：直接比较s+t与t+s。 这样做的正确性是显然地。设s的长度为lens，t的长度为lent，lens<lent。在前lens个字符进行比较时，s[i]与t[i]是一一对应的，不存在对齐问题，而进行到lens+1时，如果执行s+t操作，相当于把之前已经确认相等的子串接在s后面，即两个字符串做了等价放大。 ```cpp #include using namespace std; string x, y; int main() { while(cin >> x >> y) { if(x + y < y + x) puts("<"); else if(x + y > y + x) puts(">"); …
传送门 题目大意 给一个长度为n的序列A={1,2,3,...,n}以及置换的次数k，在对A使用k次置换P后得到新的排列B。 输入n,k和B，输出A，如果无解则输出-1。 思路 这种“给出原序列、目标序列与置换规则”的题一般都是置换群。 首先给你一个序列，假如： s = {1 2 3 4 5 6} 然后给你一个变换规则 t = {6 3 4 2 1 5} 就是每一次按照t规则变换下去 比如这样 第一次：6 3 4 2 1 5 第二次：5 4 2 3 6 1 第三次：1 2 3 4 5 …