赛题链接：牛客（NC）广西大学第四届程序设计竞赛（同步赛） 点击传送

借鉴了mrgg等诸位大佬的代码

第一次写题解，希望大佬勿喷，时间有限，错误难以避免，希望各位大佬指正

A题 Antinomy与比赛的含金量（签到题）

 签到题，给n个比赛，每个比赛有三个参数a，b，c如果a,b大于90，c大于60，输出A+，否则输出E+。

#include <iostream>
using namespace std;
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        printf("%s\n",(a>90&&b>90&&c>60)?"A+":"E+");
    }
    return 0;
}

B题 Antinomy与取模（数论）

 

数论入门题

两个知识点：GCD（最大公约数）、LCM（最小公倍数）

1.最大公约数GCD

整数a和b的最大公约数记为gcd（a，b）。在编程时有两种做法

（1）经典的欧几里得算法，用辗转相除法求最大公约数，模板如下：

int gcd(int a,int b){

return b==0? a:gcd(a%b);

}

时间复杂度差不多是O（log2n）的，非常快。

（2）或者直接用c++的内置函数求GCD

包含在头文件algorithm下

std::__gcd(a,b)

2.最小公倍数LCM

整数a和b的最小公倍数记为lcm(a,b),模板如下：

Int lcm(int a,int b){

Return a/gcd(a,b)*b;

}

由题意可知yi是a和b的最小公倍数的整数倍。且yi介于l和r之间。所以我可以先求得a，b的最小公倍数，记为c。由于l<=yi<=r,所以我们可以推得 l/c<=yi/c<=r/c（c=0的情况也满足）

所以让倍数i从l/c遍历到r/c，一旦i*c介于l和r之间，即可输出并跳出循环。如果遍历完还没有输出即不存在答案，输出-1。

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
 
int main() {
     
    int t;
    cin >> t;
    ll a, b, l, r;
    while (t--) {
        int flag = 0;
        cin >> a >> b >> l >> r;
        ll c = lcm(a, b);
        for (int i = l/ c; i <= r / c; i++) {
            if (l <= i*c && i*c <= r) {
                cout << i*c << endl;
                flag = 1;
                break;
            }  
        }
        if(flag==0)cout << "-1" << endl;
         
    }
    return 0;
}

C题 Antinomy与清理魔法（排序题）

sort函数用于C++中，对给定区间所有元素进行排序，默认为升序，也可进行降序排序。sort函数进行排序的时间复杂度为n*log2n，比冒泡之类的排序算法效率要高，sort函数包含在头文件为#include<algorithm>的c++标准库中。

由于对选择的下标没有要求，为了便于筛选，我们可以通过排序获得一个升序的整齐序列。（这样可以使得任意两个数值相近的数在空间上靠在一起）我们利用贪心的思想，遍历数组，如果前一个数减去后一个数的差值大于k，那么，输出NO并跳出循环，最后如果都满足便输出YES。

 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
 
const int N=5007;
 
inline  ll read()//快读板子
{
    ll x=0,ch=getchar(),j=1;
    while(!isdigit(ch))
    {
        if(ch=='-') j=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*j;
}
 
ll n,k;
ll a[N];
 
int main()
{
    n=read(),k=read();
    for(int i=1;i<=n;i++)
    {
        a[i]=read();
    }  
    sort(a+1,a+1+n);
    for(int i=2;i<=n;i++)
    {
        if(a[i]-a[i-1]>k)
        {
            cout<<"NO";
            return 0;
        }
    }
    cout<<"YES";
}

D题 Antinomy学内存对齐

 

 

根据内存对齐的部分规则以及备注可知，默认的对齐数是4，也就是说int、long、float这些4字节和double、long long、long double这些8字节的成员可以留在最后输出（因为它们的字节数都是4的倍数）。所以只需要考虑char、bool、short这三个成员的顺序情况

即优先级：char>bool>short

如代码所示，结构体node类型数组s[maxn]中每个元素都存储一个字符串string pa和一个优先级p。每次输入一行字符串，通过判断这行字符串的首字母’c’ ‘b’ ‘s’来对这行字符串赋予优先级：即’c’为首的字符串优先级为1，最高，依次类推。

贴个代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
const int maxn = 1e6 + 10;
 
struct node {
    string pa;
    int p;
}s[maxn];
int t = 0;
string st, ed;
 
bool cmp(node a, node b) {
    return a.p < b.p;
}
 
int main() {
    getline(cin, st);
    while (getline(cin, s[++t].pa)) {
        string str = s[t].pa;
        int len = str.size();
        if (str == "};")break;
        if (str[0] == 'c')s[t].p = 1;
        else if (str[0] == 'b')s[t].p = 2;
        else if (str[0] == 's')s[t].p = 3;
        else s[t].p = 4;
    }
    sort(s + 1, s + t, cmp);
    cout << st;
    for (int i = 0; i < t; i++) {
        cout << s[i].pa<<endl;
    }
    cout << "};";
    return 0;
}      

E题 Antinomy慢慢点技能树(01背包)

 

仔细读题，每个技能最多只能点一次，也就是点或者不点两种情况。可以对应到01背包问题上来

关于01背包问题，可以参考这篇博客：动态规划之01背包问题 - kkbill - 博客园

对于每一个精确到小数点后4位的浮点数，由于不能按int类型直接处理，我们可以将它扩大1w倍，这样它就可以被当作int类型来处理了

But

很多同学发现，为什么扩大1w倍后仍然不能ac呢？这里涉及到一个小小的知识点,也就是说会出现下面这种情况：

 具体解释可以参考：组成原理|为什么计算机中0.3 + 0.6 等于 0.899999999...？ - fishers - 博客园

 

也就是说我们如果想要使得答案准确，需要给原来的数上加上一点数，使得它可以进位，从而不会发生如上图所示的情况。

解决这些问题后，答案就显然易见了：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5+7;
double x[maxn];
long long w[maxn];
long long v[maxn];
ll dp[maxn];
int main(){
    int t = 1;
    while(t--) {
        ll n ,k;
        cin >> n;
        k = 10000;
        for(int i = 1; i <= n ; i++) {
            scanf("%lf%lld",&x[i],&v[i]);
            w[i] = (x[i]+0.000001)*10000;
            for(int j = k;j>=w[i];j--) {
                dp[j] = max(dp[j],dp[j - w[i]] + v[i]);
            }
        }     
        cout<<dp[k]<<"\n";
    }
}

本题解用到了滚动数组:
在处理dp[][]状态数组的时候有一个小技巧：把它变成一维的dp[]，以节省空间。观察二维表dp[][]可以发现，每一行是从上面一行算出来的，只跟上面一行有关系，跟更前面的行没有关系。那么用新的一行覆盖原来的一行就可以了。
滚动数组板子：（hdu2602）
int dp[T];
int ans(){
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=N;i++)
		for(int j=V;j>=bone[i].vol;j--)
			dp[j]=max(dp[j],dp[j-bone[i].vol]+bone[i].val);
	return dp[V];
}

F题 Antinomy与金手指（kmp解法）

仔细读题，本题可以这样理解：

第一次输入一个字符串str

第二次输入一个字符串pattern

当时做题时，我想到了一个经典问题：石子合并问题

其中处理一段循环石子堆时，它使用了将石子堆重复两遍的方法来进行合并

所以利用这种思想，我们来处理这道题：

如str=abcde pattern=cdeab的情况时，我们可以修改str=abcdeabcde，然后判断str是否存在一段pattern序列，如果存在即满足条件。

当然可以选择暴力搜索，就是算法复杂度会很大（因为n<=2e6）

这里我选择使用kmp算法，当然大佬可以考虑更优的算法AC自动机、后缀树等，这里不做过多讲解。

Kmp算法可以参考下列这篇博客：

（原创）详解KMP算法 - 孤~影 - 博客园

贴个代码：

#include<iostream>
using namespace std;
const int MAXN = 400005;
//char str[MAXN], pattern[MAXN];
string str, pattern;
int Next[MAXN];
int cnt=0;
void getfail(string p, int plen) {
	Next[0] = 0; Next[1] = 0;
	for (int i = 1; i < plen; i++) {
		int j = Next[i];
		while (j && p[i] != p[j]) j = Next[j];
		Next[i + 1] = (p[i] == p[j]) ? j + 1 : 0;
	}
}
void kmp(string s, string p) {
	int last = -1;
	int slen = s.length(), plen = p.length();
	getfail(p, plen);
	int j = 0;
	for (int i = 0; i < slen; i++) {

		while (j && s[i] != p[j])j = Next[j];
		if (s[i] == p[j]) j++;
		if (j == plen) {
			if (i - last >= plen) {
				cnt++;
				last = i;
			}
		}
	}

}
int main() {

	int n;
	cin >> n;
	
	cin >> str;
	str += str;
	cin >> pattern;

	kmp(str, pattern);

	if (cnt != 0) cout << "wow";
	else cout << "TAT";
	return 0;
}

 以上就是我对这次比赛部门题目的理解。由于太菜了，只能解释这点题目。不正确的地方希望有大佬能帮忙指正，拜托了拜托了。