当前位置: 首页 > 工具软件 > Ender > 使用案例 >

STO GZM Orz %%%% ender魔王考试题解(前两道)(贪心和DP)STO WK orz

呼延运恒
2023-12-01

STO Ender orz 太强了        STO WK orz 太神了

首先,为什么是前两道呢?

因为最后一道是导数推论+泰勒展开,对于我一个初中生来说只能稍作理解,严格推论还是写不出

第一题 W


题目描述


给定正整数n,将其表示为n=a_1+a_2+...a_m,其中a_i的绝对值为2的非负整数幂(即a_i=1,-1,2,-2,4,-4or so)
求最小的m

输入格式

输入 一个正整数n,以二进制形式给出。

输出格式

输出 一个正整数m

思路解析:

这道题解法有二,一曰动态规划,一曰贪心

吾辈蒟蒻,只能贪心,可殿试手滑,少刻一符,曰c[i]='1'。

问如何贪心:

且观此题,一看无非两种操作,

一 :直接用2的k次方,填在第k位上

二:或者在一堆1的的前面一位填上1,再在最后一位减回。

明显第二种更优,所以在代价变小的前提下尽量向二靠拢,

如111101111

就可填上中间的0,代价会更小。

但还有一种更小:

1110101010111111

就是坑点,因为本来

101用二是不优的,可这样就变优了。

所以要特判

请看代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<vector>
using namespace std;
#define LL long long
#define M (1000005)
#define isdigit(x) ((x) >= '0' && (x) <= '9')
LL read() {
    LL res = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) res = ((res << 1) + (res << 3) + c - 48), c = getchar();
    return res;
}
void write(LL x) {
    if(x / 10) write(x / 10);
    putchar(x % 10 + '0');
}
char c[M];
LL len=0,s[M],ans;
int main(){
	scanf("%s",c);
	len=strlen(c);
	s[0]=c[0]-'0';
	for(int i=1;i<len-1;i++){
		if(c[i-1]=='1'&&c[i+1]=='1'&c[i]=='0'&&(c[i-2]=='1'||c[i+2]=='1')){
			s[i]=1;
			c[i]='1';//看这里,玄机就在于如果将这个置成1,就可以在特殊的情况的情况下用上面的判断正确计算了
			ans++;
		}else{
			s[i]=c[i]-'0';
		}
	}
	s[len-1]=c[len-1]-'0';
	LL k=0;
	for(int i=0;i<=len;i++){
		if(!s[i]&&k){
			if(k>=2)
				ans++;
			ans++,k=0;
		}
		if(s[i]==1)
			k++;
	}
	write(ans);
}

第二题 inint

题目描述


从起点1开始,每次选择当前数的任意一位上加上去,问得到n的最小步数以及方案数。多组数据。
 
例如,从1开始得到100,有很多方法,其中有下面两种方式:
A. 1-2-4-8-16-17-18-19-20-22-24-28-36-39-48-56-62-68-76-83-91-100
B. 1-2-4-8-16-17-24-28-36-39-48-56-62-68-76-83-91-100
显然,B只需要17步。
而事实上,有两种17步的方法。
C. 1-2-4-8-16-22-24-28-36-39-48-56-62-68-76-83-91-100

输入格式

第一行一个T
接下来T行每行一个n

输出格式

对于每个n输出得到n的最小步数和方案数,方案数mod 1000000007后输出
如果无法得到输出IMPOSSIBLE

数据规模


对于20%的数据n<=10^6
对于60%的数据n<=10^9
对于100%的数据n<=10^12,T<=100

思路解析:

这道题真正体现了大魔王的功力,太难了。

首先,你可以发现数据太大了,普通的dp O(n)都带不动,只能另寻他法。

这时候,魔王Ender想出了预处理后几位的跳跃,再暴力Dp,但不幸TLE了,这时候,他灵机一动,都处理了几位了,为什么不加一维来存储位数,相当于10位倍增。

可以用dp[S][k][i][j]来表示:

S是状态压缩成二进制来表示每一种数字出现过没有,9位,最大512。

k表示这是第几位。

i表示起点为0...0i。

j表示终点为0...0j。

这样最后再用每一个n来刷一遍就好了,至于方案数,就不用讲了吧。

见代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<map>
#include<cmath>
#include<vector>
using namespace std;
#define LL long long
#define M (513)
#define Mod (1000000007)
#define isdigit(x) ((x) >= '0' && (x) <= '9')
LL read() {
    LL res = 0;
    char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) res = ((res << 1) + (res << 3) + c - 48), c = getchar();
    return res;
}
void write(LL x) {
    if(x / 10) write(x / 10);
    putchar(x % 10 + '0');
}
LL f[M][15][12][12],fs[M][15][12][12],s[15][12],cnt[15][12];
LL T,n;
bool vis[20];
void get(LL x){
	for(LL i=1;i<=9;i++,x>>=1ll)
		vis[i]=x&1ll;
}
void pre(){
	memset(f,0x3f,sizeof(f));//最低位
	for(LL S=0;S<M-1;S++){
		for(LL i=9;i>=0;i--){
			memset(vis,0,sizeof(vis));
			get(S);
			vis[i]=1;
			for(LL j=0;j<=8;j++){
				if(vis[j+10-i])
					f[S][0][i][j]=1ll,fs[S][0][i][j]=1ll;
				else{
					for(LL k=i+1;k<=9;k++)
						if(vis[k-i]){
							if(f[S][0][k][j]+1<f[S][0][i][j])
								f[S][0][i][j]=f[S][0][k][j]+1,fs[S][0][i][j]=0;
							if(f[S][0][k][j]+1==f[S][0][i][j])
								fs[S][0][i][j]+=fs[S][0][k][j];
						}
				}
			}
		}
	}
	for(LL i=1;i<=11;i++){//倍增
		for(LL S=0;S<M-1;S++)
			for(LL st=0;st<=8;st++){
				memset(s,0x3f,sizeof(s));
				s[0][st]=0,cnt[0][st]=1;
				for(LL j=0;j<=9;j++)
					for(LL a=0;a<9;a++)
						for(LL b=0;b<9;b++){
							LL ns=j?S|(1<<(j-1)):S;
							if(s[j][a]+f[ns][i-1][a][b]<s[j+1][b])
								s[j+1][b]=s[j][a]+f[ns][i-1][a][b],cnt[j+1][b]=0;
							if(s[j][a]+f[ns][i-1][a][b]==s[j+1][b])
								cnt[j+1][b]=(cnt[j+1][b]+cnt[j][a]*fs[ns][i-1][a][b]%Mod)%Mod;
						}
				for(LL ed=0;ed<9;ed++)
					f[S][i][st][ed]=s[10][ed],fs[S][i][st][ed]=cnt[10][ed];			
			}
	}
}
int main(){
	freopen("inint.in","r",stdin);
	freopen("inint.out","w",stdout);
	pre();
	T=read();
	while(T--){
		memset(s,0x3f,sizeof(s));
		n=read();
		LL t=0ll,S=0ll;
		s[0][1]=0ll;
		cnt[0][1]=1ll;
		for(LL i=1000000000000ll,ti=11;i>=10;i/=10,ti--){
			for(LL j=0;j<(n/i)%10;j++){//取每一位值
				t=!t;
				memset(s[t],0x3f,sizeof(s[t]));
				LL ns=j?S|(1<<(j-1)):S;
				for(LL a=0;a<9;a++)
					for(LL b=0;b<9;b++){
						if(s[!t][a]+f[ns][ti][a][b]<s[t][b])
							s[t][b]=s[!t][a]+f[ns][ti][a][b],cnt[t][b]=0;
						if(s[!t][a]+f[ns][ti][a][b]==s[t][b])
							cnt[t][b]=(cnt[t][b]+(LL)cnt[!t][a]*fs[ns][ti][a][b]%Mod)%Mod;
					}
			}
			if((n/i)%10)S|=1<<((n/i)%10-1);//这个颜色可用了
		}
		for(LL i=0;i<=9;i++){
			memset(vis,0,sizeof(vis));
			get(S);
			vis[i]=1;
			for(LL a=1;a<=9;a++){
				if(vis[a]&&i+a<=9){
					LL j=i+a;
					if(s[t][j]>s[t][i]+1)
						s[t][j]=s[t][i]+1,cnt[t][j]=0;
					if(s[t][i]+1==s[t][j])
						cnt[t][j]=(cnt[t][j]+cnt[t][i])%Mod;
				}
			}
		}
		if(s[t][n%10]==0x3f3f3f3f3f3f3f3fll)
			puts("IMPOSSIBLE");
		else
			write(s[t][n%10]),putchar(' '),write(cnt[t][n%10]),putchar('\n');
	}
}

 

 

 

 类似资料: