CodeCraft-21 and Codeforces Round 711 (Div. 2)A-F

1.Problem - A - Codeforces

        （1）题意 

                求一个大于等于n的整数x，满足gcd(x,sum(dig(x)) > 1，dig表示x的各个数位。

        （2）思路

                考虑最差是满足gcd(x,sum(dig(x)) = 2,因此不会枚举很多，直接暴力枚举即可。

        （3）代码

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
bool check(ll x)
{ll s = 0,rx = x;while(rx) {s += rx % 10;rx /= 10;}return __gcd(x,s) >= 2;
}
void solve()
{ll n;cin >> n;while(n) {if(check(n)) break;n ++;}cout << n << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;cin >> T;while(T --) solve();return 0;
}

2.Problem - B - Codeforces

        （1）题意

                给你n个高为1，宽为w[i]的矩形，你有一个大矩型已经确定了宽为W，你需要确定最小的h满足能放入所有的高为1的矩形。

        （2）思路

                考虑h一定满足单调性，所以直接二分h的值即可。

        （3）代码

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int a[N],n,w;
bool check(int x)
{multiset<int> st;rep(i,1,x) st.insert(w);per(i,n,1) {auto it = st.lower_bound(a[i]);if(it == st.end()) return false;int res = *it - a[i];st.erase(it);st.insert(res);}return true;
}
void solve()
{cin >> n >> w;rep(i,1,n) cin >> a[i];sort(a + 1,a + 1 + n);int l = 1,r = n;while(l <= r) {int m = (l + r) >> 1;if(check(m)) r = m - 1;else l = m + 1;}cout << l << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;cin >> T;while(T --) solve();return 0;
}

3.Problem - C - Codeforces

        （1）题意

                给你一条长为k的射线，有n面镜子，每次你穿过一面镜子有两种选择，一种是降低你目前的等级，然后新生成一条反方向为目前等级-1的射线，一种是直接穿过镜子，问最多会有多少条射线。

        （2）思路

                发现这是个计数题，因此直接考虑dp，dp[i][j]表示当前射线为i有j面镜子的方案数是多少。

                转移方程：

                        1.若前一条是通过降级来的，则应该是dp[i - 1][n - j]这个位置来的。

                        2.若前一条是通过直接穿的，则应该是dp[i][j - 1]这个位置来的。

        （3）代码

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
using i64 = long long;constexpr int P = 1e9 + 7;
// assume -P <= x < 2P
int Vnorm(int x) {if (x < 0) {x += P;}if (x >= P) {x -= P;}return x;
}
template<class T>
T power(T a, i64 b) {T res = 1;for (; b; b /= 2, a *= a) {if (b % 2) {res *= a;}}return res;
}
struct Mint {int x;Mint(int x = 0) : x(Vnorm(x)) {}Mint(i64 x) : x(Vnorm(x % P)) {}int val() const {return x;}Mint operator-() const {return Mint(Vnorm(P - x));}Mint inv() const {assert(x != 0);return power(*this, P - 2);}Mint &operator*=(const Mint &rhs) {x = i64(x) * rhs.x % P;return *this;}Mint &operator+=(const Mint &rhs) {x = Vnorm(x + rhs.x);return *this;}Mint &operator-=(const Mint &rhs) {x = Vnorm(x - rhs.x);return *this;}Mint &operator/=(const Mint &rhs) {return *this *= rhs.inv();}friend Mint operator*(const Mint &lhs, const Mint &rhs) {Mint res = lhs;res *= rhs;return res;}friend Mint operator+(const Mint &lhs, const Mint &rhs) {Mint res = lhs;res += rhs;return res;}friend Mint operator-(const Mint &lhs, const Mint &rhs) {Mint res = lhs;res -= rhs;return res;}friend Mint operator/(const Mint &lhs, const Mint &rhs) {Mint res = lhs;res /= rhs;return res;}friend std::istream &operator>>(std::istream &is, Mint &a) {i64 v;is >> v;a = Mint(v);return is;}friend std::ostream &operator<<(std::ostream &os, const Mint &a) {return os << a.val();}
};void solve()
{int n,k;cin >> n >> k;vector<vector<Mint>> dp(k + 1,vector<Mint>(n + 1));rep(i,1,k) dp[i][0] = 1;rep(i,1,k) {rep(j,1,n) {dp[i][j] += dp[i - 1][n - j] + dp[i][j - 1];}}cout << dp[k][n] << '\n';
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;cin >> T;while(T --) solve();return 0;
}

4.Problem - D - Codeforces

        （1）题意

                你有n个活动事件，m个位置，初始在0这个位置，每一次活动给出Ti,Xi,Yi表示这个活动的类型是Ti，每一次步长为Xi'(Xi = Xi'/100000)，可以执行[0,Yi]次这个步长，若Ti为1或2，若Ti为1，则表示这一次会变成pos = (pos + Xi),若Ti为2，则表示这一次会变成pos = (pos * Xi), 问你最早到达[1,m]每一个位置是第几个活动事件。

        （2）思路

                直接暴力即可，记Ans[i]表示到第i个位置的最早时间，若这个位置被走过了则时间可以不执行了，若当前位置已经跳出m了，则也不执行了。

        （3）代码

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
int Ans[N];
const int inf = 0x3f3f3f3f;
void solve()
{int n,m;cin >> n >> m;rep(i,1,m) Ans[i] = inf;rep(i,1,n) {ll t,x,y;cin >> t >> x >> y;per(j,m,0) {if(Ans[j] == inf) continue;ll p = j;rep(k,1,y) {if(t == 1) p = p + (99999 + x) / 100000;else p = (p * x + 99999) / 100000;if(p > m) break;if(Ans[p] < inf) break;Ans[p] = i;}}}rep(i,1,m) {if(Ans[i] == inf) cout << -1 << ' ';else cout << Ans[i] << ' ';}
}   
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

5.Problem - E - Codeforces

        （1）题意        （2）思路

                考虑这个图是一个竞赛图，我们可以直接用竞赛图解，对于一个竞赛图若按照点的出度进行排序，缩点后前面的点必定向后面所有点右边，若某一个位置前面的点的出度和为i * (i - 1) / 2,说明前面必定出现了SCC，如果前面j个点也出现了这个情况，说明要么前i个点存在两个SCC，要么后面这个不存在SCC，证明可得后面这个也一定是SCC。那么我们只需要挑一个最大的SCC的|Ka-Kb|即可。

        （3）代码

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
PII e[N];
void solve()
{int n;cin >> n;rep(i,1,n) {cin >> e[i].fi;e[i].se = i;}stable_sort(e + 1,e + 1 + n);int v = 0,mx = -1,lst = 0;PII Ans = {0,0};rep(i,1,n) {v += e[i].fi;if(v == i * (i - 1) / 2) {if(lst != i - 1) {int rs = e[i].fi - e[lst + 1].fi;if(rs > mx) {Ans = {e[lst + 1].se,e[i].se};mx = rs;}}lst = i;}}cout << "! " << Ans.fi << ' ' << Ans.se << endl;
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

6.Problem - F - Codeforces

        （1）题意

                Alice和Bob在一颗树上玩游戏，第i个节点有a[i]个石头，每轮可以选择一个距离根深度至少为k的点往上移动任意石头，问对每个节点作为根最后谁会赢。

        （2）思路

                对于k为1，无非就是一个树上阶梯尼姆博弈

                对于k为d，我们猜测会是一个dep/d的树上阶梯尼姆博弈

                因此我们考虑dp[i][j][k]表示在第i个点，距离i为j的，奇偶性为k的贡献是多少。

                1.对于j < k的奇偶性不会发生变化

                        dp[x][i][j] ^= dp[y][i - 1][j]

                2.对于j == k的会发生变化因此特殊转移就行。

                        dp[x][0][j] ^= dp[y][k - 1][j ^ 1]

                剩下的其他根换根dp一下就可以

       （3）代码

#include <bits/stdc++.h>
#define rep(i,z,n) for(int i = z;i <= n; i++)
#define per(i,n,z) for(int i = n;i >= z; i--)
#define PII pair<int,int>
#define fi first
#define se second
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
const int N = 1e5 + 10;
vector<int> e[N];
int dp[N][21][2],Ans[N],a[N];
int n,k;
inline void do_dp(int x,int y)
{rep(i,1,k - 1) {rep(j,0,1) {dp[x][i][j] ^= dp[y][i - 1][j];}}dp[x][0][0] ^= dp[y][k - 1][1];dp[x][0][1] ^= dp[y][k - 1][0];
}
inline void dfs(int u,int f)
{dp[u][0][0] = a[u];for(auto v : e[u]) {if(v == f) continue;dfs(v,u);do_dp(u,v);}
}
inline void dfs2(int u,int f)
{if(f) {do_dp(f,u);do_dp(u,f);}rep(i,0,k - 1) Ans[u] ^= dp[u][i][1];for(auto v : e[u]) {if(v == f) continue;dfs2(v,u);}if(f) {do_dp(u,f);do_dp(f,u);}
}
void solve()
{cin >> n >> k;rep(i,2,n) {int u,v;cin >> u >> v;e[u].pb(v),e[v].pb(u);}rep(i,1,n) cin >> a[i];dfs(1,0);dfs2(1,0);rep(i,1,n) {if(Ans[i]) cout << 1 << ' ';else cout << 0 << ' ';}
}
int main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);int T = 1;// cin >> T;while(T --) solve();return 0;
}

                

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/148155.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

Webpack 基础入门以及接入 CSS、Typescript、Babel

Webpack 基础入门以及接入 CSS、Typescript、Babel

一、什么是 Webpack Webpack 是一款 JS 模块化开发的技术框架&#xff0c;其运作原理是将多个 JS 文件关联起来构成可运行的应用程序。 Webpack 拥有丰富的 plugins / loaders 插件生态圈&#xff0c;可以让 js 识别不同的语言如 .css, .scss, .sass, .json, .xml, .ts, .vue…
阅读更多...
数据结构：复杂度分析

数据结构：复杂度分析

目录 1 算法效率评估 1.1 实际测试 1.2 理论估算 2 迭代与递归 2.1 迭代 1. for 循环 2. while 循环 3. 嵌套循环 2.2 递归 1. 调用栈 2. 尾递归 3. 递归树 2.3 两者对比 3 时间复杂度 3.1 统计时间增长趋势 3.2 函数渐近上界…
阅读更多...
c++的io流

c++的io流

文章目录 1.C语言的输入和输出2.流失是什么3.cIO流3.1c标准io流3.2c文件io流 4.stringstream的简单介绍 1.C语言的输入和输出 C语言中我们用到的最频繁的输入输出方式就是scanf ()与printf()&#xff0c;scanf(): 从标准输入设备(键盘)读取数据&#xff0c;并将值存放在变量中…
阅读更多...
学信息系统项目管理师第4版系列16_资源管理过程

学信息系统项目管理师第4版系列16_资源管理过程

1. 组建项目团队&#xff0c;建设项目团队和管理项目团队属于执行过程组 1.1. 【高22上选21】 1.1.1. 【高21上选25】 1.2. 3版 2. 【高19上案三】 2.1. 【高18上案三】 2.2. 【高23上案一】 3. 规划资源管理 3.1. 定义如何估算、获取、管理和利用团队以及实物资源的过…
阅读更多...
lv7 嵌入式开发-网络编程开发 04 IP地址与端口号

lv7 嵌入式开发-网络编程开发 04 IP地址与端口号

目录 1 IP地址 1.1 IP 地址及其表示方法 1.2 分类的 IP 地址 1.3 无分类编址 CIDR 1.3.1 网络前缀 1.3.2 地址块 1.3.3 地址掩码 (address mask) 1.4 IPv6 的地址 1.4.1 表示方式 1.4.2 零压缩 2 端口号 2.1 进程之间的通信 2.2 运输层的作用 2.3 屏蔽作用 2.4…
阅读更多...
C#中的for和foreach的探究与学习

C#中的for和foreach的探究与学习

一：语句及表示方法 for语句： for(初始表达式;条件表达式;增量表达式) {循环体 }foreach语句： foreach(数据类型 变量 in 数组或集合) {循环体 }理解 1.从程序逻辑上理解，foreach是通过指针偏移实现的（最初在-1位置，每循环一次，指针就便宜一个单位），而for循环是通
阅读更多...
十二、【漏洞复现】Rails任意文件读取(CVE-2019-5418）

十二、【漏洞复现】Rails任意文件读取(CVE-2019-5418）

十二、【漏洞复现】Rails任意文件读取(CVE-2019-5418&#xff09; 12.1、漏洞原理 Ruby on Rails是一个使用 Ruby 语言写的开源 Web 应用框架&#xff0c;它是严格按照 MVC 结构开发的。它努力使自身保持简单&#xff0c;来使实际的应用开发时的代码更少&#xff0c;使用最少…
阅读更多...
下载盗版网站视频并将.ts视频文件合并

下载盗版网站视频并将.ts视频文件合并

. 1.分析视频请求123 2.数据获取和拼接 1.分析视频请求 1 通过抓包观察我们发现视频是由.ts文件拼接成的每一个.ts文件代表一小段2 通过观察0.ts和1.ts的url我们发现他们只有最后一段不同我们网上找到url获取的包3 我们发现index.m3u8中储存着所有的.ts文件名在拼接上前面固定…
阅读更多...
数据结构 1.1 初学数据结构

数据结构 1.1 初学数据结构

数据结构的基本概念 数据结构在学什么&#xff1f; 如何用程序代码把现实世界的问题信息化 如何用计算机高效处理信息从而创造价值 数据&#xff1a; 数据元素、数据项&#xff1a; 数据元素——描述一个个体 数据对象——数据元素之间具有同样的性质 同一个数据对象里的数…
阅读更多...
kubernetes集群kubeadm方式安装

kubernetes集群kubeadm方式安装

测试网络和DNS解析 kubectl run busybox --image busybox:1.28 --restart=Never --rm -it busybox -- sh ping www.baidu,com nslookup kubernetes.default.svc.cluster.localbusybox要用指定的1.28版本，不能用最新版本，最新版本，nslookup会解析不到dns和ip 延长kubernetes…
阅读更多...
linux命令行配置音频设备

linux命令行配置音频设备

linux命令行配置音频设备 TLTR在linux命令行播放音乐cmus需要开始声音条件功能才能调节播放的音量&#xff0c;看这个链接&#xff0c;继续折腾&#xff0c;have fun! TLTR 以archLinux为例&#xff0c;把下面软件都装一遍。 sudo pacman -S alsa-utils sudo pacman -S alsa-…
阅读更多...
数据结构—栈、队列、链表

数据结构—栈、队列、链表

一、栈 Stack&#xff08;存取O(1)&#xff09; 先进后出&#xff0c;进去123&#xff0c;出来321。 基于数组&#xff1a;最后一位为栈尾&#xff0c;用于取操作。 基于链表&#xff1a;第一位为栈尾&#xff0c;用于取操作。 1.1、数组栈 /*** 基于数组实现的顺序栈&#…
阅读更多...
（枚举 + 树上倍增）Codeforces Round 900 (Div. 3) G

（枚举 + 树上倍增）Codeforces Round 900 (Div. 3) G

Problem - G - Codeforces 题意&#xff1a; 思路&#xff1a; 首先&#xff0c;目标值和结点权值是直接联系的&#xff0c;最值不可能直接贪心&#xff0c;一定是考虑去枚举一些东西&#xff0c;依靠这种枚举可以遍历所有的有效情况&#xff0c;思考的方向一定是枚举 如果去…
阅读更多...
协议-SSL协议-基础概念01-SSL位置-协议套件-握手和加密过程-对比ipsec

协议-SSL协议-基础概念01-SSL位置-协议套件-握手和加密过程-对比ipsec

SSL的位置-思维导图 参考来源&#xff1a; 华为培训ppt:HCSCE122_SSL VPN技术 ##SSL的位置 SSL协议套件 ​​​​握手阶段&#xff0c;完成验证&#xff0c;协商出密码套件&#xff0c;进而生成对称密钥&#xff0c;用于后续的加密通信。 加密通信阶段&#xff0c;数据由对…
阅读更多...
93、Redis 之 使用连接池管理Redis6.0以上的连接 及 消息的订阅与发布

93、Redis 之 使用连接池管理Redis6.0以上的连接 及 消息的订阅与发布

★ 使用连接池管理Redis连接 从Redis 6.0开始&#xff0c;Redis可支持使用多线程来接收、处理客户端命令&#xff0c;因此应用程序可使用连接池来管理Redis连接。 上一章讲的是创建单个连接来操作redis数据库&#xff0c;这次使用连接池来操作redis数据库 Lettuce连接池 支持…
阅读更多...
【maven】idea中基于maven-webapp骨架创建的web.xml问题

【maven】idea中基于maven-webapp骨架创建的web.xml问题

IDEA中基于maven-webapp骨架创建的web工程&#xff0c;默认的web.xml是这样的。 <!DOCTYPE web-app PUBLIC"-//Sun Microsystems, Inc.//DTD Web Application 2.3//EN""http://java.sun.com/dtd/web-app_2_3.dtd" ><web-app><display-name…
阅读更多...
ADB的概念、使用场景、工作原理

ADB的概念、使用场景、工作原理

文章目录 一、adb概念&#xff1a;Android Debug Bridge&#xff0c;一个可以控制安卓设备的通用命令行工具二、adb的使用场景&#xff1a;操作手机设备、app 自动化测试1.传输文件2.兼容性测试&#xff08;手机墙&#xff09;3.云测平台4.测试框架底层封装&#xff1a;APP自动…
阅读更多...
Qt扩展-QCustomPlot绘图基础概述

Qt扩展-QCustomPlot绘图基础概述

QCustomPlot绘图基础概述 一、概述二、改变外观1. Graph 类型2. Axis 坐标轴3. 网格 三、案例1. 简单布局两个图2. 绘图与多个轴和更先进的样式3. 绘制日期和时间数据 四、其他Graph&#xff1a;曲线&#xff0c;条形图&#xff0c;统计框图&#xff0c;… 一、概述 本教程使用…
阅读更多...
[C++ 网络协议] 重叠I/O模型

[C++ 网络协议] 重叠I/O模型

目录 1. 什么是重叠I/O模型 2. 重叠I/O模型的实现 2.1 创建重叠非阻塞I/O模式的套接字 2.2 执行重叠I/O的Send函数 2.3 执行重叠I/O的Recv函数 2.4 获取执行I/O重叠的函数的执行结果 2.5 重叠I/O的I/O完成确认 2.5.1 使用事件对象&#xff08;使用重叠I/O函数的第六个参…
阅读更多...
距离矢量路由协议RIP(含Cisco模拟器实验命令配置)

距离矢量路由协议RIP(含Cisco模拟器实验命令配置)

距离矢量路由协议RIP(含Cisco模拟器实验命令配置) 简介 距离矢量路由协议&#xff08;Routing Information Protocol, RIP&#xff09;是一种内部网关协议&#xff0c;它位于应用层&#xff0c;使用520 UDP端口。RIP基于距离矢量算法&#xff08;Bellham-Ford&#xff09;根据…
阅读更多...
最新文章

Copyright @ 2022~2023