黑龙江职业学院校赛第二场(牛客网同步赛)

A 龙职院卷怪争霸

题目描述 人比人，气死人；但是气不死卷怪，卷怪是不可能落榜的。cr最近参加了专升本考试测验选拔，比的是每个人的高数成绩。参加考试的人被从左到右排成一排，头都朝向左边，然后每个人会得到一个整数数值，表示这个人的数学水平，很显然整数越大，表示这个人越能卷，而且任意两人卷的程度可能一样。由于所有的人头都朝向左边，所以每个人只能看见在它左边的人的数学水平，它们心里都在计算，在自己的眼力范围内有多少人不如自己能卷。请你帮这些人计算一下。

输入描述: 第一行输入一个整数 n，表示人的数量。对于 100% 的数据，n ≤ 100。第二行内输入 n 个整数a，用空格间隔，依次表示从左到右每个人的数学实力。 0<=a<=1e8

输出描述: 行内输出 n 个整数，用空格间隔，依次表示每个人眼中有多少人不如自己能卷。

示例1 输入 6 4 3 0 5 1 2

输出 0 0 0 3 1 2

简单暴力枚举即可，也可以用单调栈来做。

#include<bits/stdc++.h>

using namespace std;
int n;
int a[110];
int main()
{
    cin>>n;
    int cnt = 0;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;++i)
    {
        int cnt=0;
        for(int j=0;j<i;++j)
        {
            if(a[j]<a[i])
            {
                cnt++;
            }
        }
        if(cnt==0) cout<<0<<' ';
        else cout<<cnt-1<<' ';
    }
    return 0;
}

B 最后一个签到还是个字符串基础题

题目描述 给你n个字符串。字符串内有大小写字母和数字。请你输出有多少个不同的字符串。

输入描述: 第一行一个整数n 1<=n<=10000 以下n行每行一个字符串S ≤S.length()≤1500

输出描述: 输出一个整数不同的字符串的个数

示例1 输入 5 AC AC ACC ACCC ACCCC

输出 4 灵活运用map容器可以省很多事。

#include<bits/stdc++.h>

using namespace std;
const int N = 10010;
string s[N];

map<string,int> msi;
map<string,bool> msb;//给字符串计数时判个重
int n;

int main()
{
	cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>s[i];
        msi[s[i]]++;
    }
    int cnt=0;
    for(int i=0;i<n;++i)
    {
    	if(msi[s[i]]>=1&&msb[s[i]]==false) cnt++;
        msb[s[i]]=true;
	}
    cout<<cnt<<endl;
	return 0;
}

E 采购

题目描述 这一天蓝桥杯建个机房，以后国赛用，因为蓝桥杯很有钱。给了无限预算。但是由于运力有限，所以买的电脑总体积要小于等于V。因为合作的运输公司NB，所以只需要考虑体积而不用考虑形状。市面上有n种电脑,每种电脑，一台的体积为t,价钱为w。因为蓝桥杯又抠门题又坑，你决定算出最多能花掉多少钱，不买最好只买最贵。

输入描述: 第一行两个整数1<=n<=1000,1<=v<=1000 第二至n+2行有两个整数1<=t<=1000,1<=w<=1000

输出描述: 输出一个数字代表花掉的钱

示例1 输入 5 6
1 2 2 4 3 4 4 5 5 6

输出 12 这道题明显是个完全背包问题，注意最好用滚动数组优化，不然会很危险。

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int v[N],w[N];
int n,m;
int dp[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    cin>>v[i]>>w[i];
    for(int i=1;i<=n;++i)
    {
        for(int j=v[i];j<=m;++j)
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}

F 字符串

题目描述 给你两个字符串 s1和s2 保证字符串只包含数字，字母。请判断s1里面是否包含s2? 如果包含输出YES 否则输出NO

输入描述: 第一行一个字符串 s1 1≤len(s1)≤1000 第二行一个字符串 s2 1≤len(s2)≤1000

输出描述: 输出一行如果s1里面包含s2输出YES 否则输出NO

示例1 输入 accccac ac

输出 YES

示例2 输入 ababababab ba

输出 YES

示例3 输入 aaaaaa c

输出 NO

简单find函数运用即可，应该也可以用暴力枚举匹配，不过那样太冗长了。

#include<bits/stdc++.h>

using namespace std;

string s1,s2;

int main()
{
    while(cin>>s1>>s2)
    {
    	if(s1.find(s2)!=-1) cout<<"YES"<<endl;
    	else cout<<"NO"<<endl;
	}
    
    return 0;
}

G 求素数

题目描述 t次查询输出n到m之间的素数个数。

输入描述: 第一行一个整数t 1≤t≤1e5 以下t行每行两个整数 n m 1≤n≤m≤1e8

输出描述: t行每行一个整数 n到m之间的素数个数

示例1 输入 5 1 100000000 114 514 123 456 13360 65617 10010 10086

输出 5761455 67 57 4969 6

这个题目数据范围很大的，达到了1e8，用朴素筛法肯定完蛋！考虑用线性筛法，时间复杂度是O(n)。

比赛的时候发生了大无语时间。。不知道是系统还是什么问题，同样的这份代码，本来是超时超到心态炸裂，后来破罐子破摔再交一次，居然过了，太玄学了在这里插入图片描述我觉得这当个线性筛法模板题不错，再加上前缀和的思想，~~基本上能胡搞过~~ 。

#include<bits/stdc++.h>

using namespace std;
int t;
int n,m;
const int N = 1e8;
int primes[N];
int cnt;
bool st[N];
int Ha[N];

void init()
{
	for(int i=2;i<=N;++i)
	{
		if(!st[i])
		{
			primes[cnt++] = i;
			Ha[i] = cnt;
		}
		else Ha[i] = cnt;
		for(int j=0;primes[j]<=N/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0) break;
        }
	}
}


int main()
{
    cin.tie(0),ios::sync_with_stdio(false);
	init();
	Ha[0] = 0;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		cout<<Ha[m]-Ha[n-1]<<endl;
	}
	
	return 0;
}

H 玩游戏

题目描述 现在我们来玩一个小游戏。我们把一条路，分成了连续的n块，编号为1~n，1为起点，n为终点。游戏规则是：每次可以任意选择跳两格或者跳四格。跳跃次数无限。判断是否能够恰好到达终点。

输入描述: 一个正整数n 1≤n≤1e18

输出描述: 如果可以正好到达终点输出n 否则输出-1

示例1 输入 114514

输出 -1

示例2 输入 2233

输出 2233 规律题。

因为起点是从1开始的，并且每次只能跳偶数次，所以我们会发现只有当终点是奇数的时候我们才能恰好跳到，否则我们是不能跳到的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main()
{
    ll n;
	cin>>n;
    if(n%2!=0) cout<<n<<endl;
    else cout<<-1<<endl;
}