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就可以了,或者23112^{31}-1

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

待补