题目链接：https://ac.nowcoder.com/acm/contest/19483/D简要题意：给出一个不超过5阶的多项式，再给出一个数组a。m次修改，每次找一段区间[L,R]，给区间里的每个数分别加上f(1),f(2),...,f(r-l+1)利用数学定理：最高次项为n次的n阶多项式差分后余项为常数。因此，f做6次差分后，余项为一串0（也可通过如下打表寻找规律）所以，我们可以先把a做6阶差分，再把每次出来的函数f也做6阶差分，将其加入a中。这样就能保证每次加入a的是有限项（我是算了15项），从而将O(NM)的复杂度降到O(M)需要注意的是，f加入a的有效区间是[L,n],n为数组a...

题目链接：https://ac.nowcoder.com/acm/contest/19483/G 模型总结：模型1：等差数列原数组： 0 1 0 0 0 0前缀和： 0 1 1 1 1 1再前缀和：0 1 2 3 4 5 模型2：平方数列原本数组： 1 1 0 0 0 0 01次前缀和：1 2 2 2 2 2 22次前缀和：1 3 5 7 9 11 133次前缀和：1 4 9 16 25 36静态数组求前对后的影响时，考虑前缀和 本题采用模型一。给原数组做一次前缀和，就能算出该位置之前有多少个1；再求一次前缀和，就能得到前面的1对该位置的影响。需要注意下标的问题：（以10...

链接：https://ac.nowcoder.com/acm/contest/19483/I简要题意：对于一个全0数组，每次可以选一段[l,r]，将里头元素全部+1.问要想生成给定数组a，至少需要几次操作分析：差分数组的应用考虑差分数组。每次选择长度[l,r]进行+1时，差分数组中d[r+1]-1，d[l]+1.因此，差分数组中的正数和与负数和相等，且恰好等于操作次数需要注意全0数组的条件，读入a[1]到a[n]之后，记得考虑a[0]=0和a[n+1]=0 #include <bits/stdc++.h> using namespace std; typedef long long...

题目链接：https://ac.nowcoder.com/acm/contest/19483/E题目一上手，很容易想到动态规划。用dp[i][0]表示从第1层到达第i层左边的方案数，dp[i][1]表示从第1层到达第i层右边的方案数：当梯子为'/'时， dp[i][1]=dp[i-1][0]+dp[i-1][1] dp[i][0]=dp[i-1][0]当梯子为'\'时 dp[i][1]=dp[i-1][1] dp[i][0]=dp[i-1][0]+dp[i-1][1]初值dp[1][0]=dp[1][1]=1这时可以发现，该转移方程可写成矩阵形式为了表示初位置是...

题目链接：https://ac.nowcoder.com/acm/contest/19483/F简要题意：给出一个长为10的数组，其中仅含0-9且每个数恰好出现一次。给出一个操作集，每次操作可以调换两个数。现在仅针对集合中[l,r]的一小段进行操作，求操作结果这里采用的是广义前缀和的思想，当连续的操作产生某个叠加影响时，这种影响可以通过某种反向操作进行撤销。我们假设第i次操作后状态为a[i]，初状态为a[0]，经过一系列操作后变成状态B，再经一系列操作后变状态A。如下图，a[0]={1,2,3}经转换先变成B={3,1,2}，再变成A={x,y,z}。下面考虑的问题就是，如何在A中抵消掉从a[...

简要题意：给出一个字符串，求增加多少字符能使之回文方法：串长减去最长回文子序列长度，即增加非最长回文串的内容传统方法dp[i] [j]表示i到j最长回文串长度若s[i]==s[j]，dp[i] [j]=dp[i+1] [j-1]+2否则dp[i] [j] = max(dp[i+1] [j],dp[i] [j-1])注意开一个5005*5005的int数组会爆空间优化法一：改成short数组，short范围 -32768~32767，即-2^15 ~ 2^15-1 #include <iostream> #include <cstdio> #include <a...

简要题意：给一串数，找连续两串使其和最大 传统求最大子串的方法不能保证两段不相交，因此考虑多开个b数组记录以它开头的最大子串 令a[i]为以i结尾的子串最大和，b[j]为以j开头的子串最大和，这样ans=max(a[i]+b[j])，这样需要O(n^2) 下面考虑将其优化成O(n): 法一：(官方题解)将a[i]更新成a[i]是以0.....i的子串最大和，b[j]为以j.......n-1开头的子串最大和，这样ans=max(a[i]+a[i+1])链接：https://www.nowcoder.com/ta/acm-solutions/review?tpId=20&tqId=143...

一开始我去考虑每个空格接受的球，后来发现想复杂了。如果最上面定义为第0行，最下面是第n-1行，那么我们可以手动补充第n行，也就是把最下面的每个格子都看成一个钉子。这样就不用考虑空格了，只需考虑钉子的事情。 令dp[i][j]为走到第i行第j列的球数，sum为最后一行的总和，那么所求的答案就是dp[n][m]/sum 考虑每个点对下方的影响，即“我为人人”型：这里采用基数的方法，假设球通过每个钉子后会自动裂开成左右两半，下方两边的钉子各接受一个，即钉子存在时，dp[i+1][j]+=dp[i][j]，dp[i+1][j+1]+=dp[i][j] 当(i,j)处的钉子不存在时，(i,j)的球都会落...

早

目标：影响力最大的冲突事件最小常见思路：①贪心；②二分；③搜索、动态规划 贪心：先按照冲突从大到小排序，冲突大的先分开：对每个罪犯建两个点，表示他在A或B监狱。若两人分开，则 罪犯1在A监狱 与 罪犯2在B监狱 合并、1在B与2在A合并。如果后面想分开两人时，发现他们已经在同一集合中，则这个事件就是今年冲突最大的事件 #include <bits/stdc++.h> using namespace std; struct point{ int x,y,nu; }a[100010]; int comp(struct point p,struct point q){ r...

2014上海区域赛真题uva一直连不上，下面的代码是我在vjudge上提交的首先，敌人按照防御从大到小排序，先解决防御强的敌人，这里用结构体数组保存就可以了。我方按照攻击力从大到小排序。每次解决防御最强的敌人：先把我方攻击力高于对方防御的人加入集合s，则集合s中的人都是这次行动的可能人选。由于对方防御从大到小排序，因此只要某人进入了集合s，那么他必定也能解决后面的敌人。下面的问题就是，在集合s中如何找到这次出站的人。如果甲能打败敌人且能存活，乙能打败敌人却不能存活，这时候就要选择能存活的人。可以想象一下，如果选择了乙上场，那么后面甲面对新的敌人，可能存活也可能牺牲。这样在甲乙两人之中最多存活一...