2022.6.10 特长生模拟

2016 2016 2016 特长生
目录：

A.子数整数
B.游戏问题
C.字串距离
D.村庄重建

A . A. A.子数整数

分析：

用 % % %和 / / /取出每 3 3 3位

CODE：

#include
#include
#include
#include
#include
#define reg register
using namespace std;
typedef long long ll;
int k,f;
int main(){
	freopen("num.in","r",stdin);
	freopen("num.out","w",stdout);
	scanf("%d",&k);
	for(int i=10000;i<=30000;i++)
	{
		int sub1=i%1000,sub2=i%10000/10,sub3=i/100;
		if(sub1%k==0&&sub2%k==0&&sub3%k==0)
		{
			printf("%dn",i);
			f=1;
		}
	}
	if(!f) puts("-1");
	return 0;
}

B . B. B.游戏问题

分析：

每轮走 m m m步 一共走 m × 1 0 k mtimes 10^k m×10k 所以相当于多走了 ( m × 1 0 k ) % n (mtimes 10^k)%n (m×10k)%n步

CODE：

#include
#include
#include
#include
#include
#define reg register
using namespace std;
typedef long long ll;
ll n,m,k,x;
ll ksm(ll a,ll k)
{
	ll res=1ll;
	while(k)
	{
		if(k&1) (res*=a)%=n;
		(a*=a)%=n;
		k>>=1;
	}
	return res%n;
}
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	scanf("%lld%lld%lld%lld",&n,&m,&k,&x);
	printf("%lld",(x%n+(m*(ksm(10,k)%n)%n))%n);
	return 0;
}

C . C. C.字串距离

分析：

d p dp dp
设 f i , j f_{i,j} fi,j​表示第一个串做了前 i i i 位 第二个串做了前 j j j 位的最小距离
那么就是 f i , j = m i n { f i , j , f i − 1 , j + k , f i , j − 1 + k , f i − 1 , j − 1 + d i s ( s 1 i , s 2 j ) } f_{i,j}=min{f_{i,j},f_{i-1,j}+k,f_{i,j-1}+k,f_{i-1,j-1}+dis(s1_i,s2_j)} fi,j​=min{fi,j​,fi−1,j​+k,fi,j−1​+k,fi−1,j−1​+dis(s1i​,s2j​)}

CODE：

#include
#include
#include
#include
#include
#define reg register
using namespace std;
typedef long long ll;
const int N=2005;
char s[N],s2[N];
int k,len,len2,f[N][N];
int Abs(int x){return (x>0)?x:-x;}
int dis(char a,char b)
{
	int x=(int)(a),y=(int)(b);
	return Abs(x-y);
}
int main(){
	freopen("blast.in","r",stdin);
	freopen("blast.out","w",stdout);
	scanf("%s%s",s+1,s2+1);
	scanf("%d",&k);
	memset(f,0x3f,sizeof f);
	len=strlen(s+1);
	len2=strlen(s2+1);
	f[0][0]=0;
	for(int i=1;i<=len;i++)
		f[0][i]=k*i;
	for(int i=1;i<=len2;i++)
		f[i][0]=k*i;
	for(int i=1;i<=len;i++)
	for(int j=1;j<=len2;j++)
		f[i][j]=min(f[i][j],min(min(f[i-1][j-1]+dis(s[i],s2[j]),f[i][j-1]+k),f[i-1][j]+k));
	printf("%d",f[len][len2]);
	return 0;
} 

D . D. D.村庄重建

分析：

枚举一个时间小于当前询问的点 把这个点当做中转点做 f l o y d floyd floyd即可

CODE：

#include
#include
#include
#include
#include
#define reg register
#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const int N=205;
int n,m,t[N],Q,f[N][N];
void work(int k)
{
	for(reg int i=1;i<=n;i++)
	for(reg int j=1;j<=n;j++)
		if(f[i][j]>f[i][k]+f[k][j])
			f[i][j]=f[i][k]+f[k][j],f[j][i]=f[i][j];
}
int main(){
	freopen("rebuild.in","r",stdin);
	freopen("rebuild.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",&t[i]);
	memset(f,0x3f,sizeof f);
	for(int i=1,x,y,w;i<=m;i++)
	{
		scanf("%d%d%d",&x,&y,&w);
		x++; y++;
		f[x][y]=w;
		f[y][x]=w;
	}
	for(int i=1;i<=n;i++) 
		f[i][i]=0;
	scanf("%d",&Q);
	int i=1;
	while(Q--)
	{
		int x,y,k;
		scanf("%d%d%d",&x,&y,&k);
		x++; y++;
		if(k
			puts("-1");
			continue;
		}
		while(t[i]<=k&&i<=n) work(i++);
		(f[x][y]==0x3f3f3f3f)?puts("-1"):printf("%dn",f[x][y]);
	}
	return 0;
}