广西大学东信杯第四届程序设计竞赛（同步赛）部分题解
赛题链接：牛客（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("%sn",(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算法可以参考下列这篇博客：
贴个代码：
#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;
}以上就是我对这次比赛部门题目的理解。由于太菜了，只能解释这点题目。不正确的地方希望有大佬能帮忙指正，拜托了拜托了。