哪个网站可以做会计试题,商城模板建站价格,网站验收 流程,做的阿里巴巴网站的放哪个科目狂欢2T1#xff1a;冒泡排序题目题解CODET2#xff1a;概率充电器题目题解CODET3#xff1a;不勤劳的图书管理员题目题解CODE我不这么认为。。。。
T1#xff1a;冒泡排序
题目
下面是一段实现冒泡排序算法的 C代码#xff1a;
for(int i1; in; i)for(int j1; j冒泡排序题目题解CODET2概率充电器题目题解CODET3不勤劳的图书管理员题目题解CODE我不这么认为。。。。
T1冒泡排序
题目
下面是一段实现冒泡排序算法的 C代码
for(int i1; in; i)for(int j1; jn-i; j)if(a[j]a[j1])swap(a[j],a[j1]);其中待排序的a数组是一个1,2…n的排列swap 函数将交换数组中对应位置的值。 对于给定的数组 a 以及给定的非负整数k 使用这段代码执行了正好k次 swap 操作之后数组 a 中元素的值会是什么样的呢
题解
首先我们要了解冒泡排序的原理举个例子
3421首先3会与4进行比较不交换 接着4与2比较交换 4往后移了一位j下标也1所以j还是映射的是4与1比较交换 外层第一轮i循环后的结果如下
32143与2比较交换 j13也右移了一位j仍映射着3与1比较交换 接着与4比较小于4中断把接力棒给44是最后一位停止交换 外层第二轮i循环后的结果如下
2134接下来让我们用理论来推导这个过程的一些规律 1.外层循环在第i次结束后对应的第i大的数就会出现在自己应该在的位置并且[n−i1,n][n-i1,n][n−i1,n]这一区间是严格不下降序列此题中是严格上升每一次交换是成单调不下降的 换言之即x会一直与右边交换直到遇到一个比x大的y然后x停下y又与右边交换直到遇到与x相似的情况…
2.对于每一个x最多只会发生一次左移因为它只会有一次与左边的数进行比较但是对于一个x可能发生多次右移但x发生多少次右移就代表着有多少个数发生了左移对于x它左移的次数为左边比它大的数的个数因为那些比它大的数必须要越过x才能到达自己应该在的位置 最后如果x左边没有比它大的数后它就会固定在这个位置因为没有数会越过它了
3.我们只考虑x左边比它大的数因为如果x要右移的话就意味着有其他的数会左移把其他数左移后留下来的位置就是x的位置啦 考虑用树状数组去求[1,i−1][1,i-1][1,i−1]区间比a[i]a[i]a[i]大的个数 然后用二分去枚举外层循环的i看能最多跑满多少次外层循环 剩下的就是跑不满的那我们就暴力转移一次即可
CODE
#include queue
#include cstdio
#include iostream
using namespace std;
#define LL long long
#define MAXN 1000005
priority_queue int q;
int n, ans;
int a[MAXN], result[MAXN];
LL k;
int maxx[MAXN], tree[MAXN];int lowbit ( int x ) {return x ( -x );
}LL query ( int x ) {LL tot 0;for ( int i x;i 1;i - lowbit ( i ) )tot tree[i];return tot;
}void add ( int x ) {for ( int i x;i n;i lowbit ( i ) )tree[i] ;
}LL check ( int x ) {LL tot 0;for ( int i 1;i n;i )tot min ( x, maxx[i] );return tot;
}void solve ( int l, int r ) {if ( l r )return;int mid ( l r ) 1;if ( check ( mid ) k ) {ans mid;solve ( mid 1, r );}elsesolve ( l, mid - 1 );
}int main() {scanf ( %d %lld, n, k );for ( int i 1;i n;i ) {scanf ( %d, a[i] );maxx[i] query ( n ) - query ( a[i] );add ( a[i] );}LL sum 0;for ( int i 1;i n;i )sum maxx[i];if ( sum k )return ! printf ( Impossible! );solve ( 1, n - 1 );for ( int i 1;i n;i )if ( maxx[i] ans )result[i - ans] a[i];elseq.push ( a[i] );for ( int i n;i 1;i -- )if ( ! result[i] ) {result[i] q.top();q.pop();if ( q.empty() )break;}k - check ( ans );for ( int i 1;i n;i )if ( result[i] result[i 1] ) {if ( ! k )break;swap ( result[i], result[i 1] );k --;}for ( int i 1;i n;i )printf ( %d , result[i] );return 0;
} T2概率充电器
题目
Luogu走一波 著名的电子产品品牌SHOI 刚刚发布了引领世界潮流的下一代电子产品—— 概率充电器 “采用全新纳米级加工技术实现元件与导线能否通电完全由真随机数决 定SHOI 概率充电器您生活不可或缺的必需品能充上电吗现在就试试看 吧”
SHOI 概率充电器由n-1 条导线连通了n 个充电元件。进行充电时每条导 线是否可以导电以概率决定每一个充电元件自身是否直接进行充电也由概率 决定。随后电能可以从直接充电的元件经过通电的导线使得其他充电元件进行 间接充电。
作为SHOI 公司的忠实客户你无法抑制自己购买SHOI 产品的冲动。在排 了一个星期的长队之后终于入手了最新型号的SHOI 概率充电器。你迫不及待 地将SHOI 概率充电器插入电源——这时你突然想知道进入充电状态的元件 个数的期望是多少呢
输入格式 第一行一个整数n概率充电器的充电元件个数。充电元件由1-n 编号。 之后的n-1 行每行三个整数a, b, p描述了一根导线连接了编号为a 和b 的 充电元件通电概率为p%。 第n2 行n 个整数qi。表示i 号元件直接充电的概率为qi%。
输出格式 输出一行一个实数为能进入充电状态的元件个数的期望四舍五入到小 数点后6 位小数。
输入输出样例 输入 3 1 2 50 1 3 50 50 0 0 输出 1.000000
输入 5 1 2 90 1 3 80 1 4 70 1 5 60 100 10 20 30 40 输出 4.300000 说明/提示 对于30%的数据n≤5000 对于100%的数据n≤5000000≤p,qi≤100
题解
又是期望哎先引入一些关于概率的计算我用通俗易懂的文字帮助大家理解不用去搞那么死板的事件我不会告诉你因为我也不是很清楚 事件A与事件B同时发生的概率事件A发生的概率*事件B发生的概率 事件A和事件B只其中一件发生的概率事件A发生的概率事件B发生的概率-事件AB同时发生的概率 可以不用看 反正下面我不用 设dp[u]dp[u]dp[u]表示uuu号充电器亮的期望 那么我们思考转移方程式如果uuu要亮只需要任意一个儿子或者父亲给它供电所以uuu点亮的期望等于自己本身亮加上父亲点亮加上任何一个儿子点亮的概率和即 dp[u]∏(v∈son[u])dp[v]∗pu,vq[u]dp[fa]∗pu,fadp[u]\prod(v∈son[u])dp[v]*p_{u,v} q[u]dp[fa]*p_{u,fa}dp[u]∏(v∈son[u])dp[v]∗pu,vq[u]dp[fa]∗pu,fa
但是这么想其实是错误的因为这个转移方程式的前提是fafafa与uuu的这一条充电线是好的但是当我们用uuu在往上去转移fafafa的时候又不能保证这一条充电线是好的并且这个转移方程式中各个儿子间会重复可能同时多个儿子供电的事件发生 因此我们反着来设dp[u]dp[u]dp[u]表示uuu号充电器不亮的期望 那么转移方程式也是类似的如果uuu不亮要所有儿子和父亲都不给它供电又有父亲算了我们先不管父亲重新定义dp[u]dp[u]dp[u]表示uuu号充电器不亮的期望且只考虑u的儿子不给它供电导致的 dp[u]∏(v∈son[u])(1−(1−dp[v])∗pu,v)∗(1−q[u])dp[u]\prod(v∈son[u])(1-(1-dp[v])*p_{u,v})*(1-q[u])dp[u]∏(v∈son[u])(1−(1−dp[v])∗pu,v)∗(1−q[u])
分条来理解含义(1−dp[v])(1-dp[v])(1−dp[v])儿子vvv亮的概率pu,vp_{u,v}pu,v这条充电线是好的相乘就是儿子vvv给uuu供电的概率再用1−()1-()1−()表示儿子不供电的概率
为什么是相乘呢因为所有儿子都不给它供电才能使得uuu不亮所以这个事件是要同时发生的并且要建立在uuu本身不亮的基础上所以是相乘结果还是用到了之前的铺垫打脸了 接下来我们必须去面对父亲了设f[u]f[u]f[u]表示uuu号充电器不亮的概率且是只考虑父亲不给它供电导致的 我们知道父子关系是相互的uuu是fafafa的一个儿子相反fafafa也是uuu的唯一父亲 所以dp[fa]dp[fa]dp[fa]的更新会有uuu的参与那么我们现在又是考虑fafafa给uuu供电 就必须把uuu给fafafa供电的概率给去掉 fafafa给uuu供电的概率且不考虑uuu是由fafafa的父亲或者fafafa的其它儿子供应的 转移方程式就出来了 f[u]1−(1−(dp[fa]∗f[fa]/(1−(1−dp[u])∗faw)))∗fawf[u]1 - ( 1 - ( dp[fa] * f[fa] / ( 1 - ( 1 - dp[u] ) * fa_w ) ) ) * fa_wf[u]1−(1−(dp[fa]∗f[fa]/(1−(1−dp[u])∗faw)))∗faw
再分条理解 dp[fa]∗f[fa]dp[fa] * f[fa]dp[fa]∗f[fa]则是父亲不亮的期望(包含有父亲的父亲和父亲的其他儿子给父亲供电的两种情况) (dp[fa]∗f[fa]/(1−(1−dp[u])∗faw)( dp[fa] * f[fa] / ( 1 - ( 1 - dp[u] ) * fa_w )(dp[fa]∗f[fa]/(1−(1−dp[u])∗faw)则是排除掉uuu给fafafa供电的概率 1−(dp[fa]∗f[fa]/(1−(1−dp[u])∗faw))1-( dp[fa] * f[fa] / ( 1 - ( 1 - dp[u] ) * fa_w ) )1−(dp[fa]∗f[fa]/(1−(1−dp[u])∗faw))则是表示fafafa亮的期望排除掉uuu供电使父亲亮起来的概率 (1−(dp[fa]∗f[fa]/(1−(1−dp[u])∗faw)))∗faw( 1 - ( dp[fa] * f[fa] / ( 1 - ( 1 - dp[u] ) * fa_w ) ) ) * fa_w(1−(dp[fa]∗f[fa]/(1−(1−dp[u])∗faw)))∗faw表示fafafa与uuu相连的充电线是好的相乘则表示父亲让uuu亮的概率 最后减掉就是不亮的概率了 最后把f[u]f[u]f[u]和dp[u]dp[u]dp[u]相乘就表示没有任何一个亲戚能给该点供电就是不亮的期望最后把每个点用 1-不亮期望加起来就是亮起来的期望即答案 精度问题就定义一个极小值即可。。。
CODE
#include cmath
#include cstdio
#include vector
using namespace std;
const int eps 1e-8;
#define MAXN 1000005
struct node {int v;double w;node ( int V, double W ) {v V;w W;}
};
vector node G[MAXN];
int n;
double result;
double dp[MAXN], f[MAXN];void dfs1 ( int u, int fa ) {f[u] 1;dp[u] 1 - dp[u];for ( int i 0;i G[u].size();i ) {int v G[u][i].v;double w G[u][i].w;if ( v fa )continue;dfs1 ( v, u );dp[u] * ( 1 - ( 1 - dp[v] ) * w );}
}void dfs2 ( int u, int fa, double fa_w ) {if ( fabs ( 1 - ( 1 - dp[u] ) * fa_w ) eps ) //维护精度 f[u] 1 - ( 1 - ( dp[fa] * f[fa] / ( 1 - ( 1 - dp[u] ) * fa_w ) ) ) * fa_w;elsef[u] 1 - fa_w;result - dp[u] * f[u];for ( int i 0;i G[u].size();i ) {int v G[u][i].v;if ( v fa )continue;dfs2 ( v, u, G[u][i].w );}
}
int main() {scanf ( %d, n );for ( int i 1;i n;i ) {int a, b;double w;scanf ( %d %d %lf, a, b, w );G[a].push_back( node ( b, w / 100 ) );G[b].push_back( node ( a, w / 100 ) );}for ( int i 1;i n;i ) {scanf ( %lf, dp[i] );dp[i] / 100;}result n;dfs1 ( 1, 0 );dfs2 ( 1, 0, 0 );printf ( %.6f, result );return 0;
}T3不勤劳的图书管理员
题目
luogu链接 加里敦大学有个帝国图书馆小豆是图书馆阅览室的一个书籍管理员。他的任务是把书排成有序的所以无序的书让他产生厌烦两本乱序的书会让小豆产生这两本书页数的和的厌烦度。现在有n本被打乱顺序的书在接下来m天中每天都会因为读者的阅览导致书籍顺序改变位置。因为小豆被要求在接下来的m天中至少要整理一次图书。小豆想知道如果他前i天不去整理第i天他的厌烦度是多少这样他好选择厌烦度最小的那天去整理。
输入格式 第一行会有两个数nm分别表示有n本书m天 接下来n行每行两个数ai和vi分别表示第i本书本来应该放在ai的位置这本书有vi页保证不会有放置同一个位置的书 接下来m行每行两个数xj和yj表示在第j天的第xj本书会和第yj本书会因为读者阅读交换位置
输出格式 一共m行每行一个数第i行表示前i天不去整理第i天小豆的厌烦度因为这个数可能很大所以将结果模10^9 7后输出
输入输出样例 输入 5 5 1 1 2 2 3 3 4 4 5 5 1 5 1 5 2 4 5 3 1 3 输出 42 0 18 28 48 说明/提示 对于20%的数据1 ≤ ai; xj; yj ≤ n ≤ 5000, m ≤ 5000, vi ≤ 10^5 对于100%的数据1 ≤ ai; xj; yj ≤ n ≤ 50000, m ≤ 50000, vi ≤ 10^5
题解
这道题与动态逆序对是类似的也是一道树套树板题 lll与rrr的交换只会影响[l1,r−1][l1,r-1][l1,r−1]区间lll与rrr我们单独判断 1.原本xxx的优先级比lll小的在交换后会与lll形成逆序对厌烦度则是这些xxx的页数和加上满足条件的xxx的个数乘以lll的页数 2.原本xxx的优先级比lll大的在交换后会与lll不再形成逆序对要减去它的厌烦度厌烦度则是这些xxx的页数和加上满足条件的xxx的个数乘以lll的页数 3.原本xxx的优先级比rrr小的在交换后会与rrr形成逆序对厌烦度则是这些xxx的页数和加上满足条件的xxx的个数乘以rrr的页数 4.原本xxx的优先级比rrr大的在交换后会与rrr不再形成逆序对减去厌烦度厌烦度则是这些xxx的页数和加上满足条件的xxx的个数乘以rrr的页数
因为线段树套平衡树和线段树套权值线段树都要T所以我被迫选择树状数组套线段树
CODE
#include cstdio
#include iostream
using namespace std;
#define LL long long
#define mod 1000000007
#define MAXN 500005
struct node {int l, r;LL v, cnt;
}tree[MAXN * 100];
int n, m, Size;
int root[MAXN * 100];
//注意开log级或者大一点不然就会TLE/RE
LL ans;
LL a[MAXN], v[MAXN];
/*内层线段树*/
void modify ( int t, int l, int r, int id, LL w1, LL w2 ) {if ( ! t )t Size;tree[t].v ( tree[t].v w1 ) % mod;tree[t].cnt ( tree[t].cnt w2 ) % mod;if ( l r )return; int mid ( l r ) 1;if ( id mid )modify ( tree[t].l, l, mid, id, w1, w2 );elsemodify ( tree[t].r, mid 1, r, id, w1, w2 );
}void query ( int t, int l, int r, int L, int R, LL s1, LL s2 ) {if ( ! t )return;if ( L l r R ) {s1 ( s1 tree[t].v ) % mod;s2 ( s2 tree[t].cnt ) % mod;return;}int mid ( l r ) 1;if ( L mid )query ( tree[t].l, l, mid, L, R, s1, s2 );if ( mid R )query ( tree[t].r, mid 1, r, L, R, s1, s2 );
}
/*外层树状数组*/
int lowbit ( int x ) {return x ( -x );
}void Modify ( int x, int id, LL w1, LL w2 ) {for ( int i x;i n;i lowbit ( i ) )modify ( root[i], 1, n, id, w1, w2 );
}void Query ( int l, int r, int L, int R, LL s1, LL s2 ) {if ( L R )return;LL w1 0, w2 0;//[l,r][1,r]-[1,l-1]for ( int i r;i 1;i - lowbit ( i ) )query ( root[i], 1, n, L, R, s1, s2 );for ( int i l - 1;i 1;i - lowbit ( i ) )query ( root[i], 1, n, L, R, w1, w2 );s1 ( s1 - w1 mod ) % mod;s2 ( s2 - w2 mod ) % mod;
}
//以下标作为外层树状数组以优先级作为内层线段树树状数组套线段树
int main () {scanf ( %d %d, n, m );for ( int i 1;i n;i )scanf ( %lld %lld, a[i], v[i] );for ( int i 1;i n;i ) {LL s1 0, s2 0;Modify ( i, a[i], v[i], 1 );Query ( 1, i - 1, a[i] 1, n, s1, s2 );ans ( ans s1 v[i] * s2 % mod ) % mod;}for ( int i 1;i m;i ) {int l, r;scanf ( %d %d, l, r );if ( l r ) {printf ( %lld\n, ans );continue;}if ( l r )swap ( l, r );//l和r进行交换只会对(l,r)区间带来影响 LL s1 0, s2 0, w1 0, w2 0;Query ( l 1, r - 1, a[l] 1, n, s1, s2 );//原本比l优先级高的在l交换后就形成了逆序对 Query ( l 1, r - 1, 1, a[l] - 1, w1, w2 );//原本比l优先级低的在交换后就不再形成逆序对 ans ( ans s1 - w1 mod ) % mod;ans ( ans s2 * v[l] % mod - w2 * v[l] % mod mod ) % mod;//注意l和r的情况刚好是相反的 s1 s2 w1 w2 0;Query ( l 1, r - 1, 1, a[r] - 1, s1, s2 );//原本比r优先级低的在交换后就形成了逆序对 Query ( l 1, r - 1, a[r] 1, n, w1, w2 );//原本比r优先级高的在交换后就不再形成逆序对 ans ( ans s1 - w1 mod ) % mod;ans ( ans s2 * v[r] % mod - w2 * v[r] % mod mod ) % mod;//单独考虑l和r之间的关系 if ( a[l] a[r] )ans ( ans v[l] v[r] ) % mod;if ( a[l] a[r] )ans ( ans - v[l] - v[r] mod ) % mod;//很巧妙如果要删掉某一个数的信息就传mod-(...)这样相加再取模就刚好消成了0实现了删除操作 Modify ( l, a[l], mod - v[l], mod - 1 );Modify ( r, a[r], mod - v[r], mod - 1 );Modify ( l, a[r], v[r], 1 );Modify ( r, a[l], v[l], 1 );swap ( a[l], a[r] );swap ( v[l], v[r] );printf ( %lld\n, ans );}return 0;
}有什么问题欢迎评论byebye
