网站建设设计官网,网站为什么做优化ppt,新站网站推广该如何做,怎样在手机上创建网站cf1561D Up the Strip(D1D2)
题意#xff1a;
一个长度为n的赛道#xff0c;一开始在n的位置#xff0c;你要前往到1#xff0c;每次移动你有两种方式#xff1a;
在1和x-1之间选择一个整数y#xff0c;并从位置x移动到位置x-y在2和x之间选择一个整数z…cf1561D Up the Strip(D1D2)
题意
一个长度为n的赛道一开始在n的位置你要前往到1每次移动你有两种方式
在1和x-1之间选择一个整数y并从位置x移动到位置x-y在2和x之间选择一个整数z从位置x移动到位置⌊xz⌋\lfloor \frac{x}{z} \rfloor⌊zx⌋
问有多少移动方法 问题D1n的数据范围是2e5 问题D1n的数据范围是4e6
D1
题解
对于第一个转移任何一个状态都可以转移到x因为是线性递推的 而对于第二个转移我们可以发现⌊xz⌋\lfloor \frac{x}{z} \rfloor⌊zx⌋在一个区间内值是稳定不变的这不就是整除分块 因为z∈[2,x],所以整除分块l的初始值为2 知道l根据整除分块可知ri/(i/l)ri/(i/l)ri/(i/l) 对于这一整个区间i∈[l,r]他们的值⌊ni⌋\lfloor \frac{n}{i} \rfloor⌊in⌋的值是一样所以可以这一整段区间的值都可以由dp[n/i]转移过来 所以有转移方程 dp[x]∑i1x−1dp[i]∑dp[xl]\sum_{i1}^{x-1}dp[i]\sum dp[\frac{x}{l}]∑i1x−1dp[i]∑dp[lx] 前者我用树状数组维护 复杂度nnn\sqrt{n}nn
代码
// Problem: D1. Up the Strip (simplified version)
// Contest: Codeforces - Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))
// URL: https://codeforces.com/contest/1561/problem/D1
// Memory Limit: 128 MB
// Time Limit: 6000 ms
// Data:2021-08-25 00:01:00
// By Jozky
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 2e5 9;
ll a[maxn];
ll f[maxn];
ll n, mod;
ll lowbits(ll x)
{return x (-x);
}
void update(int pos, ll val)
{for (int i pos; i maxn; i lowbits(i)) {a[i] (a[i] val) % mod;}
}
ll query(int pos)
{ll val 0;for (int i pos; i; i- lowbits(i)) {val (val a[i]) % mod;}return val;
}
int main()
{//rd_test();cin n mod;for (int i 1; i n; i) {if (i 1) {f[i] 1;update(i, f[i]);continue;}f[i] query(i - 1);int r;for (int l 2; l i; l r 1) {r i / (i / l);int R min(r, i);int len R - l 1;f[i] (f[i] 1ll * len * f[i / l] % mod) % mod;}update(i, f[i]);}printf(%lld\n, f[n] % mod);return 0;//Time_test();
}D2
题解
这个题的数据大了20很明显nnn\sqrt{n}nn过不了 现在对于4e6的数据很明显我们要优化成nlognn\log{n}nlogn的做法 对于一个数i那么某种倍数j会让[i∗j,i∗ji)[i*j,i*ji)[i∗j,i∗ji)这个范围内都可以移动到i位置 当然还要注意边界情况i∗jn且j∗iin1i*jn且j*iin1i∗jn且j∗iin1 转移方程为 dp[i]∑ji1ndp[j]∑i1i∗jn∑ki∗ji∗jj−1dp[k]\sum_{ji1}^{n}dp[j]\sum_{i1}^{i*jn} \sum_{ki*j}^{i*jj-1} dp[k]∑ji1ndp[j]∑i1i∗jn∑ki∗ji∗jj−1dp[k] 枚举倍数的时间复杂度是O(logn)O(log n)O(logn) 总复杂度是nlognn\log{n}nlogn
代码
// Problem: D1. Up the Strip (simplified version)
// Contest: Codeforces - Codeforces Round #740 (Div. 2, based on VK Cup 2021 - Final (Engine))
// URL: https://codeforces.com/contest/1561/problem/D1
// Memory Limit: 128 MB
// Time Limit: 6000 ms
// Data:2021-08-25 00:01:00
// By Jozky
#include bits/stdc.h
#include unordered_map
#define debug(a, b) printf(%s %d\n, a, b);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pairint, int PII;
clock_t startTime, endTime;
//Fe~Jozky
const ll INF_ll 1e18;
const int INF_int 0x3f3f3f3f;
void read(){};
template typename _Tp, typename... _Tps void read(_Tp x, _Tps... Ar)
{x 0;char c getchar();bool flag 0;while (c 0 || c 9)flag| (c -), c getchar();while (c 0 c 9)x (x 3) (x 1) (c ^ 48), c getchar();if (flag)x -x;read(Ar...);
}
template typename T inline void write(T x)
{if (x 0) {x ~(x - 1);putchar(-);}if (x 9)write(x / 10);putchar(x % 10 0);
}
void rd_test()
{
#ifdef LOCALstartTime clock();freopen(in.txt, r, stdin);
#endif
}
void Time_test()
{
#ifdef LOCALendTime clock();printf(\nRun Time:%lfs\n, (double)(endTime - startTime) / CLOCKS_PER_SEC);
#endif
}
const int maxn 5e6 9;
ll a[maxn];
ll f[maxn];
int n;
ll mod;
ll lowbits(ll x)
{return x (-x);
}
void update(int pos, ll val)
{for (int i pos; i maxn; i lowbits(i)) {a[i] (a[i] val) % mod;}
}
ll query(int pos)
{ll val 0;for (int i pos; i; i- lowbits(i)) {val (val a[i]) % mod;}return val;
}
ll sum[maxn];
int main()
{//rd_test();cin n mod;f[n] 1ll;sum[n] 1ll;for (int i n - 1; i 1; i--) {f[i] sum[i 1];for (int j 2; j * i n; j) {ll l i * j;ll r min(1ll * j * i j, 1ll * n 1);f[i] (f[i] sum[l] - sum[r]) % mod;}sum[i] (sum[i 1] f[i]) % mod;}printf(%lld\n, f[1] % mod);return 0;//Time_test();
}
