建立网站 多少钱,北京关键词排名推广,乐清建站公司哪家好,wordpress hexo主题A. Penchick and Modern Monument
翻译#xff1a; 在繁华大都市马尼拉的摩天大楼中#xff0c;菲律宾最新的 Noiph 购物中心刚刚竣工#xff01;建筑管理方 Penchick 订购了一座由 n 根支柱组成的先进纪念碑。 纪念碑支柱的高度可以用一个由 n 个正整数组成的数组 h 来表示…A. Penchick and Modern Monument
翻译 在繁华大都市马尼拉的摩天大楼中菲律宾最新的 Noiph 购物中心刚刚竣工建筑管理方 Penchick 订购了一座由 n 根支柱组成的先进纪念碑。 纪念碑支柱的高度可以用一个由 n 个正整数组成的数组 h 来表示其中 表示 1 到 n 之间所有 i 的第 i 根支柱的高度。 彭契克希望石柱的高度不递减即 1 到 n-1 之间所有 i 的高度为。然而由于混淆不清纪念碑的高度反而是非递增的即对于 1 到 n-1 之间的所有 i。 幸运的是彭奇克可以修改石碑并根据需要多次对石柱进行以下操作 将支柱的高度修改为任意正整数。形式上选择一个下标 和一个正整数 x然后赋值 。 帮助彭奇克确定使纪念碑支柱的高度不递减所需的最少操作次数 . 思路 变为同一高度最好选择同一高度最多的柱子为标准。 实现
#includebits/stdc.h
using namespace std;
using ll long long;
// using pll pairll,ll;void solve(){int n;int maxx 0; vectorint nums(100,0);cinn;for (int i0,num;in;i){cinnum;nums[num];maxx max(maxx,nums[num]);} coutn-maxxendl;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 中间填保留几位小数不填默认// cout.precision();ll t;cint;while (t--) solve();}
B. Penchick and Satay Sticks 翻译 Penchick 和他的朋友 Kohane 正在印度尼西亚旅游他们的下一站是泗水 在泗水熙熙攘攘的小吃摊上Kohane 买了 n 根沙爹把它们排成一行其中第 i 根沙爹的长度为 。已知 p 是长度为 n 的排列。 彭奇克想把沙爹棒按长度递增的顺序排列这样每 时。为了好玩他们制定了一条规则只能交换长度相差 1 的相邻沙爹棒。从形式上看他们可以执行以下操作任意多次包括零次 选择一个下标使得 交换 和 。 判断是否可以通过执行上述操作对排列 p 进行排序从而对嗲嗲棒进行排序。 思路 当左边比当前数大2即以上的数时那个数必定换不到当前数的右边。遍历时维护左边最大值即可。 实现
#includebits/stdc.h
using namespace std;
using ll long long;
// using pll pairll,ll;void solve(){int n; cinn;vectorint a(n);for (int i0;in;i) cina[i];if (n2||n1){coutYESendl;return;}else{int maxx a[0];for (int i1;in;i){if (maxxa[i]1){coutNOendl;return;}maxx max(a[i],maxx);}coutYESendl;}
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 中间填保留几位小数不填默认// cout.precision();ll t;cint;while (t--) solve();
}
C. Penchick and BBQ Buns 翻译 Penchick 喜欢两样东西方块数字和港式烧腊包在 Penchick 生日的时候Kohane 想送他一份礼物n 个从左到右排列的烧腊包。烧腊包有 种馅料可供选择从 1 到 。为了确保彭奇克会喜欢这份礼物科哈尼有几个目标 每种馅料都不能使用一次也就是说每种馅料要么完全不出现要么至少出现两次。对于具有相同馅料的两个包子 i 和 j它们之间的距离 必须是完全平方。 帮助 Kohane 找到选择包子馅的有效方法或者确定是否不可能满足她的目标如果有多个解决方案请打印其中任何一个。 思路 对于n为偶数相同馅料间隔为i,i1 n为奇数时由于存在即可以有三个相同的馅料位置为1,10,2610到26间为奇数有一个没配对而111627即11可以与27配对。那么结论即为n27位置1,10,26填相同馅11,27填相同馅料剩下的为偶数可以通过偶数情况求解。 实现
#includebits/stdc.h
using namespace std;
using ll long long;
// using pll pairll,ll;void solve(){int n; cinn;vectorint a(n1,0);if (n%21){if (n27){a[1] 1;a[10] 1;a[26] 1;a[11] 2;a[27] 2;int cnt 3,f 0;for (int i1;in;i){if (a[i]0){a[i] cnt;f;}if (f2){f 0;cnt;}}}else{cout-1endl;return;}}else{int cnt 1;for (int i1;in;i2){a[i] cnt;a[i1] cnt;cnt;}}for (int i1;in;i){couta[i] ;}couta[n]endl;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 中间填保留几位小数不填默认// cout.precision();ll t;cint;while (t--) solve();}
D. Penchick and Desert Rabbit
翻译 Penchick 致力于挑战自己的极限在阿拉伯沙漠的正午阳光下他向自己发起了挑战 当彭奇克沿着一片线状绿洲跋涉时他发现一只沙漠兔正准备沿着一排棕榈树跳跃。一共有 n 棵棕榈树每棵树的高度用 表示。 如果以下条件之一完全为真兔子就能从第 i 棵树跳到第 j 棵树 ji 且 兔子可以向后跳到更高的树上。ji 且 兔子可以向前跳到较矮的树上。 对于 1 到 n 中的每个 i确定兔子从第 i 棵树开始所能到达的所有树的最大高度。 思路 对于每个可跳的位置可以任意往来构成连通块。从左到右维护每个连通块最大值当前值小于连通块时合并连通块并更新连通块最大值。 每个位置的答案就是所属连通块的最大值。 代码
#includebits/stdc.h
using namespace std;
using ll long long;
// using pll pairll,ll;
const int N 5e510;
vectorint f(N),sz(N);
int find(int k){return f[k]k ? f[k] : f[k] find(f[k]);
}
void add(int x,int y){x find(x);y find(y);if (xy) return;if (sz[x]sz[y]) swap(x,y);f[y] x;sz[x] sz[y];
}int n;
vectorint nums(N);void solve(){int n;cinn;for (int i1;in;i){cinnums[i];sz[i] 1;f[i] i;}priority_queuepairint,int piece1;for (int i1;in;i){int temp nums[i];while (!piece1.empty()){int x piece1.top().first, y piece1.top().second;if (xnums[i]){temp max(x,temp);add(y,i);piece1.pop();}else{break;}}piece1.push(make_pair(temp,find(i)));}mapint,int mp;while (!piece1.empty()){int x piece1.top().first, y piece1.top().second;piece1.pop();mp[find(y)] x;}for (int i1;in;i){coutmp[find(i)] ;}coutmp[find(n)]endl;
}
int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);// 中间填保留几位小数不填默认// cout.precision();ll t;cint;while (t--) solve();}
