软院蓝桥杯选拔赛
购买力
https://ac.nowcoder.com/acm/contest/25111/A
A
简单的说就是在一个数组中对于每一个询问x,有多少个数小于等于x，排序之后，单调，二分位置，比较数的大小。
#include<bits/stdc++.h>
using namespace std;
int n,x,a[1000010],c[1000010];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
int q;
scanf("%d",&q);
while(q--){
scanf("%d",&x);
int l=1,r=n;
int ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(a[mid]<=x) ans=mid,l=mid+1;
else r=mid-1;
}
cout<<ans<<endl;
}
}
B
这题，我是套的线段树维护区间GCD的板子，但是这题 其实区间一直都是1~n比较特殊，可以不需要线段树，但其实这个原理也是线段树维护区间gcd的原理。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 23;
struct Node{
int l, r;
ll v, d;
}tr[maxn * 4];
ll a[maxn], b[maxn],num[maxn];
void pushup(Node &u, Node &l, Node &r)
{
u.v = l.v + r.v;
u.d = __gcd(l.d, r.d);
}
void pushup(int u)
{
pushup(tr[u], tr[u << 1], tr[u << 1 | 1]);
//printf("%d[%d,%d]=%d\n",u,tr[u].l,tr[u].r,tr[u].d);
}
void build(int u, int l, int r)
{
if(l == r) tr[u] = {l, r, b[l], b[l]};
else
{
tr[u] = {l, r};
int mid = l + r >> 1;
build(u << 1, l, mid); build(u << 1 | 1, mid + 1, r);
pushup(u);
}
}
ll query(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].d;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query(u << 1, l, r);
else if(l > mid) return query(u << 1 | 1, l, r);
else return __gcd(query(u << 1, l, r), query(u << 1 | 1, l, r));
}
}
ll query2(int u, int l, int r)
{
if(tr[u].l >= l && tr[u].r <= r) return tr[u].v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(r <= mid) return query2(u << 1, l, r);
else if(l > mid) return query2(u << 1 | 1, l, r);
else return query2(u << 1, l, r) + query2(u << 1 | 1, l, r);
}
}
void modify(int u, int p, ll v)
{
if(tr[u].l == tr[u].r && tr[u].l == p) tr[u].d += v, tr[u].v += v;
else
{
int mid = tr[u].l + tr[u].r >> 1;
if(p <= mid) modify(u << 1, p, v);
else modify(u << 1 | 1, p, v);
pushup(u);
}
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]), b[i] = a[i] - a[i - 1];
build(1, 1, n);
for(int i=1;i<=m;i++){
scanf("%lld",&num[i]);
ll op1 = 1, op2 = n, op3 = num[i];
modify(1, op1, op3);
if(op2 + 1 <= n) modify(1, op2 + 1, -op3);
ll t = query2(1, 1, op1);
printf("%lld ", abs( __gcd(t, query(1, op1 + 1, op2))));
op3 = -num[i];
modify(1, op1, op3);
if(op2 + 1 <= n) modify(1, op2 + 1, -op3);
}
}
C
这题其实算一道比较简单的模拟题的，四个循环模拟就可以，关键就是不要被题目吓到了，其实并不是数学题。大概意思就是一个小的矩形在一个大的矩行里遍历，小矩形可以走到的每一个位置，然后对应行列相乘算出一个值，就为答案矩阵的一个值。类似于二维的滑动窗口。
#include<bits/stdc++.h>
using namespace std;
int x[210][210],w[210][210];
int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
cin>>x[i][j];
}
}
int u,v;
cin>>u>>v;
for(int i=0;i<u;i++){
for(int j=0;j<v;j++){
cin>>w[i][j];
}
}
for(int i=0;i<n-u+1;i++){
for(int j=0;j<m-v+1;j++){
long long ans=0;
for(int k=0;k<u;k++){
for(int l=0;l<v;l++){
ans+=w[k][l]*x[k+i][l+j];
}
}
cout<<ans<<" ";
}
cout<<endl;
}
}
D
几何，不会，不想补
E
C++直接输出INT_MAX就可以了,或者
F
每个人都只能拿2的次方个，所以只能拿1,2,4,8……等，但是2,4,8……以后的其实就是等价的，最后两次拿，一定是一个人拿2，一个人拿1，判断是不是3的倍数就OK了。刚好是3的倍数一定后者赢。
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define endl '\n'
typedef long long ll;
const int N=5e5+10;
const int M=1e6+7;
const int mod=1e9+7;
ll n,m,k;
int a[N],b[N];
void solve(){
cin>>n;
if(n%3!=0) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main(){
int _=1;
cin>>_;
while(_--) solve();
}
G
是一个模拟题，题意大概就是每天都会有人申请土豆，你要给他们分配，按给定的规则排序，然后取要求的前几个（因为每一天土豆的数量有限），一个人拿过土豆之后他就只能在i+P+1之后才能拿土豆，最后还要输出健康状态为1的所有人。要注意的地方就是要判断身份证号不是18位的情况。其实就是考一个重载小于号，STL的容器的使用。
代码：
#include <bits/stdc++.h>
using namespace std;
#define PAIR pair<string,string>
const int mod=1e9+7;
const int N=1e3+7;
int D,P;
unordered_map<string,int>mp;
typedef struct {
int n,m;
string name;//姓名
string id;//身份证号
int cnt;//出现的顺序
int heal;//健康状态
int hour,minter;//提交的时间
}node;
typedef struct {
int n,m; // 每天的人数和土豆数
node info[N];
}node2 ;
node2 nums[50];
bool cmp(node a,node b){
if(a.hour == b.hour){
if(a.minter==b.minter) return a.cnt<b.cnt;
return a.minter<b.minter;
}
return a.hour<b.hour;
}
set<string>mp2;
vector<PAIR>ans;//存健康状态为 1 的人
int main(){
cin>>D>>P;
string s;
for(int i=1;i<=D;i++){
cin>>nums[i].n>>nums[i].m;
for(int j=0;j<nums[i].n;j++){//输入
cin>>nums[i].info[j].name;
cin>>nums[i].info[j].id;
cin>>nums[i].info[j].heal;
nums[i].info[j].cnt=i;
scanf("%d:%d",&nums[i].info[j].hour,&nums[i].info[j].minter);
}
sort(nums[i].info,nums[i].info+nums[i].n,cmp);//排序
for(int j=0;j<nums[i].n;j++){
if(nums[i].info[j].id.size()!=18) continue;
if(mp[nums[i].info[j].id]<=i&&nums[i].m>0){
cout<<nums[i].info[j].name<<" "<<nums[i].info[j].id<<endl;
mp[nums[i].info[j].id]=i+P+1;
nums[i].m--;
}
if(nums[i].info[j].heal==1) {
if(!mp2.count(nums[i].info[j].id))
ans.push_back({nums[i].info[j].name,nums[i].info[j].id});
mp2.insert(nums[i].info[j].id);
}
}
}
for(auto it : ans){
cout<<it.first<<" "<<it.second<<endl;
}
}
H
思路大概就是先把大的整数尽可能的变成负数，然后多余的步数如果是奇数，就把绝对值最小的那个数变成正数
两次sort就行，比赛的时候可能有点急，想的有点慢。
然后还有就是一开始没有看数据范围，cin直接超时了。
#include<bits/stdc++.h>
using namespace std;
ll n,m,k,h;
int a[M];
void solve(){
scanf("%lld%lld",&n,&m);
bool ok=false;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
int pos=-1;
for(int i=1;i<=n;i++){
if(a[i]>=0){
pos = i;
break;
}
}
if(pos==-1){
int sum=0;
if(m&1) a[n]=-a[n];
for(int i=1;i<=n;i++) sum+=a[i];
//cout<<sum<<endl;
printf("%d\n",sum);
return;
}
for(int i=n;i>=pos&&m>0;i--){
a[i]=-a[i];
m--;
}
sort(a+1,a+n+1);
if(m&1) a[n]=-a[n];
int sum=0;
for(int i=1;i<=n;i++) sum+=a[i];
printf("%d\n",sum);
}
int main(){
int t;
//cin>>t;
scanf("%d",&t);
while(t--){
solve();
}
}
I
待补
