字符串的距离
题目描述
设有字符串 (X)，我们称在 (X) 的头尾及中间插入任意多个空格后构成的新字符串为 (X) 的扩展串，如字符串 (X) 为 “ (abcbcd) ”，则字符串 “ (abcb square cd) ”，” (square a square bcbcd square) ” 和 “(abcb square cd square) ” 都是 (X) 的扩展串，这里“ (square) ”代表空格字符。
如果 (A_1) 是字符串 (A) 的扩展串，(B_1) 是字符串 (B) 的扩展串，(A_1) 与 (B_1) 具有相同的长度，那么我们定义字符串 (A_1) 与 (B_1) 的距离为相应位置上的字符的距离总和：
- 两个非空格字符的距离定义为它们的 (ASCII) 码的差的绝对值，
- 空格字符与其它任意字符之间的距离为已知的定值 (K)，
- 空格字符与空格字符的距离为 (0)，
在字符串 (A,B) 的所有扩展串中，必定存在两个等长的扩展串 (A_1,B_1)，使得 (A_1) 与 (B_1) 之间的距离达到最小，我们将这一距离定义为字符串 (A,B) 的距离。
请你写一个程序，求出字符串 (A,B) 的距离。
输入格式
输入文件第一行为字符串 (A) 。
第二行为字符串 (B)，(A,B) 均由小写字母组成且长度均不超过 (2000) 。
第三行为一个整数 (K,1leq Kleq 100)，表示空格与其它字符的距离。
输出格式
输出文件仅一行包含一个整数，表示要求的字符串 (A,B) 的距离。
样例
样例输入
cmc
snmn
2
样例输出
10
思路
很裸的一个 (dp)，一开始打了一手 (DFS)，找了找思路，跑了一遍差不多长度为 (10) 的字符串，直接 (TLE)，本地都跑不出来，于是切换了一下思路，改用 (n^2) 的 (dp)，定义 (f[i][j]) 为第一个字符串用了 (i) 个字符，第二个字符串用了 (j) 个字符（不算空格），从上面的状态转移过来即可。
本来分四种情况：
- 第一个字符串选用字符，第二个字符串选用空格。
- 第一个字符串选用空格，第二个字符串选用字符。
- 第一个字符串选用字符，第二个字符串选用字符。
- 第一个字符串选用空格，第二个字符串选用空格（很明显不用考虑，不然会直接跑死）。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e3+50,INF=0x3f3f3f3f;
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
char a[maxn],b[maxn];
int n,m,k;
int f[maxn][maxn];
int main(){
memset(f,0x3f,sizeof(f));
scanf("%s%s",a+1,b+1);
k=read();
n=strlen(a+1);
m=strlen(b+1);
f[0][0]=0;
f[1][1]=min(2*k,abs(a[1]-b[1]));
for(int i=0;i<=n;i++){
for(int j=0;j<=m;j++){//注意数组不要越界，对拍的时候发现的问题，不然会出现负数
if(i>=1) f[i][j]=min(f[i-1][j]+k,f[i][j]);
if(j>=1) f[i][j]=min(f[i][j-1]+k,f[i][j]);
if(i>=1&&j>=1) f[i][j]=min(f[i-1][j-1]+abs(a[i]-b[j]),f[i][j]);
}
}
printf("%d
",f[n][m]);
return 0;
}
Blue Mary的战役地图
题目描述
(Blue Mary) 最近迷上了玩 (Starcraft) （星际争霸） 的 (RPG) 游戏。她正在设法寻找更多的战役地图以进一步提高自己的水平。
由于 (Blue Mary) 的技术已经达到了一定的高度,因此，对于用同一种打法能够通过的战役地图，她只需要玩一张，她就能了解这一类战役的打法，然后她就没有兴趣再玩儿这一类地图了。而网上流传的地图有很多都是属于同一种打法，因此 (Blue Mary) 需要你写一个程序，来帮助她判断哪些地图是属于同一类的。
具体来说， (Blue Mary) 已经将战役地图编码为 (n imes n)的矩阵，矩阵的每个格子里面是一个 (32) 位（有符号）正整数。对于两个矩阵，他们的相似程度定义为他们的最大公共正方形矩阵的边长。两个矩阵的相似程度越大，这两张战役地图就越有可能是属于同一类的。
输入格式
输入文件的第一行包含一个正整数 (n) 。
以下 (n) 行，每行包含 (n) 个正整数，表示第一张战役地图的代表矩阵。
再以下 (n) 行，每行包含 (n) 个正整数，表示第二张战役地图的代表矩阵。
输出格式
输出文件仅包含一行。这一行仅有一个正整数，表示这两个矩阵的相似程度。
样例
样例输入
3
1 2 3
4 5 6
7 8 9
5 6 7
8 9 1
2 3 4
样例输出
2
数据范围与提示
子矩阵：
5 6
8 9
为两个地图的最大公共矩阵
对于 (100\%) 的数据，(1leq nleq 100) 。
思路
考试的时候打了一手 (n^5) 的暴力，好像思路有点问题，直接 (W) 掉了，数据比较水，用一手 (n^4) 的 (dp) 也能过。
定义 (f[i][j][l][r]) 的数组，表示第一个矩阵到右下角 ((i,j))，第二个矩阵到右下角 ((l,r))，所能得到的最大相似程度，从这个位置的左边、右边、左上转移过来，取最小值。
小声bb：当时交的时候，加了一堆 (register)，反而负优化了，建议 (for) 循环多的时候，不要用。
正解是比较裸的二维 (hash) 板子，多打几遍就好了，尽管我还没记住。
代码
dp
#include <bits/stdc++.h>
using namespace std;
const int maxn=100+50,INF=0x3f3f3f3f;
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int n;
int ans;
int a[maxn][maxn],b[maxn][maxn];
int f[maxn][maxn][maxn][maxn];
int main(){
n=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=read();
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b[i][j]=read();
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int l=1;l<=n;l++){
for(int r=1;r<=n;r++){
if(a[i][j]==b[l][r]){
f[i][j][l][r]=min(f[i-1][j-1][l-1][r-1],min(f[i][j-1][l][r-1],f[i-1][j][l-1][r]))+1;
ans=max(ans,f[i][j][l][r]);
}
}
}
}
}
printf("%d
",ans);
return 0;
}
hash
#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int maxn=100+50,INF=0x3f3f3f3f;
const int RowBase=11,ColBase=13;//行与列的进制
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int n;
int Row[maxn],Col[maxn];
int a[maxn][maxn],b[maxn][maxn];
int Calc(int a[][maxn],int x,int y,int h){//二维hash的标准式
return a[x][y]-a[x-h][y]*Col[h]-a[x][y-h]*Row[h]+a[x-h][y-h]*Row[h]*Col[h];
}
void Solve(){
for(int i=1;i<=n;i++){//每一行的hash值
for(int j=1;j<=n;j++){
a[i][j]=a[i][j-1]*RowBase+a[i][j];
}
}
for(int i=1;i<=n;i++){//每一列的hash值
for(int j=1;j<=n;j++){
a[i][j]=a[i-1][j]*ColBase+a[i][j];
}
}
map<int,bool> mp;
for(int d=0;d<=n;d++){
for(int i=d;i<=n;i++){
for(int j=d;j<=n;j++){
mp[Calc(a,i,j,d)]=1;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b[i][j]=b[i][j-1]*RowBase+b[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b[i][j]=b[i-1][j]*ColBase+b[i][j];
}
}
for(int d=n;d>=0;d--){
for(int i=d;i<=n;i++){
for(int j=d;j<=n;j++){
if(mp.find(Calc(b,i,j,d))!=mp.end()){
printf("%lld
",d);
return;
}
}
}
}
}
signed main(){
n=read();
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
a[i][j]=read();
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
b[i][j]=read();
}
}
Row[0]=Col[0]=1;//基数
for(int i=1;i<=n;i++){//行的基数
Row[i]=Row[i-1]*RowBase;
}
for(int i=1;i<=n;i++){//列的基数
Col[i]=Col[i-1]*ColBase;
}
Solve();
return 0;
}
反质数
题目描述
对于任何正整数 (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(1leq Nleq 2 imes 10^9))。
输出格式
不超过 (N) 的最大的反质数。
样例
样例输入
1000
样例输出
840
数据范围与提示
保证 (25\%) 的数据 (1leq Nleq 10^3)
保证 (50\%) 的数据 (1leq Nleq 10^5)
保证 (75\%) 的数据 (1leq Nleq 10^8)
保证 (100\%) 的数据 (1leq Nleq 2 imes 10^9)
思路
打表进省一！！！
省选必备基础——打表
咳咳，我打表混了 (75opts)，要不是时间太少，后面几个没跑出来。
正解用一个约数个数公式，就是约数个数定理
- 约数个数定理：
对于一个大于 (1) 的正整数 (n) 可以分解质因数：（ (p_i) 为质数）
(n=prod_{i=1}^k p_i^{a_i}={p_1}^{a_1} imes {p_2}^{a_2} imes {p_3}^{a_3} imes ...... imes {p_k}^{a_k})
那么 (n) 的正约数个数为：
(f[n]=prod_{i=1}^k (a_i+1)=(a_1+1)(a_2+1)(a_3+1)......(a_k+1))
- 证明：
易得 (p_1^{a_1}) 的约数有：(p_1^0,p_1^1,p_1^2......p_1^{a_1}) ， 一共有 ((a_1+1)) 个。
同理 (p_k^{a_k}) 的约数有 ((a_k+1)) 个。
所以诶个组合，(n) 的约数有 (prod_{i=1}^k (a_i+1)) 个。
最后直接 (DFS) 一遍即可。
代码
正解
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=1e5+50,INF=0x3f3f3f3f;
int prime[15]={0,2,3,5,7,11,13,17,19,23,29,31,37};//质数表
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int n,mx,ans,s[maxn];
void DFS(int x,int sum,int maxx){
if(x>12)return;
if(sum>mx||(sum==mx&&maxx<ans)){//质数个数超过了之前记录的最大值
mx=sum;
ans=maxx;
}
s[x]=0;
while(maxx*prime[x]<=n&&s[x]<s[x-1]){//分解质因数
s[x]++;
maxx=maxx*prime[x];
int w=sum*(s[x]+1);
DFS(x+1,w,maxx);
}
}
signed main(){
n=read();
s[0]=1000000;
DFS(1,1,1);
printf("%lld
",ans);
return 0;
}
打表
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5,INF=0x3f3f3f3f;
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int n;
int a[100]={0,1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,554400,665280,720720,1081080,1441440,2162160,2882880,3603600,4324320,6486480,7207200,8648640,10810800,14414400,17297280,21621600,32432400,36756720,43243200,61261200,73513440,110270160,122522400,147026880,183783600,245044800,294053760,367567200,551350800,698377680,735134400,1102701600,1396755360};
int main(){
n=read();
cout<<a[upper_bound(a+1,a+1+68,n)-a-1]<<endl;
return 0;
}
sam-Toy Cars
题目描述
(Jasio) 是一个三岁的小男孩，他最喜欢玩玩具了，他有 (n) 个不同的玩具，它们都被放在了很高的架子上，所以 (Jasio) 拿不到它们。为了让他的房间有足够的空间，在任何时刻地板上都不会有超过 (k) 个玩具（(Jasio) 在地板上玩玩具）。
(Jasio) 的妈妈则在房间里陪他的儿子。当 (Jasio) 想玩地板上的其他玩具时，他会自己去拿。如果他想玩的玩具在架子上，他的妈妈则会帮他去拿。当她拿玩具的时候，顺便也会将一个地板上的玩具放上架子使得地板上有足够的空间。他的妈妈很清楚自己的孩子，所以他能够预料到 (Jasio) 想玩些什么玩具。所以她想尽量的使自己去架子上拿玩具的次数尽量的少，应该怎么安排放玩具的顺序呢？
输入格式
第一行三个整数：(n,k,p(1leq kleq nleq 10^5,1leq pleq 5 imes 10^5))，分别表示玩具的总数、地板上玩具的最多个数以及 (Jasio) 他想玩玩具的序列的个数。
接下来 (p) 行每行描述一个玩具编号，表示 (Jasio) 想玩的玩具。
输出格式
一个数表示 (Jasio) 的妈妈最少要拿多少次玩具。
样例
样例输入
3 2 7
1
2
3
1
3
1
2
样例输出
4
数据范围与提示
(30\%) 的数据满足 (1leq nleq 500,1leq kleq 200,1leq pleq 2000)
(50\%) 的数据满足 (1leq nleq 5000,1leq kleq 2000,1leq pleq 40000)
(100\%)的数据满足 (1leq kleq nleq 100,000,1leq pleq 500,000)
思路
很明显的一个贪心，考试的时候直接 (DFS) 了一遍，混了 (10opts)，其他的全 (TLE) 了。
很容易发现，当书本是 (k) 本时，需要一本来替换，由样例，可以推出：在我们当前选中的 (k) 本书中，最后需要的书，要被替换到书架上。
所以维护一个大根堆，靠后出现的书本先被放到书架上。
有一个小技巧：用图论存图的方式，用前向星的方法来存储，(next[i]) 表示第 (i) 次玩的玩具 (a[i]) 下一次玩的时间。
代码
#include <bits/stdc++.h>
using namespace std;
const int maxn=5e5+50,INF=0x3f3f3f3f;
inline int read(){
int x=0,w=1;
char ch;
for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
int n,k,p;
int ans;
int a[maxn],head[maxn],next[maxn],vis[maxn];
struct Node{
int id,next;
Node(int a,int b){
id=a;
next=b;
}
bool operator < (const Node &a) const{//维护大根堆
return next<a.next;
}
};
priority_queue<Node> q;
int main(){
n=read(),k=read(),p=read();
for(int i=1;i<=p;i++){
a[i]=read();
if(head[a[i]]!=0){//用邻接表存储
next[head[a[i]]]=i;
}
head[a[i]]=i;
}
for(int i=1;i<=p;i++){
if(next[i]==0){
next[i]=p+1;
}
}
for(int i=1;i<=p;i++){
if(vis[a[i]]==1){
q.push(Node(a[i],next[i]));
continue;
}
if(k!=0){
q.push(Node(a[i],next[i]));
vis[a[i]]=1;
k--;
ans++;
}else{
while(vis[q.top().id]==0){
q.pop();
}
vis[q.top().id]=0;
q.pop();
q.push(Node(a[i],next[i]));
vis[a[i]]=1;
ans++;
}
}
printf("%d
",ans);
return 0;
}