题目链接：https://ac.nowcoder.com/acm/contest/392#question

A

这个贪心 我觉得蛮难写的（主要是我太菜了

我们先将所有区间按照左端点排序，然后从左往右遍历。

用一个变量比如e来代表我们当前最远可以够到的右端点

然后内层循环每次枚举 左端点 不超过 右端点+1 的所有区间

然后从其中选择一个右端点最靠右的，更新e的值即可。

（注意两个小细节：1、内层贪心的时候 要限定 j<m  不然会数组越界  2、内层贪心的时候要记录下结束的位置  贪心结束后在外层要直接跳过去

时间复杂度O(NlogN)

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
const int maxn=1e5+7;
typedef long long ll;
typedef struct node{
    int l,r;
}node;
node a[maxn];
int n,m;
bool cmp(node a,node b){
    return a.l<b.l;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&a[i].l,&a[i].r);
    }
    sort(a,a+m,cmp);
    if(a[0].l!=1){printf("-1\n");return 0;}

    int e=0,cnt=0;
    for(int i=0;i<m;i++){

        int mx=e,d=0;
        for(int j=i;a[j].l<=e+1&&j<m;j++){//注意j的范围
            mx=max(a[j].r,mx);
            d=j;//记录结束位置
        }
        if(mx>e){
            e=mx;cnt++;i=d;
            if(e>=n)break;
        }
        else break;//找不到能选择的点
    }
    if(e<n)cnt=-1;
    printf("%d\n",cnt);
    return 0;
}

B

快速幂+快速乘

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,n,mod;
ll mul(ll a,ll b){
	a%=mod;
	b%=mod;
	ll c=(long double)a*b/mod;
	ll ans=a*b-c*mod;
	return (ans%mod+mod)%mod;
}
ll pow_mod(ll x,ll n){
	ll res=1;
	while(n){
		if(n&1)
		res=mul(res,x);
		x=mul(x,x);
		n>>=1;
	}
	return res;
}
int T;
int main(){
    scanf("%d",&T);

	while(T--){
        cin>>x>>n>>mod;
        cout<<pow_mod(x,n)<<endl;
	}

}

C

 

D

E

二分答案的标准模板

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+7;
int a[maxn];
int n,m;
int check(int mid){
    int sum=0;
    for(int i=0;i<n;i++)sum+=a[i]/mid;

    if(sum>=m)return true;
    else return false;
}
int main(){
    scanf("%d%d",&n,&m);
    int mx=0;
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        mx=a[i]>mx?a[i]:mx;
    }
    int l=1,r=mx,ans=0;
    while(l<=r){
        int mid=(l+r)/2;
        if(check(mid))l=mid+1,ans=mid;
        else r=mid-1;
    }
    printf("%d\n",ans);
    return 0;
}

F

G

贴下赛后题解

（比赛的时候猜的

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
int gcd(ll a,ll b){
	ll r;
	while(b>0){
		r=b;
		b=a%b;
		a=r;
	}
	return a;
}
int main(){
	ll a,b;
    string s;
	cin>>a>>b>>s;
	cout<<gcd(a,b);
}

H

I

说是tarjan算法入门

可是我不会

赛后学了两个小时 勉强学明白有向图tarjan算法咋写   但是这个题是无向图  

勉强对着别人的代码  改对了 但是还不太懂   随后要补补

#include<string.h>
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#include<vector>
using namespace std;

const int maxn=1e5+7;
vector<int>a[maxn];
int dfn[maxn],low[maxn];
int top,deep,ans;
void tarjan(int u,int fa){
    dfn[u]=++deep;
    low[u]=deep;

    for(int i=0;i<a[u].size();i++){
        int v=a[u][i];
        if(v==fa)continue;
        if(!dfn[v]){
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>dfn[u])ans++;
        }
        else{
            low[u]=min(low[u],dfn[v]);
        }
    }
    return ;
}

int main(){
    int n,m,u,v;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        a[u].push_back(v);
        a[v].push_back(u);
    }
    tarjan(1,0);

    printf("%d\n",m-ans);
    return 0;
}

J