点击领取>>>信息学奥赛 NOI、NOIP、各区CSP-J/S初赛复赛试题&蓝桥杯、信息杯、智慧杯编程试卷& 海淀区科普节、程序设计大赛
第1题
题目解析：
这是道水题，只要好好读题，理解意思，先排序，然后直接输出答案就行。
#include
using namespace std;
int a[7];
int main() {
for (int i = 0; i < 7; i++) {
cin>>a[i];
}
sort(a, a+7);
cout<0 ] << " " << a[1] << " " << a[4] + a[5] - a[6]<<endl;
return 0;
}第2题
题目解析：
这题也简单，双重循环枚举区间[i, j], 1<=i<=j<=n, 检查该区间中是否有花瓣数为平均数的花朵即可。主函数如下：
int main() {
int n;
cin>>n;
for (int i = 1; i <=n; i++) {
cin >> a[i];
}
int cnt = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
if (check(i, j)) {
cnt++;
}
}
}
cout<endl ;
return 0;
}第3题
题目解析：
本题正解思路不复杂，把E方向和N方向的牛存到两个数组中，然后把E方向数组按照y升序排序，把N方向数组按照x升序排序。接下来双重循环两两比对处理即可。
for (int i = 1; i <= cntN; i++) {
for (int j = 1; j <= cntE; j++) {
// 有牛已被挡住，必定不相交
if(pointN[i].len != INT_MAX ||
pointE[j].len != INT_MAX) {
continue;
}
int lenx=pointN[i].x-pointE[j].x;
int leny=pointE[j].y-pointN[i].y;
// 同时到达或不相交
if(lenx==leny || lenx < 0 || leny < 0) {
continue;
}
if(lenx>leny){
pointE[j].len = lenx;
}else{
pointN[i].len = leny;
}
}
}
第1题
题目解析
对于每个非叶子节点，计算需要翻倍的次数，然后加上n-1即可。假设该节点需要翻倍的次数为i，需满足2的i次方恰好大于等于该节点及其子节点的个数，可以通过统计各节点度数很方便的得到。
int n;
cin >> n;
for (int i = 1; i < n; i++) {
int a, b;
cin>>a>>b;
deg[a]++;
deg[b]++;
}第2题
题目解析：
坐标离散化 + 二维前缀和求区间点数 + 组合计数
计数时为什么要加1呢？因为
// 2D prefix sum
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + p[i][j]
// 枚举最左和最右端两个点
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++)
{
int r1 = t[i], r2 = t[j];
if (r1 > r2)
swap(r1, r2);
// 正上方矩形区域点数
ll a = count(i, 1, j, r1 - 1);
// 正下方矩形区域点数
ll b = count(i, r2 + 1, j, n);
// 计算包含中间区域点的子集数
ans += (a + 1) * (b + 1);
}
}
cout << ans + 1 << endl;第3题
题目解析：
本题处理思路和铜级组第三题一致，只要多加两行代码处理一下blame次数即可。
if(lenx>leny){
pointE[j].len = lenx;
pointN[i].cnt += pointE[j].cnt; // 更新次数
}else{
pointN[i].len = leny;
pointE[j].cnt += pointN[i].cnt; // 更新次数
}
第1题
题目解析：
第2题
题目解析：
第3题
题目解析：
第1题
限于篇幅，Platinum题目就不贴了
需要者可以扫描文末二维码，添加老师微信获取
题目解析：
第2题
题目解析：
第3题
第三题福利大放送，直接附上AC(满分)代码供小伙伴们参考
题目解析：
#include
using namespace std;
typedef long long ll;
const int mod = 1000000007;
const int inv2 = 500000004;
const int inv3 = 333333336;
int n, m;
ll C2(ll x)
{
return x * (x - 1) % mod * inv2 % mod;
}
ll C3(ll x)
{
return x * (x - 1) % mod * inv2 % mod * (x - 2) % mod * inv3 % mod;
}
ll h[31];
int a[40020];
int s[40020];
inline int Q(int x)
{
int i = lower_bound(a, a + 2 * n, x) - a;
return s[i] + (i & 1 ? x : 0);
}
ll H(int t, int as, int qas, int qae, int bs, int qbs, int qbe)
{
if ((2 << t) == qae - qas && (2 << t) == qbe - qbs && ~h[t])
return h[t];
int am = as + (1 << t), qam = Q(am);
int bm = bs + (1 << t), qbm = Q(bm);
ll ac0 = qam - qas, ac1 = qae - qam;
ll bc0 = qbm - qbs, bc1 = qbe - qbm;
if (ac0 + ac1 < 1 || bc0 + bc1 < 1)
return 0;
ll re = 0;
if (t == 0)
{
if (m >> t & 1)
re = (ac0 + ac1) * (bc0 + bc1) % mod;
else
re = (ac0 * bc0 + ac1 * bc1) % mod;
}
else
{
if (m >> t & 1)
{
re = (ac0 * bc0 + ac1 * bc1) % mod;
re = (re + H(t - 1, as, qas, qam, bm, qbm, qbe)) % mod;
re = (re + H(t - 1, am, qam, qae, bs, qbs, qbm)) % mod;
}
else
re = (H(t - 1, as, qas, qam, bs, qbs, qbm) +
H(t - 1, am, qam, qae, bm, qbm, qbe)) % mod;
}
if ((2 << t) == qae - qas && (2 << t) == qbe - qbs)
h[t] = re;
return re;
}
ll g[31];
ll G(int t, int as, int qas, int qae, int bs, int qbs, int qbe)
{
if ((2 << t) == qae - qas && (2 << t) == qbe - qbs && ~g[t])
return g[t];
int am = as + (1 &
微信公众号搜索： 北京小学学习资料 家长升学指南 关注公众号，获取最新资讯！
扫码添加“家长论坛”微信好友（微信号 16619908263）
获取信息学奥赛 NOI、NOIP、各区CSP-J/S试题&蓝桥杯、智慧杯、 海淀区科普节真题
咨询信息学奥赛 NOI、NOIP、各区CSP-J/S试题&蓝桥杯、智慧杯、 海淀区科普节政策请拨打电话 16619908263 （同微信号）
0 个回复