Practice II
前言
智商游戏打不过 QAQ
被大佬们虐死了 QAQQQQ
The most distant state - UVA - 10085
题意
给定一个八数码，求从此八数码到最远状态的操作步骤和该状态的样子
思路
顺便复习一下康托展开（其实我忘了，只是康托展开部分照着模板打）
耗时900ms
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <iomanip>
#include <cmath>
using namespace std;
const int N = 5e6 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
bool used[N];
int pre[N];
char preop[N];
int dpt[N];
const int fac[] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
const int M = 9;
queue<int> que;
int cantor(int a[M]){
int sum = 0;
for(int i = 0; i < M; i++){
int cnt = 0;
for(int j = i + 1; j < M; j++){
if(a[j] < a[i]) cnt++;
}
sum += cnt*fac[M - i - 1];
}
return sum;
}
void inv_cantor(int num, int a[]){
bool used[M + 1] = {0};
for(int i = 0; i < M; i++){
int cnt = num/fac[M - i - 1];
num %= fac[M - i - 1];
int j;
for(j = 0; j < M; j++){
if(!used[j]){
if(cnt == 0) break;
cnt--;
}
}
a[i] = j;
used[j] = true;
}
}
int bfs(int s){
int maxdpt = -1;
int ansidx;
while(!que.empty()) que.pop();
memset(used, false, sizeof(used));
dpt[s] = 0;
pre[s] = -1;
used[s] = true;
que.push(s);
while(!que.empty()){
int u = que.front();
que.pop();
int a[M];
inv_cantor(u, a);
if(maxdpt < dpt[u]){
ansidx = u;
maxdpt = dpt[u];
}
int poszero;
for(int i = 0; i < M; i++){
if(a[i] == 0){
poszero = i;
break;
}
}
if(poszero > 2){
swap(a[poszero - 3], a[poszero]);
int v = cantor(a);
if(used[v] == false){
dpt[v] = dpt[u] + 1;
pre[v] = u;
preop[v] = 'U';
que.push(v);
used[v] = true;
}
swap(a[poszero - 3], a[poszero]);
}
if(poszero%3 != 0){
swap(a[poszero - 1], a[poszero]);
int v = cantor(a);
if(used[v] == false){
dpt[v] = dpt[u] + 1;
pre[v] = u;
preop[v] = 'L';
que.push(v);
used[v] = true;
}
swap(a[poszero - 1], a[poszero]);
}
if(poszero%3 != 2){
swap(a[poszero + 1], a[poszero]);
int v = cantor(a);
if(used[v] == false){
dpt[v] = dpt[u] + 1;
pre[v] = u;
preop[v] = 'R';
que.push(v);
used[v] = true;
}
swap(a[poszero + 1], a[poszero]);
}
if(poszero <= 5){
swap(a[poszero + 3], a[poszero]);
int v = cantor(a);
if(used[v] == false){
dpt[v] = dpt[u] + 1;
pre[v] = u;
preop[v] = 'D';
que.push(v);
used[v] = true;
}
swap(a[poszero + 3], a[poszero]);
}
}
return ansidx;
}
int main(){
int t, csn = 1;
scanf("%d", &t);
while(t--){
int a[M];
for(int i = 0; i < M; i++) scanf("%d", &a[i]);
int u = cantor(a);
int ansidx = bfs(cantor(a));
inv_cantor(ansidx, a);
//printf("%d %d\n", u, ansidx);
string s;
while(pre[ansidx] != -1){
s.push_back(preop[ansidx]);
ansidx = pre[ansidx];
}
reverse(s.begin(), s.end());
printf("Puzzle #%d\n", csn++);
for(int i = 0; i < M; i++){
printf("%d", a[i]);
if(i%3 == 2) putchar('\n');
else putchar(' ');
}
printf("%s\n\n", s.c_str());
}
}
Maximum Subsequence - CodeForces - 888E
题意
给定一个序列和整数m，求其中选择某些数字，它们的和模m的最大值（可以不选）
思路
由于n给定的最大范围是35，而根据 (a%m + b%m)%m = (a + b)%m，可知区间具有合并性，因此用meet-in-the-middle的思维解
把区间分成两半，前半段跑dfs，将结果存入set中
后半段跑dfs的结果，记为sum（已模m），在set中不断寻找最接近 m-sum 或者 2*m-sum 的值，记为x，不断更新答案 ans = max(ans, (x + sum)%m)
最后就会TLE，主要是被set拖的，换成数组跑完第一个dfs后sort再unique再跑第二个dfs即可，（耗时62ms，没想到set这么拖时间 = =|| ）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 3e5 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N];
int b[N], bp;
void dfs1(int i, int n, int mod, ll sum){
if(i > n){
b[bp++] = sum%mod;
return;
}
dfs1(i + 1, n, mod, sum + a[i]);
dfs1(i + 1, n, mod, sum);
}
void dfs2(int i, int n, int mod, ll sum, int& ans){
if(i > n){
sum = sum%mod;
int pos = lower_bound(b, b + bp, mod - sum) - b;
if(pos != 0){
ans = max(ans, (int)(b[pos - 1] + sum));
}
pos = lower_bound(b, b + bp, 2*mod - sum) - b;
if(pos != 0){
ans = max(ans, (int)(b[pos - 1] + sum)%mod);
}
return;
}
dfs2(i + 1, n, mod, sum + a[i], ans);
dfs2(i + 1, n, mod, sum, ans);
}
int main(){
int n, mod;
while(~scanf("%d%d", &n, &mod)){
bp = 0;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
int ans = 0;
dfs1(1, (n + 1)/2, mod, 0);
sort(b, b + bp);
bp = unique(b, b + bp) - b;
dfs2((n + 1)/2 + 1, n, mod, 0, ans);
printf("%d\n", ans);
}
}
Bubble Sort Graph | CodeForces - 340D
题意
在冒泡排序中，若给需要交换的两个数连上一条边，问冒泡排序结束后，独立集的最大大小是多少
思路
先考虑一下什么情况下两个数会连上一条边——当前面的数大于后面的数的情况下会，因此所有的逆序对都会连边
反过来考虑，则不连边的两个数必定不逆序，那么选出来的独立集也就是非降序的
那么，不就是LIS么，直接套模板
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N];
int main(){
int n;
while(~scanf("%d", &n)){
int ans = 0;
for(int i = 0; i < n; i++){
int tmp;
scanf("%d", &tmp);
int pos = upper_bound(a, a + ans, tmp) - a;
a[pos] = tmp;
if(pos == ans) ans++;
}
printf("%d\n", ans);
}
}
Soldier and Number Game - CodeForces - 546D
题意
给定一个数 n = a!/b!，每次操作中，选择一个数x满足n%x == 0，令 n = n/x，直到 n = 1 为止，求最大操作次数
思路
实际上 n = (b+1)(b+2)(…)(a)，要使操作次数最大，那么除的数当然越小越好，因此选每个数除的次数就等于自身质因子的个数（按重数计）
用素数筛法先筛出素数，再用打表思想储存每个数的质因子个数，作前缀和，答案就是 sum[a] - sum[b]
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <iomanip>
#include <vector>
using namespace std;
const int N = 5e6 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
ll sum[N];
int prime[N], pp;
bool used[N];
void init(){
memset(used, 0, sizeof(used));
fill(sum, sum + N, 1);
pp = 0, sum[0] = sum[1] = 0;
for(int i = 2; i < N; i++){
if(sum[i] == 1){
prime[pp++] = i;
for(int j = 2; i*j < N; j++){
sum[i*j] = 0;
}
}
}
for(int i = 2; i < N; i++){
for(int j = 0; prime[j] <= i && prime[j]*i < N && j < pp; j++){
if(used[i*prime[j]]) continue;
sum[i*prime[j]] += sum[i] + 1;
used[i*prime[j]] = true;
}
}
for(int i = 2; i < N; i++) sum[i] += sum[i - 1];
}
int main(){
init();
int q;
scanf("%d", &q);
while(q--){
int a, b;
scanf("%d%d", &a, &b);
printf("%lld\n", sum[a] - sum[b]);
}
}
Sagheer, the Hausmeister - CodeForces - 812B
题意
给定一张图，从左下角出发，每次只能遍历完每一行所有的1后，才能从最左端或最右端走到上一行，直到遍历完1为止，求最小移动次数
思路1 - DP
训练的时候，用DP结果WA了三发，结果用穷举过了，训练后才来补DP
首先预处理一下每一行从左右两端各自出发走到最后一个1所需要的步数
定义DP状态为 dp[i][j][k]，在第i层从j（左端0/右端1）走到k（左端0/右端1）所需步数，另定义 a[i][j][k] 为本层从j到k所需步数，则
dp[i][0][1] = min(dp[i - 1][0][0], dp[i - 1][1][0]) + a[i][0][1]
dp[i][0][0] = min(dp[i - 1][0][0], dp[i - 1][1][0]) + a[i][0][0]
dp[i][1][1] = min(dp[i - 1][0][1], dp[i - 1][1][1]) + a[i][1][1]
dp[i][1][0] = min(dp[i - 1][0][1], dp[i - 1][1][1]) + a[i][1][0]
其中，a[i][0][1] = a[i][1][0] = 列数 - 1，而a[i][0][0] = 从左端走到最后一个1所需步数*2，a[i][1][1]同理
另外，不全为0的最顶层需要最后特判一下，因为不需要走到完
本DP方程有个Bug，那就是只有1层不能用，也需要特判一下
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;
const int N = 100 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
char G[N][N];
int lpos[N], rpos[N];
int dp[N][2][2];
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
m += 2;
for(int i = n; i >= 1; i--){
getchar();
for(int j = 1; j <= m; j++){
G[i][j] = getchar();
}
}
for(int i = 1; i <= n; i++){
lpos[i] = 0;
rpos[i] = 0;
for(int j = 1; j <= m; j++){
if(G[i][j] == '1'){
lpos[i] = m - j;
break;
}
}
for(int j = m; j >= 1; j--){
if(G[i][j] == '1'){
rpos[i] = j - 1;
break;
}
}
//printf("lpos: %d rpos: %d\n", lpos[i], rpos[i]);
}
for(int i = n; i >= 2; i--){
bool flag = true;
for(int j = 1; j <= m; j++){
if(G[i][j] == '1'){
flag = false;
break;
}
}
if(!flag) break;
n--;
}
for(int i = 1; i <= n - 1; i++){
dp[i][0][1] = m - 1;
dp[i][1][0] = m - 1;
dp[i][0][0] = rpos[i] * 2;
dp[i][1][1] = lpos[i] * 2;
//printf("01:%d 10:%d 00:%d 11:%d\n", dp[i][0][1], dp[i][1][0], dp[i][0][0], dp[i][1][1] );
}
dp[1][1][0] = dp[1][1][1] = inf;
if(n == 1){
printf("%d\n", rpos[n]);
}else{
for(int i = 2; i <= n - 1; i++){
int lans = min(dp[i - 1][0][0], dp[i - 1][1][0]) + 1;
dp[i][0][1] += lans;
dp[i][0][0] += lans;
int rans = min(dp[i - 1][0][1], dp[i - 1][1][1]) + 1;
dp[i][1][1] += rans;
dp[i][1][0] += rans;
}
int lans = min(dp[n - 1][0][0], dp[n - 1][1][0]) + 1;
int rans = min(dp[n - 1][0][1], dp[n - 1][1][1]) + 1;
int ans = min(lans + rpos[n], rans + lpos[n]);
printf("%d\n", ans);
}
}
}
思路2 - 穷举
其实就DFS，每次穷举左右两端，最后取结果最小值
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;
const int N = 100 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
char G[N][N];
int lpos[N], rpos[N];
void dfs(int nxt, int dpt, int sum, int n, int m, int& ans){
int cur = nxt;
if(dpt == n){
int tmp;
if(cur == 0) tmp = sum + rpos[dpt];
else tmp = sum + lpos[dpt];
ans = min(ans, tmp);
return;
}
if(cur == 0){
dfs(0, dpt + 1, sum + 2*rpos[dpt] + 1, n, m, ans);
dfs(1, dpt + 1, sum + m, n, m, ans);
}else{
dfs(1, dpt + 1, sum + 2*lpos[dpt] + 1, n, m, ans);
dfs(0, dpt + 1, sum + m, n, m, ans);
}
}
int main(){
int n, m;
while(~scanf("%d%d", &n, &m)){
m += 2;
for(int i = n; i >= 1; i--){
getchar();
for(int j = 1; j <= m; j++){
G[i][j] = getchar();
}
}
for(int i = 1; i <= n; i++){
lpos[i] = 0;
rpos[i] = 0;
for(int j = 1; j <= m; j++){
if(G[i][j] == '1'){
lpos[i] = m - j;
break;
}
}
for(int j = m; j >= 1; j--){
if(G[i][j] == '1'){
rpos[i] = j - 1;
break;
}
}
//printf("lpos: %d rpos: %d\n", lpos[i], rpos[i]);
}
for(int i = n; i >= 2; i--){
bool flag = true;
for(int j = 1; j <= m; j++){
if(G[i][j] == '1'){
flag = false;
break;
}
}
if(!flag) break;
n--;
}
int ans = inf;
dfs(0, 1, 0, n, m, ans);
printf("%d\n", ans);
}
}
Points and Powers of Two - CodeForces - 988D
题意
给定n个点，求点点距离为2的n次方的最大集合
思路
可以大概感觉得出，答案不会超过3，因为举不出任何一个有4个点的例子 QAQ
于是就对原数组sort，枚举长度查找可能性
最后耗时686ms
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 2e5 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
ll a[N];
int main(){
int n;
while(~scanf("%d", &n)){
for(int i = 0; i < n; i++) scanf("%lld", &a[i]);
sort(a, a + n);
int ansnum = 1;
int x, y, z;
for(ll len = 1; len <= (ll)1e10; len <<= 1){
for(int i = 0; i < n; i++){
int p1 = lower_bound(a, a + i, a[i] - len) - a;
int p2 = lower_bound(a + i + 1, a + n, a[i] + len) - a;
if(p1 < n && p2 < n && a[i] - a[p1] == len && a[p2] - a[i] == len){
ansnum = 3;
x = p1, y = i, z = p2;
break;
}
if(p1 < n && a[i] - a[p1] == len){
ansnum = 2;
x = p1, y = i;
}
if(p2 < n && a[p2] - a[i] == len){
ansnum = 2;
x = i, y = p2;
}
}
if(ansnum == 3) break;
}
if(ansnum == 1) printf("1\n%lld\n", a[0]);
else if(ansnum == 2) printf("2\n%lld %lld\n", a[x], a[y]);
else printf("3\n%lld %lld %lld\n", a[x], a[y], a[z]);
}
}
Doctor - CodeForces - 84D
题意
每个动物i需要看病ai次，他们着排队到医生那么看病，对于每个动物i，如果看完这一次后还需要看病，那么他们就会排到队尾去，否则直接出队伍，问医生接待k个动物后队列的样子（按重数计），如果接待不满k个动物，则输出-1
思路
实际上，可以固定队列，而用一个下标的移动来代替动物重新到队尾
即循环不断的将数组中的元素减1，为0的元素跳过不减，直到减了k次
那么可以把答案二分出来，寻找一个数num使得答案b <= k，剩余的k - ans部分则从数组开始减1，减到最后那个位置的下一位就是队伍头，最后从队伍头开始遍历数组中还不为0的数字，保存下标，最后输出即可
还有一个问题是什么时候为-1，那就是剩下的k - ans的部分没有分配完的时候会为-1，此时说明接待不满，才会整个数组为0了却还有剩余
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 15;
const int inf = 0x3f3f3f3f;
typedef long long ll;
int a[N];
ll judge(int b, int n){
ll sum = 0;
for(int i = 1; i <= n; i++){
sum += min(a[i], b);
}
return sum;
}
int main(){
int n;
ll k;
while(~scanf("%d%lld", &n, &k)){
vector<int> vec;
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
int l = 0, r = (int)1e9;
int b;
ll anssum;
while(l <= r){
int m = (l + r) >> 1;
ll tmp = judge(m, n);
if(tmp <= k){
b = m;
anssum = tmp;
l = m + 1;
}else{
r = m - 1;
}
}
for(int i = 1; i <= n; i++){
a[i] = max(a[i] - b, 0);
}
int endpos = n;
int i = 1, j = 1;
for(i = 1, j = 1; i <= n && j <= k - anssum; i++){
if(a[i]){
a[i]--;
j++;
endpos = i;
}
}
if(j > k - anssum){
int startpos = endpos + 1;
if(startpos == n + 1) startpos = 1;
while(startpos != endpos){
if(a[startpos]) vec.push_back(startpos);
startpos++;
if(startpos == n + 1) startpos = 1;
}
if(a[endpos]) vec.push_back(endpos);
for(int i = 0; i < vec.size(); i++){
printf("%d", vec[i]);
if(i < vec.size() - 1) putchar(' ');
}
puts("");
}else{
puts("-1");
}
}
}
