寒假训练第一场-创新互联
题目给出两个数字a, b, 让你求出 a - b 范围内每个数字”圈“的总和。 对于这样的区间和问题,直接预处理出前缀和。查询即可
创新互联建站-专业网站定制、快速模板网站建设、高性价比华龙网站开发、企业建站全套包干低至880元,成熟完善的模板库,直接使用。一站式华龙网站制作公司更省心,省钱,快速模板网站建设找我们,业务覆盖华龙地区。费用合理售后完善,十多年实体公司更值得信赖。代码块:`#includeusing namespace std;
const int N = 1e6 + 10;
int cir[10] = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1};
int f[N];
int main()
{int n;
cin >>n;
//根据数据范围,预处理出 1 - 1e6 的前缀和数组
for(int i = 1; i<= 1000000; i++)
{int x = i;
int sum = 0;
while(x)
{sum += cir[x % 10];
x /= 10;
}
f[i] += f[i - 1] + sum;
}
for(int i = 0; i< n; i++)
{int a, b;
cin >>a >>b;
cout<< f[b] - f[a - 1]<< endl;
}
return 0;
}
2.题目:珂朵莉与宇宙
题目链接:珂朵莉与宇宙
解题思路:假设暴力处理,那么需要枚举所有的子区间内的和,枚举区间和用前缀和,并枚举理论上符合的 j^2。
即为, s[r] - s[l] = j^2,枚举三个变量肯定超时。
通过变化式子
s[r] - j^2 = s[l], 那么只需要枚举 r, 和 j, 和符合的 s[l], 的个数,因为s[l], 可以循环 r 时,一并维护出,所以优化掉一个枚举。
#include#include
3.题目:激光炸弹
题目链接:激光炸弹
解题思路:二维前缀和,因为我们要枚举很多子区间,观察数据范围,如果枚举子区间会超时。对于二维区间和的问题,我们使用二维前缀和。
不会二维前缀和可以参考以下文章
二维前缀和
#includeusing namespace std;
const int N = 5010;
int g[N][N];
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n, m;
cin >>n >>m;
for(int i = 0; i< n; i++)
{int a, b, c;
cin >>a >>b >>c;
a++, b++;
g[a][b] = c;
}
for(int i = 1; i< N; i++)
for(int j = 1; j< N; j++)
{g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] + g[i][j];
}
int ans = 0;
for(int i = m; i< N; i++)
for(int j = m; j< N; j++)
{int x2 = i, y2 = j;
int x1 = i - m + 1, y1 = j - m + 1;
ans = max(ans, g[x2][y2] - g[x1 - 1][y2] - g[x2][y1 - 1] + g[x1 - 1][y1 - 1]);
}
cout<< ans;
return 0;
}
二:差分
1.题目:校门外的树
题目链接:校门外的树
解题思路:首先观察数据范围,考虑暴力是否可做,可做,这里不提供暴力解法。
这个题推荐使用差分来做,来练习差分的使用。
差分可以实现对一个区间的所有数,加减一个数字。对此题,我们假设 0 代表有树木,对一段区间砍树就规定为对一段区间的数 -1。
这样我们就减少了去遍历区间内的每个数字进行减法,而在最后所有操作进行完毕之后,统一计算每个点的值。如果还是0,那么还有树。
#includeusing namespace std;
const int N=1e4 + 10;
int f[N];
int n, m;
int main()
{cin >>n >>m;
for(int i = 0; i< m; i++)
{int a, b;
cin >>a >>b;
f[a]--;
f[b + 1]++;
}
int ans = 0;
for(int i = 0; i<= n; i++)
{f[i] += f[i - 1];
if(!f[i]) ans++;
}
cout<< ans<< endl;
return 0;
}
2.题目:货物种类
题目链接:货物种类
解题思路:不难发现这个不同于以前的统计个数吗,而是统计不同种类的数量。所以我们不能对个数进行维护差分数组。
所以我们要对不同的种类维护差分数组,所以我们需要一个一个种类的进行加。并且重复区间不能重复计数,需要区间合并。
所以我们先结构体存下来,进行排序。
因为我们要进行区间合并,所以尽可能 l 的小的排在前面。
区间合并时:分三种情况。
对于同一个种类的区间合并:
1.如果说下一个区间的 l 大于当前维护的区间的 r, 说明这俩区间没有交集,那么 维护区间数组,更新维护的区间
2.否则当前l 小于等于当前维护区间的 r,说明他俩有交集,如果说当前 r >当前维护的区间,那么维护区间 r 需要扩大了。
遇到不同种类了
把之前维护的区间更新差分数组,然后更新区间
#includeusing namespace std;
const int N = 1e5 + 10;
int f[N];
struct Node
{int l, r, id;
}e[N];
bool bmp(Node x, Node y)
{if(x.id != y.id)
return x.id< y.id;
else if(x.l != y.l)return x.l< y.l;
else return x.r< y.r;
}
int main()
{int n, m;
cin >>n >>m;
for(int i = 1; i<= m; i++) cin >>e[i].l >>e[i].r >>e[i].id;
sort(e + 1, e + m + 1, bmp);
int st = e[1].l, ed = e[1].r;
int last = e[1].id;
for(int i = 2; i<= m; i++)
{if(last != e[i].id)
{last = e[i].id;
f[st]++, f[ed + 1]--;
st = e[i].l, ed = e[i].r;
}else
{if(e[i].l >ed)
{f[st]++, f[ed + 1]--;
st = e[i].l, ed = e[i].r;
}else if(ed< e[i].r) ed = e[i].r;
}
}
f[st]++, f[ed + 1]--;
int mxx = 0;
int ans = 0;
for(int i = 1; i<= n; i++)
{f[i] += f[i - 1];
if(f[i] >mxx)
{mxx = f[i];
ans = i;
}
}
cout<< ans<< endl;
return 0;
}
3.题目:放学后茶会的甜点
题目链接:[放学后茶会的甜点]
解题思路:优先学习二维差分:
二维差分
二维差分预处理题目对子区间增加 1。题目问取任意大小的区间的大平均甜度,既然是平均甜度,所以我们取大值那一个即可。
因为平均值不会超过大值。
#includeusing namespace std;
const int N = 1010;
int g[N][N];
int main()
{int n, m, t;
cin >>n >>m >>t;
for(int i = 1; i<= t; i++)
{int x1, y1, x2, y2;
cin >>x1 >>y1 >>x2 >>y2;
g[x1][y1] += 1;
g[x2 + 1][y1] -= 1;
g[x1][y2 + 1] -= 1;
g[x2 + 1][y2 + 1] += 1;
}
int ans = 0 ;
for(int i = 1; i<= n; i++)
for(int j = 1; j<= m; j++)
{g[i][j] += g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1];
ans = max(ans, g[i][j]);
}
cout<< ans<
三:贪心
1.题目:小杰的签到题
题目链接:小杰的签到题
解题思路:首先不希望桌子有空闲时间,所以谁先到谁就先排队。
所以我们先排序所有人的到达时间,从到达时间小的开始放置。
假设对于我们当前要放置的队伍来说,肯定放在最先结束的桌子上。找到三个桌子谁先结束。所以我们需要维护每个桌子当前结束时间。
void solved()
{cin >>n;
for(int i = 0; i< n; i++) cin >>a[i];
cin >>m;
//初始化桌子,时间都归0
for(int i = 0 ;i< 3; i++)
que[i] = 0;
//排序让先到的进行
sort(a, a + n);
for(int i = 0; i< n; i++)
{int x = a[i];
int mnn = 1e9; // 找到三个桌子谁最先结束
int xb = 0; //记录是第几个桌子
for(int j = 0; j< 3; j++)
{if(que[j]< mnn) mnn = que[j], xb = j;
}
//如果说当前队伍大于等于最先结束的了,那么肯定按照当前队伍到达的时间来开始
if(x >= mnn)
{que[xb] = x + m;
}else que[xb] = mnn + m;
//如果我们到达的时候还没有空桌子,那么肯定等空桌子结束我们开始
}
//三个桌子找到最晚结束的就是我们的答案
int ans = 0;
for(int i = 0; i< 3; i++)
{ans = max(ans, que[i]);
}
cout<< ans<< endl;
}
2.题目:排座椅
题目链接:排座椅
解题思路:首先题目中说所有说话的人是相邻的(上下左右), 对于竖着相邻的人来说,横着的过道才能影响,对于横着相邻的来说,竖着的过道影响。
对于一条竖着的过道,影响的只能是相邻两列的人,所以贪心的来说,对于每一条过道我们都希望是影响最多的人。
那么统计一下每对人如果要拆开,需要在哪一列 / 一行,防止过道。然后排序从大到小,输出题目要求的过道数量即可。
需要注意的点,题目要求输出过道的位置时,要求从小到大输出。
因为我们需要输出哪个过道被统计的数量最多,所以我们在统计次数的时候,也要标记上是哪个过道,这样排序的时候我们知道是哪个过道最多。
所以使用结构体存。
#includeusing namespace std;
const int N = 2010;
int hs[N], ls[N];
struct Node
{int id, w;
}he[N], le[N]; //分别统计行和列的次数
bool bmp(Node x, Node y)
{return x.w >y.w;
}
int main()
{int n, m, k, l, d;
cin >>n >>m >>k >>l >>d;
for(int i = 0; i< d; i++)
{int x1, y1, x2, y2;
cin >>x1 >>y1 >>x2 >>y2;
//上下相邻
if(x1 == x2)
{he[min(y1, y2)].w++;
he[min(y1, y2)].id = min(y1, y2); //避免排序时候不知道是哪个过道
}else if(y1 == y2) //左右相邻
{le[min(x1, x2)].w++;
le[min(x1, x2)].id = min(x1, x2);
}
}
//按照统计次数,从大到小
sort(he, he + N, bmp), sort(le, le + N, bmp);
//因为题目要求输出的时候按照 过道的下标从小到大
vectorans1, ans2;
for(int i = 0; i< k; i++)
ans1.push_back(le[i].id);
for(int i = 0; i< l; i++)
ans2.push_back(he[i].id);
sort(ans1.begin(), ans1.end()), sort(ans2.begin(), ans2.end());
for(int i = 0; i< ans1.size(); i++)
cout<< ans1[i]<< " ";
cout<< endl;
for(int j = 0; j< ans2.size(); j++)
cout<< ans2[j]<< " ";
return 0;
}
3.题目:纪念品分组
题目链接:纪念品分组
解题思路:题目规定,最多 2 个物品一组,并且组内大物品不能超过上限值,问你最少多少组。
我们肯定希望尽可能满足 2 个物品一组,所以我们让最小的价值和大的价值组一块是最优解。如果说不能组一块,那大价值只能自己一组。
那么最小值就依次找次小值。
#includeusing namespace std;
const int N = 30010;
int n, m;
int a[N];
int main()
{cin >>m >>n;
for(int i = 0; i< n; i++) cin >>a[i];
sort(a, a + n);
int l = 0;
int ans = 0;
for(int i = n - 1; i >= l; i--)
{if(i == l)
{ans++;
break;
}
if(a[i] >= m) ans++;
else
{if(a[i] + a[l] >m)
{ans++;
}else
{ans++;
l++;
}
}
}
cout<< ans;
return 0;
}
4.题目:巨石滚滚
题目链接:巨石滚滚
解题思路:需要注意的点,土球会先撞,再回复,如果说撞的时候就< 0, 那么就失败了。
首先我们可以把所有的障碍分为两类,一类是撞完会增加的,另一类是撞完会减少的。
因为我们希望尽可能的把球的稳定性变成大,然后再减小,这样尽可能满足更多的障碍。
所以我们先撞增加的,再撞减小的。
对于先撞增加的这一类:
因为先撞再增加,所以尽可能的使得撞的值小的放在前面,让球的稳定性尽可能大,避免撞完就小于0。
可能会说,存在一个增加的障碍,但是他的损耗是很大的,肯定会导致撞完就小于0,不能回复。
这样因为他是撞完增加的,我们把他放在前面,是不是最优解?。
因为我们的要求是能够到达终点,而不是通过最多的障碍。
因为这个是损耗大的回复,所以我们肯定把他放在这一类的最后来撞,因为这时已经是极大值的稳定性,如果这时都不能通过,所以肯定不能到达终点。
对于撞完损耗这一类:
因为我们目标是到重点,那么如果到终点,我们大值 + 回复 一定大于所有的损耗 (损耗是一个定值),否则肯定会在路上失败。
那么我们尽可能的让回复多的在前面,这样就尽可能的满足稳定性大。
#includeusing namespace std;
typedef pairPII; //typedef 同define, pair用法 csdn搜索
#define x first
#define y second
const int N = 500010;
int n, m;
bool bmp1(PII a, PII b)
{return a.x< b.x;
}
bool bmp2(PII a, PII b)
{return a.y >b.y;
}
PII all[N];
void solved()
{cin >>n >>m;
vectorzh, fu;
for(int i = 0; i< n; i++)
{cin >>all[i].x >>all[i].y;
if(all[i].y - all[i].x >= 0) zh.push_back(all[i]);
else fu.push_back(all[i]);
}
sort(zh.begin(), zh.end(), bmp1);
sort(fu.begin(), fu.end(), bmp2);
long long sum = m;
for(int i = 0; i< zh.size(); i++)
{if(sum - zh[i].x< 0)
{cout<< "No"<< endl;
return;
}else sum -= zh[i].x, sum += zh[i].y;
}
for(int i = 0; i< fu.size(); i++)
{if(sum - fu[i].x< 0)
{cout<< "No"<< endl;
return;
}else sum -= fu[i].x, sum += fu[i].y;
}
cout<< "Yes"<< endl;
}
int main()
{int T;
cin >>T;
while(T--) solved();
return 0;
}
四:二分&二分答案
1.题目:.完全平方数
题目链接:完全平方数
解题思路:暴力的解法就是 从 左区间l到右区间r 找到满足条件数的个数。但考虑到 l和r的大小 可以先预处理出来所有的平方数,然后用二分查找到 处于区间(l,r)满足条件数的范围。即 查找 l和r所在预处理数组中的位置。
代码块:#include#includeusing namespace std;
#define ll long long
vectorv;
void solve(){ll l1,r1;cin>>l1>>r1;
ll l=0,r=v.size()-1;
ll k1=-1;
ll k2=-1;
//找到第一个 大于等于 l1的
while(lll mid=(l+r)>>1;
if(v[mid]>=l1)r=mid;
else l=mid+1;
}
k1=l;
//找到最后一个 小于等于r1的
l=0,r=v.size()-1;
while(lll mid=(l+r+1)>>1;
if(v[mid]<=r1)l=mid;
else r=mid-1;
}
k2=l;
cout<for(ll i=0;i*i<=1e9;i++){v.push_back(i*i);
}
ll t;cin>>t;
while(t--)solve();
}
2.题目:解方程
题目链接:解方程
解题思路:可以使用二分答案 枚举区间(0,100)内的所有数字,注意写好check函数就可以了。这里可以学习经典 浮点数二分的处理方法。
代码块:#include#include#define ll long long
using namespace std;
double n;
double check(double m){ double s=m*m*m*m*2018+m*21+5*m*m*m+5*m*m+14;
return s;
}
void solve(){cin>>n;
if(check(100)cout<<"-1"<0.00001){double mid=(l+r)/2.0;
if(check(mid)>=n)r=mid;
else l=mid+0.00000001;
}
printf("%.4f\n",l);
}
int main(){ll t;cin>>t;
while(t--){solve();
}
return 0;
}
3.题目:跳石头
题目链接:跳石头
解题思路:使用二分答案,通过枚举 答案 即最短跳跃距离的大值,check()函数是判断该答案是否可行,是通过 计算 在满足该条件下需要移走岩石的个数,是否满足题目限制的大移动岩石个数。
代码块:#include#include#include#include
#include#include#include#include#define ll long long
const double eps = 1e-4;
ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a; }//最小公约数__gcd()
using namespace std;
const int NX=1e5+10;
ll x[NX];
ll y[NX];
ll L, N, M;
bool check(ll k)
{ll sum = 0;
for (int i = 1; i<= N; i++)
{ll j = i - 1;
while (y[j] != 0)j--;
if ((x[i] - x[j])sum++;
y[i] = 1;
if (sum >M)return false;
}
}
ll s = N;
while (y[s] != 0)s--;
if ((x[N + 1] - x[s])< k)sum++;
if (sum >M) return false;
else return true;
}
int main()
{cin >>L >>N >>M;
for (int i = 1; i<= N; i++)
{cin >>x[i];
}
x[0] = 0;
x[N + 1] = L;
ll l = 0;
ll r = 1e9+10;
while (l< r)
{memset(y, 0, sizeof(y));
ll mid = (l + r) >>1;
if (check(mid))l =mid+1;
else r = mid;
}
cout<< l-1<< endl;
return 0;
}
4.题目:借教室
题目链接:[借教室]
解题思路:该题目 相当于是 跳石头 的一个拓展,同样是枚举答案 需要通知哪个申请人修改订单。注意check()函数的书写,在判断答案 是否可行的时候 需要用到 一点差分的知识。 使用差分处理完该申请人 之前的所有订单,然后看是否有不符合要求的情况,即供不应求(需要的教室个数 大于 有空闲的教室个数。
代码块:#include#include#includeusing namespace std;
#define ll long long
const int N=1e6+10;
ll n,m;
ll a[N],b[N],c[N],d[N],e[N]={0};
bool check(int k)
{memset(e,0,sizeof(e));
for(int i=1;i<=k;i++)
{ e[c[i]]+=b[i];
e[d[i]+1]-=b[i];
}
for(int i=1;i<=n;i++)
{e[i]+=e[i-1];
if(e[i]>a[i])return false;
}
return true;
}
int main()
{cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<=m;i++)cin>>b[i]>>c[i]>>d[i];
ll l=1,r=m;
while(l ll mid=(l+r)>>1;
if(check(mid))l=mid+1;
else r=mid;
}
if (l != m){cout<<"-1"<
五:双指针算法
1.题目:滑动窗口
题目链接:滑动窗口
解题思路:双指针经典用法,需要 用两个指针维护一个窗口的长度,然后不停的在一个数组上滑动。首先 需要注意,两个指针必须一起移动,并且 该窗口的长度不会改变,所以 可以使用 滑动窗口去 维护 给定区间长度 的最值。
代码块:#include#include
#include#include#include#include
2.题目:逆序数(归并排序)
题目链接:[逆序数]
解题思路:首先我们知道逆序数的定义,然后发现通过 归并排序 的过程,可以计算逆序数,然后 归并排序 其实就是通过递归 在回溯的过程中(通过定义 发现 回溯过程返回的都是 有序数组),,使用 双指针 有序合并两个有序数组。
代码块:#includeusing namespace std;
#define ll long long
const int N=1e5+10;
ll q[N],tmp[N];
ll ans=0;
void merge_sort(ll q[], ll l, ll r)
{if (l >= r) return;
ll mid =( l + r) >>1;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
ll k = 0, i = l, j = mid + 1;
while (i<= mid && j<= r)
if (q[i]<= q[j]) tmp[k ++ ] = q[i ++ ];
else {tmp[k ++ ] = q[j ++ ];ans+=mid-i+1;}
while (i<= mid) tmp[k ++ ] = q[i ++ ];
while (j<= r) tmp[k ++ ] = q[j ++ ];
for (i = l, j = 0; i<= r; i ++, j ++ ) q[i] = tmp[j];
}
int main(){ll n;cin>>n;
for(int i=1;i<=n;i++)cin>>q[i];
merge_sort(q, 1, n);
cout<
六:递归&分治
1.题目:数的计算
题目链接:数的计算
解题思路:首先使用暴力 可以发现f(i)=f(1)+f(2)+…+f(i/2)然后写一个递归函数就可以
但是 发现题目数据 发现这样 暴力过不了,因为 我们做了很多重复的计算,比如 当i为奇数的时候 它能添加数字的情况跟(i-1)添加数字的情况一样,当i为偶数的时候,就相当于在(i-1)的基础上加上了 i可添加的自然数的情况,即(i/2)的情况一样。得到普遍规律: 当i为奇数的时候f(i)=f(i-1) 当i为偶数的时候 f(i)=f(i-1)+f(i/2).
#includeusing namespace std;
#define ll long long
ll dfs(ll k){if(k==1)return 1;
if(k%2)return dfs(k-1);
else return dfs(k-1)+dfs(k/2);
}
int main(){ll n;cin>>n;
cout<< dfs(n)<
2.题目:小q的数列
题目链接:小q的数列
解题思路:题目有两个要求,第一个要求 就可以直接通过 题目给出的条件进行递归就可以,第二个条件 通过枚举不难发现跟二进制有关系,每次一个新数x的出现一定是在 2的x次方-1的位置出现。
代码块:#include#include#include
#include#define ll long long
using namespace std;
ll solve(ll n)
{if(n==0)return 0;
if(n==1)return 1;
return solve(n/2)+solve(n%2);
}
int main()
{ ll t;cin>>t;
while(t--)
{ll n;cin>>n;
ll a=solve(n);
ll p=pow(2,a)-1;
printf("%lld %lld\n",a,p);
}
return 0;
}
3.题目:求先序排列
题目链接:求先序排列
解题思路:我们首先 需要学习 树的三种遍历方式(本质计算 对根节点的访问顺序不同),先序排列(根左右) 中序排列(左根右)后序排列(左右根)先序排列的第一个是根节点,后序排列的最后一个节点是根节点。我们可以先根据后序序列找到根节点,然后根据这个根节点来对中序以及后序序列进行分割,于是可以得到左右字数,然后对左子树以及右子树进行递归地处理。
代码块:#include#includeusing namespace std;
#define ll long long
void solve(string s1,string s2){ll k1=s1.size();
ll k2=s2.size();
if(k2<=0)return;
cout<string s1,s2;cin>>s1>>s2;
solve(s1,s2);
return 0;
}
七:STL
1.题目:扫雷游戏
题目链接:扫雷游戏
解题思路:根据题意 如果该位置是非地雷格的时候 你需要 计算它周围的地雷个数,如果是地雷格的话 就直接输出‘*’
这里有个小技巧 在地图上 位置的遍历可以用 x和y相对于原来位置数值的变化 直接判断八个方向,在代码中用 d_x和d_y实现。
#include#include#include
#include
2.题目:图书管理员
题目链接:图书管理员
解题思路:首先理解题意我们发现我们需要 找到是否能够找到读者需要的书,找到的话输出 图书编码最小的书,反之输出 -1,我们可以 先将图书排序,然后每次进行查询的时候,就遍历一遍 如果存在就输出(因为已经进行了排序,所以能够保证 每次最先找到的是图书编码最小的书),不存在就输出-1.
代码块:#include#include#include
#include
你是否还在寻找稳定的海外服务器提供商?创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源,准确流量调度确保服务器高可用性,企业级服务器适合批量采购,新人活动首月15元起,快前往官网查看详情吧
网页标题:寒假训练第一场-创新互联
URL网址:http://scyanting.com/article/psgoo.html