当前位置：网站首页>2022.07.13 暑假集训 个人排位赛（八）
2022.07.13 暑假集训 个人排位赛（八）
2022-07-17 11:36:00 【晁棠】
2022.07.13 暑假集训 个人排位赛（八）
赛后反省
中规中矩，感觉现在还是开始慢慢刷一刷动态规划了。两道动态规划没有做出。
Problem A
出处
Codeforces-1153D
题解
树形DP。
每一个父节点都是根据子节点的情况去获得的，相当于一个从叶子结点开始向上传递的过程。设dp[i]代表的是以i为根的子树中，i只能够取叶子结点中的第dp[i]大的点。
那么，当i是叶子结点的时候，显然dp[i]=1;
在其他结点的时候，分两种情况。
- 假如该节点要取子节点的最大值，那么 d p [ u ] = m i n { d p [ v ] } v 是 u 的 子 节 点 dp[u]=min\{dp[v]\}\quad v是u的子节点 dp[u]=min{ dp[v]}v是u的子节点。因为要取最大的点，那么当然要去子节点中能够取得的最大的数。
- 假如该节点要取子节点的最小值，那么 d p [ u ] = ∑ d p [ v ] v 是 u 的 子 节 点 dp[u]=\sum{dp[v]}\quad v是u的子节点 dp[u]=∑dp[v]v是u的子节点。思考一下，因为要去最小的点，也就是取下面子节点中能取到的数的最小值。假设左子树只能取第2大的数，右子树只能取第4大的数，那么假设两棵树合并之后，父节点只能够去两者的最小值，那么也就是第6大的数了。
代码
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
const int N = 3e5 + 5;
int n, T = 1;
int a[N];
vector<int> ve[N];
int dp[N], k;
void dfs(int u) {
if (!ve[u].size()) {
dp[u] = 1;
k++;
return;
}
int minn = INF;
for (auto v : ve[u]) {
dfs(v);
minn = min(dp[v], minn);
dp[u] += dp[v];
}
if (a[u]) dp[u] = minn;
return;
}
void ready()
{
cin >> n;
ffor(i, 1, n) cin >> a[i];
ffor(i, 2, n) {
int v = i, u;
cin >> u;
ve[u].push_back(v);
}
dfs(1);
int ans = k - dp[1] + 1;
cout << ans;
return;
}
void work()
{
}
signed main()
{
IOS;
// cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
Problem B
出处
Codeforces-452B
题解
选三个点，使得线段距离最短。
那么根据样例2，一条直线的提示，我们也可以对斜对角先进行类似的操作。
然后整合一下，对于矩形来说，只在以下两种情况中选择一种就是最大值。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QnPQbY8o-1657725805385)(C:\Users\k’y\AppData\Roaming\Typora\typora-user-images\image-20220713230113490.png)]
代码
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
int T=1;
double n,m;
void ready()
{
cin>>n>>m;
if(n==0){
cout<<n<<' '<<1<<'\n';
cout<<n<<' '<<m<<'\n';
cout<<n<<' '<<0<<'\n';
cout<<n<<' '<<m-1<<'\n';
return;
}
if(m==0){
cout<<1<<' '<<m<<'\n';
cout<<n<<' '<<m<<'\n';
cout<<0<<' '<<m<<'\n';
cout<<n-1<<' '<<m<<'\n';
return;
}/* if(n<=2){ cout<<0<<' '<<0<<'\n'; cout<<n<<' '<<m<<'\n'; cout<<n<<' '<<0<<'\n'; cout<<0<<' '<<m<<'\n'; return; } if(m<=2){ cout<<0<<' '<<0<<'\n'; cout<<n<<' '<<m<<'\n'; cout<<0<<' '<<m<<'\n'; cout<<n<<' '<<0<<'\n'; return; }*/
if(n>=m){
double ans1=2*sqrt(n*n+(m-1)*(m-1))+sqrt(n*n+m*m);
double ans2=2*sqrt(n*n+m*m)+n;
if(ans1>=ans2){
cout<<0<<' '<<1<<'\n';
cout<<n<<' '<<m<<'\n';
cout<<0<<' '<<0<<'\n';
cout<<n<<' '<<m-1<<'\n';
}
else{
cout<<0<<' '<<0<<'\n';
cout<<n<<' '<<m<<'\n';
cout<<0<<' '<<m<<'\n';
cout<<n<<' '<<0<<'\n';
}
return ;
}
else{
double ans1=2*sqrt(m*m+(n-1)*(n-1))+sqrt(n*n+m*m);
double ans2=2*sqrt(n*n+m*m)+m;
if(ans1>=ans2){
cout<<1<<' '<<0<<'\n';
cout<<n<<' '<<m<<'\n';
cout<<0<<' '<<0<<'\n';
cout<<n-1<<' '<<m<<'\n';
}
else{
cout<<0<<' '<<0<<'\n';
cout<<n<<' '<<m<<'\n';
cout<<n<<' '<<0<<'\n';
cout<<0<<' '<<m<<'\n';
}
}
}
void work()
{
}
signed main()
{
IOS;
ready();
//cin>>T;
while (T--) {
work();
}
return 0;
}
Problem C
出处
Codeforces-229D
题解
DP
dp[i]为当以i结尾时达到满足条件的状态需要多少步操作。las[i]为当以i为结尾并且能满足条件时该序列最后一个数是多少。
枚举i之前的j，如果区间[j+1,i]之间的和大于las[j]，则说明这是一种满足条件的变换，区间[j+1,i]合并的次数为i-j-1。那么在这个情况下所需要的操作次数即为dp[j]+i-j-1。如果dp[i]>=dp[j]+i-j-1，即可更新。
代码
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
const int N = 5005;
int n, T = 1;
int sum[N], a[N];
int las[N], dp[N];
void ready()
{
cin >> n;
ffor(i, 1, n) {
cin >> a[i];
sum[i] = sum[i - 1] + a[i];
dp[i] = las[i] = INF;
}
dp[1] = 0; las[1] = a[1];
}
void out()
{
cout << " dp \n";
ffor(i, 1, n) cout << dp[i] << ' ';
cout << " \n las \n";
ffor(i, 1, n) cout << las[i] << ' ';
cout << '\n';
cout << '\n';
}
void work()
{
ffor(i, 2, n) {
ffor(j, 0, i - 1) {
if (las[j] <= sum[i] - sum[j] && dp[i] >= dp[j] + i - j - 1) {
las[i] = sum[i] - sum[j];
dp[i] = dp[j] + i - j - 1;
}
}
//out();
//cout << " i = " << i << " dp = " << dp[i] << " las = " << las[i] << '\n';
}
cout << dp[n];
}
signed main()
{
IOS;
// cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
Problem D
出处
Codeforces-229A
题解
算出每一个位置，离它最近的1在哪里，然后每一列地求和，输出最小即可。
需要注意，如果向右转的话排在最后一个的会去到最前面去。
代码
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
int n, T = 1, m;
int a[105][10005];
int d[105][10005];
void ready()
{
cin>>n>>m;
ffor(i,1,n){
string st;
cin>>st;
ffor(j,0,m-1){
a[i][j+1]=st[j]-'0';
d[i][j+1]=INF;
}
}
ffor(i,1,n){
int di=0;
ffor(j,1,m){
if(a[i][j]) di=j;
if(di) d[i][j]=min(abs(di-j),d[i][j]);
}
//cout<< "i = "<< i << " di = "<<di<<'\n';
if(di)
ffor(j,1,m){
d[i][j]=min(d[i][j],m-di+j);
}
di=0;
rrep(j,m,1){
if(a[i][j]) di=j;
if(di) d[i][j]=min(abs(di-j),d[i][j]);
}
//cout<< "i = "<< i << " di = "<<di<<'\n';
if(di)
rrep(j,m,1){
d[i][j]=min(d[i][j],m-j+di);
}
}
/* ffor(i,1,n){ ffor(j,1,m) cout<<d[i][j]<<' '; cout<<'\n'; }*/
int ans=INF;
ffor(j,1,m){
bool ok=true;
int now=0;
ffor(i,1,n){
if(d[i][j]==INF){
ok=false;
break;
}
now+=d[i][j];
//cout<<" i j "<<i<<' '<<j<<' '<<now<<'\n';
}
if(ok) ans=min(ans,now);
}
if(ans==INF) ans=-1;
cout<<ans;
}
void work()
{
}
signed main()
{
IOS;
ready();
//cin>>T;
while (T--) {
work();
}
return 0;
}
Problem E
出处
Codeforces-229B
题解
加限制的最短路问题。
用一个map来维护， m p [ v ] [ t ] mp[v][t] mp[v][t]代表 第v个点在时间t的时候的出发时间为 m p [ v ] [ t ] mp[v][t] mp[v][t]。那么每次在SPFA用节点u对其子节点进行松弛的时候，如果当前 m p [ u ] [ d i s [ u ] ] mp[u][dis[u]] mp[u][dis[u]]是存在值的，那么原本松弛的条件为 d i s [ u ] + c ≤ d i s [ v ] dis[u]+c \le dis[v] dis[u]+c≤dis[v]就变成了 m p [ u ] [ d i s [ u ] ] + c ≤ d i s [ v ] mp[u][dis[u]]+c\le dis[v] mp[u][dis[u]]+c≤dis[v]。后面就是一般的最短路的操作。
代码
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
const int N=1e5+5,M=2e5+5;
int n, T = 1, m;
int pi,p[N],nxt[M],to[M],val[M];
vector<int> ve;
map<int,int> mp[N];
inline void add_in(int u,int v,int c){
pi++;nxt[pi]=p[u];p[u]=pi;to[pi]=v;val[pi]=c;
}
void ready()
{
cin>>n>>m;
ffor(i,1,m){
int u,v,c;
cin>>u>>v>>c;
add_in(u,v,c);
add_in(v,u,c);
}
ffor(i,1,n){
int ki;
cin>>ki;
ffor(j,1,ki){
int tij;
cin>>tij;
ve.push_back(tij);
}
if(ve.empty()) continue;
//sort(ve.begin(),ve.end());
//ve.erase(unique(ve.begin(),ve.end()),ve.end());
int tim=ve.back()+1;
rrep(j,ve.size()-2,0){
if(ve[j]+1!=ve[j+1]){
int now=ve.back();
while(now!=ve[j]){
ve.pop_back();
mp[i][now]=tim;
now=ve.back();
}
tim=ve.back()+1;
}
}
while(ve.size()){
int now=ve.back();
ve.pop_back();
mp[i][now]=tim;
}
}/* ffor(i,1,n){ cout<<"u = "<<i<<'\n'; for(auto item:mp[i]){ cout<<item.first<<' '<<item.second<<'\n'; } } cout<<'\n';*/
}
int dis[N];
bool f[N];
void out(){
for(int i=1;i<=n;i++)
cout<<dis[i]<<' ';
cout<<'\n'<<'\n';
}
void work()
{
ffor(i,1,n) dis[i]=INF;
dis[1]=0;
queue<int> s;
s.push(1);
while(s.size()){
int u=s.front();s.pop();
f[u]=false;
for(int k=p[u];k;k=nxt[k]){
int v=to[k],c=val[k];
int ut=dis[u];
if(mp[u][ut]>0) ut=mp[u][ut];
int vt=ut+c;
if(vt<=dis[v]){
dis[v]=vt;
if(!f[v]){
f[v]=true;
s.push(v);
}
}
}
// out();
}
if(dis[n]==INF) dis[n]=-1;
cout<<dis[n];
}
signed main()
{
IOS;
ready();
//cin>>T;
while (T--) {
work();
}
return 0;
}
/* 4 6 1 2 8 1 3 3 1 4 18 2 3 4 2 4 5 3 4 3 0 1 3 2 3 4 0 */
Problem H
出处
Codeforces-798D
题解
首先，肯定取越多的数越好，所以取$\left \lfloor \frac{n}{2} \right \rfloor +1 $个数是最好的选择。然后根据a的数值从大到小排序。
如果n是偶数，前两个必选，剩下的两两一组选b值最大的。
如果n是奇数，第一个必选，剩下的两两一组选b值最大的。
贪心正确性，因为每次都在两个里面选最大的一组，那么剩下的所有加起来绝对比已经选择的要小，而且已经选择了的数的个数比没选的多，所以超过总和的一半。
代码
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
int n, T = 1, m;
int alla, allb;
const int N = 1e5 + 5;
struct GGG {
int a, b, id;
}t[N];
bool cmp(GGG i, GGG j) {
return i.a > j.a;
}
void ready()
{
cin >> n;
ffor(i, 1, n) cin >> t[i].a;
ffor(i, 1, n) cin >> t[i].b;
ffor(i, 1, n) t[i].id = i;
sort(t + 1, t + n + 1, cmp);
}
void work()
{
vector<int> ans;
if (n % 2) {
ans.push_back(1);
for (int i = 2; i <= n; i += 2) {
if (t[i].b > t[i + 1].b) ans.push_back(i);
else ans.push_back(i + 1);
}
}
else {
ans.push_back(1); ans.push_back(2);
for (int i = 3; i <= n; i += 2) {
if (t[i].b > t[i + 1].b) ans.push_back(i);
else ans.push_back(i + 1);
}
}
sort(ans.begin(), ans.end());
cout << ans.size() << '\n';
for (auto item : ans) {
cout << t[item].id << ' ';
}
}
signed main()
{
IOS;
ready();
//cin>>T;
while (T--) {
work();
}
return 0;
}
n) t[i].id = i;
sort(t + 1, t + n + 1, cmp);
}
void work()
{
vector ans;
if (n % 2) {
ans.push_back(1);
for (int i = 2; i <= n; i += 2) {
if (t[i].b > t[i + 1].b) ans.push_back(i);
else ans.push_back(i + 1);
}
}
else {
ans.push_back(1); ans.push_back(2);
for (int i = 3; i <= n; i += 2) {
if (t[i].b > t[i + 1].b) ans.push_back(i);
else ans.push_back(i + 1);
}
}
sort(ans.begin(), ans.end());
cout << ans.size() << ‘\n’;
for (auto item : ans) {
cout << t[item].id << ’ ';
}
}
signed main()
{
IOS;
ready();
//cin>>T;
while (T–) {
work();
}
return 0;
}
边栏推荐
- 氟改性UiO-66|3,4-二羟基苯甲醛改性UiO-66-NH2|喜树碱衍生物/寡肽@ZIF-8纳米载药体系
- 镧系金属有机骨架([email protected]）|罗丹明6G修饰MOF材料|过氧化氢酶@ZIF复合材料|mof材料
- Implement word segmentation for text and draw word cloud
- Chapter 4 - consistency of first-order multi-agent systems - > consistency of continuous time systems with time delays
- [565. Array nesting]
- es索引、类型（mapping）、文档、ik分词器
- 【摸鱼神器】UI库秒变低代码工具——表单篇（二）子控件
- 2022-07-16: what is the output of the following go language code? A：[]； B：[5]； C：[5 0 0 0 0]； D：[0 0 0 0 0]。 package main imp
- Excel数据插入Mysql数据库可能遇到的问题
- [C language] a brief introduction to the first C language program and data type
猜你喜欢
随机推荐
cmake -- 笔记
测试vector、list、set调用empty和size的耗时是否为常数
Fiddler replay attack, simple simulated replay attack
Dedecms dream weaving article list Title repeated display solution
水下机器人ROV和AUV
Rocky基础之正则表达式
等价域名
Chapter 4 - first order multi-agent system consistency - > continuous time system consistency with time delay [program code]
es索引、类型（mapping）、文档、ik分词器
氮杂环分子改性UiO-66-NH2|聚乙烯亚胺改性UiO-66-NH2|[email protected]@ZIF67纳米材料
数据湖（十二）：Spark3.1.2与Iceberg0.12.1整合
在华为ModelArts运行YOLOV3_coco_detection_dynamic_AIPP样例
vim诡异的未知函数0
Redis cache avalanche
2022-07-16: what is the output of the following go language code? A：[]； B：[5]； C：[5 0 0 0 0]； D：[0 0 0 0 0]。 package main imp
喜报
数据库概述
[C language] string, escape character and comment
[200 opencv routines] 233 Moment invariants of regional features
死锁、线程与进程讲解