php js做网站,wordpress加入百度统计,九江市城市建设投资有限公司,江苏中南建设集团网站是多少钱一次性写两道题T1#xff1a;一个简单的询问题目题解代码实现T2#xff1a;愤怒的小鸟题目暴搜题解暴搜代码实现状压DP题解状压DP代码实现T1#xff1a;一个简单的询问
题目
给你一个长度为 N 的序列 ai ,1≤i≤N#xff0c;和 q 组询问#xff0c;每组询问读入 l1,r1,l…
一次性写两道题T1一个简单的询问题目题解代码实现T2愤怒的小鸟题目暴搜题解暴搜代码实现状压DP题解状压DP代码实现T1一个简单的询问
题目
给你一个长度为 N 的序列 ai ,1≤i≤N和 q 组询问每组询问读入 l1,r1,l2,r2需输出 ∞∞∞ ∑get(l1,r1,x)⋅get(l2,r2,x)∑get(l1,r1,x)⋅get(l2,r2,x)∑get(l1,r1,x)⋅get(l2,r2,x) x0x0x0 get(l,r,x) 表示计算区间 [l,r] 中数字 x 出现了多少次。
输入格式 第一行一个数字 N表示序列长度。 第二行N 个数字表示 a1∼aN 第三行一个数字 Q表示询问个数。 第 4∼Q3 行每行四个数字 l1,r1,l2,r2表示询问。 输出格式 对于每组询问输出一行一个数字表示答案。
输入输出样例 输入 5 1 1 1 1 1 2 1 2 3 4 1 1 4 4 输出 4 1 说明/提示 对于20% 的数据1≤N,Q≤1000 对于另外 30% 的数据1≤ai≤50 对于 100% 的数据N,Q≤500001≤ai≤N1≤l1≤r1≤N1≤l2≤r2≤N
答案有可能超过 int 的最大值
题解
首先对于一个区间我们考虑对它进行转化使用差分 get(l,r,x)get(1,r,x)−get(1,l−1,x)get(l,r,x)get(1,r,x)-get(1,l-1,x)get(l,r,x)get(1,r,x)−get(1,l−1,x) 那么答案也就可以转化为 ∑x0∞get(l1,r1,x)⋅get(l2,r2,x)\sum_{x0}^\infty get(l1,r1,x)⋅get(l2,r2,x)x0∑∞get(l1,r1,x)⋅get(l2,r2,x) ⇓\Downarrow⇓ ∑x0∞[get(1,r1,x)−get(1,l1−1,x)]∗[get(1,r2,x)−get(1,l2−1,x)]\sum_{x0}^\infty [get(1,r1,x)-get(1,l1-1,x)]*[get(1,r2,x)-get(1,l2-1,x)] x0∑∞[get(1,r1,x)−get(1,l1−1,x)]∗[get(1,r2,x)−get(1,l2−1,x)] ⇓\Downarrow⇓ ∑x0∞get(1,r1,x)∗get(1,r2,x)−get(1,r1,x)∗get(1,l2−1,x)\sum_{x0}^\infty get(1,r1,x)*get(1,r2,x)-get(1,r1,x)*get(1,l2-1,x)x0∑∞get(1,r1,x)∗get(1,r2,x)−get(1,r1,x)∗get(1,l2−1,x) −get(1,l1−1,x)∗get(1,r2,x)get(1,l1−1,x)∗get(1,l2−1,x)-get(1,l1-1,x)*get(1,r2,x)get(1,l1-1,x)*get(1,l2-1,x)−get(1,l1−1,x)∗get(1,r2,x)get(1,l1−1,x)∗get(1,l2−1,x) 之后我们把它拆成四个询问块再用一个sign记录前面的符号± 1.get(1,r1,x)∗get(1,r2,x)()get(1,r1,x)*get(1,r2,x)()get(1,r1,x)∗get(1,r2,x)() 2.get(1,r1,x)∗get(1,l2−1,x)(−)get(1,r1,x)*get(1,l2-1,x)(-)get(1,r1,x)∗get(1,l2−1,x)(−) 3.get(1,l1−1,x)∗get(1,r2,x)(−)get(1,l1-1,x)*get(1,r2,x)(-)get(1,l1−1,x)∗get(1,r2,x)(−) 4.get(1,l1−1,x)∗get(1,l2−1,x)()get(1,l1-1,x)*get(1,l2-1,x)()get(1,l1−1,x)∗get(1,l2−1,x)() 最后我们来考虑算法以及转移过程 因为这个并没有要求强制在线其次它只有多个区间查询并没有涉及到更新 所以莫队就相较于线段树更加适合线段树有点大材小用了 get(1,r,x)∗get(1,l1,x)get(1,l,x)∗get(1,r,x)sumget(1,r,x)*get(1,l1,x)get(1,l,x)*get(1,r,x)sumget(1,r,x)∗get(1,l1,x)get(1,l,x)∗get(1,r,x)sum sum表示a[l]在[1,r]区间出现的次数 为森么是这样的呢 我们思考除开a[l]其它值出现次数并未发生改变所以对答案的影响也并没有改变 当l1就意味着多加了一个get(1,r,x)即 get(1,r,x)∗get(1,l1,x)[get(1,l,x)get(l1,l1,x)]∗get(1,r,x)get(1,r,x)*get(1,l1,x)[get(1,l,x)get(l1,l1,x)]*get(1,r,x)get(1,r,x)∗get(1,l1,x)[get(1,l,x)get(l1,l1,x)]∗get(1,r,x) 那么同理r进行移动的时候就要加减a[r]在[1,l]区间内出现的次数
故我们用两个cntl[i]cntr[i]分别表示i在[1,l]出现的次数和i在[1,r]出现的次数 这里用的莫队算法跟平常不太一样平时是用于维护[l,r]区间 而这里我们维护是是[1,l]和[1,r]
代码实现
#include cmath
#include cstdio
#include algorithm
using namespace std;
#define MAXN 50005
struct node {int id, l, r, sign, num;
}query[MAXN 2];
int n, q, tot, sum;
int a[MAXN], cntl[MAXN], cntr[MAXN];
int result[MAXN];bool cmp ( node x, node y ) {return x.num y.num ? x.r y.r : x.num y.num;
}int main() {scanf ( %d, n );for ( int i 1;i n;i )scanf ( %d, a[i] );scanf ( %d, q );int T ( int ) sqrt ( double ( n ) );for ( int i 1;i q;i ) {int l1, r1, l2, r2;scanf ( %d %d %d %d, l1, r1, l2, r2 );query[ tot] ( node ) { i, r1, r2, 1, r1 / T };query[ tot] ( node ) { i, l1 - 1, r2, -1, ( l1 - 1 ) / T };query[ tot] ( node ) { i, l2 - 1, r1, -1, ( l2 - 1 ) / T };query[ tot] ( node ) { i, l1 - 1, l2 - 1, 1, ( l1 - 1 ) / T };}sort ( query 1, query tot 1, cmp );int curl 0, curr 0;for ( int i 1;i tot;i ) {int l query[i].l, r query[i].r;while ( l curl ) {cntl[a[curl]] --;sum - cntr[a[curl]];curl --;}while ( l curl ) {curl ;cntl[a[curl]] ;sum cntr[a[curl]];}while ( r curr ) {cntr[a[curr]] --;sum - cntl[a[curr]];curr --;}while ( curr r ) {curr ;cntr[a[curr]] ;sum cntl[a[curr]];}result[query[i].id] sum * query[i].sign;}for ( int i 1;i q;i )printf ( %d\n, result[i] );return 0;
} T2愤怒的小鸟
题目
Kiana 最近沉迷于一款神奇的游戏无法自拔。 简单来说这款游戏是在一个平面上进行的。 有一架弹弓位于 (0,0) 处每次 Kiana 可以用它向第一象限发射一只红色的小鸟小鸟们的飞行轨迹均为形如 yax^2bx的曲线其中 a,b是Kiana 指定的参数且必须满足 a 0,a,b 都是实数。 当小鸟落回地面即 x 轴时它就会瞬间消失。
在游戏的某个关卡里平面的第一象限中有 n 只绿色的小猪其中第 i 只小猪所在的坐标为(xi,yi) 如果某只小鸟的飞行轨迹经过了(xi,yi)那么第 i 只小猪就会被消灭掉同时小鸟将会沿着原先的轨迹继续飞行 如果一只小鸟的飞行轨迹没有经过 (xi,yi)那么这只小鸟飞行的全过程就不会对第 i 只小猪产生任何影响。 例如若两只小猪分别位于 (1,3)和 (3,3)Kiana 可以选择发射一只飞行轨迹为 y-x^24x的小鸟这样两只小猪就会被这只小鸟一起消灭。 而这个游戏的目的就是通过发射小鸟消灭所有的小猪。
这款神奇游戏的每个关卡对 Kiana来说都很难所以Kiana还输入了一些神秘的指令使得自己能更轻松地完成这个游戏。这些指令将在【输入格式】中详述。 假设这款游戏一共有 TT 个关卡现在 Kiana想知道对于每一个关卡至少需要发射多少只小鸟才能消灭所有的小猪。由于她不会算所以希望由你告诉她。
输入格式 第一行包含一个正整数 T表示游戏的关卡总数。 下面依次输入这 T 个关卡的信息。每个关卡第一行包含两个非负整数 n,m分别表示该关卡中的小猪数量和 Kiana 输入的神秘指令类型。接下来的 n 行中第 i行包含两个正实数xi,yi表示第 i 只小猪坐标为 (xi,yi)数据保证同一个关卡中不存在两只坐标完全相同的小猪。
如果 m0表示Kiana输入了一个没有任何作用的指令。 如果 m1则这个关卡将会满足至多用⌈n/31⌉ 只小鸟即可消灭所有小猪。 如果 m2则这个关卡将会满足一定存在一种最优解其中有一只小鸟消灭了至少⌊n/3⌋ 只小猪。 保证1≤n≤180≤m≤20 xi,yi 100输入中的实数均保留到小数点后两位。
上文中符号⌈c⌉ 和⌊c⌋ 分别表示对 c 向上取整和向下取整例如⌈2.1⌉⌈2.9⌉⌈3.0⌉⌊3.0⌋⌊3.1⌋⌊3.9⌋3。 输出格式 对每个关卡依次输出一行答案。 输出的每一行包含一个正整数表示相应的关卡中消灭所有小猪最少需要的小鸟数量。
输入输出样例 输入 2 2 0 1.00 3.00 3.00 3.00 5 2 1.00 5.00 2.00 8.00 3.00 9.00 4.00 8.00 5.00 5.00 输出 1 1
输入 3 2 0 1.41 2.00 1.73 3.00 3 0 1.11 1.41 2.34 1.79 2.98 1.49 5 0 2.72 2.72 2.72 3.14 3.14 2.72 3.14 3.14 5.00 5.00 输出 2 2 3
输入 1 10 0 7.16 6.28 2.02 0.38 8.33 7.78 7.68 2.09 7.46 7.86 5.77 7.44 8.24 6.72 4.42 5.11 5.42 7.79 8.15 4.99 输出 6
说明/提示 【样例解释1】 这组数据中一共有两个关卡。 第一个关卡与【问题描述】中的情形相同2只小猪分别位于(1.00,3.00)和 (3.00,3.00)只需发射一只飞行轨迹为y -x^2 4x的小鸟即可消灭它们。 第二个关卡中有5只小猪但经过观察我们可以发现它们的坐标都在抛物线 y -x^2 6x上故Kiana只需要发射一只小鸟即可消灭所有小猪。
【数据范围】
暴搜题解
首先就是计算两个点的抛物线解析式在状压题解中我就不再阐释 y1a1*x2 b1*x y2a2*x2b2*x 可以先把a算出来也就得把b1b2消掉那么方程式分别乘上另一个方程式b的系数 再两式一减把x移过去就可以了即 b2*y1a1*b2*x2 b1*b2*x b1*y2a2*b1*x2b1*b2*x 暴力的思路就是遍历每一只猪在当前状态下已经用了多少只鸟抛物线 有多少只猪猪是一只猪孤单的死去 那么答案就是用的鸟的个数加上单独的猪的个数 1.猪猪可以多个匹配被一只鸟一次性杀死 2.猪太特殊了只能单独找一鸟抵着它杀
那我们就枚举每一个猪猪的状态单独被杀或者和前后面的某些猪一起被杀 部分阐释在代码中有呈现
暴搜代码实现
#include cmath
#include cstdio
#define MAXN 20
int T, n, m, result;
double x[MAXN], y[MAXN];
double tx[MAXN], ty[MAXN];
double pwxa[MAXN], pwxb[MAXN];bool check ( double a, double b ) {return fabs ( a - b ) 1e-7;
}void dfs ( int pig, int used, int alone ) {if ( used alone result )//最优性剪枝因为在这样下去//1.抛物线的个数1少了一只单独的猪-1并不会使答案变小//2.猪仔之前与别的猪一起被一条抛物线经过了就掠过它答案也没有变//3.猪单独被一条抛物线经过1答案反而大了//所以这种时候往下搜索最多就是保持不变一定大于当前最佳答案就没有必要搜索了return;if ( pig n ) {result used alone;return;}bool flag 0;for ( int i 1;i used;i ) {//判断之前构造的抛物线有没有一条经过了这只猪if ( check ( pwxa[i] * x[pig] * x[pig] pwxb[i] * x[pig], y[pig] ) ) {dfs ( pig 1, used, alone );flag 1;break;}}if ( ! flag ) {//看能不能把这只猪和单身的猪组个队一起死for ( int i 1;i alone;i ) {//特殊判断如果x相同意味着这是一条常函数是不可能一起死的if ( check ( tx[i], x[pig] ) )continue;double a ( y[pig] * tx[i] - ty[i] * x[pig] ) / ( x[pig] * x[pig] * tx[i] - tx[i] * tx[i] * x[pig] );double b ( y[pig] - x[pig] * x[pig] * a ) / x[pig];if ( a 0 ) {//要小于零才是匹配的组队pwxa[used 1] a;pwxb[used 1] b;double Ai tx[i], Bi ty[i];//这只猪已经和本层循环的猪配对了就要把它踢出单身狗群体for ( int j i;j alone;j ) {tx[j] tx[j 1];ty[j] ty[j 1];}dfs ( pig 1, used 1, alone - 1 );//回溯后这只猪重获单身for ( int j alone;j i;j -- ) {ty[j] ty[j - 1];tx[j] tx[j - 1];}tx[i] Ai;ty[i] Bi;}}//本层循环的猪也加入单身行列tx[alone 1] x[pig];ty[alone 1] y[pig];dfs ( pig 1, used, alone 1 );}
}int main() {scanf ( %d, T );while ( T -- ) {result 0x7f7f7f7f;scanf ( %d %d, n, m );for ( int i 1;i n;i )scanf ( %lf %lf, x[i], y[i] );dfs ( 1, 0, 0 );printf ( %d\n, result );}return 0;
} 状压DP题解
n≤18在暴搜基础上我们就可以考虑状压DP 0表示这只猪还活着1表示这只猪仔已经被鸟干死了 首先我们还是暴力跑个n2去求出以任意两只猪构造一条抛物线一次性能杀死多少猪 接着就是常规的状态转移了DP[s]DP[s]DP[s]表示当状态为s时所用的最少抛物线个数 当s状态时枚举每一条抛物线与s进行或运算有可能开始s就已经杀了某只猪 而这条抛物线让猪猪重复死亡了罢了 DP[s∣pwx[i][j]]min(DP[s∣pwx[i][j],DP[s]1)DP[s|pwx[i][j]]min(DP[s|pwx[i][j],DP[s]1)DP[s∣pwx[i][j]]min(DP[s∣pwx[i][j],DP[s]1) 此处还可以有一个优化 我们想一想如果pwx能打1247它会傻着先把后面的4,7杀了再跑回来搞1,4 肯定是一路上不走回头路不打回头猪啊 所以我们就开一个数组记录当状态为s时最先打到的猪仔是谁
状压DP代码实现
#include cmath
#include cstdio
#include cstring
#include iostream
using namespace std;
#define eps 1e-7
#define MAXN 20
int n, m, T;
double x[MAXN], y[MAXN];
int pwx[MAXN][MAXN], dp[1 MAXN];
int lowcount[1 MAXN];bool check ( double u, double v ) {return fabs ( u - v ) eps;
}void count ( double a, double b, double x1, double y1, double x2, double y2 ) {a ( y1 * x2 - y2 * x1 ) / ( x1 * x1 * x2 - x2 * x2 * x1 );b ( y1 - x1 * x1 * a ) / x1;
}int main() {for ( int i 0;i ( 1 18 );i ) {int j 1;while ( ( i ( 1 ( j - 1 ) ) ) j 18 )j ;lowcount[i] j;}scanf ( %d, T );while ( T -- ) {scanf ( %d %d, n, m );for ( int i 1;i n;i )scanf ( %lf %lf, x[i], y[i] );memset ( dp, 0x7f, sizeof ( dp ) );memset ( pwx, 0, sizeof ( pwx ) );dp[0] 0; for ( int i 1;i n;i ) {for ( int j 1;j n;j ) {if ( x[i] x[j] )continue;double a, b;count ( a, b, x[i], y[i], x[j], y[j] );if ( a 0 ) continue;for ( int k 1;k n;k )if ( check ( a * x[k] * x[k] b * x[k], y[k] ) ) pwx[i][j] | ( 1 ( k - 1 ) );}}for ( int i 0;i ( 1 n );i ) {int j lowcount[i];dp[i | ( 1 ( j - 1 ) )] min ( dp[i | ( 1 ( j - 1 ) )], dp[i] 1 );for ( int k 1;k n;k )dp[i | pwx[j][k]] min ( dp[i | pwx[j][k]], dp[i] 1 );}printf ( %d\n, dp[( 1 n ) - 1] );} return 0;
} 走了如有疑问欢迎评论欢迎指出错误
