青岛城市建设局网站,wordpress上传图片错误媒体库错误,如何注册海外域名,建设部网站79号文件文章目录T1#xff1a;跳格子题目题解CODET2#xff1a;英雄联盟题目题解CODET3#xff1a;排序问题题目题解CODET1#xff1a;跳格子
题目
n 个格子排成一列#xff0c;一开始#xff0c;你在第一个格子#xff0c;目标为跳到第 n 个格子。在每个格子 i 里面你可以做…
文章目录T1跳格子题目题解CODET2英雄联盟题目题解CODET3排序问题题目题解CODET1跳格子
题目
n 个格子排成一列一开始你在第一个格子目标为跳到第 n 个格子。在每个格子 i 里面你可以做出两个选择: 选择「a」向前跳 ai 步。 选择「b」向前跳 bi 步。 把每步的选择写成一个关于字符 a 和 b的字符串。求到达格子 n 的方案中字典序最小的字符串。当做出某个选择时你跳出了这n个格子的范围则这个选择是不合法的。
当没有合法的选择序列时输出 No solution! 当字典序最小的字符串无限长时输出 Infinity! 否则输出这个选择字符串
输入格式 输入有三行。 第一行输入一个整数n 第二行输入 n 个整数分别表示 ai 第三行输入 n 个整数分别表示 bi 输出格式 输出一行字符串表示答案。
样例 样例输入 7 5 -3 6 5 -5 -1 6 -6 1 4 -2 0 -2 0 样例输出 abbbb 数据范围与提示 1≤n≤1051≤n≤10^51≤n≤105 −n≤ai,bi≤n-n≤a_i,b_i≤n−n≤ai,bi≤n
题解
其实不用太害怕我们先打个暴力试试水发现最傻的暴力都有80我们就可以知道这道题很简单 这道题后面的分数来自于Infinity!Infinity!Infinity!的判断刚开始读完题后可能大多数人是无法理解这句话的 我们来想想什么情况下会无限死循环。这个就要与字典序挂钩了字典序并不先比较长度用过字典的吧 在此题中只要对于iii位而言只要填aaa后面的字符串的字典序一定小于填bbb 所以看一下这个神奇的栗子 我们会从1选a跳到2再选a跳到4最后选b就可以跳到n了答案是aab 但是我们发现如果跳到4后可以选择一次a回到2再从2回到4最后选b到n答案变成aaaab 根据字典序第三位一个是a一个是ba所在的字符串字典序较小以此类推我们的答案就可以变成aaaaaaa…b 显然中间的a越多字典序越小这就是Infinity!Infinity!Infinity!的输出 但不仅仅是这么简单如果是这样子的栗子 我们的答案是aaa但是这里面仍然有循环出现跳到格子4后选择b跳回2但是我们发现这只会让答案变成aabbb…ba第三位比较就知道字典序大于了aaa所以这种循环的出现我们是可以输出最后答案字符串的 因此我们来思考一下如何辨别这种情况用一个手打队列记录下我们一路上的选择 假设1代表选a0代表选b。在最后走到格子n的时候就模拟一下这一路上的跳跃过程 发现如果在跳跃的某一个点时选择a会跳到已经跳过的点上并且按照我们的答案存取发现这个点应该选b才能保证后面能跳到最后格子时就意味着死循环出现了 否则仍然有解
CODE
#include cstdio
#include cstring
using namespace std;
#define MAXN 100005
int n, idx;
int a[MAXN], b[MAXN], st[MAXN];
bool vis[MAXN];
bool flag;void dfs ( int id ) {if ( flag )return;if ( id n || id 1 )return;if ( vis[id] )return;vis[id] 1;if ( id n ) {flag 1;memset ( vis, 0, sizeof ( vis ) );int t 1;vis[1] 1;for ( int i 1;i idx;i ) {if ( st[i] )t t a[t];else {if ( t a[t] 0 t a[t] n vis[t a[t]] ) {printf ( Infinity! );return;}t t b[t];vis[t] 1;}}for ( int i 1;i idx;i )printf ( %c, st[i] ? a : b );return;}st[ idx] 1;dfs ( id a[id] );idx --;st[ idx] 0;dfs ( id b[id] );idx --;
}int main() {scanf ( %d, n );for ( int i 1;i n;i )scanf ( %d, a[i] );for ( int i 1;i n;i )scanf ( %d, b[i] );dfs ( 1 );if ( ! flag )printf ( No solution! );return 0;
}T2英雄联盟
题目
正在上大学的小皮球热爱英雄联盟这款游戏而且打的很菜被网友们戏称为「小学生」。 现在小皮球终于受不了网友们的嘲讽决定变强了他变强的方法就是买皮肤 小皮球只会玩 N\text{N}N 个英雄因此他也只准备给这 N\text{N}N 个英雄买皮肤并且决定以后只玩有皮肤的英雄。
这 N\text{N}N个英雄中第 i\text{i}i 个英雄有 KiK_iKi款皮肤价格是每款 CiC_iCiQ 币同一个英雄的皮肤价格相同。
为了让自己看起来高大上一些小皮球决定给同学们展示一下自己的皮肤展示的思路是这样的对于有皮肤的每一个英雄随便选一个皮肤给同学看。
比如小皮球共有 5 个英雄这 5 个英雄分别有 0,0,3,2,4\text{0,0,3,2,4}0,0,3,2,4 款皮肤那么小皮球就有 3×2×4243 \times 2 \times 4 243×2×424 种展示的策略。
现在小皮球希望自己的展示策略能够至少达到 \text{M}M 种请问小皮球至少要花多少钱呢
输入格式 第一行两个整数 N,M\text{N,M}N,M 第二行N\text{N}N个整数表示每个英雄的皮肤数量 KiK_iKi 第三行\text{N}N 个整数表示每个英雄皮肤的价格 CiC_iCi 输出格式 一个整数表示小皮球达到目标最少的花费。
输入输出样例 输入 3 24 4 4 4 2 2 2 输出 18 说明/提示 样例解释 每一个英雄都只有4款皮肤每款皮肤2Q币那么每个英雄买3款皮肤3×3×3≥243 \times 3 \times 3 \ge 243×3×3≥24共花费 6×36 \times 36×3 Q币。
数据范围 共 10 组数据第 i\text{i}i组数据满足N≤max(5,log24i)\text{N} \le \max(5, log_2^4i)N≤max(5,log24i) 100%\text{100}\%100% 的数据M≤1017,1≤Ki≤10,1≤Ci≤199\text{M} \le 10^{17}, 1 \le K_i \le 10, 1 \le C_i \le 199M≤1017,1≤Ki≤10,1≤Ci≤199保证有解
题解
这是一道水水的dpdpdp看都看的出来 从最简单的二维dp搞起 设dp[i][j]dp[i][j]dp[i][j]表示前i种皮肤共花费j元的最大的不同种展示策略数 dp[i][j]max(dp[i][j],dp[i−1][j−ci∗p]∗p),(p∈[1,ki])dp[i][j]max(dp[i][j],dp[i-1][j-c_i*p]*p),(p∈[1,k_i])dp[i][j]max(dp[i][j],dp[i−1][j−ci∗p]∗p),(p∈[1,ki]) 我们发现这个转移式的第一维只跟上一次的dpdpdp有关我们就可以考虑滚动我就是这么写的 dp[f][j]max(dp[f][j],dp[!f][j−ci∗p]∗p)(f0/1,p∈[1,ki])dp[f][j]max(dp[f][j],dp[!f][j-c_i*p]*p)(f0/1,p∈[1,k_i])dp[f][j]max(dp[f][j],dp[!f][j−ci∗p]∗p)(f0/1,p∈[1,ki]) 当然滚动也能被压成一维 dp[j]max(dp[j],dp[j−ci∗p]∗p)dp[j]max(dp[j],dp[j-c_i*p]*p)dp[j]max(dp[j],dp[j−ci∗p]∗p) 要注意要从大到小因为要用到上一次的前面的dpdpdp如果我们先更新了小的后面更新大的的时候会产生错误
CODE
#include cstdio
#include cstring
#include iostream
using namespace std;
#define MAXN 305
#define MAXM 600005
#define LL long long
int n;
LL m, sum;
LL dp[2][MAXM], k[MAXN], c[MAXN];int main() {scanf ( %d %lld, n, m );for ( int i 1;i n;i )scanf ( %lld, k[i] );for ( int i 1;i n;i ) {scanf ( %lld, c[i] );sum k[i] * c[i];}for ( int i 0;i sum;i )dp[0][i] dp[1][i] 1;int f 0;for ( int i 1;i n;i ) {f ! f;for ( int j c[i];j sum;j ) {dp[f][j] dp[!f][j];//记得初始化for ( int p 1;p k[i];p ) {if ( j p * c[i] )break;dp[f][j] max ( dp[f][j], dp[!f][j - p * c[i]] * p );}}} for ( int i 1;i sum;i )if ( dp[f][i] m )return ! printf ( %d, i ); return 0;
}T3排序问题
题目
九条可怜是一个热爱思考的女孩子。
题目描述 九条可怜最近正在研究各种排序的性质她发现了一种很有趣的排序方法 Gobo sort Gobo sort 的算法描述大致如下 假设我们要对一个大小为 n 的数列 a 排序。 等概率随机生成一个大小为 n 的排列 p 。 构造一个大小为 n 的数列 b 满足 biapib_ia_{p_i}biapib检查 b 是否有序如果 b 已经有序了就结束算法并返回 b 不然返回步骤 2。 显然这个算法的期望时间复杂度是 O(n×n!)O(n\times n!)O(n×n!)的但是九条可怜惊奇的发现利用量子的神奇性质在量子系统中可以把这个算法的时间复杂度优化到线性。
九条可怜对这个排序算法进行了进一步研究她发现如果一个序列满足一些性质那么 Gobo sort 会很快计算出正确的结果。为了量化这个速度她定义 Gobo sort 的执行轮数是步骤 2 的执行次数。
于是她就想到了这么一个问题 现在有一个长度为 n 的序列 x 九条可怜会在这个序列后面加入 m 个元素每个元素是 [l,r] 内的正整数。 她希望新的长度为 nm 的序列执行 Gobo sort 的期望执行轮数尽量的多。她希望得到这个最多的期望轮数。
九条可怜很聪明她很快就算出了答案她希望和你核对一下由于这个期望轮数实在是太大了于是她只要求你输出对 998244353 取模的结果。
输入格式 第一行输入一个整数 T表示数据组数。 接下来 2×T2 \times T2×T 行描述了 T 组数据。 每组数据分成两行第 1 行有四个正整数 n,m,l,r表示数列的长度和加入数字的个数和加入数字的范围。 第 2 行有 n 个正整数第 i 个表示 xix_ixi 输出格式 输出 TT 个整数表示答案。
输入输出样例 输入 2 3 3 1 2 1 3 4 3 3 5 7 1 3 4 输出 180 720 说明/提示 样例解释 对于第一组数据我们可以添加 {1,2,2}\{1,2,2\}{1,2,2} 到序列的最末尾使得这个序列变成 1 3 4 1 2 2 那么进行一轮的成功概率是 1180\frac{1}{180}1801因此期望需要 180 轮。 对于第二组数据我们可以添加 {5,6,7}\{5,6,7\}{5,6,7} 到序列的最末尾使得这个序列变成 1 3 4 5 6 7 那么进行一轮的成功概率是 1720\frac{1}{720}7201 因此期望需要 720 轮。
数据范围 对于 30% 的数据 T≤10,n,m,l,r≤8T\leq 10 , n,m,l,r\leq 8T≤10,n,m,l,r≤8 对于 50% 的数据 T≤300,n,m,l,r,ai≤300T\leq 300,n,m,l,r,a_i\leq 300T≤300,n,m,l,r,ai≤300 对于 60% 的数据∑r−l1≤107\sum{r-l1}\leq 10^7∑r−l1≤107 对于 70% 的数据 ∑n≤2×105\sum{n} \leq 2\times 10^5∑n≤2×105 对于 90% 的数据 m≤2×105m\leq 2\times 10^5m≤2×105 对于 100% 的数据 T≤105,n≤2×105,m≤107,1≤l≤r≤109T\leq 10^5,n\leq 2\times 10^5,m\leq 10^7,1\leq l\leq r\leq 10^9T≤105,n≤2×105,m≤107,1≤l≤r≤109
题解
代码中有一定的解释帮助大家理解我真是太善良了 首先对于一个长度为nnn的序列排序后变为不同的序列的方案数为n!n!n! 但是会有数字重复出现煮个栗子 虽然1的含义不一样但这个序列只能算一个 所以排序后不同的序列的方案数应该为n!C1!C2!...Cx!\frac{n!}{C_1!C_2!...C_x!}C1!C2!...Cx!n! CCC表示数字x出现的次数 但是这里又出现[l,r][l,r][l,r]的抉择我们观察上面的式子分子是固定的如果要最后的结果尽量大意味着分母要尽量小我们知道阶乘越往后乘得越大所以这启发我们尽量控制CCC的一致 首先对于不属于[l,r][l,r][l,r]的数字就最先搞定然后扔掉不需要接下来我们来算[l,r][l,r][l,r]区间的CCC的贡献 我们考虑刚开始的nnn个数可能有一部分会出现在区间内我们用树状来表示一下看图 hhh表示该数出现了hhh次对应在图上就是树状的高度因为只能填mmm个数又要维持CCC的一致我们就考虑二分这条线什么线那根黄线看图 红色的部分表示填的数的区域我们尽可能让这个黄线下的可填数区域接近于mmm但不能超过但我们不能保证mmm刚好填完所以有可能有些区域上面会多一层绿色部分代表一个数的高度看图 所以就划分成了三种不同类型的树状我们分别处理 1.长度超过答案黄线的就是个数阶乘 2.长度被我们拔高到等于黄线的就是黄线高度阶乘用快速幂算多个的贡献总和 3.长度在黄线之上多了仅仅一层绿帽子 就是高度111阶乘用快速幂算多个的贡献总和 最后涉及到除法又有取模强迫我们用逆元线性筛不推荐时间空间都挺大我们就老老实实地用快速幂求逆元刚好模数是一个质数搞费马小定理
CODE
ps这个代码可能会交出TLE但是多交交几遍是AC的亲测
#include cstdio
#include algorithm
using namespace std;
#define int long long
#define mod 998244353
#define MAXN 200005
#define MAXM 20000000
int T, n, m, l, r, cnt, tot, result, height;
int a[MAXN], b[MAXN], fac[MAXM 5];void prepare () {//预处理出阶乘 fac[0] 1;//必须初始化0原因在后面 for ( int i 1;i MAXM;i )fac[i] fac[i - 1] * i % mod;
}int qkpow ( int x, int y ) {int ans 1;while ( y ) {if ( y 1 )ans ans * x % mod;x x * x % mod;y 1;}return ans;
}int inv ( int x ) {//求的是x的阶乘的逆元 return qkpow ( fac[x], mod - 2 );
}int check ( int x ) {//统计[l,r]高度在x以下有多少个空可以选择填数字 int sum ( r - l 1 - tot ) * x;//未出现在a数组里面的这一竖列上一个数字都没有 for ( int i 1;i tot;i )//出现在a数组里面的统计上方空气能填几个 if ( b[i] x )sum x - b[i];return sum;
}void solve ( int L, int R ) {if ( L R )return;int mid ( L R ) 1;if ( check ( mid ) m ) {height mid;solve ( mid 1, R );}elsesolve ( L, mid - 1 );
}signed main() {prepare();scanf ( %lld, T );while ( T -- ) {scanf ( %lld %lld %lld %lld, n, m, l, r );for ( int i 1;i n;i )scanf ( %lld, a[i] );sort ( a 1, a n 1 );a[n 1] -1;cnt tot 0;result fac[n m];for ( int i 1;i n;i ) {cnt ;if ( a[i] ! a[i 1] ) { if ( l a[i] a[i] r )//具体的数字对我们来说并不重要我们只需要知道这个数字对应的树状高度 b[ tot] cnt;elseresult result * inv ( cnt ) % mod;cnt 0;}}solve ( 0, MAXM );m - check ( height );//剩下的m就填不满一层有些空会填有些不会就特殊处理 for ( int i 1;i tot;i )if ( b[i] height ) {//处理高于height的贡献 cnt ;result result * inv ( b[i] ) % mod;}// 处理在height基础上多填一层的贡献 处理被我们拔高到height高度的贡献 result result * qkpow ( inv ( height 1 ), m ) % mod * qkpow ( inv ( height ), r - l 1 - m - cnt ) % mod;//注意这里的height可能等于0如果不在上面初始化答案就变成了0你就从100pots变成了30pots printf ( %lld\n, result );}return 0;
}byebye~~
