杭州网站建设的公司,wordpress flat 下载,php装饰公司网站源码,微网站建设方案书文章目录T1#xff1a;玩个三角形titlesolutioncodeT2#xff1a;玩个球titlesolutioncodeT3#xff1a;玩个树titlesolutioncodeT1#xff1a;玩个三角形
title
题目描述
考虑一个 n ∗ n 的矩阵 A#xff0c;初始所有元素均为 0。
执行 q 次如下形式的操作#xff…
文章目录T1玩个三角形titlesolutioncodeT2玩个球titlesolutioncodeT3玩个树titlesolutioncodeT1玩个三角形
title
题目描述
考虑一个 n ∗ n 的矩阵 A初始所有元素均为 0。
执行 q 次如下形式的操作给定 4 个整数 r, c, l, s对于每个满足 x ∈ [r, rl), y ∈ [c, x-rc] 的元素 (x, y)将权值增加 s。也就是给一个左上顶点为 (r, c)、直角边长为 l 的下三角区域加上 s。
输出最终矩阵的元素异或和。 输入格式
第一行两个整数 n, q。
接下来 q 行每行四个整数 r, c, l, s代表一次操作。 输出格式
输出一行一个整数代表答案。 样例 样例输入
10 4 1 1 10 1 5 5 4 4 1 9 4 3 3 3 5 2
样例输出
0
样例解释
1 0 0 0 0 0 0 0 3 0 1 1 0 0 0 0 0 0 3 3 1 1 3 0 0 0 0 0 3 3 1 1 3 3 0 0 0 0 3 3 1 1 3 3 7 0 0 0 0 0 1 1 3 3 7 7 0 0 0 0 1 1 3 3 7 7 7 0 0 0 1 1 1 1 5 5 5 5 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
数据范围与提示
对于100%的数据保证 n ∈ [1, 103]q ∈ [0, 3 ∗ 105]r, c, l ∈ [1, n]s ∈ [1, 109]。 solution
考虑用二维树组差分维护如果是个矩形就是特别简单的了可惜是个直角三角形 那么就拆一下用两个二维数组一个专门维护单列一个专门维护斜边
code
#include cstdio
#define MAXN 2005
#define ll long long
int n, Q;
ll ans;
ll col[MAXN][MAXN], slope[MAXN][MAXN], matrix[MAXN][MAXN];int main() {scanf( %d %d, n, Q );for( int i 1, r, c, l, s;i Q;i ) {scanf( %d %d %d %d, r, c, l, s );col[r][c] s, col[r l][c] - s;slope[r][c 1] s, slope[r l][c l 1] - s;}for( int i 1;i n;i )for( int j 1;j n;j )col[i][j] col[i - 1][j];for( int i 1;i n;i )for( int j 1;j n;j )slope[i][j] slope[i - 1][j - 1];for( int i 1;i n;i )for( int j 1;j n;j )matrix[i][j] matrix[i][j - 1] col[i][j] - slope[i][j];for( int i 1;i n;i )for( int j 1;j n;j )ans ^ matrix[i][j];printf( %lld, ans );return 0;
}T2玩个球
title
有 n 个球排成一行每个球的颜色为黑或白。
执行 k 次操作第 i(1 ≤ i ≤ k) 次操作形式如下
• 从 [1, n-i1] 中等概率随机选择一个整数 x。
• 移除从左往右数的第 x 个球或从右往左数的第 x 个球也就是从左往右数的第 n-i2-x 个。之后所有右侧的球的编号减 1。
给定每个球的颜色信息希望最大化移除的白球数量。
输出在最优策略下期望的移除白球数量。误差在1e-6范围内即算正确
输入格式
第一行两个整数 n, k。 第二行一个长度为 n、仅由 ‘W’ 和 ‘B’ 组成的字符串第 i 个字符代表第 i 个球的颜色 ‘W’ 为白色 ‘B’ 为黑色。 输出格式
输出一行一个浮点数代表答案。 样例 样例输入1
3 1 BWW
样例输出1
1.0000000000
样例解释1
如果 x 1从右侧操作如果 x 2 或 3从左侧操作均可以移除一个白球。
样例输入2
4 2 WBWB
样例输出2
1.5000000000
数据范围与提示
对于100%的数据保证 1 ≤ n ≤ 300 ≤ k ≤ n
solution
nnn怎么这么小准定要搞事 老子反手就是一个状压压不死你 但是仔细一想2302^{30}230好像逼近intintint极限值 不要担心一般这种大数据数组存不下就找蓝翔技术学校STLSTLSTL这些容器关键时刻还是不会掉链子的这里可以采取mapmapmap与数组进行分工合作数组存不下的就用mapmapmap去存
这道题仔细一看就是个披着期望皮的记忆化搜索羊 为什么呢很简单你想嘛~ 当后面剩下的颜色状态一样时操作的概率与期望计算方式与之前肯定是一样的答案也肯定一样 那我们为什么要傻逼兮兮的怼上去再来一遍 接下来我将重点讲解代码中贼冗长的一行代码的意思因为实在是太妙了
int sta1 sta 1 ~ ( ( 1 i - 1 ) - 1 ) | sta ( ( 1 i - 1 ) - 1 );如果不熟悉位运算的优先级的看到这里基本上已经告退了吧哈哈哈哈 接下来让我们加几个括号
int sta1 ( ( sta 1 ) ( ~ ( ( 1 ( i - 1 ) ) - 1 ) ) ) | ( sta ( ( 1 ( i - 1 ) ) - 1 ) );我们来一一分析提前声明因为我的iii是从111开始枚举的而二进制是从000开始故要−1-1−1 如何才能把iii这一个球彻底删掉呢让我们拭目以待吧 ( 1 ( i - 1 ) ) - 1从[0,i)[0,i)[0,i)位每一位都为111然后其余位全为000好理解下一个 sta 1全体右移一位第000位丢掉好理解下一个 ~ ( ( 1 ( i - 1 ) ) - 1 ) )~ 一种单目运算符位运算对二进制每一位上的数全都进行取反操作1变00变1 接下来进行结合操作吃俺老孙一棒
( ( sta 1 ) ( ~ ( ( 1 ( i - 1 ) ) - 1 ) ) )这行语句的目的是保留了[i1,tot][i1,tot][i1,tot]位上的每一个球的状态即画圈部分 注意sta1sta1sta1整体右移111位后再取\而我们知道除了[0,i)[0,i)[0,i)其余位置都为111 故而stastasta右移111位后以iii为分水岭原来的状态是什么右移111位的状态亦不变 而iii恰好右移成为i−1i-1i−1从i−1i-1i−1位开始往右全都是000 刚好把iii给卡掉了 最后就是上面一堆的状态[0,i)[0,i)[0,i)还是均为000的此时就需要得到原来这些位置上的状态
sta ( ( 1 ( i - 1 ) ) - 1 )最后两个残缺状态取∣|∣即是卡掉iii后的新状态 这是其中一种另一种同理不再赘述
code
#include iostream
#include cstdio
#include map
using namespace std;
map int, double mp;
int n, k;
char s[40];
double dp[1 25];double dfs( int sta, int tot ) {if( tot n - k ) return 0;if( tot 24 mp.find( sta ) ! mp.end() ) return mp[sta];if( tot 24 dp[sta] ! -1 ) return dp[sta];double sum 0;for( int i 1;i ( tot 1 );i ) {int color1 ( sta ( i - 1 ) ) 1;int color2 ( sta ( tot - i ) ) 1;int sta1 ( sta 1 ) ( ~ ( ( 1 ( i - 1 ) ) - 1 ) ) | ( sta ( ( 1 ( i - 1 ) ) - 1 ) );int sta2 ( sta 1 ) ( ~ ( ( 1 ( tot - i ) ) - 1 ) ) | ( sta ( ( 1 ( tot - i ) ) - 1 ) );sum 2 * max( dfs( sta1, tot - 1 ) color1, dfs( sta2, tot - 1 ) color2 ) / tot;}if( tot 1 ) {int i ( tot 1 ) 1; int color ( sta ( i - 1 ) ) 1;int st ( sta 1 ) ( ~ ( ( 1 ( i - 1 ) ) - 1 ) ) | ( sta ( ( 1 ( i - 1 ) ) - 1 ) );sum ( dfs( st, tot - 1 ) color ) / tot;}return ( tot 24 ) ? mp[sta] sum : dp[sta] sum;
}int main() {scanf( %d %d %s, n, k, s );int sta 0;for( int i 0;i ( 1 25 );i )dp[i] -1;for( int i 1;i n;i )sta | ( s[i - 1] W ) ( n - i );sta | ( 1 n );printf( %.8f, dfs( sta, n ) );return 0;
}T3玩个树
title
有一棵 n 个节点的树每条边长度为 1颜色为黑或白。
可以执行若干次如下操作选择一条简单路径反转路径上所有边的颜色。
对于某些边要求在操作结束时为某一种颜色。
给定每条边的初始颜色求最小操作数以及满足操作数最小时最小的操作路径长度和。 输入格式
第一行一个正整数 n。
接下来 n-1 行每行四个整数 a, b, c, d
• 树中有一条边连接 a 和 b。
• c 0, 1 表示初始颜色为白色、黑色。
• d 0, 1, 2 表示最终要求为白色、要求为黑色、没有要求。 输出格式
输出一行两个整数表示最小操作数、操作数最小时的最小路径长度和。 样例 样例输入1
5 2 1 1 0 1 3 0 1 2 4 1 2 5 2 1 1
样例输出1
1 2
样例解释1
操作路径 {2, 1, 3}。
样例输入2
3 1 3 1 2 2 1 0 0
样例输出2
0 0
样例输入3
6 1 3 0 1 1 2 0 2 2 4 1 0 4 5 1 0 5 6 0 2
样例输出3
1 4
数据范围与提示
对于100%的数据保证给出的图为一棵树有 n ∈ [1,1e5]a, b ∈ [1, n]c ∈ {0, 1}d ∈ {0, 1, 2}
solution
若操作的边集为EEE那么操作次数则为EEE中度数为奇数的点的个数/2/2/2称这种点为端点 对于点iii而言 若为奇数除去与父亲相连的边则变成了偶数儿子可以两两配对 那么它就孤了下来成为一条有可能被操作的路径的一端 若为偶数除去与父亲相连的边则变成了奇数儿子两两配对后则还剩一个儿子 那么此时iii称当一个中转站的作用衔接着儿子与父亲 反正无论如何它都只可能是一条可能被操作的路径上的一个点仅此而已
此时赤裸裸的思想先控制操作数最少其次控制路径最小 设dp[i][0/1]dp[i][0/1]dp[i][0/1]表示以iii为根的子树iii与父亲fafafa相连的那条边是否翻转翻转为111不翻转为000的最小操作数以及最小路径和 再设w1w1w1表示iii与父亲fafafa相连的边需要翻转w2w2w2表示iii与父亲fafafa相连的边不需要翻转 w1min(dp[v][0]w1,w2dp[v][1])w1min(dp[v][0]w1,w2dp[v][1])w1min(dp[v][0]w1,w2dp[v][1]) ①儿子不需要翻转iii与父亲的边已经翻转 ②iii与父亲的边尚未翻转儿子需要翻转 w2min(w2dp[v][0],w1dp[v][1])w2min(w2dp[v][0],w1dp[v][1])w2min(w2dp[v][0],w1dp[v][1]) ①儿子不翻转父亲也不翻转 ②儿子翻转父亲再翻转回来
code
#include cstdio
#include vector
using namespace std;
#define MAXN 100005
#define inf 0x3f3f3f3f
struct node {int opt, len;node(){}node( int Opt, int Len ) {opt Opt, len Len;}node operator ( const node t ) const {return node( opt t.opt, len t.len );}
}dp[MAXN][2];
vector pair int, int G[MAXN];
int n;node Min( node x, node y ) {if( x.opt y.opt ) return x;else if( x.opt y.opt x.len y.len ) return x;else return y;
}void dfs( int u, int fa, int type ) {node w1 node( inf, inf ), w2 node( 0, 0 );for( int i 0;i G[u].size();i ) {int v G[u][i].first, flag G[u][i].second;if( v fa ) continue;dfs( v, u, flag );node tmp1 Min( w1 dp[v][0], w2 dp[v][1] );node tmp2 Min( w1 dp[v][1], w2 dp[v][0] );w1 tmp1, w2 tmp2;}if( type 1 || type 2 )dp[u][1] Min( node( w1.opt, w1.len 1 ), node( w2.opt 1, w2.len 1 ) );elsedp[u][1] node( inf, inf );if( type 0 || type 2 )dp[u][0] Min( node( w1.opt 1, w1.len ), w2 );elsedp[u][0] node( inf, inf );
}int main() {scanf( %d, n );for( int i 1, a, b, c, d;i n;i ) {scanf( %d %d %d %d, a, b, c, d );c ( d 2 ) ? d : c ! d;G[a].push_back( make_pair( b, c ) );G[b].push_back( make_pair( a, c ) );}dfs( 1, 0, 2 );printf( %d %d, dp[1][0].opt 1, dp[1][0].len );return 0;
}
