AcWing打卡记录day 3

AcWing 96. 奇怪的汉诺塔
和一般的汉诺塔不同，这个有四个塔。
在三塔的时候，我们可以理解成，我们放n个圆盘的时候，是先将n-1个圆盘转移到B盘，然后将第n个转移到C盘，再将n-1个圆盘转移回来。
所以状态转移是

f[i]=f[i-1]*2+1;//整体移动两次（i-1）个圆盘  然后加上移动一次第n个圆盘。

当我们四塔的时候，和三塔类似。
因为三塔只有3个塔，在前面n-1个圆盘占据了一个塔之后，相当于只剩下两个塔给他转移了。
所以只能最后一个圆盘转移。
但是四塔的时候，将n-1个圆盘转移到一个塔之后，还剩下三个塔给他进行操作。
所以可以先转移前面一部分到不是D盘到一个盘，然后再转移后面一部分到D盘，
再将前面一部分转移到D盘。

// Problem: 奇怪的汉诺塔
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/98/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date:2021-10-07 09:03:26
//
// Powered by CP Editor (https://cpeditor.org)#include using namespace std;
#define ll long long
#define endl '\n'
const int inf = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;
int n, m, T;
int flag;int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int f[20];int a[20];a[1]=1;for(int i=2;i<=12;i++){a[i]=a[i-1]*2+1;//记录的是  三塔状态下转移i个的最小步数。}for(int i=1;i<=12;i++){f[i]=inf;}f[1]=1,f[0]=0;for(int i=2;i<=12;i++){for(int j=0;j<i;j++){f[i]=min(f[i],f[j]*2+a[i-j]);//f[j]表示在四塔时先把j个转移到不是D塔的一个塔//a[i-j]表示，因为D塔都是比他小的圆盘，所以只有三个塔能用//则表示三塔时，吧剩下的i-j个转移到D塔//再f[j]表示四塔时转移到D他的最短步数。//因为吧i拆分成不同的部分得到=的值不一样 所以要遍历取最小值。}}for(int i=1;i<=12;i++){cout<<f[i]<<endl;}return 0;
}

310. 启示录
一开始以为就是简单的数位dp，想着直接把所有情况找出来，后来才反应过来，记录不了。
只能一次一次的二分查找。然后因为记忆化搜索，每次情况都查找完后，每次查找接近O（logn）所以不会超时。

// Problem: 启示录
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/312/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date:2021-10-07 09:52:23
//
// Powered by CP Editor (https://cpeditor.org)#include using namespace std;
#define ll long long
#define endl '\n'
const ll inf = 500000000000;
const int MAXN = 1e5 + 10;
int n, m, T;
int flag;int t[MAXN];
int a[30];
ll dp[30][10][2]; //第二维表示之前有几个连续的3ll dfs(int pos, int num, bool limit /*数位上界变量*/, int flag) //不是每个题都要判断前导零
{// flag 表示这个数是否已经满足条件if (num >= 3)flag = 1;if (pos == -1)return flag;if (!limit && dp[pos][num][flag] != -1)return dp[pos][num][flag];int up = limit ? a[pos] : 9;ll ans = 0;for (int i = 0; i <= up; i++) {if (i == 6)ans += dfs(pos - 1, num + 1, limit && i == a[pos], flag);elseans += dfs(pos - 1, 0, limit && i == a[pos], flag);}if (!limit)dp[pos][num][flag] = ans;return ans;
}ll solve(ll x)
{int pos = 0;while (x) //把数位都分解出来{a[pos++] = x % 10;x /= 10;}return dfs(pos - 1, 0, true, 0); //刚开始最高位都是有限制并且有前导零的，显然比最高位还要高的一位视为0嘛
}int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);memset(dp, -1, sizeof(dp));cin >> T;while (T--) {cin >> n;ll l = 0, r = inf, mid;while (l < r) {mid = (l + r + 1) >> 1;if (solve(mid)<n) {l = mid;} else {r = mid - 1;}}cout << l+1 << endl;}return 0;
}

311. 月之谜
这个题目，一开始想是，数位dp，然后dfs下放的是，当前位数前面的位数数字的和，和这个数本身。
但是这样的话，就得相当于暴力搜索，肯定会超时。后来看题解，说是一开始就假设一下mod等于这个数所有位数上的数加起来的值sum，然后数位dp 得到这个数num对mod求余的结果，如果到最后summod并且num0 则表示这个数是魔鬼数。

// Problem: 月之谜
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/313/
// Memory Limit: 64 MB
// Time Limit: 2000 ms
// Date:2021-10-07 10:58:44
//
// Powered by CP Editor (https://cpeditor.org)#include using namespace std;
#define ll long long
#define endl '\n'
const int inf = 0x3f3f3f3f;
const int MAXN = 1e5 + 10;
int mod;
int n, m, T;
int flag;	
int a[33];
ll dp[20][200][200]; //不同题目状态不同ll dfs(int pos, bool limit, int sum,int num) //不是每个题都要判断前导零
{if (pos == -1) {if (sum == mod && !num)return 1;return 0;}if (!limit && dp[pos][sum][num] != -1)return dp[pos][sum][num];int up = limit ? a[pos] : 9;ll ans = 0;	for (int i = 0; i <= up; i++) {ans += dfs(pos - 1, limit && i == a[pos], sum + i, (num * 10 + i) % mod);}return dp[pos][sum][num] = ans;
}ll solve(ll x)
{int pos = 0;while (x) //把数位都分解出来{a[pos++] = x % 10;x /= 10;}ll ans = 0;for (mod = 1; mod <200; mod++) {memset(dp, -1, sizeof(dp));//因为每次mod都不一样  所以dp数组得初始化ans += dfs(pos - 1, true, 0, 0);// cout << ans << endl;}return ans;
}int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll l, r;cin >> l >> r;cout << (solve(r) - solve(l-1)) << endl;return 0;
}

97. 约数之和
看到的第一眼就是之前那个结论；
唯一分解定理即任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3…Pnan，这里P1 然后因为是要求这些数的和，所以再根据约束和定理递归得到结果即可，

// Problem: 约数之和
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/99/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date:2021-10-07 09:37:32
//
// Powered by CP Editor (https://cpeditor.org)#include using namespace std;
#define ll long long
#define endl '\n'
const ll inf = 0x3f3f3f3f;
const ll MAXN = 1e5 + 10;
const ll mod = 9901;
ll n, T;
ll flag;ll ksm(ll a, ll b)
{ll ans = 1;while (b) {if (b & 1)ans = (ans * a) % mod;a = (a * a) % mod;b >>= 1;}return ans;
}ll primes[1000];
ll num[1000];
ll cnt=1;
void devide(ll n)//分解质因数
{for (ll i = 2; i <= n / i; i++) { //因为n一直在变小， 当n小于i的平方的时候，则表示后面已经没有满足的质数了if (n % i == 0) {primes[cnt]=i;while (n % i == 0) { //求出是这个质数的几次方num[cnt]++;n /= i;}cnt++;}}if (n > 1) { //如果还有剩下的。num[cnt]=1;primes[cnt++]=n;}
}ll sum(ll a, ll b)
{if (b == 1)return 1;if(b % 2 == 0) {  return (ksm(a, b / 2) + 1) * sum(a, b / 2) % mod;}return (ksm(a,b - 1) + sum(a, b - 1)) % mod;
}int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll a, b;cin >> a >> b;if (a == 0) {cout << 0 << endl;return 0;}ll ans = 1;// cout<<1;devide(a);// cout<<1;for (ll i=1;i<cnt;i++) {ll p=primes[i],k=num[i]*b;// cout<ans = (ans * sum(p,k +1)) % mod;// ans = (ll)ans * sum(p, k + 1) % mod;//一开始想直接把sum里面的判断换一下，但是确实0次方也是需要考虑的 所以+1即可处理//因为是 b次方 而sum求的是到b-1项  所以要+1才行。}cout << ans << endl;return 0;
}

98.分形之城
看半天题目没看懂题意，直接看的题解。
题意就是那张图，让你看着图片找出他的规律。
找出规律后，每次转移后 再将原点转换即可。

// Problem: 分形之城
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/100/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date:2021-10-07 20:28:44
// 算法:
// 
// Powered by CP Editor (https://cpeditor.org)#include using namespace std;
#define ll long long
#define endl '\n'
const int inf=0x3f3f3f3f;
const int MAXN=1e5+10;
int n,m,T;
int flag; 
typedef pair<ll,ll> pll ;pll digui(ll n,ll m){if(n==0){// cout<<"xcxz";return {0,0};}ll len=1ll<<(n-1);//表示转移其与原点需要转移的距离。ll cnt=1ll<<(2*n-2);//表示的是 将这个等级的数分成四份 每一份是多少城市pll  pos=digui(n-1,m%cnt);//表示在上个等级的城市中是该部分的编号。ll pact=m/cnt;//表示在坐标轴哪个界限ll x=pos.first,y=pos.second;// cout<if(pact == 0)  return {-y-len,-x+len};if(pact == 1)  return {x + len,y+len};if(pact == 2)  return {x + len,y - len};return {y-len,x - len};
}int main() 
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>T;while(T--){ll a,b;cin>>n>>a>>b;pll da=digui(n,a-1);//之所以减1 是为了便于第35行 // m%cnt表示在上个等级的城市区域的编号，即 0~15分别表示1~16pll db=digui(n,b-1);double x=da.first-db.first;double y=da.second-db.second;// cout<printf("%.0lf\n",sqrt(x*x+y*y)*5);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！