decimal
-
直接模拟笔算除法即可
-
$ n % m $ 的前 $ l - 1 $ 位的余数可以 $ O(1) $ 求出来，为 $ n \times 10 ^ {l - 1} % m $
- 这里的‘余数’是将余数乘以 $ 10 ^ {l - 1} $ 后化为的正整数
-
$ R - L \le 10 ^ 5 $ 很特殊，使得可以 $ O(n) $ 模拟笔算除法，商为 $ num \times 10 / m $，余数为 $ num \times 10 % m $
-
题目与循环节无关，因为循环节可以超级长，赛时 Floyd 判环被卡了
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 1e6 + 10;
int n, m, l, r;
int Q_pow(int a, int b, int mod){
int ans = 1, p = a;
while(b){
if(b & 1){
ans = (ans * p) % mod;
}
b >>= 1;
p = (p * p) % mod;
}
return ans;
}
signed main(){
// freopen("1.in", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> l >> r;
int num = (n * Q_pow(10, l - 1, m)) % m;
for(int i = l; i <= r; i++){
cout << num * 10 / m;
num = num * 10 % m;
}
cout << "\n";
}
//Zyb Txdy
labor
-
冒泡排序的次数 = 逆序对个数
-
$ O(n log ^ 2 n) $
-
不同长度的贡献随长度增加单调不减
-
二分最短长度 + $ O(n log n) $ 维护区间逆序对
-
-
$ O(n log n) $
-
左端点相同的所有区间逆序对个数单调不减（在末尾加上一个元素，逆序对不可能减少）
-
尺取法，在当前左端点下找到了符合条件的最小右端点后，左端点++，继续
-
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 1e6 + 10;
int n, x;
int a[N];
int t[N];
int lowbit(int x){
return x & (- x);
}
void Insert(int pos, int val){
while(pos < N){
t[pos] += val;
pos += lowbit(pos);
}
}
int Query_fr(int pos){
int ans = 0;
while(pos > 0){
ans += t[pos];
pos -= lowbit(pos);
}
return ans;
}
bool Check(int len){
int ans = 0;
for(int i = 1; i < N; i++){
t[i] = 0;
}
for(int i = 1; i <= n; i++){
if(i > len){
ans -= Query_fr(a[i - len] - 1);
Insert(a[i - len], -1);
}
ans += Query_fr(n) - Query_fr(a[i]);
Insert(a[i], 1);
if(ans >= x && i >= len){
return 1;
}
}
return 0;
}
signed main(){
// freopen("1.in", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> x;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
int l = 1, r = n;
if(n <= (int)1e3){
while(l < r){
int mid = (l + r) / 2;
if(Check(mid)){
r = mid;
}else{
l = mid + 1;
}
}
cout << r << "\n";
}else{
if(Check(80)){
r = 80;
}
while(l < r){
int mid = (l + r) / 2;
if(Check(mid)){
r = mid;
}else{
l = mid + 1;
}
}
cout << r << "\n";
}
}
//Zyb Txdy
distance
-
将删去一条边后的联通块加在当前‘最优点’上一定不劣
-
以点 u 为根的子树除了重心方向的子树外，其他子树的大小一定 <= n / 2
-
操作一定是将原重心的子树拆下来连到‘最优点’上，使得拆下来的总和 >= n / 2，即‘最优点’重心方向的子树的 si <= n / 2
-
如果将当前最优点所在的、以重心为根的子树保留（不拆下来），仍能使 max_si <= n / 2，则可以少删一条边
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 1e6 + 10;
int n;
int u, v;
int ancs[N], si[N];
int mini, rt, rtt;
vector <int> e[N], vec;
void Dfs(int x, int y){
if(x == rt) ancs[x] = 0;
else if(y == rt) ancs[x] = x;
else ancs[x] = ancs[y];
si[x] = 1;
int maxi = 0;
for(auto i : e[x]){
if(i == y) continue;
Dfs(i, x);
si[x] += si[i];
maxi = max(maxi, si[i]);
}
maxi = max(maxi, n - si[x]);
if(maxi < mini){
mini = maxi;
rtt = x;
}
}
signed main(){
// freopen("1.in", "r", stdin);
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i < n; i++){
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
rt = 1;
mini = (int)1e18;
Dfs(rt, 0);
rt = rtt;
Dfs(rt, 0);
for(auto i : e[rt]){
vec.push_back(si[i]);
}
sort(vec.begin(), vec.end(), greater <int> ());
int tot = 0, edge = 0, mid = n / 2 + n % 2;
for(auto i : vec){
tot += i;
edge++;
if(tot >= mid){
mini = i;
break;
}
}
for(int i = 1; i <= n; i++){
int rtt = ancs[i];
if(rtt == 0){
cout << "0\n";
}else if(tot - (si[rtt] >= mini ? si[rtt] : mini) + si[i] >= mid){
cout << edge - 1 << "\n";
}else{
cout << edge << "\n";
}
}
}
//Zyb Txdy
worship
-
只会 15 pts 的状压……
-
$ dp(i, j) $ 表示已经选了的点组成的集合为 i，上一个点为 j 的和
\[ dp(i | (1 << (k - 1)), k) += dp(i, j) * dep(Lca(i, j))
\]
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int MOD = 1e9 + 7;
const int N = 2e6 + 10;
int n;
int fa[N], dep[N];
int dp[N][25], lca[25][25];
vector <int> e[N];
void Dfs(int x, int y){
dep[x] = dep[y] + 1;
for(auto i : e[x]){
if(i == y){
continue;
}
Dfs(i, x);
}
}
int Lca(int x, int y){
while(x != y){
if(dep[x] < dep[y]){
swap(x, y);
}
x = fa[x];
}
return x;
}
signed main(){
// freopen("1.in", "r", stdin);
cin >> n;
for(int i = 2; i <= n; i++){
cin >> fa[i];
e[i].push_back(fa[i]);
e[fa[i]].push_back(i);
}
Dfs(1, 0);
for(int i = 1; i <= n; i++){
for(int j = 1; j < i; j++){
lca[i][j] = lca[j][i] = Lca(i, j);
}
}
int up = (1 << n) - 1;
for(int i = 1; i <= n; i++){
dp[1 << (i - 1)][i] = 1;
}
for(int i = 1; i <= up; i++){
for(int j = 1; j <= n; j++){
if(!(i >> (j - 1) & 1)){
continue;
}
for(int k = 1; k <= n; k++){
if((i >> (k - 1) & 1)){
continue;
}
(dp[((1 << (k - 1)) | i)][k] += dp[i][j] * (dep[lca[j][k]]) % MOD) %= MOD;
}
}
}
int ans = 0;
for(int i = 1; i <= n; i++){
(ans += dp[up][i]) %= MOD;
}
cout << ans << "\n";
}
//Zyb Txdy