网站服务商排名,wordpress门户网站模板下载,wordpress 主机推荐,竭诚网络网站建设Day1T1#xff1a;格雷码题目题解代码实现T2#xff1a;括号树题目题解代码实现T3#xff1a;树上的数题目10pts暴力题解代码实现25pts菊花图题解代码实现25pts单链题解代码实现T1#xff1a;格雷码
题目
通常#xff0c;人们习惯将所有 n位二进制串按照字典序排列…
Day1T1格雷码题目题解代码实现T2括号树题目题解代码实现T3树上的数题目10pts暴力题解代码实现25pts菊花图题解代码实现25pts单链题解代码实现T1格雷码
题目
通常人们习惯将所有 n位二进制串按照字典序排列例如所有2位二进制串按字典序从小到大排列为 00 01 10 11。 格雷码Gray Code是一种特殊的 n位二进制串排列法它要求相邻的两个二进制串间恰好有一位不同特别地第一个串与最后一个串也算作相邻。 所有 2位二进制串按格雷码排列的一个例子为 00 01 11 10。 n 位格雷码不止一种下面给出其中一种格雷码的生成算法 1位格雷码由两个1 位二进制串组成顺序为0 1。 n1位格雷码的前2n个二进制串可以由依此算法生成的 n 位格雷码总共2n个 n 位二进制串按顺序排列再在每个串前加一个前缀 0 构成。 n 1 位格雷码的后 2n个二进制串可以由依此算法生成的 n 位格雷码总共2n个 n 位二进制串按逆序排列再在每个串前加一个前缀 1 构成。 综上 n 1 位格雷码由 n 位格雷码的 2n个二进制串按顺序排列再加前缀 0和按逆序排列再加前缀 1 构成共2{n1}个二进制串。另外对于 n 位格雷码中的2n个二进制串我们按上述算法得到的排列顺序将它们从0 ∼ 2n-1编号。 按该算法 2 位格雷码可以这样推出 已知 1 位格雷码为 0 1。 前两个格雷码为 0 1 0 1。后两个格雷码为 1 1 1 0。合并得到 00 01 11 10编号依次为 0 ∼ 3。 同理 3 位格雷码可以这样推出 已知 2 位格雷码为 00 01 11 10。 前四个格雷码为0 00 0 01 0 11 0 10。后四个格雷码为1 10 1 11 1 011 00。合并得到 000 001 011 010 110 111 101 100编号依次为 0 ∼ 7。 现在给出 n, k请你求出按上述算法生成的 n 位格雷码中的 k 号二进制串。 输入描述: 仅一行两个整数 n,k意义见题目描述。 输出描述: 仅一行一个 n 位二进制串表示答案。 示例1 输入 2 3 输出 10 说明 2 位格雷码为00011110编号从 0∼3因此 3 号串是 10 示例2 输入 3 5 输出 111 说明 3 位格雷码为000001011010110111101100编号从 0∼7因此 5 号串是 111。 备注: 对于 50% 的数据:n≤10 对于 80% 的数据k≤5×106 对于 95% 的数据k≤263−1 对于 100% 的数据1≤n≤64 ,0≤k2n
题解
额额额这道题就是一道模拟题并不打算展开讲这里的代码实现完全只是保存个代码罢了。这道题有很多方法实现很多人的方法由于涉及到二的n次方带左移又没有开ULL会爆掉更多的分这告诉我们在考场上要评估自己代码的危险性 看到格雷码的生成规律发现了如果属于下半部分它后面是与上半部分成镜面对称的意思就是属于上半部分的从上往下第x个对应着下半部分的从下往上第x个就当前那一位而言。。
所以我们可以把k转换成二进制然后开始扫遇到第一个1就输出1然后把k的当前位及其以后取个反继续往右操作
代码实现
#include cstdio
#include iostream
using namespace std;
int n;
unsigned long long k;
int main() {scanf ( %d, n );cin k;for ( int i n - 1;i 0;i -- ) {int flag ( k i ) 1;if ( flag ) printf ( 1 );else printf ( 0 );if ( flag ) k ~k;}return 0;
}可能会一脸蒙蔽为什么这么简单就可以或者为什么是取反呢接下来为大家带来比较简略的证明 假设n3时所有的情况从零开始编号依次如图所示我们开始找规律如果k的二进制前x个都是零那么它就一直属于上半部分我们观察得到上半部分的规律就是对于y号位而言把y-1号位的属于y号位的2(y-1)个数分成上下两半都是上半部分是零下半部分是1 如果出现了一个1下半部分的规律就是对于y号位而言把y-1号位的属于y号位的2(y-1)个数分成上下两半上面都是1下面都是0直到出现了第二个1才改变了它的规律变成上半部分是0下半部分是1 所以能明白为什么要这么写了吗其实跟我在考场上找到的规律是一样的但是码力差距就打出了天壤之别接下来的就是我在考场时自己写的比较复杂的代码可以跳过
#include cstdio
#include iostream
using namespace std;
#define LL unsigned long long
int n;
LL k;
LL pre[70];
void dfs1 ( int x, LL y );
void dfs2 ( int x, LL y );void dfs1 ( int x, LL y ) {if ( x 0 )return;if ( y pre[x - 1] ) {printf ( 0 );dfs1 ( x - 1, y - pre[x - 1] );}else {printf ( 1 );dfs2 ( x - 1, y );}
}void dfs2 ( int x, LL y ) {if ( x 0 )return;if ( y pre[x - 1] ) {printf ( 1 );dfs1 ( x - 1, y - pre[x - 1] );}else {printf ( 0 );dfs2 ( x - 1, y );}
}int main() {scanf ( %d, n );cin k;pre[0] 1;for ( int i 1;i 64;i )pre[i] pre[i - 1] * 2;if ( k pre[n - 1] ) {printf ( 1 );dfs1 ( n - 1, k - pre[n - 1] );}else {printf ( 0 );dfs2 ( n - 1, k );}return 0;
}T2括号树
题目
本题中合法括号串的定义如下 ()是合法括号串。 如果 A 是合法括号串则 (A) 是合法括号串。 如果 A B是合法括号串则 AB 是合法括号串。 本题中子串与不同的子串的定义如下 字符串 S 的子串是 S 中连续的任意个字符组成的字符串。 S 的子串可用起始位置 l 与终止位置 r 来表示记为 1≤l≤r≤∣S∣1 \leq l \leq r \leq|S|1≤l≤r≤∣S∣,∣S∣表示S的长度。 S的两个子串视作不同当且仅当它们在S中的位置不同即l不同或r不同。 【题目描述】 一个大小为 n 的树包含n个结点和n − 1 条边每条边连接两个结点且任意两个结点间有且仅有一条简单路径互相可达。 小 Q 是一个充满好奇心的小朋友有一天他在上学的路上碰见了一个大小为 n 的树树上结点从 1 ∼ n 编号 1 号结点为树的根。除 1 号结点外每个结点有一个父亲结点 u(2≤u≤n)u \ (2 \leq u \leq n)u (2≤u≤n)号结点的父亲为fu(1≤fuu)f_{u} \ \left(1 \leq f_{u}u\right)fu (1≤fuu)号结点。 小 Q 发现这个树的每个结点上恰有一个括号可能是’(‘或’)’。小Q定义sis_isi为将根结点到 i 号结点的简单路径上的括号按结点经过顺序依次排列组成的字符串。 显然sis_isi是个括号串但不一定是合法括号串因此现在小 Q 想对所有的i(1≤i≤n)i\ (1 \leq i \leq n)i (1≤i≤n)求出sis_isi中有多少个互不相同的子串是合法括号串。 这个问题难倒了小 Q他只好向你求助。设sis_isi 共有kik_iki个不同子串是合法括号串 你只需要告诉小 Q 所有i×kii \times k_{i}i×ki 的异或和即 (1×k1)xor(2×k2)xor(3×k3)xor ⋯xor (n×kn)\left(1 \times k_{1}\right) \operatorname{xor}\left(2 \times k_{2}\right) \operatorname{xor}\left(3 \times k_{3}\right) \text { xor } \cdots \text { xor }\left(n \times k_{n}\right)(1×k1)xor(2×k2)xor(3×k3) xor ⋯ xor (n×kn) 其中 xor 是位异或运算。 输入描述: 第一行一个整数 n表示树的大小。 第二行一个长为 n 的由’(’ 与’)’ 组成的括号串第 i 个括号表示 i 号结点上的括号。 第三行包含 n− 1 个整数第i (1≤in)个整数表示 i 1 号结点的父亲编号 fi1f_{i1}fi1。 输出描述: 仅一行一个整数表示答案。 示例1 输入 5 (()() 1 1 2 2 输出 6 说明 树的形态如下图 将根到 1 号结点的简单路径上的括号按经过顺序排列所组成的字符串为 (子串 是合法括号串的个数为 0。 将根到 2 号结点的简单路径上的括号按经过顺序排列所组成的字符串为 ((子 串是合法括号串的个数为 0。 将根到 3 号结点的简单路径上的括号按经过顺序排列所组成的字符串为 ()子 串是合法括号串的个数为 1。 将根到 4 号结点的简单路径上的括号按经过顺序排列所组成的字符串为 (((子 串是合法括号串的个数为 0。 将根到 5 号结点的简单路径上的括号按经过顺序排列所组成的字符串为 (()子 串是合法括号串的个数为 1。
题解
这里不再单独呈现单链的暴力分因为我们发现单链的思路可以完全适用于整棵树上
思考如果x这个点上的括号是右括号那么它可能对答案进行贡献的前提就是从根到x这单独的一条链上前面至少还有一个多余的左括号跟它进行匹配那么它的值就会从前一个未能匹配的左括号的值转移1。并且这个左括号一定是最远离根就是最接近于x的位置
那么我们就设dp[i]dp[i]dp[i]表示从根1到i位置为止的匹配成功的括号数不管匹配成功的括号里面又有多少个成功的括号对例如(()())(()())(()())到最后一个右括号时它的dp只有1 那么这中间多多搭配多出的成功匹配对就通过dfs往下传递就可以了
设pre[i]pre[i]pre[i]表示与i无法匹配的距离i最近的一个左括号所在的位置 如果i本身是一个左括号就不可能与前面匹配成功它的dp就是0并且离它最近的左括号就是自己本身嘛 如果i是右括号那么就要再次判断到它爸爸为止之前是否有多余的左括号与i匹配 如果有那么i就与记录下的它爸爸的最近的一个无法匹配的左括号位置进行匹配即 pre[f[i]]pre[f[i]]pre[f[i]]那么它的括号匹配对就是与i匹配的左括号的父亲为止的匹配对再加1 那么转移方程式就出来了dp[u]dp[f[pre[f[i]]]]1dp[u]dp[f[pre[f[i]]]]1dp[u]dp[f[pre[f[i]]]]1
那么接下来就要转移pre[i]pre[i]pre[i]我们想一想如果i与某一个左括号匹配成功了那么距离i最近的一个多余的左括号其实就是匹配成功的左括号的父亲所无法匹配的最近的左括号转移方程式如下pre[i]pre[f[pre[f[i]]]]pre[i]pre[f[pre[f[i]]]]pre[i]pre[f[pre[f[i]]]]
代码实现
#include cstdio
#include vector
using namespace std;
#define LL long long
#define MAXN 500005
vector int G[MAXN];
int n;
LL result;
int f[MAXN], tree[MAXN];
LL dp[MAXN], pre[MAXN];void dfs ( int u, LL sum ) {if ( tree[u] ( )pre[u] u;else if ( f[u] pre[f[u]] ) {dp[u] dp[f[pre[f[u]]]] 1;pre[u] pre[f[pre[f[u]]]];}sum dp[u];result ^ sum * u; for ( int i 0;i G[u].size();i ) {int v G[u][i];dfs ( v, sum );}
}int main() {scanf ( %d\n, n );for ( int i 1;i n;i )scanf ( %c, tree[i] );for ( int i 2;i n;i ) {scanf ( %d, f[i] );G[f[i]].push_back( i );}dfs ( 1, 0 );printf ( %lld, result );return 0;
} T3树上的数
题目
给定一个大小为 n 的树它共有 n 个结点与 n − 1 条边结点从 1 ∼ n 编号。初始时每个结点上都有一个 1 ∼ n 的数字且每个 1 ∼ n 的数字都只在恰好一个结点上出现。 接下来你需要进行恰好n − 1 次删边操作每次操作你需要选一条未被删去的边此时这条边所连接的两个结点上的数字将会交换然后这条边将被删去。 n − 1 次操作过后所有的边都将被删去。此时按数字从小到大的顺序将数字1 ∼ n 所在的结点编号依次排列就得到一个结点编号的排列PiP_iPi 。现在请你求出在最优操作方案下能得到的字典序最小的 PiP_iPi 如上图蓝圈中的数字 1 ∼ 5 一开始分别在结点 ② 、① 、③ 、⑤ 、④ 。按照 (1)(4)(3)(2)的顺序删去所有边树变为下图。按数字顺序得到的结点编号排列为 ① ③ ④ ② ⑤ 该排列是所有可能的结果中字典序最小的。 输入描述: 本题输 入包含多组测试数据。 第一行一个正整数 T表示数据组数。 对于每组测试数据 第一行一个整数 n表示树的大小。 第二行 n 个整数第 i1≤i≤ni1\leq i\leq ni1≤i≤n个整数表示数字 i 初始时所在的结点编号。 接下来 n−1 行每行两个整数 x,y表示一条连接 x 号结点与 y 号结点的边 输出描述: 对于每组测试数据输出一行共 n 个用空格隔开的整数表示最优操作方案下所 能得到的字典序最小的 PiP_iPi 示例1 输入 4 5 2 1 3 5 4 1 3 1 4 2 4 4 5 5 3 4 2 1 5 1 2 2 3 3 4 4 5 5 1 2 5 3 4 1 2 1 3 1 4 1 5 10 1 2 3 4 5 7 8 9 10 6 1 2 1 3 1 4 1 5 5 6 6 7 7 8 8 9 9 10 输出 1 3 4 2 5 1 3 5 2 4 2 3 1 4 5 2 3 4 5 6 1 7 8 9 10 对于所有测试点1≤T≤101\leq T \leq101≤T≤10保证给出的是一个树
10pts暴力题解
暴力题解的话十分简单因为n为10我们就跑出每一种可能的删边顺序一共是!(n−1)!(n-1)!(n−1)再加上有T组数据最多也就是10极限时间复杂度就是O(!n)O(!n)O(!n)对于10而言是可以卡过去的
代码实现
#include cstdio
#include iostream
using namespace std;
#define MAXN 2005
struct node {int u, v;node () {}node ( int U, int V ) {u U;v V;}
}edge[MAXN];
int T, n;
int num[MAXN], tree[MAXN], a[MAXN], b[MAXN], c[MAXN];
bool vis[MAXN];
string result;void dfs ( int x ) {if ( x n ) {string str ;for ( int i 1;i n;i ) {b[i] tree[i];c[tree[i]] i;}for ( int i 1;i n;i )swap ( c[b[edge[a[i]].u]], c[b[edge[a[i]].v]] );for ( int i 1;i n;i )str ( c[i] 0 );if ( result )result str;elseresult min ( result, str );return;}for ( int i 1;i n;i )if ( ! vis[i] ) {vis[i] 1;a[x] i;dfs ( x 1 );vis[i] 0;}
}int main() {scanf ( %d, T );while ( T -- ) {scanf ( %d, n );for ( int i 1;i n;i ) {scanf ( %d, num[i] );tree[num[i]] i;}for ( int i 1;i n;i ) {int x, y;scanf ( %d %d, x, y );edge[i] ( node ( x, y ) );}if ( n 10 ) {result ;dfs ( 1 );for ( int i 0;i n;i )printf ( %d , result[i] - 0 );printf ( \n );}}return 0;
}25pts菊花图题解
对于菊花图也就是长成如下的样子数据范围的解释也给的很明确就算考场上不知道什么是菊花图也应该画得出来这种图 都能想到肯定是依次满足123…的要求尽量把1送到1节点这样才能保证字典序最小 其实根根本没有什么特殊作用它就是起一个中转站的感觉两个叶子进行交换的时候路过了罢了 对于菊花图有三种移动方式 1、根移动到某一个叶子节点 2、某一个叶子节点移动到根那么就必须要求这一条边是所有边中最后一条被删掉的 3、两个叶子之间的移动 我们考虑有哪种情况是不合法的移动很显然 1、如果根想移动到某一个叶子节点而那个叶子节点也想移动到根这就要求这条边是最后一条被删的边并且删完其他边后根上面的值没有动过肯定是满足不了的 2、两个叶子之间想相互转移也是实现不了的只能满足其中一个 所以我们就要求转移后删的边形成一个环怎么做呢并查集 如果i与j本身就是一个集合就不能把j连向i这样会提前形成环
这种情况连边都可以直接不管了比暴力还来得容易
代码实现
#include cstdio
#include vector
#include cstring
#include iostream
using namespace std;
#define MAXN 2005
int T, n;
int num[MAXN], tree[MAXN];
int f[MAXN], ans[MAXN];
bool vis[MAXN];void makeSet () {for ( int i 1;i n;i )f[i] i;
}
int findSet ( int x ) {if ( x ! f[x] )f[x] findSet ( f[x] );return f[x];
}int main() {scanf ( %d, T );while ( T -- ) {scanf ( %d, n );for ( int i 1;i n;i ) {vis[i] 0;scanf ( %d, num[i] );tree[num[i]] i;}for ( int i 1;i n;i ) {int x, y;scanf ( %d %d, x, y );}makeSet();for ( int i 1;i n;i ) {int now 0x7f7f7f7f;for ( int j 1;j n;j ) {if ( ! vis[j] findSet ( j ) ! num[i] ) {now min ( now, j );}}ans[i] now;vis[now] 1;f[num[i]] now;}for ( int i 1;i n;i )printf ( %d , ans[i] );for ( int i 1;i n;i )if ( ! vis[i] ) {printf ( %d\n, i );break;}}return 0;
}25pts单链题解
单链的话也比较好想实现也。。。 借用菊花图的思想肯定也是123…这样依次满足下去但是单链就意味着他们是在同一条路上进行操作就会有不同的方向对于一个链上的点除开头和尾会有两条边删边顺序不是先左后右就是先右后左我们用1表示先右后左2表示先左后右0表示没限制都可以
对于接下来的操作我们思考如果点x要往左转移到y那么这一路上要满足的性质就是对于x这个点就必须先左后右地转移否则x可能往右转移走了y就必须先左后右这样当最后一次交换y与y的右边的时候x就可以被锁死在y而不被转移掉这一路上的点都必须为0无限制或者1这样从右往左才能依次像过安检一样把x传过去。。。对于一个点右移与上面的思路是一样的这里不再赘述
最后单独处理一下头和尾就不对他两个进行特殊打标反正都只有一条边就没有所谓的先后关系
代码实现
#include cstdio
#include vector
#include cstring
#include iostream
using namespace std;
#define MAXN 2005
vector int g[MAXN];
int T, n;
int num[MAXN], tree[MAXN];
int vis[MAXN];
int d[MAXN], f[MAXN], ans[MAXN], pus[MAXN];void build ( int u, int x, int fa ) {pus[x] u;num[tree[u]] x;for ( int i 0;i g[u].size();i ) {int v g[u][i];if ( v fa )continue;build ( v, x 1, u );}
}int main() {scanf ( %d, T );while ( T -- ) {scanf ( %d, n );for ( int i 1;i n;i ) {d[i] 0;vis[i] 0;pus[i] 0;g[i].clear();scanf ( %d, num[i] );tree[num[i]] i;}for ( int i 1;i n;i ) {int x, y;scanf ( %d %d, x, y );d[x] ;d[y] ;g[x].push_back( y );g[y].push_back( x );}int root;for ( int i n;i 1;i -- )if ( d[i] 1 )root i;build ( root, 1, 0 );for ( int i 1;i n;i ) {int now 0x7f7f7f7f, idx;if ( ! vis[num[i]] || vis[num[i]] 2 ) {for ( int j num[i] - 1;j 1;j -- ) {if ( ! vis[j] || vis[j] 2 ) {if ( pus[j] now ) {now pus[j];idx j;}}if ( vis[j] 2 )break;}}if ( ! vis[num[i]] || vis[num[i]] 1 ) {for ( int j num[i] 1;j n;j ) {if ( ! vis[j] || vis[j] 1 ) {if ( pus[j] now ) {now pus[j];idx j;}}if ( vis[j] 1 )break;}}ans[i] now;if ( idx num[i] ) {if ( num[i] ! 1 num[i] ! n )vis[num[i]] 2;if ( idx ! 1 idx ! n )vis[idx] 2;for ( int j idx 1;j num[i];j )vis[j] 1;}else {if ( num[i] ! 1 num[i] ! n )vis[num[i]] 1;if ( idx ! 1 idx ! n )vis[idx] 1;for ( int j idx - 1;j num[i];j -- )vis[j] 2;}}for ( int i 1;i n;i )printf ( %d , ans[i] );printf ( %d\n, ans[n] );continue;}return 0;
}把这三个部分的代码进行整合就能达到60的高分了
