D题不会双链表，在网上找到一个板子，直接用了现在还没学。

E题赛时用全排列骗了点分，感觉会是 ，但没有想出来。

F题不会，也没想补。

A-小红小紫替换

签到题

#include<bits/stdc++.h>
using namespace std;
const int N =101001;

int n,m,ans;
int main ()
{
    string s;
    cin>>s;
    if(s=="kou")cout<<"yukari";
    else cout<<s;
       return 0;
}

B-小红质因子数

分解质因数，注意开

#include <bits/stdc++.h>
using namespace std;
long long n;
long long ans = 0;
void divide(long long  x)
{
	for (long long  i = 2; i <= x / i; i++)
	{
		if (x % i == 0)
		{
			while (x % i == 0)
                x /= i;
			++ans;
		}
	}
	if (x > 1)
		++ans;
	cout << ans;
	return;
}
int main()
{
	cin >> n;
	if (n == 1)
	{
		cout << 0;
		return 0;
	}
	divide(n);
	return 0;
}

C-小红的字符串中值

自身算一种。

以自身为中值，扩展到边界，取最先到达的边界。

#include<bits/stdc++.h>
using namespace std;
const int N =101001;
char a[N];
char s;
int n,m,ans;
int main ()
{
	cin>>n>>s;
	cin>>a+1;
	for(int i=1;i<=n;i++)
	{
          if(a[i]==s){
			++ans;
			int k=min(i-1,n-i);
			ans+=k;
		  }
	}
	cout<<ans;
	   return 0;
}

D-小红的数组操作

显然这是个对数组本身要满足 增删操作。

所以要用链表，由题意可知要用双向链表。

由于数据的空间限制，需要考虑用到离散化。

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int m, ans, M, t;
int v[N];
int a[N];
int e[N], l[N], r[N], idx;
struct nihao
{
	int x, y;
	int k;
} p[N];
// 在节点a的右边插入一个数x
void insert(int a, int x)
{
	e[idx] = x;
	l[idx] = a, r[idx] = r[a];
	l[r[a]] = idx, r[a] = idx++;
}
// 删除节点a
void remove(int a)
{
	l[r[a]] = l[a];
	r[l[a]] = r[a];
}
int main()
{
	cin >> m;
	// 0是左端点，1是右端点
	r[0] = 1, l[1] = 0;
	idx = 2;
	for (int i = 1; i <= m; i++)
	{
		int op;
		cin >> op;
		int x = 0, y = 0;
		if (op == 1)
		{
			cin >> x >> y;
			a[++t] = x;
		}
		else
			cin >> x;
		p[i].k = op;
		p[i].x = x;
		p[i].y = y;
	}
	sort(a + 1, a + 1 + t);
	for (int i = 1; i <= m; i++)
	{
		int x = p[i].x;
		int mm = lower_bound(a + 1, a + t + 1, x) - a;
		if (p[i].k == 1)
		{
			int y = p[i].y;

			int nn = lower_bound(a + 1, a + t + 1, y) - a;
			v[mm] = ++ans;
			if (y == 0)
				insert(0, x);
			else
				insert(v[nn] + 1, x);
		}
		else
			remove(v[mm] + 1);
	}
	for (int i = r[0]; i != 1; i = r[i])
		++M;
	cout << M << "\n";
	for (int i = r[0]; i != 1; i = r[i])
		cout << e[i] << ' ';
	return 0;
}

E-小红的子集取反

开始看到不知道何从下手，考虑用的全排列，对于每 个数进行 的操作，枚举 进行搜索。

在搜索的时候，加一个变量，用来判断时间来骗分。

过了 的数据。

骗分代码

#include <bits/stdc++.h>
using namespace std;
const int N = 101001;
int a[N];
int b[N];
int n;
int v[N], ans[N];
int Ans;
int flag;
void dfs(int m, int k)
{
	++Ans;
	if (Ans == 10000008)
	{
		cout << -1;
		exit(0);
	}
	if (m > k)
	{
		for (int i = 1; i <= k; i++)
			a[ans[i]] *= -1;
		int s = 0;
		for (int i = 1; i <= n; i++)
			s += a[i];
		if (s == 0)
		{
			flag = 1;
		}
		for (int i = 1; i <= k; i++)
			a[ans[i]] *= -1;
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (!v[i])
		{
			ans[m] = i;
			v[i] = 1;
			dfs(m + 1, k);
			if (flag == 1)
				return;
			v[i] = 0;
		}
	}
	return;
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i], b[i] = a[i];
	for (int k = 0; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
			a[i] = b[i];
		dfs(1, k);
		if (flag == 1)
		{
			cout << k;
			return 0;
		}
	}
	cout << -1;
	return 0;
}

正解就是 了，主要没往 方程这里想，想到了自然就可以写出来了。

表示在 位置和为 时最小的操作次数。

方程转移 ：

操作的时候对于负数情况，对整个数组进行一个偏移即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 101001;
int f[201][120000];
int a[N];
int M = 40000;
int n, m, ans;
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int j = -M; j <= M; j++)
        f[0][j + M] = N;
    f[0][M] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = -M; j <= M; j++)
        {
            f[i][j + M] = min(f[i - 1][j + M - a[i]], f[i - 1][j + M + a[i]] + 1);
        }
    }
    if (f[n][M] != N)
        cout << f[n][M];
    else
        cout << -1;
    return 0;
}