T1 字符串的距离（签到题）

题目大意

*设有字符串 X，我们称在 X 的头尾及中间插入任意多个空格后构成的新字符串为 X 的扩展串，如字符串 X为“abcbcd”，则字符串“abcb□cd”，“□a□bcbcd□” 和 “abcb□cd□” 都是 X 的扩展串，这里“ □ ”代表空格字符。

• 如果 A1 是字符串 A 的扩展串，B1 是字符串 B 的扩展串，A1 与 B1 具有相同的长度，那么我们定义字符串 A1 与 B1 的距离为相应位置上的字符的距离总和：两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值 空格字符与其它任意字符之间的距离为已知的定值 K，
  空格字符与空格字符的距离为 0 。
• 在字符串 A,B 的所有扩展串中，必定存在两个等长的扩展串 A1,B1，使得 A1 与 B1 之间的距离达到最小，我们将这一距离定义为字符串 A,B的距离。
• 请你写一个程序，求出字符串 A,B的距离

算法分析：

• dp呗 很显然就看出来了 考试的时候dp初始化没全 改了就A了

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3+10;
char s1[maxn];
char s2[maxn];
int dp[maxn][maxn];//已经匹配好s1的前i位和s2的前j位
int k;

int main(){
	scanf("%s%s%d",s1+1,s2+1,&k);
	memset(dp,0x3f,sizeof(dp));
	int len1 = strlen(s1+1);
	int len2 = strlen(s2+1);
	dp[0][0] = 0;
	for(int i = 1;i <= len1;++i)dp[i][0] = k*i;
	for(int i = 1;i <= len2;++i)dp[0][i] = k*i;
	for(int i = 1;i <= len1;++i){
		for(int j = 1;j <= len2;++j){
			dp[i][j] = min(dp[i-1][j-1] + abs(s1[i] - s2[j]),min(dp[i][j-1] + k,dp[i-1][j] + k));
		}
	}
	printf("%d\n",dp[len1][len2]);
	return 0;
}

T2 Blue Mary的战役地图 （暴力你就赢了）

题目大意

• BlueMary 最近迷上了玩 Starcraft (星际争霸) 的 RPG
  游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。
• 由于 BlueMary的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此 BlueMary
  需要你写一个程序，来帮助她判断哪些地图是属于同一类的。
• 具体来说，BlueMary已经将战役地图编码为 n×n 的矩阵，矩阵的每个格子里面是一个 32 位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。

输入格式

• 输入文件的第一行包含一个正整数 n。
• 以下 n 行，每行包含 n 个正整数，表示第一张战役地图的代表矩阵。
• 再以下 n 行，每行包含 n 个正整数，表示第二张战役地图的代表矩阵。

输出格式

• 输出文件仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。

算法分析

• 首先讲第一种做法 暴力直接O(\(n^5\))亲测AC
• 哈希做法
• 有点容斥的玩意 首先预处理出来每个节点对应的哈希值 这个哈希表示的是 以这个节点作为矩形右下角的哈希值
• 然后想要知道任意一个部分的哈希值用最简单的容斥就可以做了（别说不会…………
• 然后就没啥东西了

Code

#include <cstdio>
#define ll long long
using namespace std;
const int N = 105, M = 1157621;//M是105*105*105中最大质数
const int N3 = N*N*N;
int n, a[N][N], b[N][N];
ll s[2][N][N];//存前缀和
struct Node {
    int k, x, y, next;
}h[N3];//链表
int head[N3], tot;
int Ha(int k, int x, int y, int p) {//求Hash值
    x--, y--;
    return (int)(s[p][x+k][y+k] - s[p][x][y+k] - s[p][x+k][y] + s[p][x][y]) % M;//通过前缀和求期间和
}
void Add(int k, int i, int j) {//在Hash表中添加，挺像加边操作
    int ha = Ha(k, i, j, 0);
    h[++tot] = (Node) {k, i, j, head[ha]};
    head[ha] = tot;
}
bool Judge(int n, int k, int x, int y) {//判断是否相同
    if (h[n].k != k) return 0;
    for (int i = 0; i < k; ++i)
        for (int j = 0; j < k; ++j)
            if (a[h[n].x+i][h[n].y+j] != b[x+i][y+j])
                return 0;
    return 1;
}
bool Find(int k, int x, int y) {
    int ha = Ha(k, x, y, 1);
    if (!head[ha]) return 0;
    for (int i = head[ha]; i; i = h[i].next)//遍历这条链
        if (Judge(i, k, x, y)) return 1;
    return 0;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &a[i][j]), 
            s[0][i][j] = s[0][i-1][j] + s[0][i][j-1] - s[0][i-1][j-1] + a[i][j];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            scanf("%d", &b[i][j]),
            s[1][i][j] = s[1][i-1][j] + s[1][i][j-1] - s[1][i-1][j-1] + b[i][j];
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i + k - 1 <= n; ++i)
            for (int j = 1; j + k - 1 <= n; ++j)
                Add(k, i, j);//将第一个图的所有子矩阵加入
    for (int k = n; k >= 1; --k)//从大到小枚举，找到了直接输出，这个for也可以二分
        for (int i = 1; i + k - 1 <= n; ++i)
            for (int j = 1; j + k - 1 <= n; ++j)
                if (Find(k, i, j)) return printf("%d\n", k), 0;
    puts("0");
    return 0;
}

T3反质数 （打表大法好）

题目大意

• 对于任何正整数 x 其约数的个数记作 g(x)。例如 g(1)=1,g(6)=4 。
• 如果某个正整数 x 满足：对任意的 i(0<i<x) 满足 g(x)>g(i)，则称 x为反质数。
• 例如，整数 1,2,4,6 等都是反质数。
  现在给定一个数 N ，你能求出不超过 N 的最大的反质数么？

输入格式

N

输出格式

答案

样例

输入

1000

输出

840

算法分析

• 打表啊 刚开始考试就整个打表 大约仨半小时你就A了
• 挺高级的玩意 推式子
• 首先一合数肯定可以分成几个质数相乘的形式（唯一分解定理） ，质数的质因子为2就不用解释了叭（细节叭）
• 然后看这样一个数756 = \(2^2\) * \(2^3\) * \(7^1\)，约数有24个 即三个指数+1 连乘（唯一分解定理）
• 而对于这样一个数756 我们完全可以将7换成一个更小的质数5 然后就有540 = \(2^2\) * \(2^3\) * \(5^1\)
• 而540的约数数 与 756的一样 所以我们选择540更优
• 由此我们可以推出来 一个数必须要由连续的几个质数的乘积组成而不能跳数（like 上面那个5与7）
• 通过这个dfs就好了

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
const int N=1e7+10;
const int pri[]={0,2,3,5,7,11,13,17,19,23,29};

int ans,Mx,n;

void dfs(int x,int d,int idx,int c){
	if(d > Mx || (d == Mx && x < ans))Mx = d,ans = x;
	for(int j = 1;j <= c;++j){
		if(n < (long long)pri[idx] * x)return;
		x *= pri[idx];
		dfs(x,d * (j + 1),idx + 1,j);
	}
}

int main(){
	scanf("%d",&n);
	dfs(1,1,1,31);
	printf("%d\n",ans);
}

T4 sam-Toy Cars（瞎搞就A了）

题目大意

• Jasio 是一个三岁的小男孩，他最喜欢玩玩具了，他有 n 个不同的玩具，它们都被放在了很高的架子上，所以Jasio 拿不到它们。为了让他的房间有足够的空间，在任何时刻地板上都不会有超过 k 个玩具（Jasio在地板上玩玩具）。
• Jasio的妈妈则在房间里陪他的儿子。当 Jasio 想玩地板上的其他玩具时，他会自己去拿。如果他想玩的玩具在架子上，他的妈妈则会帮他去拿。当她拿玩具的时候，顺便也会将一个地板上的玩具放上架子使得地板上有足够的空间。他的妈妈很清楚自己的孩子，所以他能够预料到 Jasio 想玩些什么玩具。所以她想尽量的使自己去架子上拿玩具的次数尽量的少，应该怎么安排放玩具的顺序呢？

输入格式

• 第一行三个整数：n,k,p(1<=k<=n<=105,1<=p<=5×105)，分别表示玩具的总数、地板上玩具的最多个数以及 Jasio 他想玩玩具的序列的个数。
• 接下来 p 行每行描述一个玩具编号，表示 Jasio 想玩的玩具。

输出格式

• 一个数表示 Jasio 的妈妈最少要拿多少次玩具。

算法分析

• 贪心的思想 显然如果当前地上已经有了k个玩具 再拿玩具的时候就要放回去一个
• 而放回去哪个呢？ 如果这小p孩下个就要玩A 结果你这次拿了个B把A换了 下次再拿个A 这不是闲的egg疼吗……
• 所以咱们预处理整他呗 看看这个玩意下次啥时候玩 在现在地板上找一个下次玩的时间最晚的 给它扔了 就好了
• 这玩意优先队列一搞不就出来了嘛

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
int pos[maxn];
int next[maxn];
int ans;
int vis[maxn];

struct node{
	int val,next;
	node(){
		next = 0x3f3f3f3f;
		val = 0;
	}
	node(int X,int Y){
		next = Y;
		val = X;
	}
	bool operator <(const node &x)const{
		return next < x.next;
	}
}a[maxn];

priority_queue<node> q;

int main(){
	//freopen("in","r",stdin);
	int n,k,m;scanf("%d%d%d",&n,&k,&m);
	for(int i = 1;i <= m;++i)scanf("%d",&a[i].val);
	for(int i = m;i;--i){
		if(pos[a[i].val])a[i].next = pos[a[i].val];
		pos[a[i].val] = i;
	}
	for(int i = 1;i <= m;++i){
		if(!vis[a[i].val]){
			if(ans >= k){
				int now = q.top().val;
				vis[now] = 0;
				q.pop();
			}
			ans++;
			vis[a[i].val] = 1;
		}
		q.push(node(a[i].val,a[i].next));
	}
	printf("%d\n",ans);
	return 0;
}

大假期集训模拟赛十

原文：https://www.cnblogs.com/2004-08-20/p/13405948.html